حدوث التحول: متى تتوقف عن التخفيض؟

Question

أحاول أن أتعرف على تحليل التحلل. لنفترض أن لدينا القواعد النحوية التالية ، باستخدام القواعد العودية التي تنفذ ترتيب العمليات ، مستوحاة من ANSI C YACC GRAMMAR:

S: A;

P
    : NUMBER
    | '(' S ')'
    ;

M
    : P
    | M '*' P
    | M '/' P
    ;

A
    : M
    | A '+' M
    | A '-' M
    ;

ونريد تحليل 1+2 باستخدام تحليل التحول. أولاً ، يتم تحويل 1 كرقم. سؤالي هو ، هل تم تخفيضه بعد ذلك إلى P ، ثم M ، ثم A ، ثم أخيرًا؟ كيف تعرف من أين تتوقف؟

لنفترض أنه يقلل من الطريق إلى S ، ثم يتحول "+". سيكون لدينا الآن كومة تحتوي على:

S '+'

إذا تحولنا "2" ، فقد تكون التخفيضات:

S '+' NUMBER
S '+' P
S '+' M
S '+' A
S '+' S

الآن ، على جانبي الخط الأخير ، يمكن أن يكون S P أو M أو A أو Number ، وسيظل صالحًا بمعنى أن أي مزيج سيكون تمثيلًا صحيحًا للنص. كيف يعلم المحلل "أن يصنعه"

A '+' M

بحيث يمكن أن يقلل من التعبير كله إلى ، ثم s؟ وبعبارة أخرى ، كيف يعرف التوقف عن التخفيض قبل تحويل الرمز القادم؟ هل هذه صعوبة أساسية في جيل محلل LR؟

---

تعديل: إضافة إلى السؤال التالي.

افترض الآن أننا تحليلنا 1+2*3. بعض عمليات التحول/تقليل هي كما يلي:

Stack    | Input | Operation
---------+-------+----------------------------------------------
         | 1+2*3 | 
NUMBER   | +2*3  | Shift
A        | +2*3  | Reduce (looking ahead, we know to stop at A)
A+       | 2*3   | Shift
A+NUMBER | *3    | Shift (looking ahead, we know to stop at M)
A+M      | *3    | Reduce (looking ahead, we know to stop at M)

هل هذا صحيح (منحت ، لم يتم تحليلها بالكامل بعد)؟ علاوة على ذلك ، لا يبدو لنا رمز واحد أيضًا عدم التقليل A+M ل A, ، لأن القيام بذلك سيؤدي إلى خطأ في بناء الجملة لا مفر منه بعد القراءة *3 ?

Answer 1

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

خاصية مثيرة للاهتمام LR القواعد هي أنه بالنسبة لأي قواعد نحوية LR(k) ل k>1, ، من الممكن إنشاء LR(1) القواعد التي تعادل. ومع ذلك ، فإن الشيء نفسه لا يمتد على طول الطريق إلى LR(0) - هناك العديد من القواعد التي لا يمكن تحويلها إليها LR(0).

انظر هنا لمزيد من التفاصيل حول LR(k)-لن:

http://en.wikipedia.org/wiki/lr_parser

Answer 2

لست متأكدًا تمامًا من خوارزمية تحليل YACC / Bison ، وعندما تفضل التحول أكثر من الانتقال ، لكنني أعلم أن Bison يدعم تحليل LR (1) مما يعني أنه يحتوي على رمز Lookahead. هذا يعني أن الرموز لا تنتقل إلى المكدس على الفور. بدلاً من ذلك ينتظرون حتى لا يمكن أن تحدث تخفيضات مزيد من التخفيضات. ثم ، إذا كان تحويل الرمز المميز التالي أمرًا منطقيًا ، فهو ينطبق هذه العملية.

بادئ ذي بدء ، في حالتك ، إذا كنت تقوم بتقييم 1 + 2 ، فسوف يتحول 1. سيقلل الرمز المميز إلى A لأن الرمز المميز " +" يشير إلى أن المسار الوحيد الصحيح. نظرًا لعدم وجود تخفيضات أخرى ، فإنه سيحول الرمز المميز "+" على المكدس ويحمل 2 كـ Lookahead. سوف يتحول 2 ويقلل إلى M لأن A + M ينتج A A والتعبير اكتمل.