تصميم محلل نموذجي تعاودي بسيط Recursive Descent Parser في جافا

يستخدم الحاسوب اللغات الطبيعية natural language، مثل اللغة الإنجليزية واللغات الصناعية. هناك تساؤلاتٌ كثيرة حول الطريقة التي تنقل بها لغةٌ معينة معلومةً ما، وحول بنية اللغات في العموم، حيث تتشابه اللغات الطبيعية والصناعية إلى الحد الذي يُمكِن معه الاستعانة بدراسة اللغات البرمجية البسيطة والمفهومة نوعًا ما من أجل فهم اللغات الطبيعية الأكثر تعقيدًا.

تطرح اللغات البرمجية الكثير من القضايا والتساؤلات الشيقة بما يكفي لتكون دراستها بحد ذاتها جديرةً بالاهتمام، ومنها مثلًا التساؤل حول كيفية تصميم الحاسوب ليكون قادرًا على فهم أبسط اللغات المُستخدَمة لكتابة البرامج. في الواقع، يستطيع الحاسوب التعامل على نحوٍ مباشر مع التعليمات المكتوبة بلغة الآلة machine language البسيطة؛ أي لا بُدّ من ترجمة اللغات عالية المستوى high level languages إلى لغة الآلة، ولكن إذا نظرنا للأمر، فإن المُصرِّف المسؤول عن ترجمة البرامج هو بالنهاية برنامج، فكيف يُمكِننا كتابة برنامج الترجمة ذاك؟

صيغة باكوس ناور Backus-Naur Form

تتشابه اللغات الصناعية والطبيعية بأن لديهما بنيةً معروفةً تُعرَف باسم قواعد الصيغة syntax، والتي تتكوَّن من مجموعةٍ من القواعد المُستخدَمة لوصف ما يعنيه أن تكون الجملة صحيحة. يُستخدَم غالبًا أسلوب صيغة باكوس ناور Backus-Naur Form - تختصر إلى BNF - بالنسبة للغات البرمجة للتعبير عن قواعد الصيغة، حيث طوَّر عالمي الحاسوب جون باكوس John Backus وبيتر ناور Peter Naur هذا الأسلوب بأواخر الخمسينيات، وفي نفس تلك الفترة، طوّر عالم اللغويات نعوم تشومسكي Noam Chomsky نظامًا مكافئًا مُستقلًا لوصف قواعد اللغات الطبيعية.

لا تستطيع صيغة باكوس ناور BNF التعبير عن كل قواعد الصيغة المحتملة، فلا يُمكنها مثلًا التعبير عن قاعدة "ضرورة الإعلان عن المتغير قبل استخدامه"، كما أنها لا تستطيع أن تقول أي شيءٍ عن معنى أو دلالة semantics اللغة. تُعدّ مشكلة تخصيص دلالة لغة معينة حتى وإن كانت لغة برمجةٍ صناعية واحدةً من المشكلات التي لم تُحَل إلى الآن. على الرغم من ذلك، تستطيع صيغة باكوس ناور BNF التعبير عن البنيات الأساسية للغة كما تلعب دورًا مركزيًا بتصميم المُصرِّفات compilers.

تتوفَّر في الحقيقة تشكيلةٌ مختلفة من الترميزات لصيغة باكوس ناور، وسنستخدم خلال ما يلي الصيغة الأكثر شيوعًا.

تُشيِر مصطلحاتٌ مثل "اسم noun" و"فعل متعد transitive verb" و"شبه جملة prepositional phrase" في اللغة الإنجليزية إلى تصنيفاتٍ نحويةٍ syntactic تصِف لَبِنات building blocks الجمل؛ وتُشير أيضًا مصطلحاتٌ، مثل "تعليمة statement" و"عدد number" و"حلقة while" إلى تصنيفاتٍ نحويةٍ تَصِف اللبنات الأساسية لبرامج جافا.

يُكْتَب التصنيف النحوي بصيغة باكوس ناور على هيئة كلمةٍ محاطةٍ بالقوسين "<" و">"، مثل و و، وتُخصِّص القواعد rules بصيغة باكوس ناور BNF بنية عنصرٍ معينٍ ضمن تصنيفٍ نحويٍ معينٍ بالنسبة للتصنيفات النحوية الآخرى والرموز الأساسية للغة، ويُمثِل ما يلي أحد قواعد صيغة باكوس ناور للغة الإنجليزية:

