0

私は初めて Bison 文法を幅広く扱っています。文法をセットアップし、結果を相関させるための小さなテスト スイートを用意しました。

場合によっては、テスト スイートに合格することがあります。

Reducing stack by rule 101 (line 613):
   $1 = nterm mathenv ()
-> $$ = nterm closedTerm ()
Stack now 0 5 3
Entering state 120
Reading a token: Next token is token ENDMATH ()
Reducing stack by rule 28 (line 517):
   $1 = nterm closedTerm ()
-> $$ = nterm compoundTerm ()
Stack now 0 5 3
Entering state 119
Reducing stack by rule 12 (line 333):
   $1 = nterm compoundTerm ()
-> $$ = nterm compoundTermList ()
Stack now 0 5 3
Entering state 198
Next token is token ENDMATH ()
Shifting token ENDMATH ()
Entering state 325

... continues to completion ...

場合によっては、次のことが行われません。

Reducing stack by rule 101 (line 613):
   $1 = nterm mathenv ()
-> $$ = nterm closedTerm ()
Stack now 0 5 3
Entering state 120
Reading a token: Next token is token MN ()
Reducing stack by rule 28 (line 517):
   $1 = nterm closedTerm ()
-> $$ = nterm compoundTerm ()
Stack now 0 5 3
Entering state 119
Reducing stack by rule 12 (line 333):
   $1 = nterm compoundTerm ()
-> $$ = nterm compoundTermList ()
Stack now 0 5 3
Entering state 198
Next token is token MN ()
Shifting token MN ()
Entering state 11

... errors eventually ...

Now at end of input.
Line: 9 Error: syntax error at token

ENDMATHは、シフト先の正しいトークンですが、場合によってMNは決定されます。テストを実行するたびに一貫性のない結果が得られます。そのような「ランダムな」あいまいさは正常ですか? 何が原因でしょうか？%precedenceいくつかのルールを定義する必要がありますか?

y.outputの上部に、次のような状態の競合がいくつか見られます

State 0 conflicts: 3 shift/reduce
State 120 conflicts: 2 shift/reduce
State 127 conflicts: 2 shift/reduce
State 129 conflicts: 2 shift/reduce
State 154 conflicts: 1 shift/reduce
State 207 conflicts: 3 shift/reduce
State 265 conflicts: 109 shift/reduce
State 266 conflicts: 109 shift/reduce
State 267 conflicts: 109 shift/reduce
State 268 conflicts: 109 shift/reduce
State 269 conflicts: 109 shift/reduce
State 342 conflicts: 2 shift/reduce
State 390 conflicts: 109 shift/reduce
State 391 conflicts: 109 shift/reduce
State 396 conflicts: 1 shift/reduce
State 397 conflicts: 1 shift/reduce

これらの競合をすべて排除することをお勧めしますか? 状態 120 は競合があるとリストされており、このランダム エラーが発生する直前の状態であることに注意してください。

4

1 に答える 1

1

文法の矛盾は、文法が LALR(1) ではないことを意味します。これは、文法が曖昧であることが原因である可能性があります。または、文法が先読みの複数のトークンを必要とすることが原因である可能性があります。競合が発生した場合は常に、bison は優先順位のディレクティブに基づいて可能なアクション (シフトまたは削減) のいずれかを選択することによって解決します。これにより、文法によって記述された言語のサブセットを認識 (解析) するパーサーが生成されます。

競合が純粋にあいまいさによるものである場合、これはあいまいな解析を排除するだけで、実際には言語をまったく削減しない可能性があります。このような場合、優先順位規則を使用してあいまいさを解決することは、問題に対処する正しい方法です。これにより、必要な言語を解析する文法が得られるからです。

より多くの先読みが必要なために競合が発生している場合、優先ルールは通常役に立ちません。先読みを必要としないように文法を再編成するか、入力またはその他の情報のさらなる先読みに基づいてレクサーに余分な合成トークンを挿入させるなどの他の手法 (ハック) を使用して、問題を解決する必要があります。

あなたの場合、差し迫った問題はレクサーにあるようです。トークンENDMATHを返す場合と返す場合がありますMN。で見られる競合に関連する文法のあいまいさや先読みの問題もあるかもしれませんがy.output、そのような問題は一見するとレクサーの問題とは完全に無関係であるように見えます。

于 2014-09-21T22:10:29.507 に答える