2

C++ で式を解析するための YACC 文法があります。ここに軽量版があります：

// yacc.y
%token IDENT

%%

expr:
    call_expr
    | expr '<' call_expr
    | expr '>' call_expr
    ;

call_expr:
    IDENT
    | '(' expr ')'
    | IDENT '<' args '>' '(' args ')'
    ;

args:
    IDENT
    | args ',' IDENT
    ;

%%

テンプレート引数を使用した関数呼び出しをサポートしたい場合、shift/reduce競合が発生しました。

input を受け取ったときIDENT '<' IDENT、yacc はシフトすべきか削減すべきかわかりません。

IDENT '<' args '>' '(' args ')'よりも高い優先順位を取得したいexpr '<' call_exprので、次の expr を解析できます。

x < y
f<x>(a,b)
f<x,y>(a,b) < g<x,y>(c,d)

C++/C# の両方がこの構文をサポートしていることがわかります。この問題を yacc で解決する方法はありますか?

.yファイルを変更するにはどうすればよいですか?

ありがとうございました！

4

1 に答える 1

1

-vyacc/bisonのオプションが必要です。生成された shift/reduce パーサーに関するすべての情報を含む .output ファイルが提供されます。あなたの文法で、バイソンはあなたに与えます：

State 1 conflicts: 1 shift/reduce
      :
state 1

    4 call_expr: IDENT .
    6          | IDENT . '<' args '>' '(' args ')'

    '<'  shift, and go to state 5

    '<'       [reduce using rule 4 (call_expr)]
    $default  reduce using rule 4 (call_expr)

問題がどこにあるかを示します。を見た後IDENT、次のトークンがである場合、それを減らす必要があるか(最終的にルール に一致するため)、またはルール 6 に一致するようにシフトする必要<があるかはわかりません。call_exprexpr: expr '<' call_expr

<トークンには 2 つの異なる意味(小なりまたは開き山かっこ) があり、どちらが意味するかは後のトークンに依存するため、1 つのトークン先読みのみでこれを解析するのは困難です。

このケースは、次のような入力としてあいまいであるため、実際にはさらに悪いです。

a < b > ( c )

おそらく、両方の引数リストがシングルトンであるテンプレート呼び出しですが、

( a < b ) > ( c )

したがって、文法を素因数分解するだけでは役に立ちません。あなたの最善の策は、バイソンの%glr-parserオプションやbtyaccのような、より強力な解析方法を使用することです

于 2013-06-14T21:45:04.783 に答える