<sentence>  ::=  <noun-phrase> <verb-phrase>

يُقْرأ الرمز "‎::=‎" على النحو التالي "يُمكِنه أن يكون"، حيث تنص القاعدة بالأعلى على أن أي جملة يُمكِنها أن تكون جملة اسمية متبوعةً بجملةٍ فعلية . نستخدم "يُمكِنه أن يكون" بدلًا من "يكون"؛ حيث من الممكن أن يكون هناك قواعدٌ أخرى تُخصِّص صيغًا محتملةً أخرى لتكوين الجمل.

يُمكِننا التفكير بتلك القواعد على أنها أشبه بوصفةٍ لتكوين جملة ؛ أي إذا كنت تريد إنشاء جملةٍ، فيُمكِنك إنشاء جملةٍ اسمية ، ثم اتباعها بجملة فعلية . لاحِظ أنه لا بُدّ من تعريف الجملة الفعلية والاسمية أيضًا باستخدام قواعد صيغة باكوس ناور.

عند استخدام صيغة باكوس ناور، يُستخدَم الرمز "|"، الذي يُقْرأ "أو" لتمثيل البدائل المتاحة. انظر القاعدة التالية على سبيل المثال، والتي تنص على احتمالية كون الجملة الفعلية فعلًا لازمًا ، أو فعلًا متعديًا متبوعًا بجملةٍ اسمية .

<verb-phrase>  ::=  <intransitive-verb>  |
                    ( <transitive-verb> <noun-phrase> )

لاحِظ استخدام الأقواس للتجميع؛ فإذا أردت التعبير عن أن عنصرًا معينًا اختياري، ضعه بين القوسين "[" و"]"؛ وإذا كان من الممكن تكرار العنصر الاختياري أي عددٍ من المرات، ضعه بين القوسين "‎[‎" و"‎]…‎"؛ وضَع الرموز التي تُمثِل جزءًا فعليًا من اللغة الموصوفة داخل أقواس اقتباس quotes. ألقِ نظرةً على المثال التالي:

<noun-phrase>  ::=  <common-noun> [ "that" <verb-phrase> ]  |
                    <common-noun> [ <prepositional-phrase> ]...

تنص القاعدة السابقة على أن الجملة الاسمية من الممكن أن تكون اسمًا قد يتبعُه كلمة "that" وجملة فعلية ، أو أن تكون اسمًا متبوعًا بصفرٍ أو عددٍ من أشباه الجمل . يُمكِننا إذًا وصف أي بنية معقدة بنفس الأسلوب، حيث تَكْمُن القوة الحقيقية لقواعد صيغة باكوس ناور BNF بأنها قد تكون تعاودية recursive، حيث تُعدّ القاعدتان المُبينتان أعلاه تعاوديتين.

لقد عرَّفنا الجملة الاسمية جزئيًا باستخدام الجملة الفعلية ، في حين أن الجملة الفعلية مُعرَّفةٌ أيضًا جزئيًا باستخدام الجملة الاسمية، حيث تُمثِل "the rat that ate the cheese" جملةً اسميةً ؛ لأن "ate the cheese" جملةً فعلية .

نستطيع الآن استخدام التعاود recursion لإنشاء جملةٍ اسميةٍ أكثر تعقيدًا، مثل:

اقتباس

"the cat that caught the rat that ate the cheese"

المُكوَّنة من الاسم "the cat" وكلمة "that" والجملة الفعلية:

اقتباس

"caught the rat that ate the cheese"

وبناءً على ذلك، يُمكِننا إنشاء جملةٍ اسميةٍ ، مثل الجملة:

اقتباس

"the dog that chased the cat that caught the rat that ate the cheese".

