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

في علم الحاسوب ، يُعدّ محلل الانحدار التكراري نوعًا من المحللات التنازلية التي تُبنى من مجموعة من الإجراءات التكرارية المتبادلة (أو ما يُعادلها غير التكراري)، حيث يُنفّذ كل إجراء من هذه الإجراءات أحد الرموز غير الطرفية للقواعد النحوية . وبالتالي، فإن بنية البرنامج الناتج تُحاكي بدقة بنية القواعد النحوية التي يتعرف عليها. ^{[ 1 ] [ 2 ]}

المحلل التنبؤي هو محلل انحداري تكراري لا يتطلب التراجع . ^{[ 3 ]} التحليل التنبؤي ممكن فقط لفئة قواعد LL( k ) ، وهي القواعد الخالية من السياق التي يوجد لها عدد صحيح موجب k يسمح للمحلل الانحداري التكراري بتحديد قاعدة الإنتاج التي سيستخدمها بفحص k رمزًا من المدخلات التالية فقط. لذلك، تستبعد قواعد LL( k ) جميع القواعد الغامضة ، وكذلك جميع القواعد التي تحتوي على تكرار يساري . يمكن تحويل أي قاعدة خالية من السياق إلى قاعدة مكافئة لا تحتوي على تكرار يساري، ولكن إزالة التكرار اليساري لا ينتج عنها دائمًا قاعدة LL( k ). يعمل المحلل التنبؤي في وقت خطي .

الانحدار التكراري مع التراجع هو أسلوب يحدد قاعدة الإنتاج التي يجب استخدامها من خلال تجربة كل قاعدة إنتاج على حدة. لا يقتصر الانحدار التكراري مع التراجع على قواعد LL( k )، ولكنه لا يضمن الانتهاء إلا إذا كانت القاعدة من نوع LL( k ). حتى عند الانتهاء، قد تتطلب المحللات التي تستخدم الانحدار التكراري مع التراجع وقتًا أُسّيًا .

على الرغم من شيوع استخدام المحللات التنبؤية، وكثرة اختيارها عند كتابة المحلل يدويًا، إلا أن المبرمجين غالبًا ما يفضلون استخدام محلل قائم على الجداول، مُنتَج بواسطة مولد محللات ، سواءً للغات LL( k ) أو باستخدام محلل بديل، مثل LALR أو LR . ويصدق هذا بشكل خاص إذا لم تكن القواعد النحوية بصيغة LL( k ) ، إذ يتطلب الأمر تحويلها إلى صيغة LL لجعلها مناسبة للتحليل التنبؤي. كما يمكن توليد المحللات التنبؤية تلقائيًا باستخدام أدوات مثل ANTLR .

يمكن تمثيل المحللات التنبؤية باستخدام مخططات الانتقال لكل رمز غير طرفي، حيث يتم تسمية الحواف بين الحالات الأولية والنهائية بواسطة الرموز (الطرفية وغير الطرفية) الموجودة على الجانب الأيمن من قاعدة الإنتاج. ^{[ 4 ]}

القواعد النحوية التالية الشبيهة بـ EBNF ( لغة البرمجة PL/0 الخاصة بـ Niklaus Wirth ، من كتاب Algorithms + Data Structures = Programs ) هي في شكل LL(1) :

البرنامج = كتلة "." .block = [ "const" ident "=" number { "," ident "=" number } ";" ] [ "var" ident { "," ident } ";" ] { "procedure" ident ";" block ";" } statement .statement = ident ":=" expression | "call" ident | "begin" statement { ";" statement } "end" | "if" condition "then" statement | "while" condition "do" statement .الشرط = تعبير "فردي" | تعبير ( "=" | "#" | "<" | "<=" | ">" | ">=" ) تعبير .التعبير = [ "+" | "-" ] مصطلح {( "+" | "-" ) مصطلح } .term = factor {( "*" | "/" ) factor } .العامل = المعرف | الرقم | "(" تعبير ")" .

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

