المترجمون: ما الفرق بين موزعي LL (0) و LR (0). هل هناك شيء مثل المحلل اللغوي LL (0)؟


الاجابه 1:

يبدو أن هذا السؤال يركز على المحلل اللغوي LL (0) ، لذلك دعونا نحددهم. محلل LL (0) ، يوزع من اليسار إلى اليمين باستخدام الرموز المميزة في بداية الإنتاج لتحديد الإنتاج المراد تطبيقه. ماذا يعني هذا الرمز المميز ، فهذا يعني أن المحلل اللغوي لا يمكنه استخدام النص الذي يتم تحليله لتحديد الإنتاج المطلوب تطبيقه. هذا يعني أن المحلل اللغوي لا يمكنه اتخاذ أي خيارات. يجب أن تعرف قبل أن تبدأ في تحليل بالضبط تسلسل الرموز التي سيتم تحليلها. يجب إصلاح تسلسل الرموز ، مما يعني أنه لا يمكن أن يكون هناك سوى تسلسل واحد يقوم المحلل اللغوي بتحليله. وبالتالي ، يمكن أن يكون لديك محلل يقبل "Hello world!" مع قواعد النحو مثل هذا:

الهدف: علامة "تعبير" Hello whitespace "world" علامة التعجب ؛

لاحظ أن الاختلافات الوحيدة المسموح بها هي كيف يطابق lexer الرموز المميزة.

(آمل أن يكون الرمز واضحًا - إنه في الأساس الذي استخدمه في Yacc ++. السلاسل المقتبسة هي رموز ، وكذلك أي معرفات غير محددة.)

المحلل اللغوي يتوقع دائماً نفس تسلسل الرموز بالضبط. ليس من الضروري وجود قاعدة واحدة فقط ، كما فعل المثال الأول لدينا. يمكن أن يبدو مثل هذا.

الهدف: مرحبا جزء جزء أبيض مسافة النهاية؛

hello-part: hello1؛

hello1: "Hello"؛

الجزء الأخير: الجزء الأخير من العالم ؛

جزء من العالم: "العالم" ؛

الجزء الاخير: "!"؛

ومع ذلك ، لاحظ كيف أن أيا من القواعد لديها أي عوامل تشغيل "أو" (|) ولا يوجد سوى قاعدة واحدة لكل محطة. هذا هو ما يسمح للمحلل بمعرفة كيفية مطابقة كل قاعدة دون استخدام أي رموز مميزة (الرموز التي تختار الطريقة التي ينتقل بها المحلل) ، مما يجعل القواعد LL (0).

الآن ، هل من الممكن استخدام إنتاج متكرر ولا يزال لديك قواعد لغة LL (0)؟ الجواب هو "لا". دعونا نرى ما يحدث إذا كان لدينا قاعدة العودية.

هدف: "س" هدف "ص" ؛

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

وبالتالي ، يجب على قواعد اللغة (0) LL تحليل قائمة محدودة من الرموز المميزة ، بالضبط قائمة محدودة واحدة (نفس القائمة في كل مرة).

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

الهدف: "س" | "(" هدف ")"؛

يوزع هذا النحو "x" محاطًا بعدد من الأقواس. لاحظ أنه يمكن استخدام الرمز المميز "x" و "(" الرمز المميز لتحديد القاعدة التي يجب تطبيقها. 0 في LR (0) لا يقيد استخدام الرموز المميزة داخل قاعدة ، مثل 0 في LL (0). الشيء الوحيد الذي يقيده هو استخدام الرموز (السياق ، بعد القاعدة في بعض الاستخدامات لغير الطرفي) عند اتخاذ قرار التخفيض. هذه القواعد لا تحتاج إلى أي سياق لتقرر تقليله. على البديل الأول ، إنها تقلل عند الرؤية "x" في الثانية تقلل بعد رؤية ")". تحدد الرموز المميزة داخل القاعدة متى يجب تقليل القاعدة تمامًا.


الاجابه 2:

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

يعني محللون LR (0) أنهم يعالجون دفق الرمز المميز من اليسار إلى اليمين ، باستخدام اشتقاق أقصى اليمين مع صفر نظرة إلى الأمام. هذا يعني أنهم يبنون شجرة التحليل من أسفل إلى أعلى ، في حين يقوم محللون LL (0) ببناء شجرة التحليل من أعلى إلى أسفل.