تُعدّ البنية التعاودية recursive لأي لغة واحدةً من أهم خواصها الأساسية، وقدرة صيغة باكوس ناور BNF على التعبير عن تلك البنية التعاودية هو ما يجعلها مفيدة، حيث يُمكِننا استخدام صيغة باكوس ناور BNF لوصف قواعد صيغة لغات البرمجة، مثل جافا بطريقةٍ رسميةٍ مختصرة. على سبيل المثال، يُمكِننا تعريف حلقة التكرار على النحو التالي:

<while-loop>  ::=  "while" "(" <condition> ")" <statement>

تنص القاعدة المُوضحة أعلاه على أن حلقة التكرار تتكوَّن من كلمة "while" متبوعةً بقوس أيسر ")" يتبعه شرطٌ ، ثم يتبعه قوسٌ أيمن "("، وبالنهاية تعليمة . سيتبقى بالطبع تعريف المقصود في كلٍ من الشرط والتعليمة. وبما أنّه من الممكن للتعليمة أن تكون حلقة تكرار من بين أشياءٍ أخرى محتملة، فيُمكِننا أن نرى بوضوح البنية التعاودية recursive structure للغة جافا، ويُمكننا أيضًا تخصيص تعريفٍ دقيق لتعليمة if على النحو التالي:

<if-statement>  ::=  
             "if" "(" <condition> ")" <statement>
             [ "else" "if" "(" <condition> ")" <statement> ]...
             [ "else" <statement> ]

تبيِّن القاعدة بالأعلى أن الجزء "else" اختياري، وأنه من الممكن إضافة جزءٍ واحدٍ أو أكثر من "else if".

التحليل النموذجي التعاودي recursive descent parsing

سنستخدم في الجزء المتبقي من هذا المقال، قواعد صيغة باكوس ناور BNF للغةٍ معينة لإنشاء مُحلّل parser؛ والمُحلّل ببساطة هو برنامجٌ يُحدِّد البنية النحوية لجملةٍ مُصاغَةٍ بتلك اللغة، ويُعدّ ذلك بمثابة الخطوة الأولى لتحديد معنى الجملة، وهو ما يعني ضمن سياق لغات البرمجة ترجمتها إلى لغة الآلة machine language. على الرغم من أننا سنتناول مثالًا بسيطًا، نأمل أن يقنعك هذا المثال بأننا في الحقيقة قادرون على كتابة المُصرِّفات compilers وفهمها.

يُطلَق اسم "التحليل النموذجي التعاودي recursive descent parsing" على أسلوب التحليل parsing الذي سنستخدمه، وهو ليس الأسلوب الوحيد المتوفِّر كما أنه ليس الأسلوب الأكثر كفاءة، ولكنه يُعدّ الأكثر ملائمة إذا كنا نريد كتابة المُصرِّف يدويًا بدلًا من الاستعانة بالبرامج المعروفة باسم "مولد مُحلّل parser generator"؛ حيث تُعدّ كل قاعدةٍ بصيغة باكوس ناور BNF في المُحلل النموذجي التعاودي recursive descent parser نموذجًا لبرنامجٍ فرعي subroutine.

ليس بالضرورة أن تكون كل قاعدةٍ ملائمةً للتحليل النموذجي التعاودي، حيث ينبغي أن تتوفر بها خاصيةٌ معينة؛ وتتلّخص تلك الخاصية بأنه أثناء تحليل أي جملة، لا بُدّ أن يكون بإمكاننا معرفة التصنيف النحوي syntactic category التالي بمجرد النظر إلى العنصر التالي بالمُدْخَل. غالبية القواعد مُصمَّمة بحيث تَستوفِي تلك الخاصية.

عندما نحاول تحليل parse جملةٍ مُكوّنةٍ من خطأ في بناء الجملة syntax error، فإننا نحتاج إلى طريقةٍ للاستجابة إلى ذلك الخطأ، ويُعدّ التبليغ عن حدوث اعتراض exception إحدى الطرائق المناسبة، حيث سنعتمد تلك الطريقة، وسنَستخدِم تحديدًا صنف اعتراض اسمه ParseError المُعرَّف على النحو التالي:

private static class ParseError extends Exception {
   ParseError(String message) {
      super(message);
   }
} // end nested class ParseError

