Parse-Grammatik abwechselnd und wiederholen

Question

Ich konnte Unterstützung für die Grammatik meines Parsers für abwechselnde Zeichen hinzufügen (z. B. ababa oder baba), indem Sie mit this question folgen.

Ich versuche nun, das zu erweitern, indem ich Wiederholungen von Zeichen erlaube.

Zum Beispiel würde ich gerne auch abaaabab und aababaaa unterstützen können. In meinem speziellen Fall ist nur die a erlaubt zu wiederholen, aber eine Lösung, die das Wiederholen von b 's erlaubt, wäre auch nützlich.

die Regeln von der anderen Frage Gegeben:

expr ::= A | B 
A ::= "a" B | "a" 
B ::= "b" A | "b" 

... ich versuchte es erstreckt Wiederholungen zu unterstützen, etwa so:

expr ::= A | B 

# support 1 or more "a" 
A_one_or_more = A_one_or_more "a" | "a" 

A ::= A_one_or_more B | A_one_or_more 
B ::= "b" A | "b" 

... aber das Grammatik ist mehrdeutig. Ist es möglich, dass dies eindeutig gemacht wird, und wenn ja, könnte mir jemand helfen, es zu disambiguieren?

Ich verwende die lemon parser, die ein LALR (1) Parser ist.

Answer 1

Der Punkt des Parsing, im allgemeinen ist zu parsen; das heißt, bestimmen Sie die syntaktische Struktur einer Eingabe. Das ist wesentlich anders als einfach zu überprüfen, ob eine Eingabe zu einer Sprache gehört.

Zum Beispiel ist die Sprache, die mit dem regulären Ausdruck beschrieben wird, kann von beliebigen Wiederholungen von a und b besteht werden (a|b)*, die als

in BNF geschrieben werden können

S ::= /* empty */ | S a | S b 

Aber das ist wahrscheinlich die syntaktische Struktur nicht erfassen du versuchst zu definieren. Auf der anderen Seite, da Sie diese Struktur nicht angeben, ist es schwer zu wissen.

Hier ein paar mehr Möglichkeiten geben, die unterschiedlichen Parse-Bäume bauen:

S ::= E | S E 
E ::= A b | E b 
A ::= a | A a 

---

S ::= E | S E 
E ::= A B 
A ::= a | A a 
B ::= b | B b 

Wenn eine Grammatik zu schreiben, eine Sprache zu analysieren, ist es sinnvoll, durch Ziehen von Ihnen vorgeschlagenen Parse-Bäume zu beginnen . Normalerweise können Sie die Grammatik direkt aus der Form der Bäume schreiben, was zeigt, dass eine formale Grammatik in erster Linie ein Werkzeug ist, da es die Sprache so beschreibt, wie informelle Beschreibungen es nicht können. Durch die Verwendung eines Parser-Generators zum Umwandeln dieser Grammatik in einen Parser wird sichergestellt, dass der Parser die beschriebene Sprache implementiert. Zumindest ist das das Ziel.

Answer 2

Hier ist ein nettes Werkzeug zum Überprüfen Ihrer Grammatik online http://smlweb.cpsc.ucalgary.ca/start.html. Es akzeptiert tatsächlich the grammar you provided als eine gültige LALR (1) Grammatik.

Eine andere LALR (1) Grammatik, dass eine der ermöglicht reapeating, wäre:

S ::= "a" S | "a" | "b" A | "b" 
A ::= "a" S .