extern void error ( const char msg []); extern void consumesym ();typedef enum Symbol { ident , number , lparen , rparen , times , slash , plus , minus , eql , neq , lss , leq , gtr , geq , callsym , beginsym , semicolon , endsym , ifsym , whilesym , comes , thensym , dosym , constsym , comma , varsym , procsym , period , oddsym } Symbol ; extern Symbol peeksym ();دالة منطقية تقبل ( الرمز s ) { إذا ( كان الرمز المعروض يساوي s ) { استهلك الرمز (); أرجع صحيحًا ؛ } أرجع خطأً ؛ }bool expect ( Symbol s ) { if ( accept ( s )) { return true ; } error ( "expect: unexpected symbol" ); return false ; }void factor () { if ( accept ( ident ) || accept ( number )) { return ; } if ( accept ( lparen )) { expression (); expect ( rparen ); } else { error ( "factor: syntax error" ); consumesym (); } }void term () { factor (); while ( peeksym () == times || peeksym () == slash ) { consumesym (); factor (); } }void expression () { if ( peeksym () == plus || peeksym () == minus ) { consumesym (); } term (); while ( peeksym () == plus || peeksym () == minus ) { consumesym (); term (); } }void condition () { if ( accept ( oddsym )) { expression (); return ; } expression (); if ( peeksym () == eql || peeksym () == neq || peeksym () == lss || peeksym ( ) == leq || peeksym () == gtr || peeksym () == geq ) { consumesym (); expression (); } else { error ( "condition: invalid operator" ); consumesym (); } }void statement () { if ( accept ( ident )) { expect ( becomes ); expression (); } else if ( accept ( callsym )) { expect ( ident ); } else if ( accept ( beginsym )) { do { statement (); } while ( accept ( semicolon )); expect ( endsym ); } else if ( accept ( ifsym )) { condition (); expect ( thensym ); statement (); } else if ( accept ( whilesym )) { condition (); expect ( dosym ); statement (); } else { error ( "statement: syntax error" ); consumesym (); } }void block () { if ( accept ( constsym )) { do { expect ( ident ); expect ( eql ); expect ( number ); } while ( accept ( comma )); expect ( semicolon ); } if ( accept ( varsym )) { do { expect ( ident ); } while ( accept ( comma )); expect ( semicolon ); } while ( accept ( procsym )) { expect ( ident ); expect ( semicolon ); block (); expect ( semicolon ); } statement (); }void program () { block (); expect ( period ); }

بعض مولدات محلل الانحدار المتكرر:

• TMG – مُجمِّع-مُجمِّع مبكر استُخدم في الستينيات وأوائل السبعينيات من القرن العشرين
• جافا سي سي
• كوكو/آر
• ANTLR
• إطار عمل Spirit Parser – إطار عمل لتوليد محلل نحوي تنازلي متكرر بلغة C++ لا يتطلب خطوة ما قبل التجميع
• parboiled (Java) – مكتبة تحليل PEG تنازلية متكررة للغة Java

تحتوي الواجهة الأمامية للغة C++ الخاصة بمترجم Clang على محلل مكتوب يدويًا يعتمد على خوارزمية التحليل التنازلي المتكرر. ^{[ 5 ]}

• مُركِّب المُحلِّل النحوي – دالة من الرتبة العليا تُستخدم في التحليل النحوي التوافقي، وهي طريقة لتحليل تصميمات المُحلِّل النحوي التنازلي المتكرر.
• قواعد تحليل التعبيرات – شكل آخر يمثل قواعد الانحدار التكراري
• محلل تصاعدي متكرر
• محلل التكرار الذيل – نوع من محلل الانحدار التكراري

• جاك دبليو. كرينشو: لنقم ببناء مترجم (1988-1995) ، بلغة باسكال ، مع مخرجات بلغة التجميع ، باستخدام نهج "البساطة".