المحلل اللغوي LL

[ S, +, F, ), $ ]

الآن المحلل عنده 'a' على تدفق مدخلاته و's' في أعلى المكدس. جدول التحليل يرشد إلى تطبيق القاعدة (1) من قواعد اللغة وكتابة القاعدة رقم 1 إلى تدفق الإخراج. المكدس يصبح:

التحليل إلى عوامل اليسار

• عامل يسار مشترك يكون خارج الحسبان مثل 3x + 3y = 3(x+y).
• A -> X | X Y Z
• يصبح
• A -> X B

TS_PLUS, // +

TS_EOS, // $, in this case corresponds to '\0'

break;

• default:
• cout << "parsing table defaulted" << endl;
• return 0;
• break;
• }
• }
• }
• cout << "finished parsing" << endl;
• return 0;
• }

o Fi(ε) = { ε }

4. كرر الخطوات 2 و3 حتى كافة مجموعات Fi تبقى متساوية.

إضافةً إلى ذلك، وللأسف، فإن المجموعات الأولى ليست كافية لحساب جدول التحليل، لأن الجزء اليمين w من القاعدة قد يكتب أخيراً لسلسلة فارغة. لذلك فإن المحلل ينبغي أن يستعمل القاعدة A → w إذا ε في Fi(w) وترا على تدفق الإدخال الرمز الذي يمكن أن يتبع a ولذلك نحن بحاجة كذلك المجموعة التابعة لـ A، تكتب هنا Fo(A)، التي تعرف على أنها مجموعة من المحطات الطرفية a ومن هذا القبيل هناك سلسلة من الرموز αAaβ التي يمكن استخلاصها من رمز البداية. ويمكن أن يتم احتساب المجموعات التابعة للمحطات الغير طرفية في القواعد على النحو التالي:

3. أضف Fi(wi) إلى Fi(Ai) لكل قاعدة Ai → wi

}

int main(int argc, char **argv)

{

TS_INVALID, // invalid token

• // Non-terminal symbols:
• NTS_S, // S
• NTS_F
• };

using namespace std;

• if (argc < 2)
• {
• cout << "usage:\n\tll '(a+a)'" << endl;
• return 0;

break;

return TS_EOS;

case '\0': // this will act as the $ terminal symbol

B -> Y Z | ε

يمكن تطبيقه عندما يبدأ بديلين بنفس الرمز مثل تعارض أول/أول

break;

• default:
• return TS_INVALID;
• break;
• }

المحلل يتكون من

وعلى صعيد آخر، مكدس لتخزين المحطات الطرفية والغير طرفية من القاعدة لتحليلها

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

علاوةً على ذلك، المحلل يطبق الحكم الذي يجده في الجدول عن طريق مطابقة الرمز أعلى المكدس (صف) مع الرمز الحالي في تدفق المدخلات (العمود).

في هذا الإطار، وجود مخزن مرحلي للمدخلات صوان (معلوماتية)، يجري سلسلة المدخلات (الذي بنته القاعدة)

عندما يبدأ محلل، المكدس يحتوي بالفعل على رمزين:

break;

return TS_R_PARENS;

case ')':

