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

تتضمن هذه المقالة قائمة بالمراجع العامة ، لكنها تفتقر إلى الاستشهادات المضمنة الكافية . يُرجى المساعدة في تحسين هذه المقالة من خلال تقديم استشهادات أكثر دقة. ( فبراير 2009 ) ( تعرف على كيفية ومتى يمكنك إزالة هذه الرسالة )

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

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

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

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

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

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

 البرنامج =  كتلة "."  .
 
 كتلة = 
     [ "ثابت"  ident "="  رقم { "،"  ident "="  رقم }  ";" ] 
     [ "var"  ident { "،"  ident }  ";" ] 
     { "procedure"  ident ";"  كتلة ";" }  بيان .
 
 بيان = 
     ident ":="  تعبير 
     |  "call"  ident 
     |  "begin"  بيان { ";"  بيان }  "end" 
     |  "if"  شرط "then"  بيان 
     |  "while"  شرط "do"  بيان .
 
 الشرط = 
     "فردي"  تعبير 
     |  تعبير ( "=" | "#" | "<" | "<=" | ">" | ">=" )  تعبير .
 
 التعبير =  [ "+" | "-" ]  المصطلح {( "+" | "-" )  المصطلح }  .
 
 المصطلح =  العامل {( "*" | "/" )  العامل }  .
 
 العامل = 
     هوية 
     |  رقم 
     |  "("  التعبير ")"  .

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

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

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

تم حذف تنفيذات الوظائف nextsym و error من أجل البساطة.

typedef enum { ident ، number ، lparen ، rparen ، times ، slash ، plus ، minus ، eql ، neq ، lss ، leq ، gtr ، geq ، callsym ، beginsym ، semicolon ، endsym ، ifsym ، whilesym ، becomes ، thensym ، dosym ، constsym ، comma ، varsym ، procsym ، period ، oddsym } الرمز ؛        
             
           
        

الرمز sym ؛ void nextsym ( void )؛ void error ( const char msg []); 
 
   

int قبول ( الرمز s ) { إذا ( sym == s ) { nextsym (); إرجاع 1 ؛ } إرجاع 0 ؛ }   
        
        
         
    
     


int expect ( الرمز s ) { إذا ( قبول ( s )) ارجع 1 ؛ خطأ ( "توقع: رمز غير متوقع" )؛ ارجع 0 ؛ }   
     
         
    
     


عامل الفراغ ( void ) { if ( قبول ( ident )) { ; } else if ( قبول ( number )) { ; } else if ( قبول ( lparen )) { expression (); expect ( rparen ); } else { error ( "factor: syntax error" ); nextsym (); } }  
      
        
        
        
        
        
        
      
        
        
    


مصطلح فارغ ( void ) { عامل (); بينما ( sym == times || sym == slash ) { nextsym (); عامل (); } }  
    
            
        
        
    


تعبير فارغ ( void ) { if ( sym == plus || sym == minus ) nextsym (); term (); while ( sym == plus || sym == minus ) { nextsym (); term (); } }  
           
        
    
            
        
        
    


شرط فارغ ( void ) { if ( accept ( oddsym )) { expression (); } else { expression (); if ( sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq ) { nextsym (); expression (); } else { error ( "شرط: عامل غير صالح" ); nextsym (); } } }  
      
        
      
        
                                
            
            
          
            
            
        
    


عبارة فارغة ( void ) { if ( accept ( ident )) { expect ( becomes ); expression (); } else if ( accept ( callsym )) { expect ( ident ); } else if ( accept ( beginsym )) { do { statement (); } while ( accept ( فاصلة منقوطة )); expect ( endsym ); } else if ( accept ( ifsym )) { condition (); expect ( thensym ); statement (); } else if ( accept ( whilesym )) { condition (); expect ( dosym ); statement (); } else { error ( "statement: syntax error" ); nextsym (); } }  
      
        
        
        
        
        
         
            
          
        
        
        
        
        
        
        
        
        
      
        
        
    


كتلة فارغة ( void ) { if ( accept ( constsym )) { do { expect ( ident ); expect ( eql ); expect ( number ); } while ( accept ( comma )); expect ( فاصلة منقوطة ); } if ( accept ( varsym )) { do { expect ( ident ); } while ( accept ( comma )); expect ( فاصلة منقوطة ); } while ( accept ( procsym )) { expect ( ident ); expect ( فاصلة منقوطة ); block (); expect ( فاصلة منقوطة ); } statement (); }  
      
         
            
            
            
          
        
    
      
         
            
          
        
    
      
        
        
        
        
    
    


برنامج فارغ ( void ) { nextsym (); block (); expect ( period ); }  
    
    
    

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

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

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

• المترجمون: المبادئ والتقنيات والأدوات ، الطبعة الأولى، ألفريد في آهو، ورافي سيثي، وجيفري دي أولمان، وخاصة القسم 4.4.
• تنفيذ المترجم الحديث في جافا، الطبعة الثانية ، أندرو آبل، 2002، ISBN 0-521-82060-X . 
• تقنيات البرمجة التكرارية ، دبليو إتش بيرج، 1975، ISBN 0-201-14450-6 
• صياغة المترجم باستخدام لغة C ، تشارلز ن. فيشر وريتشارد ج. لوبلانك الابن، 1991، ISBN 0-8053-2166-7 . 
• التجميع باستخدام C# وJava ، بات تيري، 2005، ISBN 0-321-26360-X ، 624 
• الخوارزميات + هياكل البيانات = البرامج ، نيكلاوس ويرث، 1975، ISBN 0-13-022418-9 
• بناء المترجم ، نيكلاوس ويرث، 1996، ISBN 0-201-40353-6 

• جاك دبليو كرينشو: دعونا نبني مُجمِّعًا (1988-1995)، بلغة باسكال ، مع إخراج لغة التجميع ، باستخدام نهج "الحفاظ على البساطة"

Original text

Rate this translation

Your feedback will be used to help improve Google Translate