https://stackoverflow.com/questions/196179
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は、曖昧さがないとわかっている文法のshift / reduce confictを理解するのに問題があります。ケースはif elseタイプの1つですが、コードブロックを区切る必須のEND句があるため、「dangling else」問題ではありません。
gppgの文法は次のとおりです（コンパイラコンパイラのようなBisonです...それはエコーではありませんでした）：
%output=program.cs
%start program
%token FOR
%token END
%token THINGS
%token WHILE
%token SET
%token IF
%token ELSEIF
%token ELSE
%%
program : statements
;
statements : /*empty */
| statements stmt
;
stmt : flow
| THINGS
;
flow : '#' IF '(' ')' statements else
;
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
競合の出力は次のとおりです。
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 10: else -> elseifs
Shift "'#'": State-22 -> State-23
Items for From-state State 22
10 else: elseifs .
-lookahead: '#', THINGS, EOF
11 elseifs: elseifs . '#' ELSEIF statements else
Items for Next-state State 23
11 elseifs: elseifs '#' . ELSEIF statements else
// End conflict information for parser
すでにすべてを切り替えており、それを解決する方法を知っていますが、その解決策は、右の再帰のために「elseif」で左の再帰を放棄することを伴います。
この問題に関してインターネット上で見つけた貴重なドキュメントをすべて調べましたが（最後にいくつかのリンクを投稿しました）、まだエレガントな解決策を見つけていません。私はANTLRについて知っていますが、今は考えたくありません。ソリューションをYacc / Bisonパーサーに制限してください。
エレガントなソリューションに感謝します./* empty * /ルールを削除し、空のリストを必要とするすべてのものを複製することでそれを行うことができましたが、作業中のより大きな文法では、「sparghetti grammar syndrome」のようになります。
リンクは次のとおりです。
http://nitsan.org/~maratb/cs164/bison.html
解決
修正したELSEIFルールには条件のマーカーがありません。名目上は '（'と '）'が追加されているはずです。
もっと真剣に、あなたは今のルールを持っています
elsebody : else
| elseifs else
;
and
elseifs : /* Nothing */
| elseifs ...something...
;
「何も」は必要ありません。 「elseifs」なしで「elsebody」によって暗黙のうちに処理されます。
ルール 'opt_elseifs'、 'opt_else'、および 'end'を使用する傾向があります。
flow : '#' IF '(' ')' statements opt_elseifs opt_else end
;
opt_elseifs : /* Nothing */
| opt_elseifs '#' ELSIF '(' ')' statements
;
opt_else : /* Nothing */
| '#' ELSE statements
;
end : '#' END
;
これをパーサージェネレーターで実行したことはありませんが、これは比較的簡単に理解できます。
他のヒント
問題はelseifs句にあると思います。
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
else節はとにかくelseifsを参照するため、最初のバージョンは必要ないと思います：
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
elseifsを変更するとどうなりますか？：
elseifs : '#' ELSEIF statements else
;
上記のJonathanからの答えは最高のように見えますが、それが機能しないので、エラーのデバッグに役立ついくつかの提案があります。
まず、ハッシュ/シャープ記号をトークン自体の一部にすることを検討しましたか（つまり＃END、＃IFなど）？そのため、それらはレクサーに取り出されます。つまり、パーサーに含める必要はありません。
第二に、トークンストリームを複製せずにルールを書き換えることをお勧めします。 （自分自身を繰り返さないという原則の一部。）したがって、ルール＆quot; '＃' ELSEIFステートメントelse＆quot;そのファイル内の1つの場所にのみ存在する必要があります（上記の2つではありません）。
最後に、IF / ELSEIF / ELSEトークンの優先順位と結合性を検討することをお勧めします。これを必要としないパーサーを作成できるはずですが、この場合は必要になるかもしれません。
まだ前後を切り替えていますが、 elseifs シーケンスの最後に else が常に間違っていたため、元の質問にはいくつかのエラーがありました。質問の別のテイクがありますが、今回は2つのshift / reduce競合が発生します：
flow : '#' IF '(' ')' statements elsebody
;
elsebody : else
| elseifs else
;
else : '#' ELSE statements '#' END
| '#' END
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
現在の競合は次のとおりです。
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 12: elseifs -> /* empty */
Shift "'#'": State-10 -> State-13
Items for From-state State 10
7 flow: '#' IF '(' ')' statements . elsebody
4 statements: statements . stmt
Items for Next-state State 13
10 else: '#' . ELSE statements '#' END
11 else: '#' . END
7 flow: '#' . IF '(' ')' statements elsebody
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements
Shift "'#'": State-24 -> State-6
Items for From-state State 24
13 elseifs: elseifs '#' ELSEIF statements .
-lookahead: '#'
4 statements: statements . stmt
Items for Next-state State 6
7 flow: '#' . IF '(' ')' statements elsebody
// End conflict information for parser
空のルールはただのgppgを悪化させます。しかし、それらは使用するのがとても自然なようです。私はそれらを試し続けます。
1800情報が述べたように、正しい再帰が問題を解決することは既に知っています。しかし、私は elseifs句に左再帰を使用した解決策を探しています。
elsebody : elseifs else
| elseifs
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
else : '#' ELSE statements '#' END
;
これは再帰を残し、常に終了する必要があると思います。
OK-ifブロックの文法（最小ではない）です。私が持っているいくつかのコード（Kernighan＆amp; Plaugerの「The UNIX Programming Environment」のhocに基づいてアドホックと呼ばれる）から掘り下げました。このアウトライン文法は、競合することなくYaccでコンパイルされます。
%token NUMBER IF ELSE
%token ELIF END
%token THEN
%start program
%%
program
: stmtlist
;
stmtlist
: /* Nothing */
| stmtlist stmt
;
stmt
: ifstmt
;
ifstmt
: ifcond endif
| ifcond else begin
| ifcond eliflist begin
;
ifcond
: ifstart cond then stmtlist
;
ifstart
: IF
;
cond
: '(' expr ')'
;
then
: /* Nothing */
| THEN
;
endif
: END IF begin
;
else
: ELSE stmtlist END IF
;
eliflist
: elifblock
| elifcond eliflist begin /* RIGHT RECURSION */
;
elifblock
: elifcond else begin
| elifcond endif
;
elifcond
: elif cond then stmtlist end
;
elif
: ELIF
;
begin
: /* Nothing */
;
end
: /* Nothing */
;
expr
: NUMBER
;
%%
THINGSの代わりにダミー要素として「NUMBER」を使用し、ELSEIFの代わりにELIFを使用しました。 THENが含まれていますが、それはオプションです。 「開始」および「終了」操作は、生成されたプログラムのプログラムカウンターを取得するために使用されました。したがって、これに影響を与えることなく、これから削除する必要があります。
通常の左再帰の代わりに右再帰を使用する必要があると思った理由がありましたが、それは他の何よりも、私が使用していたコード生成戦略に関係していると思います。コメント内の疑問符はオリジナルにありました。私はそれに満足していないことを覚えています。このプログラムは全体として機能します-これは過去10年ほどバックバーナーにあるプロジェクトです（うーん... 2004年の終わりから2005年の初めに仕事をしました;それ以前は1992年でしたおよび1993）。
これがなぜコンフリクトフリーでコンパイルされるのか、以前に概説したものがコンパイルしないのかを解明するのに時間を費やしていません。役に立てば幸いです。
