先読みトークンの制限のためにyaccのShift/reduce競合が発生しましたか？

Question

私は一見シンプルなシフントシップ/無用の競合を解決しようとしてきました。当然のことながら、コンフリクトを無視すれば、パーサはうまく動作しますが、ルールを再編成すればもっと安全に感じられます。ここで、私は、単一の紛争に比較的複雑な文法簡略化されました：

state 2 

    lvalue -> IDENTIFIER . (rule 5) 
    function -> IDENTIFIER . '(' ')' (rule 9) 

    '(' shift, and go to state 7 

    '(' [reduce using rule 5 (lvalue)] 
    $default reduce using rule 5 (lvalue) 

感謝：YACCで冗長オプションで

statement_list 
    : statement_list statement 
    | 
    ; 

statement 
    : lvalue '=' expression 
    | function 
    ; 

lvalue 
    : IDENTIFIER 
    | '(' expression ')' 
    ; 

expression 
    : lvalue 
    | function 
    ; 

function 
    : IDENTIFIER '(' ')' 
    ; 

を、私が言及した紛争に状態を記述する、この出力ファイルを取得しますあなたはどんな援助のためにも。

Answer 1

問題は、ステートメントの終わりに達したことを知るために2トークン先読みが必要になることです。フォームの入力がある場合：

ID = ID (ID) = ID 

をパーサは（先読みが(である）第2のIDを移行した後、それはそれは最初の文の終わりだかどうか分かりません（(は、第二文の始まりです）、またはこれは関数です。そのため、上記の入力例では間違ったことですが（関数の解析を続ける）シフトします。あなたは、実際の表現を可能にするために括弧とexpression内部の引数を許可するようにfunctionを拡張する場合に必要な先読みが無制限であるよう

は、物事は、悪くなる - パーサはこのことを判断するために、第2 =にすべての方法を取得する必要があります関数呼び出しではありません。

ここでの基本的な問題は、パーサが文の終わりを見つけるのを助けるヘルパー句読がないことです。有効なステートメントの先頭にあるテキストは、有効なステートメントの途中にも出現する可能性があるため、ステートメントの境界を見つけることは困難です。