كيفية حل النزاع للحد من التحول في قواعد القواعد غير المبنية

Question

أحاول تحليل قواعد نحوية بسيطة باستخدام مولد محلل (1) Lalr (1) (Bison، ولكن المشكلة ليست خاصة بهذه الأداة)، وأضرب النزاع في التحول. تميل المستندات والمصادر الأخرى التي وجدتها حول تحديد هذه إلى القول واحد أو أكثر مما يلي:

• إذا كان القواعد النحوية غامضة (على سبيل المثال الغموض إذا كان - إذن آخر)، فقم بتغيير اللغة لإصلاح الغموض.
• إذا كانت مشكلة الأسبقية المشغل، فحدد الأسبقية بشكل صريح.
• قبول الدقة الافتراضية وأخبر المولد عدم التشكيك في ذلك.

ومع ذلك، يبدو أن أي من هذه لا ينطبق على وضعي: القواعد النحوية لا لبس فيه بقدر ما أستطيع أن أقول (على الرغم من أنها غير غامضة بحرف واحد فقط من Lookahead)، فإنه يحتوي على مشغل واحد فقط، والتحليل الافتراضي يؤدي إلى تحليل الأخطاء على المدخلات المشكلة بشكل صحيح. هل هناك أي تقنيات لإعادة صياغة تعريف قواعد القواعد لإزالة النزاعات في التحول التي لا تقع في الدلاء أعلاه؟

للحصول على concreteness، إليك القواعد المعنية:

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

النية هي تحليل الأسطر المنفصلة من النموذج الفاصلة من النموذج [A-ZA-Z] +" أو [A-ZA-Z] -> [A-ZA-Z] +".

Answer 1

باستخدام نسخة سولاريس من yacc, ، انا حصلت:

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

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

successor: LETTER | successor LETTER;

يتم القضاء على تحول / تقليل الصراع.

Answer 2

شكرا على تباين القواعد ونشرها. تغيير حكم الخلف -

successor:      /* empty */ | LETTER successor;

... عملت بالنسبة لي. إيتي لغة بدا لا لبس فيه.