كتب المحلل اللغوي ll
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
المحلل اللغوي LL (معلومة)
المحلل اللغوي LL LL parser
محلل LL هو محلل من أعلى إلى أسفل تصميم أعلى أسفل وأسفل أعلى لمجموعة فرعية من قواعد السياق الحرcontext-free grammar]]s]] فإنه يقوم بتحليل المدخلات من اليسار إلى اليمين، ويبني الاستخلاص أقصى اليسار من الجملة (وبالتالي محلل LL، مقارنة مع محللLR). فئة القواعد التي تحلل على النحو هذا يقال عليه قواعد LL. ما تبقى من هذه المقالة يصف نوع الجدول الذي يستند إليه المحلل، والبديل هو محلل نزول تكراريالترميز التكراري النموذجي الذي يتم ترميزه عادة باليد (وإن لم يكن دائما، وانظر على سبيل المثال ANTLR لـ (*)LL مولد محلل نزول تكراري).
ويسمى محلل LL محلل (k) LL إذا كان يستخدم الرموز K للاستباق عند تحليل الجملة. إذا كان هذا المحلل موجود لقواعد معينة، ويمكنه تحليل جمل هذه القواعد بدون تراجع فهو يسمى قواعد LL(k). اللغة التي لديها قواعد LL(k) تسمى لغة LL(k). وهناك لغات LL(k+n) التي ليست لغات LL(k). [1] والنتيجة لذلك هو أن ليس كل لغات السياق الحر هي لغات LL(k).
قواعد [[LL (1) LL(grammars شعبية جدا لأن المحلل LL المقابل يحتاج فقط لإلقاء نظرة على الرمز التالي لاتخاذ قرارات التحليل. الغات التي تستند إلى قواعد مع قيمة مرتفعة من k اعتبرت تقليديا [who?] [من?] صعبة التحليل، رغم أن هذا يعتبر نوعا ما غير صحيح الآن، نظرا لتوافر والتوسع في نطاق الاستخدام [citation needed] لمولدات المحلل الذي يدعم قواعد LL(k) لـ k الأعتباطى.
ويسمى محلل LL محلل (*)LL محلل إذا لم يقتصر على الرموز K للاستباق، ولكن يمكنه اتخاذ قرارات التحليل عن طريق التعرف على ما إذا كانت الرموز التالية تنتمي إلى لغة عادية (على سبيل المثال عن طريق استخدام أوتوماتيكية محدودة القطعية.
و هناك خلاف بين "المدرسة الأوروبية" لتصميم اللغة، والذين يفضلون الاستناد على قواعد LL، وبين " مدرسة الولايات المتحدة "، الذين يفضلون في الغالب الاستناد على قواعد [[LR. citation needed وهذا يرجع إلى حد كبير لتقاليد التدريس وتفاصيل وصف أساليب وأدوات في بعض الكتب المدرسية ؛ التأثير الآخر قد يكون نيكلاوس ويرث في أي تي أتش زيوريخ في سويسرا، الذي بحوه وصف عدد من الطرق لتحسين لغات ومترجمينLL(1)..
الحالة العامة
المحلل يعمل على سلاسل من قواعد السياق الحرقواعد خالية من السياق.
المحلل يتكون من
- وجود مخزن مرحلي للمدخلات صوان (معلوماتية)، يجري سلسلة المدخلات (الذي بنته القاعدة)
- مكدس لتخزين المحطات الطرفية والغير طرفية من القاعدة لتحليلها
- جدول التحليل الذي يقول ما حكم القاعدة (إن وجدت) التي سوف تطبق بإعطاء الرموز في أعلى المكدس الخاص به ورمز المدخلات التالي.
المحلل يطبق الحكم الذي يجده في الجدول عن طريق مطابقة الرمز أعلى المكدس (صف) مع الرمز الحالي في تدفق المدخلات (العمود). عندما يبدأ محلل، المكدس يحتوي بالفعل على رمزين : [ S, $ ] حيث "$" هو محطة طرفية خاصة للإشارة إلى أسفل المكدس ونهاية تدفق المدخلات، و"S" هو رمز البداية للقاعدة. المحلل سوف يحاول إعادة كتابة محتويات هذا المكدس على ما يراه على تدفق المدخلات. ومع ذلك، فإنه يحتفظ فقط في مكدس على ما هو ما زال بحاجة إلى إعادة صياغة.
مثال البناء
الإعداد
لتفسير كيف يعمل، سوف ننظر للقاعدة الصغيرة التالية :
- S → F
- S → ( S + F )
- F → a
ونقوم بتحليل المدخلات التالية :
- (a + a)
جدول التحليل لهذه القواعد تبدو على النحو التالي :
(لاحظ أن هناك أيضا عمود للمحطة الطرفية الخاصة، الممثلة هنا بـ $، التي تستخدم لتشير إلى نهاية تدفق المدخلات.)
خطوات التحليل
في كل خطوة، المحلل يقرأ الرمز المتاحة التالي من تدفق المدخلات، وأعلى رمز من المكدس. إذا كان رمز المدخلات والرمز أعلى المكدس متطابقان، محلل سوف يتجاهلهم على حد سواء، ويبقي على الرموز التي لا متطابقة في تدفق المدخلات وعلى المكدس.
وهكذا، في الخطوة الأولى، المحلل يقرأ رمز الإدخال ")" والرمز أعلى المكدس"S". تعليمات جدول التحليل تأتي من العمود الذي على رأسه رمز الإدخال ")" والصف الذي على رأسه المكدس الذي أعلاه "S"؛ هذه الخلية تحتوي "2"الذي يوجه المحلل لتطبيق القاعدة (2) ويجب على المحلل إعادة كتابة. "S" إلى "(S + F)" على المكدس ويكتب القاعدة رقم 2 على المخرجات والمكدس سوف يصبح هكذا :
[ (, S, +, F, ), $ ]
حيث الرمز "(" من تدفق المدخلات لم يتطابق مع الرمز الأعلى، "S"، من المكدس، لم يتم إزالته، ويبقى الرمز المتاح المقبل في المدخلات للخطوة التالية.
في الخطوة الثانية، المحلل يزيل ")" من تدفق مدخلاته ومن المكدس، نظرا لأنها متطابقة يصبح المكدس الآن :
[ S, +, F, ), $ ]
الآن المحلل عنده "a" على تدفق مدخلاته و"s" في أعلى المكدس. جدول التحليل يرشد إلى تطبيق القاعدة (1) من قواعد اللغة وكتابة القاعدة رقم 1 إلى تدفق الإخراج. المكدس يصبح :
[ F, +, F, ), $ ]
الآن المحلل عنده "a" على تدفق مدخلاته و"f" في أعلى المكدس. جدول التحليل يرشد إلى تطبيق القاعدة (3) من قواعد اللغة وكتابة القاعدة رقم 3 إلى تدفق الإخراج. المكدس يصبح ::
[ a, +, F, ), $ ]
في الخطوتان المقبلتان المحلل يقرأ "a" و"+ من jدفق المدخلات و، نظرا لأنهما متطابقان فالبندين التاليين على المكدس، يزيلهما أيضاً من المكدس وهذا ينتج:
[ F, ), $ ]
في الخطوات الثلاث القادمة سوف يقوم المحلل باستبدال " F" على مكدس بـ " a" ،و يكتب القاعدة رقم 3 إلى تدفق الإخراج وإزالة "a" و")" من كلا من المكدس وتدفق المدخلات. وبذلك ينتهي المحلل بـ "$" على حد سواء في مكدس وتدفق المدخلات.
في هذه الحالة المحلل سوف يقوم بعمل التقرير إلى أنه وافق على سلسلة المدخلات ويكتب القائمة التالية من عدد القواعد إلى تدفق الإخراج :
- [ 2, 1, 3, 3 ]
هذا في الواقع هو قائمة من القواعد للاستخلاص أقصى اليسارقواعد خالية من السياق من سلسلة المدخلات، والتي هي كالتالي:
- S → ( S + F ) → ( F + F ) → (a + F ) → (a + a)
تنفيذ المحلل في C++
ما يلي يتبع تنفيذ C++ على أساس جدول محلل LL للغة في المثال التالي :
#include <iostream> #include <map> #include <stack> enum Symbols { // the symbols: // Terminal symbols: TS_L_PARENS, // ( TS_R_PARENS, //) TS_A, // a TS_PLUS, // + TS_EOS, // $, in this case corresponds to '