نلاحظ عدم ذكر قواعد صيغة باكوس ناور BNF أي شيءٍ عن الفراغات المحتملة بين العناصر، ولكن ينبغي واقعيًا أن نكون قادرين على إدخال فراغاتٍ بين العناصر كما نشاء. وللسماح بذلك، يُمكِننا استدعاء البرنامج TextIO.skipBlanks()‎ قبل محاولة قراءة قيمة الدْخَل التالية، حيث يتخطى البرنامج TextIO.skipBlanks()‎ أي مسافاتٍ فارغة بالمُدْخَل حتى يُصبِح الحرف التالي حرفًا غير فارغ أو محرف نهاية السطر. ألقِ نظرةً على مقال كيفية كتابة برامج صحيحة باستخدام لغة جافا للإطلاع على المزيد عن الصنف TextIO.

لنبدأ الآن بمثال بسيط يُمكّننا من وصف "تعبير بين قوسين بالكامل fully parenthesized expression" بصيغة باكوس ناور BNF بكتابة القواعد التالية:

<expression>  ::=  <number>  |
                   "(" <expression> <operator> <expression> ")"

<operator>  ::=  "+" | "-" | "*" | "/"

يشير بالأعلى إلى أي عددٍ حقيقيٍ موجب. يُعدّ "‎(((34-17)8)+(27))‎" مثالًا على "تعبير بين قوسين بالكامل". نظرًا لأن كل عامل operator يقابله زوجًا من الأقواس، ليس هناك أي غموضٍ بخصوص الترتيب الذي ينبغي أن تُطبَّق به العوامل. لنفترض أننا نريد كتابة برنامجٍ يقرأ تلك التعبيرات ويُحصِّل قيمتها، فسيقرأ البرنامج التعبيرات من الدخل القياسي standard input باستخدام الصنف TextIO؛ ولتطبيق التحليل النموذجي التعاودي recursive descent parsing، سنحتاج إلى تعريف برنامجٍ فرعيٍ subroutine لكل قاعدة.

سنُعرِّف مثلًا برنامجًا فرعيًا مقابلًا لقاعدة العامل ، بحيث يكون ذلك البرنامج الفرعي مسؤولًا عن قراءة العامل . وفقًا للقاعدة المُبينة أعلاه، فيُمكِن للعامل أن يكون أيًا من الأربعة أشياء المذكورة بالأعلى، بينما سيُعدّ أي مُدْخل آخر خطأً. ألقِ نظرةً على تعريف البرنامج الفرعي:

// 1
static char getOperator() throws ParseError {
   TextIO.skipBlanks();
   char op = TextIO.peek(); // انظر إلى المحرف التالي دون أن تقرأه
   if ( op == '+' || op == '-' || op == '*' || op == '/' ) {
      TextIO.getAnyChar();  // اقرأ العامل لحذفه من المُدْخلات
      return op;
   }
   else if (op == '\n')
      throw new ParseError("Missing operator at end of line.");
   else
      throw new ParseError("Missing operator.  Found \"" +
            op + "\" instead of +, -, *, or /.");
} // end getOperator()

[1] إذا كان المحرف المُدخَل التالي أحد العوامل الصحيحة، اقرأه ثم أعده مثل قيمة للتابع؛ أما إذا لم يكن كذلك، بلغ عن حدوث اعتراض.

حاولنا إعطاء رسالة خطأ معقولةٍ نوعًا ما اعتمادًا على ما إذا كان الحرف التالي هو محرف نهاية السطر أو شيءٌ آخر. استخدمنا التابع TextIO.peek()‎ للإطلاع على قيمة الحرف التالي دون قراءته، كما استخدمنا TextIO.skipBlanks()‎ قبل استدعاء TextIO.peek()‎ للتأكُّد من تجاهُل أي فراغاتٍ محتملة بين العناصر، وسنتبِع نفس النمط بكل حالة.

نحتاج الآن إلى تعريف البرنامج الفرعي المقابل لقاعدة التعبير ، والتي تنص على إمكانية أن يكون التعبير عددًا أو تعبيرًا بين قوسين. يُمكِننا بسهولة معرفة إلى أيهما ينتمي المُدْخَل التالي بمجرد فَحْص الحرف التالي؛ فإذا كان الحرف رقمًا digit، فسنقرأ عددًا؛ أما إذا كان الحرف قوسًا ")"، فسنقرأ القوس ")" متبوعًا بتعبير متبوعًا بعامل متبوعًا بتعبير آخر، وأخيرًا القوس "("؛ وإذا كان الحرف التالي أي شيءٍ آخر، يعني ذلك حدوث خطأ.

سنحتاج إلى التعاود recursion لقراءة التعبيرات المتداخلة nested expressions، حيث لا يقرأ البرنامج التعبير فقط، وإنما يُحصِّل قيمته أيضًا ثم يعيدها. يتطلَّب ذلك بعض المعلومات الدلالية semantical، التي لا تُوضِحها قواعد باكوس ناور BNF.

private static double expressionValue() throws ParseError {
   TextIO.skipBlanks();
   if ( Character.isDigit(TextIO.peek()) ) {
       // العنصر التالي بالمُدْخلات هو عدد، لذلك ينبغي أن يتكون 
       // التعبير من مجرد ذلك العدد. اقرأه وأعده
      return TextIO.getDouble();
   }
   else if ( TextIO.peek() == '(' ) {
       // 1
      TextIO.getAnyChar();  // ‫اقرأ القوس "("
      double leftVal = expressionValue();  // اقرأ المعامل الأول وحصِّل قيمته
      char op = getOperator();             // اقرأ العامل
      double rightVal = expressionValue(); // اقرأ المعامل الثاني وحصِّل قيمته
      TextIO.skipBlanks();
      if ( TextIO.peek() != ')' ) {
          // وفقًا للقاعدة، لا بُدّ من وجود قوس هنا
          // نظرًا لأنه غير موجود، سنُبلِّغ عن اعتراض
         throw new ParseError("Missing right parenthesis.");
      }
      TextIO.getAnyChar();  // ‫اقرأ القوس ")"
      switch (op) {   // طبّق العامل وأعد النتيجة
      case '+':  return leftVal + rightVal;
      case '-':  return leftVal - rightVal;
      case '*':  return leftVal * rightVal;
      case '/':  return leftVal / rightVal;
      default:   return 0;  // لا يُمكِن أن يحدث لأن العامل لا بُدّ أن يكون أيًا مما سبق
      }
   }
   else {  // لا يُمكِن لأي محرفٍ آخر أن يكون ببدية التعبير
      throw new ParseError("Encountered unexpected character, \"" + 
            TextIO.peek() + "\" in input.");
   }
} // end expressionValue()

[1] لا بُدّ أن يكون التعبير expression مكتوبًا بالصياغة التالية "(" ")". اقرأ جميع أجزاء التعبير واحدًا تلو الآخر، ثم نفِّذ العملية، وأعد الناتج.

ينبغي أن تكون قادرًا على فهم الكيفية التي يُمثِل بها البرنامج المُعرَّف بالأعلى قاعدة باكوس ناور BNF، فبينما تَستخدِم القاعدة الترميز "|" لتسمح بالاختيار بين عدة بدائل، فإن البرنامج الفرعي يَستخدِم تعليمة if لتحديد الخيار الذي ينبغي أن يتخذه؛ وبينما تحتوي القاعدة على متتالية من العناصر "(" ")"، يَستخدِم البرنامج الفرعي سلسلةً من التعليمات لقراءة تلك المُدْخَلات واحدًا تلو الآخر.

عند استدعاء expressionValue()‎ لتحصيل قيمة التعبير "‎(((34-17)8)+(27))‎"، سيَجِد التابع القوس ")" ببداية المُدْخَل، ولهذا سيُنفِّذ جزء "else" من تعليمة if. بعد قراءته لذلك القوس، سيقرأ الاستدعاء التعاودي الأول للتابع expressionValue()‎ التعبير الفرعي "‎((34-17)8)‎" ويُحصِّل قيمته. بعد ذلك، سيستدعي البرنامج التابع getOperator()‎ لقراءة العامل "+"، ثم سيقرأ الاستدعاء التعاودي الثاني للتابع expressionValue()‎ التعبير الفرعي الآخر "‎(27)‎" ويُحصِّل قيمته. أخيرًا، سيقرأ البرنامج القوس "(" الموجود بنهاية التعبير.

