تقييم الشجرة
احسب النتيجة
تقييم الشجرة درس مجاني في C Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في C Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة C Academy 4 دروس في المجموع.
المرور على AST
التقييم هو اجتياز بترتيب لاحق: نحسب قيم الأبناء أولًا، ثم ندمجها باستخدام معامل العقدة. أما الورقة التي تمثل عددًا فتعيد قيمتها ببساطة.
هذا المفسر الذي يمر عبر الشجرة هو أبسط backend يمكن أن يمتلكه المفسر.
توقيع eval
يستقبل المقيّم مؤشرًا إلى عقدة ويعيد عددًا صحيحًا. وبما أن الشجرة عودية، فإن الدالة كذلك.
في اللغات التي تتعامل مع الأعداد العشرية، ستعيدون بدلًا من ذلك double أو قيمة موسومة.
int eval(Node *n); /* returns the integer value of the subtree */تقييم الورقة
توقف الحالة الأساسية الاستدعاء الذاتي. فعندما تكون العقدة عددًا، تكون قيمتها هي إجابة تلك الشجرة الفرعية.
يجب أن يصل كل نزول تكراري إلى حالة أساسية، وإلا فلن ينتهي أبدًا.
int eval(Node *n) {
if (n->kind == N_NUM) {
return n->value;
}
/* ... handle N_BINOP below ... */
return 0;
}تقييم BinOp
بالنسبة إلى عقدة معامل، ننزل تكراريًا إلى كلا الابنين، ثم نطبق المعامل. ويؤدي تقييم اليسار قبل اليمين إلى ترتيب التنفيذ المعتاد من اليسار إلى اليمين.
يساعد استخدام switch على محرف المعامل في إبقاء المنطق واضحًا.
int eval(Node *n) {
if (n->kind == N_NUM) return n->value;
int l = eval(n->bin.left);
int r = eval(n->bin.right);
switch (n->bin.op) {
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
}
return 0;
}الحماية من القسمة على صفر
القسمة الصحيحة على صفر سلوك غير معرّف في C، وعادةً ما تؤدي إلى انهيار العملية. لذلك يتحقق المفسر الآمن من المقسوم عليه أولًا.
إن الإبلاغ عن خطأ واضح أثناء التشغيل أفضل من حدوث SIGFPE خارج نطاق التحكم.
#include <stdio.h>
#include <stdlib.h>
static int safe_div(int a, int b) {
if (b == 0) {
fprintf(stderr, "runtime error: division by zero\n");
exit(1);
}
return a / b;
}التقييم من البداية إلى النهاية
يُقيَّم هنا هيكل بُني يدويًا للتعبير (2 + 3) * 4، فتكون النتيجة 20. ويمكن لـ eval نفسه تشغيل أي شجرة ينتجها المحلل النحوي.
شغّلوه للتأكد من أن الاجتياز بترتيب لاحق يحسب الإجابة الصحيحة.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int is_num; int value;
char op; struct Node *l, *r;
} Node;
static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }
static int eval(Node *n){
if (n->is_num) return n->value;
int l = eval(n->l), r = eval(n->r);
switch (n->op){
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
}
return 0;
}
int main(void){
Node *ast = B('*', B('+', N(2), N(3)), N(4));
printf("%d\n", eval(ast));
return 0;
}عمق المكدس
يضيف كل معامل متداخل إطارًا إلى مكدس استدعاءات C. وقد يؤدي تعبير شديد التداخل، مثل تعبير يحوي ألف قوس، إلى تجاوز سعته.
معظم التعبيرات الحقيقية بسيطة التداخل، لكن قد يحوّل المفسر المتين التنفيذ إلى مكدس صريح لمزيد من الأمان.
طي الثوابت
بما أن التقييم والتحليل النحوي يشتركان في الشجرة، يمكنكم تحسينها. فإذا كان ابنا عقدة binop عددين، يمكن حساب النتيجة مرة واحدة واستبدال العقدة بورقة.
يُعد طي الثوابت تحسينًا كلاسيكيًا في المفسرات.
/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
if (n->kind == N_BINOP) {
n->bin.left = fold(n->bin.left);
n->bin.right = fold(n->bin.right);
if (n->bin.left->kind == N_NUM &&
n->bin.right->kind == N_NUM)
return num(eval(n));
}
return n;
}تحرير الشجرة
يجب تحرير العقد المخصّصة على الكومة. ويزور التحرير بترتيب لاحق الأبناء قبل العقدة الأب، محاكيًا بذلك التقييم.
يؤدي نسيان ذلك إلى تسريب الذاكرة مع كل تعبير يشغله المفسر.
void free_tree(Node *n) {
if (n->kind == N_BINOP) {
free_tree(n->bin.left);
free_tree(n->bin.right);
}
free(n);
}السالب الأحادي
يحتاج النفي، مثل -5، إلى معالجة خاصة. ويتمثل أحد الخيارات في استخدام عقدة أحادية، بينما يتمثل خيار آخر في تحويل -x إلى 0 - x أثناء التحليل النحوي.
وفي كلتا الحالتين، يظل التقييم مرورًا تكراريًا بسيطًا.
/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
bump();
return binop('-', num(0), parse_factor());
}لماذا المرور عبر الشجرة؟
يسهل كتابة مفسرات المرور عبر الشجرة وتصحيحها، ولو كان ذلك على حساب بعض السرعة. وقد استخدمت لغات مثل Ruby القديمة هذا النموذج قبل الانتقال إلى أجهزة افتراضية تعتمد على bytecode.
سنضيف بعد ذلك المتغيرات حتى يتمكن المفسر من تذكر القيم.
تحقق سريع
حلّل ترتيب زيارة eval للعقد.
مراجعة
لقد نفذتم مقيّمًا تكراريًا: حالة أساسية للأوراق، واستدعاءً تكراريًا لـ binop، وحماية من القسمة على صفر، إضافةً إلى تحرير الشجرة وطي الثوابت.
يحسب المفسر الآن قيمة أي AST حسابية. والخطوة التالية هي إضافة المتغيرات.
الأسئلة الشائعة
هل درس «تقييم الشجرة» مجاني؟
نعم — نص درس «تقييم الشجرة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة C Academy، انتقل إلى CoddyKit PRO. تتضمن دورة C Academy 4 دروس في المجموع.
ماذا ستتعلم في «تقييم الشجرة»؟
احسب النتيجة تتمرن على C Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ C Academy؟
لا تُشترط خبرة سابقة. C Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «تقييم الشجرة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس C Academy هذا؟
نعم. كل درس في C Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.