Verschiebung reduzieren Konflikte in einer einfachen (?) Grammatik

Question

Ich versuche, eine Grammatik in Bison zu beschreiben, aber ich bin mir nicht sicher, ob es getan werden kann. My bestimmt Grammatik ist dies:

%token A B C D SEP 

%% 

items   : /* empty */ 
       | items_nonempty 
       ; 

items_nonempty : item 
       | items_nonempty SEP item 
       ; 

item   :  B 
       |  B  SEP D 
       |  B SEP C 
       |  B SEP C SEP D 
       | A SEP B 
       | A SEP B  SEP D 
       | A SEP B SEP C 
       | A SEP B SEP C SEP D 
       ; 

"items" ist eine (möglicherweise leere) Folge von item Elemente von einem SEP Token getrennt.

Jeder Artikel besteht aus bis zu 4 Token (A B C D), in dieser Reihenfolge, getrennt durch SEP. Die A, C und Tokens in einem Element sind optional.

Beachten Sie die Wiederverwendung von demselben Separator-Token September in jedem Element, und zwischen den Einzelteilen selbst.

Ich hoffe, die vorgesehene Grammatik ist klar. Ich denke, es ist eindeutig, aber ich bin mir ziemlich unsicher, ob es ausreichend beschränkt ist, um von Bison analysiert zu werden - leider ist mein Parser-Wissen ziemlich rostig.

die Grammatik als gegeben, Bisons Berichte 4-Verschiebung/Konflikte reduzieren. Mit Blick auf die "Ausgabe" verstehe ich, wo sie auftreten und warum; aber ich weiß nicht, wie (und wenn) die beabsichtigte Grammatik geschrieben werden kann, um die S/R-Konflikte loszuwerden.

Ich bin nicht bereit, eine %expect Erklärung zu verwenden. Ebenso möchte ich nicht, dass mein Scanner die Separator-Tokens verbraucht, anstatt sie an den Parser weiterzugeben.

Irgendwelche Hinweise, wie diese Grammatik sanieren würde sehr geschätzt werden.

Answer 1

Die Grammatik ist in der Tat eindeutig, es ist LL (7) und (ohne überprüft zu haben) Ich glaube, es LR ist (2), vermutlich sogar LALR (2). Wenn Sie also einen Generator für diese beiden hätten, würde es die Aufgabe erfüllen.

Die Lookahead-1-Konflikte entstehen durch die Verwendung des gleichen Trennzeichens sowohl zwischen Elementen als auch innerhalb von Elementen, und sie verschwinden, wenn Sie entweder das Trennzeichen oder die Elementstruktur aufgeben.

Also was Sie tun könnten, ist zweimal zu analysieren, mit verschiedenen Grammatiken. Im ersten Durchgang konnte man überprüfen Separatoren richtig positioniert ist und die Grammatik etwas wie

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty SEP item 
       ; 
item   : A 
       | B 
       | C 
       | D 
       ; 

In der zweiten (und wichtiger) passieren könnte, würde überprüfen Sie die Item-Struktur. Dies könnte sein

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty item 
       ; 
item   : B 
       | B D 
       | B C 
       | B C D 
       | A B 
       | A B D 
       | A B C 
       | A B C D 
       ; 

wo Sie die Separatoren vom Lexer ignoriert haben.

Beide der oben genannten sind LALR (1), der erstere ist LL (1) und der letztere ist LL (4), aber es könnte LL (1) durch etwas Factoring gemacht werden.

Dies wäre eine Lösung, die von Bison von speziellen Angeboten wie verfügbar unabhängig ist, oder das Lexer-Tool. Ich freue mich darauf zu erfahren, was von ihnen gemacht werden kann.

Answer 2

Dies hat eine Verschiebung/reduce-Konflikt:

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c_d_list 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c_d_list 
    : /* Nothing */ 
    | opt_c_d_list c_or_d 
    ; 

c_or_d 
    : SEP C 
    | SEP D 
    ; 