{

• cout << "Rule " << table[ss.top][lexer(*p)] << endl;
• switch(table[ss.top][lexer(*p)])
• {
• case 1: // 1. S → F
• ss.pop;
• ss.push(NTS_F); // F

أولا / أول تعارض

أول مجموعات من تقاطع محطتين غير طرفيتين مختلفتين.

المصطلحات

التعارضات LL(1)

هناك 3 أنواع من تعارضات LL(1):

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

break;

return TS_PLUS;

case '+':

{

• cout << "Matched symbols: " << lexer(*p) << endl;
• p++;
• ss.pop;
• }
• else

ss.pop;

• ss.push(TS_R_PARENS); //)
• ss.push(NTS_F); // F
• ss.push(TS_PLUS); // +
• ss.push(NTS_S); // S
• ss.push(TS_L_PARENS); // (
• break;
• case 3: // 3. F → a
• ss.pop;
• ss.push(TS_A); // a

A -> 'a' | epsilon

في هذا الإطار، المجموعة الأولى من A الآن { 'a' epsilon } والمجموعة التابعة { 'a' }.

1. نبدأ كل Fo(Ai) مع المجموعة الفارغة

من جانب آخر، الآن يمكن أن نحدد بالضبط أي القواعد التي سوف ترد في جدول التحليل. إذا T[A, a] تشير إلى الدخول في الجدول لمحطة غير طرفية A وطرفية a، إذا

• 2. إذا كان هناك قاعدة للنموذج Aj → wAiw'، إذا
• * إذا كانت المحطة الطرفية a في Fi(w')، قم بإضافة a إلى Fo(Ai)
• * إذا كانت ε في Fi(w')، قم بإضافة a إلى Fo(Ai)
• 3. كرر الخطوة 2 حتى كل مجموعات Fo تبقى متساوية.

T[A،a]يحتوي على مادة A → w إذا وفقط إذا كانت

استدعاء ذاتي من اليسار

• و التكرار من اليسار سوف يسبب تعارض أول / أول مع جميع البدائل.
• E -> E '+' term | alt1 | alt2
• الحلول لتعارضات LL(1)

F → a

• ونقوم بتحليل المدخلات التالية:
• (a + a)
• جدول التحليل لهذه القواعد تبدو على النحو التالي:

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

*/

enum Symbols lexer(char c)

}

• stack ss; // symbol stack
• char *p; // input buffer
• // initialize the symbols stack
• ss.push(TS_EOS); // terminal, $
• ss.push(NTS_S); // non-terminal, S
• // initialize the symbol stream cursor
• p = &argv[1][0];
• // setup the parsing table
• table[NTS_S][TS_L_PARENS] = 2; table[NTS_S][TS_A] = 1;

كذلك، map< enum Symbols, map > table; // LL parser table, maps < non-terminal, terminal> pair to action

[ F, +, F, ), $ ]

ومن جهة أخرى، الآن المحلل عنده 'a' على تدفق مدخلاته و'f' في أعلى المكدس. جدول التحليل يرشد إلى تطبيق القاعدة (3) من قواعد اللغة وكتابة القاعدة رقم 3 إلى تدفق الإخراج. المكدس يصبح::

break;

case 'a':

return TS_A;

-> T

E -> T Z

Z -> '+' T Z

علاوةً على ذلك، هذه القاعدة ليست سوى مجموعة من الـ T منفصلة بـ '+' في شكل تعبير عادي T ('+' T)* لذا يمكن إعادة كتابة الحكم هكذا

-> ε

• الآن لا يوجد أي تكرار من اليسار ولا تعارضات على أي من القواعد.
• ومع ذلك، ليس كل CFGs لديها قواعد مساوية لـقواعد LL(k)، مثلًا:
• S -> A | B

/*

Converts a valid token to the corresponding terminal symbol

1. نبدأ كلFi(wi) وFi(Ai) مع المجموعة الفارغة

ومن جهة أخرى، 2. نضيف Fi(wi) على Fi(Ai) لأي حكم Ai → wi، حيث Fi يتم تعريفها على النحو التالي:

ومن جهة أخرى، o Fi(A w') = Fi(A) for every nonterminal A with ε not in Fi(A) لكل محطة طرفية a مع ε ليست في

o Fi(a w') = { a } for every terminal a لكل محطة طرفية

من جهة ثانية، o Fi(A w') = Fi(A) \ { ε } ∪ Fi(w') for every nonterminal A with ε in Fi(A) لكل محطة غير طرفية aمع ε في

[ a, +, F, ), $ ]

علاوةً على ذلك، في الخطوتان المقبلتان المحلل يقرأ 'a' و'+ من jدفق المدخلات و، نظرا لأنهما متطابقان فالبندين التاليين على المكدس، يزيلهما كذلك من المكدس وهذا ينتج:

{

switch(c)

break;

case 2: // 2. S → (S + F)

[ F, ), $ ]

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

من جانب آخر، في الخطوات الثلاث القادمة سوف يقوم المحلل باستبدال ' F' على مكدس بـ ' a' ، ويكتب القاعدة رقم 3 إلى تدفق الإخراج وإزالة 'a' و')' من كلا من المكدس وتدفق المدخلات. وبذلك ينتهي المحلل بـ '$' على حد سواء في مكدس وتدفق المدخلات.

إزالة التكرار من اليسار

ومن جهة أخرى، مثال بسيط لإزالة التكرار من اليسار قاعدة الإنتاج التالية تركت التكرار على E

E -> E '+' T

المحلل اللغوي LL LL parser

في هذا الإطار، ويسمى محلل LL محلل (k) LL إذا كان يستعمل الرموز K للاستباق عند تحليل الجملة. إذا كان هذا المحلل موجود لقواعد معينة، ويمكنه تحليل جمل هذه القواعد بدون تراجع فهو يسمى قواعد LL(k). اللغة التي لديها قواعد LL(k) تسمى لغة LL(k). وهناك لغات LL(k+n) التي ليست لغات LL(k). [1] والنتيجة لذلك هو أن ليس كل لغات السياق الحر هي لغات LL(k).

وفي هذا الصدد، محلل LL هو محلل من أعلى إلى أسفل تصميم أعلى أسفل وأسفل أعلى لمجموعة فرعية من قواعد السياق الحرcontext-free grammars فإنه يقوم بتحليل المدخلات من اليسار إلى اليمين، ويبني الاستخلاص أقصى اليسار من الجملة (وبالتالي محلل LL، مقارنة مع محللLR). فئة القواعد التي تحلل على النحو هذا يقال عليه قواعد LL.

وعلى صعيد آخر، ما تبقى من هذه المقالة يصف نوع الجدول الذي يستند إليه المحلل، والبديل هو محلل نزول تكراريالترميز التكراري النموذجي الذي يتم ترميزه عادة باليد (وإن لم يكن دائما، وانظر مثلًا ANTLR لـ (*)LL مولد محلل نزول تكراري).

في هذا الإطار، قواعد LL (1) LL(grammars شعبية جدا لأن المحلل LL المقابل يحتاج فقط لإلقاء نظرة على الرمز التالي لاتخاذ قرارات التحليل. الغات التي تستند إلى قواعد مع قيمة مرتفعة من k اعتبرت تقليديا [who?] [من?] صعبة التحليل، رغم أن هذا يعتبر نوعا ما غير صحيح الآن، نظرا لتوافر والتوسع في نطاق الاستخدام [citation needed] لمولدات المحلل الذي يدعم قواعد LL(k) لـ k الأعتباطى.

في هذا الإطار، و هناك خلاف بين «المدرسة الأوروبية» لتصميم اللغة، والذين يفضلون الاستناد على قواعد LL، وبين «مدرسة الولايات المتحدة»، الذين يفضلون في الغالب الاستناد على قواعد LR. citation needed وهذا يرجع إلى حد كبير لتقاليد التدريس وتفاصيل وصف أساليب وأدوات في بعض الكتب المدرسية؛ التأثير الآخر قد يكون نيكلاوس ويرث في أي تي أتش زيوريخ في سويسرا، الذي بحوه وصف عدد من الطرق لتحسين لغات ومترجمينLL(1)..

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

table[NTS_F][TS_A] = 3;

while(ss.size > 0)

تنفيذ المحلل في C++

• ما يلي يتبع تنفيذ C++ على أساس جدول محلل LL للغة في المثال التالي:
• #include
• #include
• #include

الاستبدال

وفي السياق ذاته، استبدال قاعدة مكان قاعدة أخرى لإزالة غير مباشرة أو تعارض الأولى / التالي. لاحظ أن هذا قد يؤدي إلى تعارض الأول/ أول.

أولا / يتبع التعارض

S -> A 'a' 'b'

في هذا الإطار، المجموعة الأولى والمجموعة التابعة للقواعد المتداخلة. مع ابسيلون في المجموعة الأولى وهو غير معروف أي بديل تختار.

مثال على تعارض LL(1):

{

if(lexer(*p) == ss.top)

enum Symbols {

// the symbols:

// Terminal symbols:

{

case '(':

return TS_L_PARENS;

خطوات التحليل

من جانب آخر، وهكذا، في الخطوة الأولى، المحلل يقرأ رمز الإدخال ')' والرمز أعلى المكدس'S'. تعليمات جدول التحليل تأتي من العمود الذي على رأسه رمز الإدخال ')' والصف الذي على رأسه المكدس الذي أعلاه 'S'؛ هذه الخلية تحتوي '2"الذي يوجه المحلل لتطبيق القاعدة (2) ويجب على المحلل إعادة كتابة. 'S' إلى '(S + F)' على المكدس ويكتب القاعدة رقم 2 على المخرجات والمكدس سوف يصبح هكذا:

[ (, S, +, F, ), $ ]

من جهة ثانية، حيث الرمز '(' من تدفق المدخلات لم يتطابق مع الرمز الأعلى، 'S'، من المكدس، لم يتم إزالته، ويبقى الرمز المتاح المقبل في المدخلات للخطوة التالية.

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

وعلى صعيد آخر، في الخطوة الثانية، المحلل يزيل ')' من تدفق مدخلاته ومن المكدس، نظرا لأنها متطابقة يصبح المكدس الآن:

[ 2, 1, 3, 3 ]

S → ( S + F ) → ( F + F ) → (a + F ) → (a + a)

إضافةً إلى ذلك، هذا في الواقع هو قائمة من القواعد للاستخلاص أقصى اليسارقواعد خالية من السياق من سلسلة المدخلات، والتي هي كالتالي:

TS_L_PARENS, // (

TS_R_PARENS, //)

TS_A, // a

a في Fi(w) أو

ε في Fi(w) وFo(A)

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

ومن جهة أخرى، حتى منتصف التسعينات، وكان يعتقد على نطاق واسع أن LL(k) تحليل لـ (k > 1) كان غير عملياً [citation needed]، إذ أن جدول التحليل سيكون حجمه هائل في k في أسوأ الأحوال. وهذا المفهوم تغيير تدريجيا بعد إصدار PCCTS في نحو عام 1992، عندما اتضح أنه يمكن تحليل الكثير من لغات البرمجة بكفاءة من خلال المحلل LL(k) من دون التسبب في أعمال أسوأ الحالات للمحلل اللغوي. وعلاوة على ذلك، في بعض حالات تحليل LL مجدية حتى مع الاستباق غير المحدود. على النقيض من ذلك، مولدات المحلل التقليدي، مثل yacc يستعمل جدول تحليل LALR(1) لبناء محلل LR المقيد مع استباق رمز ثابت واحد.

بناء جدول تحليل LL(k)

[ S, $ ]

مثال البناء

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

S → F

S → ( S + F )

التعارضات

كذلك، كما هو موضح في المقدمة، محللات(1) LL تتعرف على اللغات ذات قواعد (1) LL، والتي هي حالة خاصة من قواعد السياق الحر (CFG's)؛ محللات (1) LL لا يمكن أن تتعرف على كل لغات السياق الحر. لغات (1) LLهي بالضبط تلك التي يتم التعرف عليها بتأكيدية التشغيل الذاتي التنازلى deterministic pushdown automata الذي يقتصر على حالة واحدة. من أجل CFG أن تكون قاعدة (1) LL، يجب أن لا تنشأ تعارضات معينة، التي وصفناها في هذا القسم.

A -> 'a' A 'b' | ε

• B -> 'a' B 'b' 'b' | ε
• ويمكن أن نتبين أن ليس هناك أي قاعدة LL(k)، تقبل اللغة المولدة بهذه القاعدة.
• انظر كذلك
• Comparison of parser generators
• Parse tree
• Top-down parsing
• Bottom-up parsing

الحالة العامة

من جانب آخر، المحلل يعمل على سلاسل من قواعد السياق الحرقواعد خالية من السياق.

الإعداد

لتفسير كيف يعمل، سوف ننظر للقاعدة الصغيرة التالية: