10

あいまいさがないとわかっている文法の shift/reduce 競合を理解するのに問題があります。ケースはif elseタイプの1つですが、コードブロックを区切る必須のEND句があるため、「ぶら下がっている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 */ ルールを削除し、空のリストを必要とするすべてのものを複製することでなんとかそれを実現できましたが、私が取り組んでいるより大きな文法では、「スパルゲッティ文法症候群」のようになってしまいます。

ここにいくつかのリンクがあります：

http://nitsan.org/~maratb/cs164/bison.html

http://compilers.iecc.com/comparch/article/98-01-079

GPPG、私が使用しているパーサー

バイソンマニュアル

4

6 に答える 6

6

改訂された ELSEIF ルールには、条件のマーカーがありません。名目上は「(」と「)」を追加する必要があります。

もっと真剣に、あなたは今ルールを持っています

elsebody : else
         | elseifs else
         ;

と

elseifs : /* Nothing */
        | elseifs ...something... 
        ;

「何も」は必要ありません。「elseif」なしで「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
    ;

これをパーサージェネレーターで実行したことはありませんが、これは比較的理解しやすいと思います。

于 2008-10-12T23:39:21.253 に答える
2

問題はelseifs節にあると思います。

elseifs : elseifs '#' ELSEIF statements else
        | '#' ELSEIF statements else
        ;

とにかくelse句はelseifを参照するので、最初のバージョンは必要ないと思います：

else : '#' END
     | '#' ELSE statements '#' END
     | elseifs
     ;

elseifs を変更するとどうなりますか?:

elseifs : '#' ELSEIF statements else
        ;
于 2008-10-12T22:10:20.403 に答える
1

上記のジョナサンからの回答が最善のようですが、うまくいかないため、エラーのデバッグに役立ついくつかの提案があります。

まず、ハッシュ/シャープ記号をトークン自体の一部にすることを検討しましたか (つまり、#END、#IF など)? つまり、パーサーに含める必要はありません。

次に、トークン ストリームを複製せずにルールを書き直すことをお勧めします。(Don't Repeat Yourself 原則の一部です。) したがって、ルール " '#' ELSEIF statement else " は、そのファイルの 1 か所にのみ存在する必要があります (上記のように 2 か所ではありません)。

最後に、IF/ELSEIF/ELSE トークンの優先順位と結合性を調べることをお勧めします。これを必要としないパーサーを作成できるはずですが、この場合はそれが必要になる可能性があります。

于 2008-10-13T00:40:04.190 に答える
0

OK-これがifブロックの文法（最小ではない）です。私が持っているいくつかのコードからそれを掘り出しました（Kernighan＆Plaugerの「UNIXプログラミング環境」からのホックに基づいてアドホックと呼ばれます）。このアウトライン文法は、競合なしで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が含まれていますが、これはオプションです。'begin'および'end'操作は、生成されたプログラムのプログラムカウンターを取得するために使用されたため、影響を与えることなく、これから削除できる必要があります。

通常の左再帰の代わりに右再帰を使用する必要があると思った理由がありましたが、それは私が使用していたコード生成戦略に関係していると思います。コメントの疑問符はオリジナルにありました。満足していなかったのを覚えています。プログラムは全体として機能します-それは過去10年ほどの間バックバーナーになっているプロジェクトです（うーん...私は2004年の終わりと2005年の初めにいくつかの仕事をしました;それ以前は1992年でしたおよび1993）。

なぜこれが競合なしでコンパイルされるのか、そして前に概説したものがそうではないのかを理解するのに時間を費やしていません。お役に立てば幸いです。

于 2008-10-13T04:10:25.183 に答える
0 
elsebody : elseifs else
         | elseifs
         ;

elseifs : /* empty */
        | elseifs '#' ELSEIF statements
        ;

else : '#' ELSE statements '#' END
     ;

これは再帰を残し、常に終了する必要があると思います。

于 2008-10-12T23:43:57.813 に答える
0

私はまだ物事を切り替えていますが、elseifsシーケンスの最後に常にelseがあったため、元の質問にはいくつかのエラーがありましたが、これは間違っていました。質問に対する別の見方を次に示します。今回は、2 つのシフト/リデュースの競合が発生します。

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 INFORMATIONが言ったように、正しい再帰が問題を解決することはすでに知っています。しかし、elseifs 句に左再帰を使用したソリューションを探しています。

于 2008-10-12T22:42:20.730 に答える