محلل تصاعدي متكرر

الموسوعة الحرة

في علوم الحاسوب ، يُعدّ تحليل الصعود التكراري أسلوبًا لتنفيذ محلل LR يستخدم دوالًا تكرارية متبادلة بدلًا من الجداول. وبالتالي، يُشفّر المحلل مباشرةً في لغة البرمجة المضيفة، على غرار تحليل الهبوط التكراري . عادةً ما ينتج عن التشفير المباشر محلل أسرع من نظيره القائم على الجداول [ 1 ]، وذلك للسبب نفسه الذي يجعل الترجمة أسرع من التفسير. كما يُمكن (نظريًا) تعديل محلل الصعود التكراري يدويًا، بينما يصعب على المستخدم العادي قراءة التنفيذ الجدولي.

وُصِفَ الصعود التكراري لأول مرة من قِبَل توماس بينيلو في مقالته " بينيلو، توماس ج. (1986). "تحليل LR سريع جدًا" . وقائع ندوة SIGPLAN لعام 1986 حول بناء المترجمات - SIGPLAN '86 . الصفحات 145-151 . doi : 10.1145/12276.13326 . ISBN  0897911970. S2CID 17214407 . في عام ١٩٨٦. لم يكن ينوي إنشاء تطبيق قابل للتعديل اليدوي لمحلل LR، بل محللًا قابلًا للصيانة وفعالًا مكتوبًا بلغة التجميع . وقد شرح جي إتش روبرتس [ ٢ ] هذه التقنية لاحقًا في عام ١٩٨٨، وكذلك في مقالٍ لليرماكرز وأوغستاين وكروسمان أريتز [ ٣ ] في عام ١٩٩٢ في مجلة علوم الحاسوب النظرية . وقدّم موريل وميدلتون [ ٤ ] وصفًا سلسًا للغاية لهذه التقنية في عام ٢٠٠٣. كما يمكن الاطلاع على شرحٍ وافٍ في مقالٍ لسبيربر وثيمان في مجلة TOPLAS [ ٥ ] .

تم دمج الصعود التكراري مع الهبوط التكراري، مما أدى إلى ظهور تقنية تُعرف باسم الصعود/الهبوط التكراري . تُعتبر هذه التقنية أسهل في التعديل اليدوي نظرًا لانخفاض عدد الحالات، ولأن بعض هذه الحالات أكثر سهولة في فهمها من الأعلى إلى الأسفل بدلًا من الأسفل إلى الأعلى. كما أنها تُحسّن الأداء بشكل طفيف مقارنةً بالصعود التكراري التقليدي. [ 6 ]

ملخص

بشكل بديهي، يُعدّ الصعود التكراري تطبيقًا حرفيًا لمفهوم تحليل LR . تمثل كل دالة في المحلل حالة واحدة من حالات أوتوماتون LR . داخل كل دالة، تُستخدم عبارة متعددة الفروع لاختيار الإجراء المناسب بناءً على الرمز المميز الحالي المقروء من دفق الإدخال. بمجرد تحديد الرمز المميز، يُتخذ الإجراء بناءً على الحالة التي يتم ترميزها. هناك إجراءان أساسيان مختلفان يمكن اتخاذهما بناءً على الرمز المميز المعني:

  • Shift - يتم ترميزها كاستدعاء دالة، مما يؤدي فعليًا إلى الانتقال إلى حالة آلية جديدة.
  • يُشفّر إجراء الاختزال بشكل مختلف وفقًا لروتين الإجراء الدلالي للإنتاج ذي الصلة . تُغلّف نتيجة هذا الروتين في نوع بيانات مجردة (ADT) تُعاد إلى المُستدعي. يجب على إجراء الاختزال أيضًا تسجيل عدد الرموز المميزة التي أُزيحت قبل الاختزال، وإعادة هذه القيمة إلى المُستدعي مع قيمة الاختزال. يُحدد عداد الإزاحة هذا النقطة في مكدس الاستدعاءات التي يجب معالجة الاختزال عندها.

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

مثال

ضع في اعتبارك القواعد النحوية التالية في صيغة بيسون :

