22

指定された文法のバイソンのshift-reduce競合を削除するにはどうすればよいですか？

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

修正された文法を与える解決策をいただければ幸いです。

4

3 に答える 3

44

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

if ( expression ) statement * else statement

ここで、星はカーソルの現在の位置を示します。パーサーが答えなければならない質問は、「シフトすべきか、それとも削減すべきか」です。通常、をelse最も近いにバインドする必要があります。つまり、トークンを今すぐifシフトする必要があります。ここで減らすということは、が「古い」にバインドされるelseのを待つことを意味します。elseif

"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構文を使用します。

私は%nonassocここで不安を感じています。なぜなら、それは実際"then"に"else"は非連想的であり、ほとんどの文法に当てはまりますが、私はそれらに連想性ではなく優先順位を与えることだけを意図していたからです。バイソンは%precedenceこの目的のために提供します：

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

実際、私のお気に入りの答えは、同じ優先順位を与えること"then"です"else"。優先順位が等しい場合、シフトしたいトークンと削減したいルールの間の結びつきを断ち切るために、Bison/Yaccは結合性を調べます。ここでは、いわば右結合性を促進したい（より正確には、「シフト」を促進したい）ので、次のようになります。

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

十分であろう。

于 2012-10-04T19:29:58.210 に答える
7

statementif-elseの場合の真ん中は、ぶら下がっているif（ifが他にない場合）になることはできない（または終わる）ことができないという事実を認識する必要があります。これを行う最も簡単な方法は、stmtルールを2つに分割することです。

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...

で終わらない他のstmt -> whateverルールはルールに含まれますが、終わらないルールは2つのバージョンに分割されます。ルール内のバージョンとルール内のバージョン。whateverstmtstmt-not-ending-with-ifstmtstmtnot-ending-with-ifnot-ending-with-ifdangling-ifdangling-if

編集

他のプロダクションとのより完全な文法：

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

のようなルールはWHILE (expr) stmt（で終わるので）2つに分割されますがstmt、のようなルールはexpr;そうではありません。

于 2012-10-04T17:17:57.903 に答える
-1

次のように、他の場合は通常のステートメントよりも高いレベルを作成します。

statements:
  statements lineEnd statement
| statements lineEnd IfStat
| statements lineEnd IfElseStat
| IfStat
| IfElseStat
;
IfStat:
  if ( statement )
;
IfElse:
  IfStat else statement
;
于 2016-03-25T09:19:44.543 に答える