In dem Artikel Parsing Expressions by Recursive Descent von Theodore Norvell (1999) beginnt der Autor mit der folgenden Grammatik für arithmetische Ausdrücke:
E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v
Das ist ziemlich schlecht, weil es mehrdeutig und linksrekursiv ist. Also beginnt er damit, die linke Rekursion daraus zu entfernen, und sein Ergebnis ist als solches:
E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"
Aber ich kann nicht herausfinden, wie er zu diesem Ergebnis gekommen ist. Wenn ich versuche, die linke Rekursion selbst zu entfernen, gehe ich folgendermaßen vor:
Zunächst gruppiere ich die Produktionen, die keine Rekursion hinterlassen haben, in einer Gruppe und andere (linksrekursiv) in einer anderen Gruppe:
E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E // L-recursive E --> v | "(" E ")" | "-" E
Als nächstes benenne ich sie und berücksichtige sie für einfachere Manipulationen:
E --> E B E // L-recursive; B stands for "Binary operator" E --> P // not L-recursive; P stands for "Primary Expression" P --> v | "(" E ")" | U E // U stands for "Unary operator" B --> "+" | "-" | "*" | "/" | "^" P --> "-"
Jetzt muss ich mich nur noch mit den ersten beiden Produktionen befassen, die jetzt einfacher zu handhaben sind.
Ich schreibe diese ersten beiden Produktionen neu, indem ich von der nicht-L-rekursiven Produktion (die einfach
P
der primäre Ausdruck ist) ausgehe und dem optionalen Schwanz folgeT
, den ich als Rest der Originalproduktion abzüglich des ersten linksrekursiven Nichtterminals definiere (das heißt, nurB E
) gefolgt vom SchwanzT
, oder der leer sein könnte:E --> P T T --> B E T |
(Beachten Sie die leere Alternative für den Schwanz).
Diese beiden Produktionen kann ich jetzt wie folgt in EBNF umschreiben:
E --> P {B E}
Das ist fast das, was der Autor bekommt, aber ich habe
E
stattdessenP
innerhalb des Null-oder-Mehr-Wiederholungsmusters (den Schwanz). Die anderen Produktionen bekomme ich ganz gleich wie er:P --> v | "(" E ")" | U E B -> "+" | "-" | "*" | "/" | "^" U -> "-"
aber auch hier habe ich
E
stattP
in der ersten produktion fürP
.
Meine Frage lautet also: Was fehlt mir? Welche algebraische Transformation der Syntax muss ich jetzt durchführen, um genau die Form zu erhalten, die der Autor erhält? Ich habe Substitutionen für versucht E
, aber es führt mich nur in Schleifen. Ich vermute , dass ich irgendwie ersetzen P
für E
, aber ich kenne keine rechtliche Umwandlung zu rechtfertigen. Vielleicht wissen Sie, was der letzte fehlende Schritt ist?
Antworten:
Der fehlende Schritt:
schreibe E in T um:
Vereinfache T:
Gleichwertig:
Und da bist du ja.
quelle
T
s sicher zu einem zusammenführen kannstT
? Gibt es dafür eine Regel? (Ich vermute, es könnte irgendwie der Regel in der booleschen algebraischen Logik ähnlich sein, die "aa = a" sagt.)*
? Ich habe das in "Dragon Book" (3.3, S.91) gesehenx** = x*
. Ist das die gleiche Regel, die Sie verwendet haben?