明確な文法でのshift-reduce競合を解決する方法

Question

LALR(1) パーサー ジェネレーター (Bison ですが、問題はそのツールに固有のものではありません) を使用して単純な文法を解析しようとしているのですが、shift-reduce の競合が発生しています。これらの修正に関して私が見つけたドキュメントやその他のソースには、次の 1 つ以上のことが記載されている傾向があります。

• 文法があいまいな場合（例：if-then-else のあいまいさ)、言語を変更してあいまいさを修正します。
• 演算子の優先順位の問題の場合は、優先順位を明示的に指定します。
• デフォルトの解決策を受け入れ、ジェネレーターにそれについて文句を言わないように指示します。

ただし、これらのどれも私の状況には当てはまらないようです。私の知る限り、文法は明確であり (もちろん、先読み文字が 1 文字だけなので曖昧ですが)、演算子は 1 つだけで、デフォルトの解決策では、正しく形成された入力で解析エラーが発生します。上記のバケットに当てはまらないシフトとリデュースの競合を削除するために文法の定義を再加工するためのテクニックはありますか?

具体的に言うと、問題の文法は次のとおりです。

%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のSolarisバージョンを使用して、私が入手ます：

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;

...私のために働きました。 ITYM の言語の明確な見えます。