Fixing Lemon Parsing confilcts

Ich schreibe einen kleinen Parser, der Einschränkungen analysiert, mit Flex und Lemon. Lemon berichtet über einige Parsing-Konflikte, die ich nicht loswerden konnte. Gibt es bestimmte Tricks, um Parsing-Konflikte in einer kontextfreien Grammatik loszuwerden?Fixing Lemon Parsing confilcts

Die Grammatik ist wie folgt.

// Reprint of input file "Constraint_grammar.y". 
// Symbols: 
// 0 $   5 NE  10 PLUS  15 NOT   20 error 
// 1 IFF  6 GT  11 MINUS  16 LPAREN  21 constraint 
// 2 AND  7 GTE  12 TIMES  17 RPAREN  22 bool_expr 
// 3 OR   8 LT  13 DIVIDE  18 VARIABLE 23 int_expr 
// 4 EQ   9 LTE  14 POWER  19 INTEGER 
constraint ::= bool_expr. 
bool_expr ::= LPAREN bool_expr RPAREN. 
int_expr ::= LPAREN int_expr RPAREN. 
bool_expr ::= int_expr LT int_expr. 
bool_expr ::= int_expr GT int_expr. 
bool_expr ::= int_expr EQ int_expr. 
bool_expr ::= int_expr NE int_expr. 
bool_expr ::= int_expr GTE int_expr. 
bool_expr ::= int_expr LTE int_expr. 
bool_expr ::= bool_expr AND bool_expr. 
bool_expr ::= bool_expr OR bool_expr. 
bool_expr ::= bool_expr IFF bool_expr. 
int_expr ::= int_expr PLUS int_expr. 
int_expr ::= int_expr MINUS int_expr. 
int_expr ::= int_expr TIMES int_expr. 
int_expr ::= int_expr DIVIDE int_expr. 
int_expr ::= int_expr POWER int_expr. 
bool_expr ::= NOT bool_expr. 
int_expr ::= MINUS int_expr. 
int_expr ::= VARIABLE. 
bool_expr ::= VARIABLE. 
int_expr ::= INTEGER.

%nonassoc IFF. 
%left AND. 
%left OR. 
%nonassoc EQ NE GT GTE LT LTE. 
%left PLUS MINUS. 
%left TIMES DIVIDE. 
%right POWER NOT. 
%nonassoc LPAREN RPAREN.

Die Fehler sind wie folgt.

State 28: 
    (19) int_expr ::= VARIABLE * 
    (20) bool_expr ::= VARIABLE * 

          $ reduce 20 
          IFF reduce 20 
          AND reduce 20 
          OR reduce 20 
          EQ reduce 19 
          NE reduce 19 
          GT reduce 19 
          GTE reduce 19 
          LT reduce 19 
          LTE reduce 19 
          PLUS reduce 19 
         MINUS reduce 19 
         TIMES reduce 19 
         DIVIDE reduce 19 
         POWER reduce 19 
         RPAREN reduce 19 
         RPAREN reduce 20 ** Parsing conflict **

State 40: 
      bool_expr ::= bool_expr * AND bool_expr 
      bool_expr ::= bool_expr * OR bool_expr 
      bool_expr ::= bool_expr * IFF bool_expr 
    (11) bool_expr ::= bool_expr IFF bool_expr * 

          $ reduce 11 
          IFF shift 4 
          IFF reduce 11 ** Parsing conflict ** 
          AND shift 1 
          OR shift 3 
         RPAREN reduce 11

Der gesamte Bericht Parser-Generator ist hier über. http://pastebin.com/TRsV3WvK

Wer weiß, was ich hier falsch mache? Kann ich diese Konflikte ignorieren?

Quelle

2011-01-03 Null Set

Ich würde erwarten, den 'State 28'-Konflikt zu beheben, indem ich zwischen einer booleschen Variablen und einer Integer-Variablen unter Verwendung der Symboltabelle, um festzustellen, welche Art von Token zurückgegeben wird, unterscheiden. Sie hätten vielleicht BOOL_VARIABLE und INT_VARIABLE. Tests zeigen, dass diese Änderung den Konflikt "Staat 28" beseitigt.

Der Konflikt 'State 40' kann leicht entfernt werden, indem die Assoziativität von IFF von nonassoc zu left geändert wird. Gibt es einen guten Grund, es nicht assoziativ zu machen?

Quelle

2011-01-03 21:41:09

Ich hatte gehofft, dass Variablentyp könnte durch welche Art von Ausdruck es gefunden wurde, aber ich denke, ich kann das nicht tun, ohne diesen Parse-Konflikt. Ich hatte IFF als nonassoc, weil ich ein Idiot bin und nicht bemerkte, dass es assoziativ war. Ich glaube, ich habe einfach angenommen, dass es dasselbe ist wie EQ. –

@Null Set: IFF ist mehr wie AND oder OR als EQ, denke ich. Das Problem mit den Variablentypen kann vermieden werden, indem man nicht sowohl 'int_expr' als auch' bool_expr' verwendet (indem man ein uniformes 'expr' verwendet) und Semantik für die Behandlung eines Integer-Ausdrucks in einem booleschen Kontext definiert (zum Beispiel wie C mit _0 ist falsch, nicht 0 ist wahr_). Sie würden dann eine der beiden 'expr :: = LPAREN expr RPAREN.-Regeln loswerden. Aber da die Grammatik nicht erkennen kann, ob eine Variable Boolesch oder Integer ist, kann man nicht sagen, wie sie mit '(Variable)' umgehen soll, weil sie ganzzahlig oder boolesch sein könnte. es ist wirklich mehrdeutig. –

Das explizite Eingeben von Variablendeklarationen ist wahrscheinlich eine gute Idee. Ich sehe jetzt, dass ich sie immer brauchen würde. –

Sie haben Parserkonflikte, was bedeutet, dass die von Ihnen angegebene Grammatik nicht eindeutig ist, dh es gibt mehr als einen Syntaxbaum für eine gegebene Eingabe von Terminalsymbolen. Dies ist durchaus üblich, aber wenn wir eine eindeutige Grammatik wollen, müssen wir Disambiguierungsregeln wie Assoziativität und Vorrang festlegen, so dass wir immer nur einen der Parse-Bäume auswählen können.

Ich bin nicht sicher, welche Art von Einschränkungen Sie die Grammatik mit analysieren, aber ich bin mir ziemlich sicher, dass Sie eine umabigous Grammatik hier wollen, Programmiersprachen sind (fast) immer eindeutig. (Wenn die Bedingungen jedoch aus einer natürlichen Quelle stammen, müssen Sie wahrscheinlich einen geeigneteren Parser verwenden.) Ich bin mir nicht sicher, was der Parser Lemon tun wird, wenn Sie ihm eine mehrdeutige Grammatik geben, wahrscheinlich nur den einen der Übergänge bevorzugen in seinem Automaten, der sehr gut zu dem Baum führen könnte, den du nicht willst.

Quelle

2011-01-03 21:56:44

Fixing Lemon Parsing confilcts

Antwort

Verwandte Themen