تشتمل قراءة التعبير الفرعي الأول "‎((34-17)*8)‎" بالطبع على استدعاءاتٍ تعاوديةٍ أخرى للبرنامج expressionValue()‎، ولكن من الأفضل عدم التفكير بالأمر على نحوٍ أبعد من ذلك، حيث علينا فقط الاعتماد على التعاود لمعالجة تلك التفاصيل. يُمكِنك الاطلاع على البرنامج بالكامل الذي يَستخدِم تلك البرامج بالملف SimpleParser1.java.

لا يلجأ أحدٌ في العموم إلى استخدام التعبيرات بين الأقواس بالكامل fully parenthesized expressions؛ وفي المقابل، إذا استخدمنا التعبيرات العادية، فسنضطّر للقلق بشأن أولوية العوامل operator precedence، التي تُخبرنا بوجوب تطبيق العامل "" قبل العامل "+" بتعبيرٍ مثل "5+37".

سننظر للتعبير التالي "‎36+8(7+1)/4-24" على أنه مُكوّنٌ من ثلاثة أجزاء terms، هي: 36 و ‎8(7+1)/4 و 24؛ وهذه الأجزاء مربوطةٌ معًا باستخدام "+" و"-"، ويتكوَّن كل جزءٍ term منها من عدة عوامل factors مربوطةٍ معًا باستخدام "*" و"/".

يتكون التعبير "‎8*(7+1)/4" مثلًا من العوامل 8، و ‎(7+1)‎، و 4، حيث يُمكِننا أن نرى أن العامل factor قد يكون عددًا أو تعبيرًا داخل أقواس. سنُعقِد الأمر قليلًا بالسماح باستخدام الإشارة السالبة ضمن التعبيرات، مثل "‎-(3+4)‎" أو "‎-7". بما أن القاعدة تُمثّل عددًا موجبًا، فإنها تُعدّ الطريقة الوحيدة للحصول على أعدادٍ سالبة. يُمكننا التعبير عما سبق باستخدام قواعد باكوس ناور BNF التالية:

<expression>  ::=  [ "-" ] <term> [ ( "+" | "-" ) <term> ]...
<term>  ::=  <factor> [ ( "*" | "/" ) <factor> ]...
<factor>  ::=  <number>  |  "(" <expression> ")"

تَستخدِم القاعدة الأولى الترميز "‎[ ]…‎" لتُبيِّن أن العناصر المُضمَّنة داخل الأقواس قد تحدث أي عددٍ من المرات بما في ذلك الصفر، وتنص القاعدة أيضًا على أن أي تعبيرٍ يُمكِنه أن يبدأ بإشارة سالبة "-" يتبعها بالضرورة ، الذي من الممكن أن يتبعه اختياريًا العامل "+" أو "-" مع جزءٍ آخر، ثم قد يتبع ذلك عاملًا آخرًا مع جزء ، وهكذا. سيَستخدِم البرنامج الفرعي المسؤول عن قراءة تعبير وتحصيل قيمته حلقة while لمعالجة التكرار السابق، كما سيَستخدِم تعليمة if ببداية الحلقة لفحص ما إذا كانت الإشارة السالبة موجودةً أم لا. اُنظر تعريف البرنامج الفرعي:

private static double expressionValue() throws ParseError {
   TextIO.skipBlanks();
   boolean negative;  // ‫يُساوِي `true` في حالة وجود إشارة سالبة
   negative = false;
   if (TextIO.peek() == '-') {
      TextIO.getAnyChar();  // اقرأ الإشارة السالبة
      negative = true;
   }
   double val;  // قيمة التعبير
   val = termValue();  // اقرأ الجزء الأول وحصِّل قيمته
   if (negative)
      val = -val;
   TextIO.skipBlanks();
   while ( TextIO.peek() == '+' || TextIO.peek() == '-' ) {
       // اقرأ الجزء التالي وأَضِفه، أو اطرحه من قيمة الجزء السابق بالتعبير
      char op = TextIO.getAnyChar();  // اقرأ العامل
      double nextVal = termValue();    // اقرأ الجزء التالي وحصِّل قيمته
      if (op == '+')
         val += nextVal;
      else
         val -= nextVal;
      TextIO.skipBlanks();
   }
   return val;
} // end expressionValue()

