محلل الرجوع الذيلى (Tail Recursive Parser)

مقدمة

في علم الحاسوب، تُعد محللات الرجوع الذيلي نوعًا من محللات الهبوط العودي، ولكنها تتميز بخصائص معينة تجعلها أكثر كفاءة في بعض الحالات. محللات الهبوط العودي هي نوع شائع من المحللات التي تعتمد على مجموعة من الدوال المتداخلة، حيث تمثل كل دالة قاعدة إنتاجية في النحو (grammar). ومع ذلك، يمكن أن تؤدي المكالمات العودية المتكررة إلى استهلاك كبير للذاكرة بسبب الاحتفاظ بمعلومات الاستدعاء في مكدس الاستدعاءات. محللات الرجوع الذيلي تتغلب على هذه المشكلة من خلال ضمان أن المكالمة العودية هي آخر عملية يتم تنفيذها في الدالة، مما يسمح للمترجم أو المفسر بتحسين التنفيذ عن طريق استبدال استدعاء الدالة الحالي باستدعاء الدالة العودية، وبالتالي تجنب الحاجة إلى تخصيص ذاكرة إضافية للمكدس.

مفهوم الرجوع الذيلي

لفهم محللات الرجوع الذيلي، من الضروري أولاً فهم مفهوم الرجوع الذيلي نفسه. في البرمجة، يعتبر الاستدعاء العودي استدعاءً ذيليًا إذا كان هو العملية الأخيرة التي يتم تنفيذها في الدالة. هذا يعني أنه بعد عودة الاستدعاء العودي، لا توجد عمليات أخرى يجب تنفيذها في الدالة الأصلية. على سبيل المثال، لنأخذ الدالة التالية (بصيغة مبسطة):


function factorial(n, accumulator = 1):
  if n == 0:
    return accumulator
  else:
    return factorial(n - 1, n * accumulator)

في هذا المثال، الاستدعاء العودي للدالة `factorial` هو آخر عملية يتم تنفيذها. هذا يجعلها دالة رجوع ذيلي. على النقيض من ذلك، الدالة التالية ليست رجوعًا ذيليًا:


function factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n - 1)

هنا، بعد عودة الاستدعاء العودي `factorial(n – 1)`، يجب ضرب النتيجة في `n`. هذا يجعلها ليست رجوعًا ذيليًا.

آلية عمل محللات الرجوع الذيلي

تعتمد محللات الرجوع الذيلي على نفس مبادئ محللات الهبوط العودي، ولكنها مصممة بطريقة تضمن أن جميع الاستدعاءات العودية هي استدعاءات ذيلية. هذا يسمح بتحسين التنفيذ وتجنب تجاوز سعة مكدس الاستدعاءات، خاصة عند تحليل قواعد نحوية معقدة تتطلب الكثير من الاستدعاءات العودية. بشكل عام، تتضمن عملية عمل محلل الرجوع الذيلي الخطوات التالية:

تمثيل النحو: يتم تمثيل النحو الذي سيتم تحليله باستخدام مجموعة من القواعد الإنتاجية. كل قاعدة إنتاجية تحدد كيفية اشتقاق الرموز غير الطرفية (non-terminal symbols) إلى رموز طرفية (terminal symbols) أو رموز غير طرفية أخرى.
الدوال التحليلية: يتم إنشاء دالة تحليلية لكل رمز غير طرفي في النحو. هذه الدالة تحاول مطابقة الرموز الطرفية وغير الطرفية في المدخلات وفقًا لقواعد الإنتاجية المرتبطة بالرمز غير الطرفي.
الرجوع الذيلي: عندما تحتاج دالة تحليلية إلى استدعاء دالة تحليلية أخرى بشكل عودي، فإنها تفعل ذلك بطريقة تضمن أن الاستدعاء العودي هو آخر عملية يتم تنفيذها. هذا يتحقق عادةً عن طريق تمرير حالة المحلل (مثل مؤشر إلى الموضع الحالي في المدخلات) كمُدخل للدالة العودية، بحيث يمكن للدالة العودية استئناف التحليل مباشرة بعد العودة.
التحكم في الفشل: إذا فشلت دالة تحليلية في مطابقة المدخلات، فإنها تعيد مؤشرًا إلى نقطة الفشل في المدخلات أو قيمة تشير إلى الفشل. يمكن للدالة المستدعية بعد ذلك محاولة قاعدة إنتاجية بديلة أو التراجع (backtrack) إلى نقطة سابقة في التحليل.

مزايا وعيوب محللات الرجوع الذيلي

تتمتع محللات الرجوع الذيلي بعدة مزايا وعيوب يجب أخذها في الاعتبار عند اختيارها كأداة للتحليل:

المزايا:

