Shift/reduce Konflikt in yacc wegen Look-Ahead Token Begrenzung?

Question

Ich habe versucht, eine scheinbar einfache Verschiebung zu bewältigen/Konflikt ohne Erfolg zu reduzieren. Natürlich funktioniert der Parser gut, wenn ich den Konflikt einfach ignoriere, aber ich würde mich viel sicherer fühlen, wenn ich meine Regeln reorganisiere. Hier habe ich eine relativ komplexe Grammatik zu dem einzigen Konflikt vereinfacht:

statement_list 
    : statement_list statement 
    | 
    ; 

statement 
    : lvalue '=' expression 
    | function 
    ; 

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

expression 
    : lvalue 
    | function 
    ; 

function 
    : IDENTIFIER '(' ')' 
    ; 

Mit der Option verbose in yacc, erhalte ich diese Ausgabedatei beschreibt den Zustand mit dem erwähnten Konflikt:

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) 

Thank Sie für jede Hilfe.

Answer 1

Das Problem ist, dass dies erfordert 2-Token Lookahead zu wissen, wann es das Ende einer Anweisung erreicht hat. Wenn Sie den Eingang des Formulars haben:

ID = ID (ID) = ID 

nach Parser die zweite ID verschiebt (Look-Ahead ist (), weiß es nicht, ob das das Ende der ersten Anweisung ist (die ( ist der Beginn einer zweiten Aussage), oder das ist eine Funktion. Es verschiebt sich also (eine Funktion wird weiter analysiert), was mit der obigen Beispieleingabe falsch ist.

Wenn Sie function erweitern ein Argument in der Klammer zu ermöglichen und expression tatsächlichen Ausdrücke zu ermöglichen, werden die Dinge schlimmer, da die notwendige Look-Ahead unbegrenzt ist - der Parser den ganzen Weg auf den zweiten = bekommen muss, dass dies zu bestimmen ist kein Funktionsaufruf.

Das grundlegende Problem hier ist, dass es keine Hilfssatzzeichen gibt, die dem Parser helfen, das Ende einer Aussage zu finden. Da der Text, der den Anfang einer gültigen Anweisung darstellt, auch in der Mitte einer gültigen Anweisung stehen kann, ist es schwierig, Anweisungsgrenzen zu finden.