يتشابه البرنامج الفرعي المسؤول عن قراءة جزء مع البرنامج المُعرَّف بالأعلى؛ أما البرنامج الفرعي المسؤول عن قراءة عامل فهو شبيهٌ بمثال تعبيراتٍ ذات أقواس بالكامل fully parenthesized expressions. يُمكِنك الإطلاع على شيفرة البرنامج المسؤول عن قراءة التعبيرات وتحصيل قيمتها اعتمادًا على قواعد باكوس ناور BNF المذكورة بالأعلى بالملف SimpleParser2.java.

إنشاء شجرة تعبير Expression Tree

لم نفعل حتى الآن أكثر من مجرد تحصيل قيم التعبيرات expressions، فما العلاقة بين ذلك وبين ترجمة البرامج إلى لغة الآلة machine language؟ ببساطة، بدلًا من تحصيل قيمة التعبير فعليًا، يُمكِننا توليد التعليمات المطلوبة لتحصيل قيمة التعبير بلغة الآلة؛ فإذا كنا نعمل مع "آلة مكدس stack machine" مثلًا، فستكون التعليمات عملياتٍ على المكدس، مثل دفع push عددٍ إلى المكدس، أو تطبيق عملية "+". يمكن للبرنامج SimpleParser3.java تحصيل قيمة التعبيرات وطباعة قائمة العمليات المطلوبة لتحقيق ذلك.

في الواقع، يُمثّل الانتقال من البرنامج السابق إلى برنامج "محلل نموذجي تعاودي recursive descent parser" قادرٍ على قراءة البرامج المكتوبة بلغة جافا وتحويلها إلى شيفرة لغة الآلة خطوةً كبيرةً، ولكن الفرق في المفاهيم ليس كبيرًا.

لا يولِّد البرنامج SimpleParser3 عمليات المكدس مباشرةً أثناء تحليله parse لتعبيرٍ معين، ولكنه يُنشِئ شجرة تعبير expression tree، التي ناقشناها بالمقال السابق حول الأشجار الثنائية Binary Trees في جافا لتمثيل ذلك التعبير، ثم يَستخدِم شجرة التعبير لحساب قيمة التعبير وتوليد عمليات المكدس.

تتكوَّن الشجرة من عقدٍ nodes تنتمي إلى الصنفين ConstNode وBinOpNode المشابهين تمامًا للأصناف التي تعرَّضنا لها بالمقال السابق. وعرَّفنا صنفًا فرعيًا جديدًا من الصنف ExpNode اسمه هو UnaryMinusNode لتمثيل عملية الإشارة السالبة الأحادية، كما أضفنا أيضًا تابعًا اسمه printStackCommands()‎ لكل صنف؛ بحيث يكون مسؤولًا عن طباعة عمليات المكدس المطلوبة لتحصيل قيمة تعبير معين.

تعرض الشيفرة التالية التعريف الجديد للصنف BinOpNode من برنامج SimpleParser3.java:

private static class BinOpNode extends ExpNode {
   char op;        // العامل
   ExpNode left;   // التعبير على يسار العامل
   ExpNode right;  // التعبير على يمين العامل
   BinOpNode(char op, ExpNode left, ExpNode right) {
       // ‫أنشِئ عقدة من النوع BinOpNode تحتوي على البيانات المُخصصة
      assert op == '+' || op == '-' || op == '*' || op == '/';
      assert left != null && right != null;
      this.op = op;
      this.left = left;
      this.right = right;
   }
   double value() {
       // القيمة التي حصلنا عليها بعد تطبيق العامل على قيمة المعاملين
       // الأيمن والأيسر
      double x = left.value();
      double y = right.value();
      switch (op) {
      case '+':  
         return x + y;
      case '-':  
         return x - y;
      case '*':  
         return x * y;
      case '/':  
         return x / y;
      default:   
         return Double.NaN;  // لا يُمكِن أن يحدث
      }
   }
   void  printStackCommands() {
          // 1
      left.printStackCommands();
      right.printStackCommands();
      System.out.println("  Operator " + op);
   }
}

