2

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

  • 文法があいまいな場合 (if-then-else のあいまいさなど)、言語を変更してあいまいさを修正します。
  • 演算子の優先順位の問題である場合は、優先順位を明示的に指定してください。
  • デフォルトの解像度を受け入れ、ジェネレーターに文句を言わないように伝えます。

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

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

%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]+" の形式のセミコロンで区切られた行を解析することです。

4

2 に答える 2

2

の Solaris バージョンを使用すると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;

shift/reduce の競合が解消されます。

于 2009-06-06T04:48:40.833 に答える
0

文法を削って投稿してくれてありがとう。後続ルールを - に変更

successor:      /* empty */ | LETTER successor;

...私のために働いた。ITYM言語は明確に見えました。

于 2009-06-06T04:03:40.640 に答える