كفاءة الذاكرة: الميزة الرئيسية لمحللات الرجوع الذيلي هي كفاءة الذاكرة. نظرًا لأن الاستدعاءات العودية هي استدعاءات ذيلية، يمكن للمترجم أو المفسر تحسين التنفيذ عن طريق استبدال استدعاء الدالة الحالي باستدعاء الدالة العودية، مما يقلل من استهلاك الذاكرة.
سهولة الفهم والصيانة: يمكن أن تكون محللات الرجوع الذيلي أسهل في الفهم والصيانة مقارنة بأنواع أخرى من المحللات، خاصة إذا كان النحو بسيطًا نسبيًا.
المرونة: يمكن تكييف محللات الرجوع الذيلي للتعامل مع مجموعة متنوعة من اللغات والقواعد النحوية.

العيوب:

القيود على النحو: قد تتطلب محللات الرجوع الذيلي قيودًا معينة على النحو، مثل تجنب الرجوع الأيسر (left recursion). الرجوع الأيسر يحدث عندما تبدأ قاعدة إنتاجية برمز غير طرفي نفسه، مما قد يؤدي إلى حلقات لا نهائية في التحليل.
صعوبة التعامل مع القواعد النحوية المعقدة: قد يكون من الصعب تصميم محلل رجوع ذيلي للقواعد النحوية المعقدة للغاية.
الأداء: على الرغم من كفاءة الذاكرة، قد لا يكون أداء محللات الرجوع الذيلي هو الأمثل في بعض الحالات، خاصة إذا كانت هناك حاجة إلى الكثير من التراجع.

مثال على محلل رجوع ذيلي (بصيغة زائفة)

لنفترض أننا نريد تحليل تعبيرات حسابية بسيطة تتضمن الجمع والطرح. يمكن تمثيل النحو على النحو التالي:


expression -> term (('+' | '-') term)*
term -> factor (('*' | '/') factor)*
factor -> number | '(' expression ')'

يمكننا كتابة محلل رجوع ذيلي لهذا النحو على النحو التالي (بصيغة زائفة):


function parseExpression(input, position, accumulator = null):
  let result = parseTerm(input, position)
  if result == null:
    return accumulator

  let termResult = result;

  while input[termResult.newPosition] == '+' or input[termResult.newPosition] == '-':
    let operator = input[termResult.newPosition]
    let nextTermResult = parseTerm(input, termResult.newPosition + 1)

    if (nextTermResult == null):
      return null // Error: Expected term after operator

    if (operator == '+'):
      accumulator = termResult.value + nextTermResult.value
    else:
      accumulator = termResult.value - nextTermResult.value

    termResult = nextTermResult // Update the position with the new term's position.

  return { value: accumulator, newPosition: termResult.newPosition };

function parseTerm(input, position):
  // Implementation for parsing a term
  // Similar structure to parseExpression, handling '*' and '/'
  // Returns {value, newPosition} or null if parsing fails.
  return null;


function parseFactor(input, position):
    // Implementation for parsing a factor (number or parenthesized expression)
    // Returns {value, newPosition} or null if parsing fails.
    return null;

في هذا المثال، الدالة `parseExpression` هي مثال على دالة رجوع ذيلي. بدلاً من الاحتفاظ بقيمة متوسطة في مكدس الاستدعاءات، يتم تمريرها كـ “accumulator” في كل استدعاء عودي. هذا يسمح للمترجم أو المفسر بتحسين التنفيذ وتجنب تجاوز سعة مكدس الاستدعاءات.

استخدامات محللات الرجوع الذيلي

تُستخدم محللات الرجوع الذيلي في مجموعة متنوعة من التطبيقات، بما في ذلك:

المترجمات والمفسرات: تستخدم المترجمات والمفسرات محللات لتحويل التعليمات البرمجية المصدر إلى تعليمات برمجية قابلة للتنفيذ. يمكن استخدام محللات الرجوع الذيلي لتحليل لغات البرمجة ذات القواعد النحوية البسيطة نسبيًا.
معالجة النصوص: يمكن استخدام محللات الرجوع الذيلي لتحليل النصوص بتنسيقات مختلفة، مثل HTML أو XML.
أدوات البرمجة اللغوية: يمكن استخدام محللات الرجوع الذيلي لتحليل اللغات الطبيعية، على الرغم من أن هذا يتطلب عادةً استخدام قواعد نحوية أكثر تعقيدًا.

خاتمة

محللات الرجوع الذيلي هي نوع من محللات الهبوط العودي التي تتميز بكفاءة الذاكرة وسهولة الفهم. تعتمد هذه المحللات على مفهوم الرجوع الذيلي، حيث يكون الاستدعاء العودي هو آخر عملية يتم تنفيذها في الدالة، مما يسمح بتحسين التنفيذ وتجنب تجاوز سعة مكدس الاستدعاءات. على الرغم من أنها قد تكون محدودة من حيث القدرة على التعامل مع القواعد النحوية المعقدة للغاية، إلا أنها لا تزال أداة قيمة في العديد من التطبيقات، مثل المترجمات والمفسرات ومعالجة النصوص.