if-then-elseでshiftを減らすために文法を改訂する

Question

与えられた文法のためにbisonのshift-reduce競合を取り除くにはどうすればよいですか？

selection-stmt -> if (expression) statement | 
         if (expression) statement else statement 

修正された文法を与える解決策が高く評価されます。

Answer 1

はるかに簡単な解決法があります。あなたはLRパーサがどのように機能するかを知っている場合は、競合がここで起こることを知っている：

if (expression) statement * else statement 

スターは、カーソルの現在位置をマークし

。パーザが答えなければならない質問は、 "私は変わるべきか、減らすべきか"です。通常、elseを最も近いifにバインドします。つまり、今すぐelseトークンを移動する必要があります。今すぐ減らすことは、elseが "古い" ifにバインドされるのを待つことを意味します。

パーサージェネレータに "トークン"else"とルール" stm - > if（exp）stm "の間にシフト/リダクションの競合がある場合、トークンが勝つ必要があります。そうするには、ルールの優先順位に「名前を付ける」（例："then"）。"then"は"else"より優先度が低いと指定します。次のようなものがあります。

// Precedences go increasing, so "then" < "else". 
%nonassoc "then" 
%nonassoc "else" 
%% 
stm: "if" "(" exp ")" stm   %prec "then" 
    | "if" "(" exp ")" stm "else" stm 

Bison構文を使用します。

実際、私の好きな答えは、"then"と"else"に同じ優先順位を付けることさえあります。優先順位が等しい場合、シフトしたいトークンと縮小したいルールとの間の繋がりを壊すために、Bison/Yaccは結合性を調べます。ここでは、そう、（より正確には、あなたが「シフト」を推進したい）いわば、右結合性を促進したい：

%right "then" "else" // Same precedence, but "shift" wins. 

は十分です。今後の個人のための

statements: 
    statements lineEnd statement 
| statements lineEnd IfStat 
| statements lineEnd IfElseStat 
| IfStat 
| IfElseStat 
; 
IfStat: 
    if (statement) 
; 
IfElse: 
    IfStat else statement 
; 

Answer 2

あなたがいる場合ダングリングのif-else場合によっては（またはで終わる）することができないでいる途中statement事実を認識する必要がある（ANがない場合は、他と。）それを行うための最も簡単な方法は、stmtルールを分割することです二つに：

stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if 
stmt-not-ending-with-dangling-if -> 
    if (expression) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if | 
    ...other statements not ending with dangling if... 
stmt-ending-with-dangling-if -> 
    if (expression) stmt | 
    if (expression) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if | 
    ...other statements ending with dangling if... 

whateverがstmtで終わっていないその他のstmt -> whateverルールは、2つのバージョンがstmt GET分割で終了しないすべてのstmtルールながら、stmt-not-ending-with-ifルールに進み、 ルールのnot-ending-with-ifバージョンとdangling-ifルールのdangling-ifバージョンです。

編集

他の作品とのより完全な文法：WHILE (expr) stmtよう

stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if 
stmt-not-ending-with-dangling-if : 
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if | 
    WHILE '(' expr ')' stmt-not-ending-with-dangling-if | 
    DO stmt WHILE '(' expr ')' ';' | 
    expr ';' | 
    '{' stmt-list '}' 
stmt-ending-with-dangling-if: 
    IF '(' expr ')' stmt | 
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if | 
    WHILE '(' expr ')' stmt-ending-with-dangling-if 

ルール（彼らはstmtで終わるような）二つに分割し得る、expr;ようなルールがない間はありません。

Answer 3

は次のように、通常の文よりもあれば、他のより高いレベルにします。 html）は、同様の問題で私を助けました。また、スイッチ `--debug`と` --verbose`をbisonに渡して、生成されたファイルを見てください。すべての情報が標準出力に印刷されるわけではありません。