'(' ではなく ')' でシフト リデュース/競合が発生するのはなぜですか?

Question

次のような構文があります

%(var)

そして

%var

そして（var）

私のルールは次のようなものです

optExpr:
    | '%''('CommaLoop')'
    | '%' CommaLoop

CommaLoop:
    val | CommaLoop',' val

Expr:
    MoreRules
    | '(' val ')'

問題は、) が次のものに属しているかどうかを判断できないようです。 %(CommaLoop) または % (val) しかし、( ではなく ) について文句を言います。一体何？文句を言うべきではないか (?そしてエラーを修正するにはどうすればよいですか?作ると思う %( トークンは良い解決策ですが、その理由を確認したいです $( これを実行する前はエラーではありません。

Answer 1

これは、LR 解析の仕組みによるものです。LR 解析は事実上ボトムアップであり、文法規則の RHS に従ってトークンをグループ化し、それらを LHS に置き換えます。パーサーが「シフト」すると、スタックにトークンが置かれますが、実際にはまだルールに一致していません。代わりに、部分的に一致したルールを現在の状態を通じて追跡します。ルールの終わりに対応する状態になると、RHS のシンボルをスタックからポップし、LHS を示す 1 つのシンボルをプッシュバックして縮小することができます。したがって、競合がある場合、パーサーがルールの最後に到達し、削減するかどうか (または何を削減するか) を決定できないまで、競合は表示されません。

あなたの例では、見た後、 % ( ヴァル, 、それがスタック上にあるものになります (ここでは一番上が右側です)。先読みの場合 ), 、ルールを介して val をポップして減らすべきかどうかを決定できません コンマループ:ヴァル, 、またはそれをシフトする必要があるかどうか ) したがって、3 つのものをポップし、ルールに従って減らすことができます 説明:'(' val ')'

ここでは、次のような追加のルールがあると仮定します。 コンマループ:エクスプレッション, そうでない場合、文法は実際には何も一致せず、bison/yacc は未使用の非端末について文句を言います。

Answer 2

今、あなたの説明とあなたの文法が一致していないようです。あなたの説明では、「VAR」を持つとすべての3つのフレーズを示すが、1なしでは唯一のシングル「val」を可能にしながら、あなたの文法は、カンマ区切りのリストを可能として「％」で始まるものを示しています。

現時点では、私はすべての3つのカンマ区切りリストを可能にしなければならないと仮定します。この場合、私はより多くのこのような文法を考慮すると思います：

optExpr: '%' aList

aList: CommaLoop
    | parenList

parenList: '(' CommaLoop ')'

CommaLoop: 
    | val 
    | CommaLoop ',' val

Expr: MoreRules
    | parenList

私はそうoptExprとのExprを変更しませんしましたどちらも空のシーケンスを一致させることができます - 私の推測では、あなたはおそらくで開始することを意図していなかったです。私はbyaccにを通してそれを実行するのに十分な、これを肉付けしました。それは何の警告やエラーを発生しない。