3

なぜこれが競合の削減/削減に関する警告を発するのか

root : set1 'X'     
     | set2 'X' 'X' 

set1 : 'A'          
     | 'B'             

set2 : 'B'          
     | 'C'

しかし、次は大丈夫ですか？

root : 'A' 'X'     
     | 'B' 'X'     
     | 'B' 'X' 'X'  
     | 'C' 'X' 'X'
4

1 に答える 1

9

違いは、最初のケースでは、パーサーが1つ'X'または2つが続くかどうかを確認する前に、削減について選択する必要があるためです。

2番目の例では、パーサーは同じ状態を使用できます。これは、と（両方がシフトされている）が表示されたときに呼び出します。BX次に、次のトークンに応じて、シフト（の場合）してから、ルールを減らすか、そうでない場合は減らします。すぐに。BXX'B' 'X' 'X''B' 'X'

直後に同一のトークンがない場合（たとえば、持っていset1 'X'たがset2 'Y'）、先読みが開始してどの削減を行うかを選択できるため、問題はありません。

bison -vこの問題を公開するための出力からの関連セクションは次のとおりです。

ケース1

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4
set1  go to state 5
set2  go to state 6

を取得すると仮定すると'B'、状態2に進みます。

state 2

set1: 'B' .
set2: 'B' .

'X'       reduce using rule 4 (set1)
'X'       [reduce using rule 5 (set2)]
$default  reduce using rule 4 (set1)

同じ入力トークンを使用して、 toset1または、の2つの可能な削減があることに注意してください。set2したがって、reduce / reduce; 先読みのトークンは1つしかありません。この文法では、トークンはaだけになります'X'—どちらの場合も！

ケース2

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4

を取得すると仮定すると'B'、状態2に進みます。

state 2

root: 'B' . 'X'
    | 'B' . 'X' 'X'

'X'  shift, and go to state 6

'B' 'X'先読みのトークンは1つしかありませんが、パーサージェネレーターは、入力の構造に対応しているため、先読みの状態を生成できます。したがって、どのような場合でも状態6になります（またはエラーが発生します;-)）：

状態6

root: 'B' 'X' .
    | 'B' 'X' . 'X'

'X'  shift, and go to state 9

$default  reduce using rule 2 (root)

ここで魔法が起こります。が表示された場合は'X'、シフトして状態9（削減）に進みます。それ以外の場合は、'B' 'X'すぐに削減します。

完全を期すために、ここに状態9があります。

state 9

root: 'B' 'X' 'X' .

$default  reduce using rule 3 (root)

曖昧さを解消するための先読みのトークンがあった場合

このサンプル文法では：

root: set1 'X'
    | set2 'Y'

set1: 'A'          
    | 'B'             

set2: 'B'          
    | 'C'

次に、開始します。

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4
set1  go to state 5
set2  go to state 6

シフト'B'して状態2に進みます。

state 2

set1: 'B' .
set2: 'B' .

'Y'       reduce using rule 5 (set2)
$default  reduce using rule 4 (set1)

したがって、この状態はとの両方のルールで到達しset1、スタックにset2単一の'B'トークンがあります。この場合、次にが表示される'Y'と、に減少します。set2それ以外の場合は、に減少しset1ます。

set1これが「デフォルト」の削減として選択されているという事実は、エラー処理に影響を与える可能性があります。

GLRに関する付録

Happy（およびbisonまたはyacc）はデフォルトでLALR（1）パーサーを生成しますが、GLRパーサーは--glr（または宣言ファイルで）生成でき%glr-parserます。bisonこれにより、両方の「可能性」を同時に試すことで、あいまいさを解決できます。パーサーはフォークして、どちらの場合でもどこまで到達するかを確認します。

ただし、本当に必要であり、必要であることがわかっていて、問題が発生した場合に何が起こるかを知っている場合を除いて、これはおそらく賢明ではありません。両方のフォークが正常に終了した場合にどうなるかわかりません。私の非科学的なテストでは、常に長い解析を選択することになったようです。

レクサーハック

GLRを使用したくないが、パーサーを大幅に再構築したくない場合は、レクサーハックを使用してこの問題を解決することを検討できます。

今、あなたはこれを持っています：

root : set1 'X'     
     | set2 'X' 'X'

'X'代わりに、1つの文字に対してトークンを発行し、2つの文字に対して別のトークンを発行することができます。

root : set1 ONE_X
     | set2 TWO_XS

これにより、単一のトークン内のあいまいさが解決され、結果として明確なLALR（1）文法になります。

于 2012-05-26T10:53:16.430 に答える