expr : expr '+' term { $$ = $1 + $3; } | expr '-' term { $$ = $1 - $3; } | term { $$ = $1; } ؛ term : '(' expr ')' { $$ = $2; } | رقم { $$ = $1; } ؛ num : '0' { $$ = 0; } | '1' { $$ = 1; } ؛

هذه القواعد النحوية من نوع LR(0) لأنها تكرارية من اليسار (في الرمز غير الطرفي للتعبير ) ولكنها لا تتطلب أي استباق. كما أن الصعود التكراري قادر على التعامل مع القواعد النحوية من نوع LALR(1) بنفس الطريقة التي تتعامل بها المحللات النحوية المعتمدة على الجداول مع هذه الحالات (عن طريق الحساب المسبق لحلول التعارض بناءً على الاستباق المحتمل).

فيما يلي تطبيق بلغة سكالا لمحلل تصاعدي متكرر يعتمد على القواعد النحوية المذكورة أعلاه:

كائن ExprParser { نوع خاص Result = ( NonTerminal , Int ) سمة خاصة مغلقة NonTerminal { قيمة v : Int } فئة حالة خاصة NTexpr ( v : Int , in : Stream [ Char ]) تمتد من NonTerminal فئة حالة خاصة NTterm ( v : Int , in : Stream [ Char ]) تمتد من NonTerminal فئة حالة خاصة NTnum ( v : Int , in : Stream [ Char ]) تمتد من NonTerminal فئة ParseException ( msg : String ) تمتد من RuntimeException ( msg ) { دالة this () = this ( " " ) دالة this ( c : Char ) = this ( c.toString ) } دالة parse ( in : Stream [ Char ]) = state0 ( in ) ._ 1.v / *  * 0 $accept: . expr $end  *  * '(' إزاحة، والانتقال إلى الحالة 1  * '0' إزاحة، والانتقال إلى الحالة 2  * '1' إزاحة، والانتقال إلى الحالة 3  *  * expr الانتقال إلى الحالة 4  * term الانتقال إلى الحالة 5  * num الانتقال إلى الحالة 6  */ private def state0 ( in : Stream [ Char ]) = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto )= tuple إذا كان ( goto == 0 ) { loop ( res match { case NTexpr ( v , in ) => state4 ( in , v ) case NTterm ( v , in ) => state5 ( in , v ) case NTnum ( v , in ) => state6 ( in , v ) }) } else ( res , goto - 1 ) } loop ( cur match { case '(' => state1 ( tail ) case '0' => state2 ( tail ) case '1' => state3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /*  * 4 term: '(' . expr ')'  *  * '(' shift, and go to state 1  * '0' shift, and go to state 2  * '1' shift, and go to state 3  *  * expr go to state 7  * term go to state 5  * num go to state 6  */ private def state1 ( in : Stream [ Char ]): Result = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto ) = tuple if ( goto == 0 ) { loop ( res match { case NTexpr ( v ,في ) => الحالة 7 ( في ، v ) حالة NTterm ( v ، في ) => الحالة 5 ( في ، v ) حالة NTnum ( v ، في ) => الحالة 6 ( في ، v ) }) } else ( res ، goto - 1 ) } loop ( cur match { case '(' => الحالة 1 ( tail ) case '0' => الحالة 2 ( tail ) case '1' => الحالة 3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /*  * 6 num: '0' .  *  * $default reduce using rule 6 (num)  */ private def state2 ( in : Stream [ Char ]) = ( NTnum ( 0 , in ), 0 ) /*  * 7 num: '1' .  *  * $default reduce using rule 7 (num)  */ private def state3 ( in : Stream [ Char ]) = ( NTnum ( 1 ، في )، 0 ) /*  * 0 $accept: expr . $end  * 1 expr: expr . '+' term  * 2 | expr . '-' term  *  * $end shift، وانتقل إلى الحالة 8  * '+' shift، وانتقل إلى الحالة 9  * '-' shift، وانتقل إلى الحالة 10  */ private def state4 ( in : Stream [ Char ], arg1 : Int ): Result = in match { case cur#:: tail => { decrement ( cur match { case '+' => state9 ( tail , arg1 ) case '-' => state10 ( tail , arg1 ) case c => throw new ParseException ( c ) }) } case Stream () => state8 ( arg1 ) } /*  * 3 expr: term .  *  * $default reduce using rule 3 (expr)  */ private def state5 ( in : Stream [ Char ], arg1 : Int ) = ( NTexpr ( arg1 , in ), 0 ) /*  * 5 term: num .  *  * $default reduce using rule 5 (term)  */ private def state6 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 0 ) /*  * 1 expr: expr . '+' term  * 2 | expr . '-' الحد  * 4 الحد: '(' تعبير . ')'  *  * '+' إزاحة، ثم الانتقال إلى الحالة 9  * '-' إزاحة، ثم الانتقال إلى الحالة 10  * ')' إزاحة، ثم الانتقال إلى الحالة 11  */ private def state7 ( in : Stream [ Char ], arg1 : Int ): Result = in match { case cur #:: tail => { decrement ( cur match { case '+' => state9 ( tail , arg1 ) case '-' => state10 ( tail , arg1 ) case ')' => state11 ( tail ,arg1) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /*  * 0 $accept: expr $end .  *  * $default accept  */ private def state8 ( arg1 : Int ) = ( NTexpr ( arg1 , Stream ()), 1 ) /*  * 1 expr: expr '+' . term  *  * '(' shift, and go to state 1  * '0' shift, and go to state 2  * '1' shift, and go to state 3  *  * term go to state 12  * num go to state 6  */ private def state9 ( in : Stream [ Char ], arg1 : Int ) = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto ) = tuple if ( goto == 0 ) { loop ( res match { case NTterm ( v , in ) => state12 ( in , arg1 , v ) case NTnum ( v , in ) => state6 ( in , v ) case _ => throw new AssertionError }) } else ( res , goto - 1 ) } loop ( cur match { case '(' => state1 ( tail ) case '0' => state2 ( tail ) case '1' =>state3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /*  * 2 expr: expr '-' . term  *  * '(' shift, and go to state 1  * '0' shift, and go to state 2  * '1' shift, and go to state 3  *  * term go to state 13  * num go to state 6  */ private def state10 ( in : Stream [ Char ], arg1 : Int ) = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto ) = tuple if ( goto == 0 ) { loop ( res match { case NTterm ( v , in ) => state13 ( in , arg1 , v ) case NTnum ( v , in ) => state6 ( in , v ) case _ => throw new AssertionError }) } else ( res , goto - 1 ) } loop ( cur match { case '(' => state1 ( tail ) case '0' => state2 ( tail ) case '1' => state3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException} /*  * 4 term: '(' expr ')' .  *  * $default reduce using rule 4 (term)  */ private def state11 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 2 ) /*  * 1 expr: expr '+' term .  *  * $default reduce using rule 1 (expr)  */ private def state12 ( in : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 + arg2 , in ), 2 ) /*  * 2 expr: expr '-' term .  *  * $default reduce using rule 2 (expr)  */ private def state13 ( in : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 - arg2 , in ), 2 ) private def decrement ( tuple : Result ) = { val ( res , goto ) = tuple assert ( goto != 0 ) ( res , goto - 1 ) } }

فيما يلي تطبيق بلغة برولوج لمحلل تصاعدي متكرر يعتمد على القواعد النحوية المذكورة أعلاه:

الحالة ( S )، [ S ] --> [ S ]. الحالة ( S0 ، S )، [ S ] --> [ S0 ]./*  0. S --> E$  1. E --> E + T  2. E --> E - T  3. E --> T  4. T --> (E)  5. T --> N  6. N --> 0  7. N --> 1 */ accept --> state ( s ([], [ e ( _ )])). r ( 1 ) --> state ( s ( Ts , [ t ( A1 ), '+' , e ( A0 )| Ss ]), s ( Ts , [ e ( A0 + A1 )| Ss ])). r ( 2 ) --> state ( s ( Ts , [ t ( A1 ), '-' , e ( A0 )| Ss ]), s ( Ts , [ e ( A0 - A1 )| Ss ])). r ( 3 ) --> state ( s ( Ts , [ t ( A )| Ss ]), s ( Ts , [ e ( A )| Ss ])). r ( 4 ) --> state ( s ( Ts , [ ')' , e ( A ), '(' | Ss ]), s ( Ts , [ t ( A )| Ss ])). r ( 5 ) --> state ( s ( Ts , [ n ( A )| Ss ]), s ( Ts , [ t ( A )| Ss ])). r ( 6 ) --> state ( s ( Ts)، [ '0' | Ss ]), s ( Ts , [ n ( 0 )| Ss ])). r ( 7 ) --> state ( s ( Ts , [ '1' | Ss ]), s ( Ts , [ n ( 1 )| Ss ])). t ( T ) --> state ( s ([ T | Ts ], Ss ), s ( Ts , [ T | Ss ]))./*  S --> .E$  E --> .E + T  E --> .E - T  E --> .T  T --> .(E)  T --> .N  N --> .0  N --> .1 */ s0 --> t ( '(' ), s3 , s2 , s1 . s0 --> t ( '0' ), s11 , s10 , s2 , s1 . s0 --> t ( '1' ), s12 , s10 , s2 , s1 ./*  S --> E.$  E --> E. + T  E --> E. - T */ s1 --> accept . s1 --> t ( '+' ), s7 , s1 . s1 --> t ( '-' ), s8 , s1 ./*  E --> T. */ s2 --> r ( 3 )./*  T --> (.E)  E --> .E + T  E --> .E - T  E --> .T  T --> .(E)  T --> .N  N --> .0  N --> .1 */ s3 --> t ( '(' ), s3 , s2 , s4 . s3 --> t ( '0' ), s11 , s10 , s2 , s4 . s3 --> t ( '1' ), s12 , s10 , s2 , s4 ./*  T --> (E.)  E --> E .+ T  E --> E .- T */ s4 --> t ( ')' ), s9 . s4 --> t ( '+' ), s7 , s4 . s4 --> t ( '-' ), s8 , s4 ./*  E --> E + T. */ s5 --> r ( 1 )./*  E --> E - T. */ s6 --> r ( 2 )./*  E --> E + .T  T --> .(E)  T --> .N  N --> .0  N --> .1 */ s7 --> t ( '(' ), s3 , s5 . s7 --> t ( '0' ), s11 , s10 , s5 . s7 --> t ( '1' ), s12 , s10 , s5 ./*  E --> E - .T  T --> .(E)  T --> .N  N --> .0  N --> .1 */ s8 --> t ( '(' ), s3 , s6 . s8 --> t ( '0' ), s11 , s10 , s6 . s8 --> t ( '1' ), s12 , s10 , s6 ./*  ت --> (ه). */ s9 --> r ( 4 )./*  T --> N. */ s10 --> r ( 5 )./*  ن --> '0'. */ s11 --> ص ( 6 )./*  N --> '1'. */ s12 --> r ( 7 ).parser ( Cs , T ) :- length ( Cs , _ ), phrase ( s0 , [ s ( Cs , [])], [ s ([], [ e ( T )])]).% state(S0, S), [S] --> [S0, S]. %?- S0 = [s("(1+1)", [])|_], phrase(s0, S0, [S]), maplist(portray_clause, S0).

انظر أيضاً

مراجع

  1. ↑ توماس ج. بينيلو (1986). "تحليل LR سريع للغاية" . إشعارات ACM SIGPLAN . 21 (7): 145-151 . doi : 10.1145/13310.13326 .
  2. ↑ جي إتش روبرتس (1988). "الصعود المتكرر: نظير LR للهبوط المتكرر" . إشعارات ACM SIGPLAN . 23 (8): 23-29 . doi : 10.1145/47907.47909 . S2CID 12740771 . 
  3. ^ ليرماكرز، أوغستين، كروسمان أريتز (1992). "محلل LR وظيفي" . علوم الكمبيوتر النظرية . 104 (2): 313-323 . دوى : 10.1016 / 0304-3975 (92)90128-3 .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  4. ↑ لاري موريل وديفيد ميدلتون (2003). "تحليل التصاعد التكراري" . مجلة علوم الحاسوب في الكليات . المجلد 18، العدد 6. الصفحات 186-201 .   
  5. ↑ سبيربر وثيمان (2000). "توليد محللات LR عن طريق التقييم الجزئي" . معاملات ACM في لغات البرمجة والأنظمة . 22 (2): 224-264 . doi : 10.1145/349214.349219 . S2CID 14955687 . 
  6. ↑ جون بويلاند ودانيال سبيواك (2009). "مولد محلل ScalaBison التكراري للصعود والهبوط" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 18 يوليو 2009.