حيث تشير [1] إلى تحصيل قيمة التعبير باستخدام آلة مكدس، علينا تحصيل قيمة المعامل الأيسر، ثم ترك الإجابة بالمكدس. بعد ذلك، سنفعل الأمر نفسه مع المعامل الثاني. وأخيرًا، سنُطبّق العامل؛ أي سنسحب pop قيمة المعاملين من المكدس ونطبِّق العامل عليهما، ثم ندفع الناتج إلى المكدس.

لنفحص أيضًا البرامج الفرعية subroutine المسؤولة عن عملية التحليل parsing، فبدلًا من حساب قيمة التعبير، سيبني كل برنامجٍ فرعي منها شجرة تعبير expression tree. تعرض الشيفرة التالية مثلًا البرنامج الفرعي المقابل لقاعدة :

    static ExpNode expressionTree() throws ParseError {
        // اقرأ تعبيرًا من سطر المُدْخلات الحالي ثم أعد شجرة تعبير تُمثِل ذلك السطر
       TextIO.skipBlanks();
       boolean negative;  // True if there is a leading minus sign.
       negative = false;
       if (TextIO.peek() == '-') {
          TextIO.getAnyChar();
          negative = true;
       }
       ExpNode exp;   // شجرة التعبير الممثلة للتعبير المقروء
       exp = termTree();  // ابدأ بشجرة للجزء الأول من التعبير
       if (negative) {
           // ابنِ شجرةً مُكافِئةً لتطبيق عامل الإشارة السالبة الأحادي 
           // على الجزء المقروء
          exp = new UnaryMinusNode(exp);
       }
       TextIO.skipBlanks();
       while ( TextIO.peek() == '+' || TextIO.peek() == '-' ) {
           // اقرأ الجزء التالي واِدمجه مع الجزء السابق ضمن شجرة تعبير أكبر
           char op = TextIO.getAnyChar();
           ExpNode nextTerm = termTree();
           // انشئ شجرة تُطبِق العامل الثنائي على الشجرة السابقة والجزء الذي قرأناه للتو
           exp = new BinOpNode(op, exp, nextTerm);
           TextIO.skipBlanks();
       }
       return exp;
    } // end expressionTree()

يُنشِئ المحلّل parser ببعض المُصرِّفات compilers الحقيقية شجرةً لتمثيل البرنامج قيد التحليل، حيث يُطلَق على تلك الشجرة اسم "شجرة تحليل parse tree"، أو "شجرة صيغة مجردة abstract syntax tree". تختلف أشجار التحليل بعض الشيء عن أشجار التعبير expression trees، ولكنها تُستخدَم لنفس الغرض. بمجرد الحصول على شجرة تحليل، يُمكِنك استخدامها كما تشاء، كأن تولِّد منها شيفرة لغة الآلة machine language المقابلة.

تتوفَّر أيضًا بعض التقنيات المسؤولة عن فحص الشجرة والكشف عن أنواعٍ معينةٍ من الأخطاء البرمجية مثل محاولة الإشارة إلى متغيّرٍ محلي local variable قبل إسناده إلى قيمة؛ حيث يرفض مُصرِّف جافا بالطبع أن يُصرِّف البرنامج إذا كان يحتوي على مثل ذلك الخطأ. من الممكن أيضًا إجراء بعض التعديلات على شجرة التحليل لتحسين أداء البرنامج قبل توليد شيفرة لغة الآلة.

والآن، عدنا إلى النقطة التي بدأنا بها الجزء الأول من السلسلة أي فحص لغات البرمجة والمُصرِّفات compilers ولغة الآلة machine language، ولكن نأمل أن تكون المفاهيم أكثر وضوحًا وأن يكون التصور أكثر اتساعًا الآن.

ترجمة -بتصرّف- للقسم Section 5: A Simple Recursive Descent Parser من فصل Chapter 9: Linked Data Structures and Recursion من كتاب Introduction to Programming Using Java.