Happy/YACC reduziert, wann es sich ändern sollte

Question

Ich arbeite an einem Parser und bin wirklich frustriert.In der Sprache können wir einen Ausdruck haben wie:

new int[3][][]

oder

new int[3]

Das meiste davon wird korrekt analysiert, mit Ausnahme der leeren Arrays am Ende.In meinem Parser habe ich:

Expression : int
             char
             null
             (...many others...)
             new NewExpression

und dann ist ein NewExpression:

NewExpression : NonArrayType '[' Expression ']' EmptyArrays
              | NonArrayType '[' Expression ']' 

und dann ist EmptyArrays eine oder mehrere leere geschweifte Klammern. Wenn EmptyArrays die leere Zeichenfolge ableitet, werden 20 Verschiebungs-/Reduzierungskonflikte hinzugefügt:

EmptyArrays : EmptyArrays EmptyArray
            | EmptyArray
EmptyArray  : '[' ']'

Wenn ich jedoch in die schaue .info Datei für den Parser, erhalte ich Folgendes:

State 214¬
¬
▸   NewExpression -> NonArrayType lbrace Expression rbrace . EmptyArrays    (rule 80)¬
▸   NewExpression -> NonArrayType lbrace Expression rbrace .    (rule 81)¬
¬
▸   dot            reduce using rule 81¬
▸   ';'            reduce using rule 81¬
▸   ','            reduce using rule 81¬
▸   '+'            reduce using rule 81¬
▸   '-'            reduce using rule 81¬
▸   '*'            reduce using rule 81¬
▸   '/'            reduce using rule 81¬
▸   '<'            reduce using rule 81¬
▸   '>'            reduce using rule 81¬
▸   '<='           reduce using rule 81¬
▸   '>='           reduce using rule 81¬
▸   '=='           reduce using rule 81¬
▸   '!='           reduce using rule 81¬
▸   ')'            reduce using rule 81¬
▸   '['            reduce using rule 81    --I expect this should shift
▸   ']'            reduce using rule 81¬
▸   '?'            reduce using rule 81¬
▸   ':'            reduce using rule 81¬
▸   '&&'           reduce using rule 81¬
▸   '||'           reduce using rule 81

Ich gehe jedoch davon aus, dass wir, wenn wir uns im Status 214 befinden und eine linke geschweifte Klammer sehen, diese auf den Stapel verschieben und mit dem Parsen von EmptyArrays fortfahren sollten.

Ich bin mir nicht ganz sicher, was los ist, denn wenn ich den gesamten Überschuss aus dem Gepäck entferne (z. B. indem ich die Analyse mit beginne). NewExpression, werden die zusätzlichen Klammern korrekt analysiert.Es ist nicht möglich, dass ein Ausdruck, eine Anweisung oder irgendein Nichtterminal in der Grammatik mit einer linken Klammer beginnt.Vor allem, weil ich eine ähnliche Regel für if/else-Anweisungen habe, die einen Shift/Reduction-Konflikt erzeugt, sich aber für die Verschiebung entscheidet, wenn das nächste Token ein else ist (dieses Problem ist gut dokumentiert).

Können Sie mir helfen herauszufinden, was falsch läuft?Ich schätze Ihre Hilfe wirklich sehr. Ich versuche wirklich, das Problem herauszufinden.

Answer 1

Sie haben wahrscheinlich eine Priorität für „[“ und/oder „]“ mit etwas wie „ %left '[' was dieses Verhalten verursacht.Wenn Sie diese Vorrangdeklaration entfernen, wird der Verschiebungs-/Reduzierungskonflikt, den Sie hier haben, sichtbar.Was die Frage angeht, warum es sich um einen Verschiebungs-/Reduzierungskonflikt handelt, haben Sie wahrscheinlich auch eine Regel:

Expression: Expression '[' Expression ']'

für einen Array-Zugriff.Das Problem ist, dass seit a NewExpression ist ein Expression Darauf kann ein Index wie dieser folgen, und wenn man sich den Lookahead von „[“ ansieht, kann man nicht sagen, ob das der Anfang eines Indexausdrucks oder der Anfang eines ist EmptyArray – das würde einen 2-Token-Lookahead erfordern.

Eine Sache, die Sie für diesen speziellen Fall versuchen könnten, wäre, Ihren Lexer den hier erforderlichen zusätzlichen Lookahead durchführen und erkennen zu lassen [] als einzelnes Token.