Bison Indexausdruck unerwarteter Fehler

Question

Mit der folgenden Grammatik:

program: /*empty*/ | stmt program; 
stmt: var_decl | assignment; 
var_decl: type ID '=' expr ';'; 
assignment: expr '=' expr ';'; 
type: ID | ID '[' NUMBER ']'; 
expr: ID | NUMBER | subscript_expr; 
subscript_expr: expr '[' expr ']'; 

ich folgenden gültig sein erwarten:

array[5] = 0; 

Das ist nur auf der linken Hand ein assignment mit einem subscript_expr ist Seite. Jedoch der erzeugte Parser einen Fehler für diese Anweisung gibt:

syntax error, unexpected '=', expecting ID 

die Parser generieren warnt auch, dass es eine Schiebe-/Reduzier Konflikt. Entfernen subscript_expr macht es weg.

Warum passiert das und wie kann ich es bekommen, um array[5] = 0; als assignment mit einem subscript_expr zu parsen?

Ich benutze Bison 2.3.

Answer 1

die folgenden zwei Aussagen gelten sowohl in Ihrer Sprache:

x [ 3 ] = 42; 

x [ 3 ] y = 42; 

Die erste eine Zuordnung eines Elements des Arrays ist variablex, während der zweite eine Erklärung und Initialisierung der ist Array-Variable y, deren Elemente Typx sind.

Aber aus Sicht des Parsers, x und y sind beide nur ID s; es kann nicht wissen, dass x eine Variable im ersten Fall und ein Typ im zweiten Fall ist. Alles, was es tun kann, ist, dass die beiden Anweisungen die Produktionen assignment und var_decl entsprechen.

Leider kann es das nicht tun, bis es das Token nach der ] sieht. Wenn dieses Token eine ID ist, muss die Anweisung eine var_decl sein; Ansonsten ist es ein assignment (vorausgesetzt, die Aussage ist natürlich gültig).

Aber um die Anweisung als eine Zuordnung zu analysieren, muss der Parser kann

expr '=' expr 

erzeugen, die das Ergebnis der expr: subsciprt_expr in diesem Fall ist, was wiederum subscript_expr: expr ist [expr] `.

Also wird die Menge der Kürzungen für die erste Aussage wie folgt sein: (Anmerkung: Ich habe die Verschiebungen nicht geschrieben, sondern den Fortschritt der Analyse durch Setzen von • am Ende jeder Reduktion Gehe zum nächsten Schritt, verschiebe einfach • bis zum Ende des Griffs.

)

ID • [ NUMBER ] = NUMBER ;    expr: ID 
expr [ NUMBER • ] = NUMBER ;   expr: NUMBER 
expr [ expr ] • = NUMBER ;    subscript_expr: expr '[' expr ']' 
subscript_expr • = NUMBER ;   expr: subscript_expr 
expr = NUMBER • ;      expr: NUMBER 
expr = expr ; •      assignment: expr '=' expr ';' 
assignment 

Die zweite Anweisung muss analysiert werden, wie folgt:

ID [ NUMBER ] • ID = NUMBER ;   type: ID '[' NUMBER ']' 
type ID = NUMBER • ;     expr: NUMBER 
type ID = expr ; •      var_decl: type ID '=' expr ';' 
var_decl 

, dass eine Verschiebung ist/reduzieren Konflikt, weil die wichtige Entscheidung muss unmittelbar nach der ersten ID gemacht werden. In der ersten Anweisung müssen wir den Bezeichner auf expr reduzieren. In der zweiten Aussage müssen wir weiterschalten, bis wir bereit sind, eine type zu reduzieren.

Natürlich wäre dieses Problem nicht existieren, wenn wir könnten lexikalisch Typ ID s von Variablennamen ID s unterscheiden, aber das kann nicht möglich sein (oder, wenn möglich, ist es nicht wünschenswert sein kann, weil es eine Rückmeldung vom Parser zum Lexer benötigt).

Wie beschrieben, kann die Shift/Reduce-Vorhersage mit festem Lookahead durchgeführt werden, da der vierte Token nach der ID die Möglichkeiten bestimmt. Das macht die Grammatik LALR (4), aber das hilft nicht viel, da Bison nur LALR (1) Parser implementiert. In jedem Fall ist es wahrscheinlich, dass eine weniger vereinfachte Grammatik nicht fest vorgegeben ist, beispielsweise wenn konstante Ausdrücke für Array-Größen zulässig sind oder wenn Arrays mehrere Dimensionen haben können.

Trotzdem ist die Grammatik nicht mehrdeutig, daher ist es möglich, einen GLR-Parser zu verwenden, um es zu parsen. Bison implementiert GLR-Parser; es ist nur notwendig, in das Prolog

%glr-parser 

einzufügen. (Die Verschiebung/reduziert Warnung wird noch produziert werden, aber der Parser korrekt beiden Arten von Aussage identifizieren.)

Es ist erwähnenswert, dass C nicht über dieses besondere Parsing Problem, gerade weil es die Größe Array setzt nach Der Name der Variablen, die deklariert wird. Ich glaube nicht, dass dies gemacht wurde, um Parsing-Probleme zu vermeiden (obwohl wer weiß?), Sondern weil es geglaubt wurde, dass es natürlicher ist, Deklarationen so zu schreiben, wie Variablen verwendet werden. Daher schreiben wir int a[3] und char *p, weil wir in dem Programm mit a[i] und *p dereferenzieren.

Es ist möglich, eine LALR (1) Grammatik für diese Syntax zu schreiben, aber es ist ein bisschen nervig. Der Schlüssel ist, die Reduzierung der Syntax ID [ NUMBER ] zu verzögern, bis wir sicher wissen, welche Produktion es sein wird. Das heißt, wir müssen die Produktion expr: ID '[' NUMBER ']' einschließen. Das wird zu einer größeren Anzahl von Shift/Reduce-Warnungen führen (da es die Grammatik mehrdeutig macht), aber da Bison immer eine Verschiebung vorzieht, sollte es einen korrekten Parser erzeugen.

Answer 2

Hinzufügen %glr-parser löst dies.