Die opt_a Regel allein ändert die S/R Zahl von 4 bis 2. Das Restproblem ist, dass der gleiche September sepaerates ein C oder D nach dem B und Yacc können nicht nach vorne schauen.Sie würden eine semantische Prüfung benötigen, um 'B SEP D SEP C' zu verbieten; die obigen Regeln würden das erlauben.

Können Sie in Betracht ziehen, Ihren Tokenizer so zu ändern, dass C beim Lesen von SEP C ?, und D beim Lesen von SEP D zurückgegeben wird? Sie könnten sogar eine lexikalische Rückmeldung und eine Startbedingung in flex verwenden, so dass Sie beim Lesen von B einen Schalter umlegen, so dass SEP C nur als C zurückgegeben wird und SEP D als nur D. zurückgegeben wird. Wenn dies möglich ist, folgt Folgendes eindeutige Grammatik wäre ohne S/R Konflikte arbeiten:

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c opt_d 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c 
    : /* Nothing */ 
    | C 
    ; 

opt_d 
    : /* Nothing */ 
    | D 
    ; 

Answer 3

das grundlegende Problem ist, dass die Grammatik als zwei Token von Look-Ahead muss geschrieben, um zu entscheiden, wenn es das Ende eines item gefunden hat und es somit reduzieren oder wenn Es gibt ein weiteres Stück des aktuellen Artikels nach dem SEP es sieht als das nächste Zeichen des Lookahead.

Es gibt eine Reihe von Ansätzen Sie

• Verwendung btyacc oder Bisons GLR Unterstützung effektiv versuchen können, um mehr Look-Ahead zu bekommen. sie in Mengen von 1-4 Einzelteilen mit mindestens 1 B und Ablehnen fehlerhafte Sätze

• die Grammatik zu schreiben, eine beliebige Liste der einzelnen Elemente zu übernehmen und dann einen Postdurchlauf verwenden, neu zu formieren (Dies ist Gunther Anregung)

• Verwenden Sie den Scanner, um mehr Lookahead zu tun - anstatt einfache SEP Token zurückzugeben, geben Sie SEP_BEFORE_A_OR_B oder SEP_NOT_BEFORE_A_OR_B zurück, je nachdem, was der nächste Token nach dem SEP ist.

• kombinieren Token in den Scanner - Rückkehr SEP_C und SEP_D als Einzelmarker (einen Separator, gefolgt von einem C oder D)

Answer 4

Sie können die SEP nach Ihrer anderen Token in einer einzigen Regel enthalten.

%token A B C D SEP 
%% 
items : /* empty */ | item | itemsSEP item ; 
item : a B | a b C | a b c D ; 
itemsSEP : itemSEP | itemsSEP itemSEP ; 
itemSEP : a b c d ; 
a : /* empty */ | A SEP ; 
b : B SEP ; 
c : /* empty */ | C SEP ; 
d : /* empty */ | D SEP ; 

Ich habe also jetzt itemSEP für ein Element durch einen Separator, wobei jedoch item für die letzten, die nicht durch einen Separator folgt: Geschrieben sehr prägnant, könnte Ihr grammer wie folgt ausgedrückt werden. Diese bestehen aus den Kleinbuchstaben aus Nicht-Termen mit einem Buchstaben, die jeweils auch das folgende Trennzeichen enthalten, und sorgen dafür, dass einige Argumente optional sind. Nur das letzte Argument zu item ist immer ein unbehandeltes Terminal, da nach diesem kein Trennzeichen folgt.

Mit der auf diese Weise ausgedrückten Grammatik werden Sie keinen Shift-Reduce-Konflikten begegnen, da die Grammatik jetzt LALR (1) ist. Bei jedem Schritt wird es genau wissen, welche Reduktion angewendet werden soll, auch wenn der Hauptpunkt dieser Regel darin besteht, einen SEP loszuwerden, damit wir einen Token weiter voraus schauen können.