Bison reduzieren/reduzieren Konflikt in der Grammatik

Question

Ich baue eine Grammatik in Bison und ich habe einen R/R-Konflikt (wo ich weiß, wo es ist), aber ich weiß nicht, wie es zu beheben ist. Ich würde jede mögliche Hilfe schätzen.

Der Teil meines Code, der den Konflikt beinhaltet ist:

orismos2: %empty 
|orismos orismos2 
|error {yyerrok;yyclearin;}; 

orismos: orismosmetablitwn 
|orismossunartisis 
|prwtotuposunartisis; 

orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON ; 

tuposdedomenwn: INT 
|BOOL 
|STRING; 

listametablitwn: ID nid ; 

nid: %empty 
|pid nid 
|error {yyerrok;yyclearin;}; 

pid: COMMA ID ; 

orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn; 

prwtotuposunartisis: kefalidasunartisis SEMICOLON; 

kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET; 

typos_synartisis: INT 
|BOOL 
|VOID; 

Ich habe eine Ausgabedatei machen, bei dem ich alle Konflikte sehen.

Der Teil der Datei, die die Konflikte beinhaltet ist:

State 21 conflicts: 1 reduce/reduce 
State 22 conflicts: 1 reduce/reduce 


Grammar 

    10 orismos2: %empty 
    11   | orismos orismos2 
    12   | error 

    13 orismos: orismosmetablitwn 
    14  | orismossunartisis 
    15  | prwtotuposunartisis 

    16 orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON 

    17 tuposdedomenwn: INT 
    18    | BOOL 
    19    | STRING 

    20 listametablitwn: ID nid 

    21 nid: %empty 
    22 | pid nid 
    23 | error 

    24 pid: COMMA ID 

    25 orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn 

    26 prwtotuposunartisis: kefalidasunartisis SEMICOLON 

    27 kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET 

    28 typos_synartisis: INT 
    29     | BOOL 
    30     | VOID 


State 21 

    17 tuposdedomenwn: INT . 
    28 typos_synartisis: INT . 

    ID  reduce using rule 17 (tuposdedomenwn) 
    ID  [reduce using rule 28 (typos_synartisis)] 
    $default reduce using rule 17 (tuposdedomenwn) 


State 22 

    18 tuposdedomenwn: BOOL . 
    29 typos_synartisis: BOOL . 

    ID  reduce using rule 18 (tuposdedomenwn) 
    ID  [reduce using rule 29 (typos_synartisis)] 
    $default reduce using rule 18 (tuposdedomenwn) 

ich wirklich alles versucht, aber ich die Konflikte nicht entfernen kann ... Alle möglichen Ideen oder Vorschläge willkommen!

Vielen Dank !!

Answer 1

Der Schlüssel ist hier: & hellip;

orismos → (13) orismosmetablitwn → (16) tuposdedomenwn listametablitwn 
orismos → (14) orismossunartisis → (25) kefalidasunartisis … → (27) typos_synartisis … 
orismos → (15) prwtotuposunartisis → (26) kefalidasunartisis … → (27) typos_synartisis … 

auch:

tuposdedomenwn → NUMBER | BOOL | STRING 
listametablitwn → ID … 
kefalidasunartisis → typos_synartisis ID … 
typos_synartisis → NUMBER | BOOL | VOID 

So, hier sind einige Ableitungen von orismos:

orismos → orismosmetablitwn → tuposdedomenwn listametablitwn → NUMBER ID … 
orismos → orismossunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID … 
orismos → prwtotuposunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID … 

sagen wir in einem Kontext, wo orismis möglich ist, und wir haben gerade einen NUMBER gesehen und wir schauen uns jetzt eine ID an. Alle drei obigen Ableitungen sind möglich. Aber es gibt ein kleines Problem: in der ersten ist NUMBER von tuposdedomenwn abgeleitet, während in den zweiten beiden ist es von typos_synartisis abgeleitet. Bevor wir irgendetwas mit dem ID tun können, müssen wir wissen, welche der beiden Ableitungen zu reduzieren sind, aber es gibt keine Möglichkeit, dass wir das wissen können, bis wir das Token nachID sehen.

Das bedeutet, dass die Grammatik zwei Token von Lookahead benötigt, also kann ein LALR (1) Parser es nicht analysieren.

Die einfachste Lösung wäre es, die zwei nicht-Terminals zu kombinieren Sätze von Typen, die einen Nicht-Terminal zu schaffen, die alle vier Möglichkeiten erlaubt:

tuposdedomenwn: NUMBER | BOOL | STRING | VOID 

Dann werden Sie später eine semantische Prüfung zu tun haben, auf um zu überprüfen, ob eine Variable nicht VOID noch eine Funktion deklariert STRING deklariert ist. (Warum können Ihre Funktionen keine Strings zurückgeben? Das scheint ein wenig einschränkend zu sein.) Diese Strategie, eine Hochstellung der Sprache zu akzeptieren und dann semantische Prüfungen während der AST-Konstruktion oder sogar später durchzuführen, ist sehr üblich; Zum Beispiel ist es die einzige Möglichkeit, die Deklaration vor der Verwendung von Variablen zu erzwingen.

Wenn Sie jedoch die semantische Prüfung nicht durchführen möchten, können Sie die Reduzierung einfach verschieben, indem Sie Nicht-Terminals erstellen, die aus einem Datentyp und einem ID bestehen.Das zu etwas führen würde wie:

tupodedomenon_kai_metavlites 
     : INT ID 
     | BOOL ID 
     | STRING ID 
     | tupodedomenon_kai_metavlites ',' ID 

tupo_synartisis_kai_metavliton 
     : INT ID 
     | BOOL ID 
     | VOID ID 

orismos: orismosmetablitwn 
     | orismossunartisis 
     | prwtotuposunartisis 

orismosmetablitwn 
     : tupodedomenon_kai_metavlites ';' 

orismossunartisis 
     : kefalidasunartisis tmimaorismwn tmimaentolwn 

prwtotuposunartisis 
     : kefalidasunartisis ';' 

kefalidasunartisis 
     : tupo_synartisis_kai_metavliton '(' c ')' 

Mit dieser Änderung gibt es keine Notwendigkeit, die NUMBER (oder eine andere Art) zu verringern; Die ID kann verschoben werden, und dann wird die Reduzierung auf die eine oder andere Möglichkeit basierend auf dem folgenden Token durchgeführt: als Variablendeklaration, wenn das folgende Token ; oder , ist, und als Funktionsdeklaration, wenn das folgende Token ( ist.