تروي اليسار في قواعد النصر

Question

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

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

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

يحرر:
ولكن أعتقد أنه يجب علي أن أدرج مثالا خاصا على أي حال، لأن فهمي أقل قليلا من الكاملة :-) تغيير أمر فاصل القائمة "قائمة فاصل الأوامر" يحل الصراع.

State 9 conflicts: 3 shift/reduce


Grammar

    0 $accept: input $end

    1 input: error NEWLINE
    2      | input NEWLINE
    3      | input list NEWLINE
    4      | /* empty */

    5 list: command
    6     | command separator
    7     | list separator command

    8 separator: SEMI
    9          | L_OR
   10          | L_AND

   11 command: variable_assignment
   12        | external_w_redir
   13        | external_w_redir AMP
   14        | pipeline
   15        | pipeline AMP

...

state 9

    5 list: command .
    6     | command . separator

    SEMI   shift, and go to state 18
    L_AND  shift, and go to state 19
    L_OR   shift, and go to state 20

    SEMI      [reduce using rule 5 (list)]
    L_AND     [reduce using rule 5 (list)]
    L_OR      [reduce using rule 5 (list)]
    $default  reduce using rule 5 (list)

    separator  go to state 22

Answer 1

تعديل:

لا بد لي من التراجع عن إجابتي الأصلية. الخاص بك يسار القواعد العودية ليس يبدو أن غامضة، كما اعتقدت لأول مرة. أعتقد أنني كنت مرتبكا من قبل القاعدة الإضافية التي يتم استخدامها لإجراء فاصل أخير.

فيما يلي نسخة مبسطة من قواعد اللغة الأصلية المكررة الخاصة بك:

list: COMMAND
      | COMMAND SEPARATOR
      | COMMAND SEPARATOR list
      ;

هذه المباريات القواعد (إذا كنت غير مشوشة أكثر مما أعتقد، والتي تعتبر بالطبع إمكانية) المدخلات C و CS و CSC و CSCS و CSCSC و CSCSS، إلخ. وهذا هو، سلسلة من أوامر فصل الفاصل، مع فاصل اختياري في النهاية.

وهذا هو النسخة المبسطة من قواعد القواعد اليسرى العودية، والتي تعطي تحول / تقليل الصراع في بيسون:

list: COMMAND
      | COMMAND SEPARATOR
      | list SEPARATOR COMMAND
      ;

إذا قمت بتوسيع الأمور بشكل صحيح، فإن هذا القواعد يطابق المدخلات C، CS، CSC، CSCS، CSCSC، CSSCSC، وما إلى ذلك. إنه غير غامض، لكنه لا يعادل قواعد اللغة اليسرى العودية. لا يمكن أن تضاعفت قائمة الأوامر فاصل في النهاية، ويمكن مضاعفة الفواصل بين الأوامر.

أعتقد أن سبب التحول / الحد من الصراع هو أن البيسون يبدو رمز مميز واحد فقط عندما تقرر ما إذا كان التحول أو تقليل، ومع الفواصل المزدوجة التي يتم تقديمها في القواعد الثانية، يمكن أن تلتكون في بعض الأحيان.

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

list: separatedlist
      | separatedlist SEPARATOR
      ;

separatedlist: COMMAND
               | separatedlist SEPARATOR COMMAND
               ;

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

Answer 2

يبدو أن الارتباك / الأخطاء تأتي من الإنتاج في القائمة. إصدارك المكرر الخاص بك هو:

list: command
    | command separator
    | list separator command

إصدارك المكرر يمين هو:

list: command
    | command separator
    | command separator list

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

على افتراض ما تريده حقا هو نسخة متكررة من الأيسر، ما تريده هو

list_no_trailer: command
               | list_no_trailer separator command

list: list_no_trailer
    | list_no_trailer separator

يأتي الصراع في إصدارك من حقيقة أنه بعد تحليل الأمر "أمر" ورؤيته فاصل على مظهره، لا يعرف ذلك ما إذا كنت سنسحب ذلك كفاصل اختياري بعد الأمر، أو لتقليل الأمر ضمن الافتراض أن فاصل القائمة وسيكون هناك أمر آخر مباشرة بعد ذلك. سيحتاج إلى 2 حرفا من Lookahead لذلك، لذلك قواعد النحو الخاص بك هو LR (2)، ولكن ليس LR (1)