Grammatiktransformation für arithmetische Ausdrücke

9

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:

  1. 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
  2. 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.

  3. Ich schreibe diese ersten beiden Produktionen neu, indem ich von der nicht-L-rekursiven Produktion (die einfach Pder primäre Ausdruck ist) ausgehe und dem optionalen Schwanz folge T, den ich als Rest der Originalproduktion abzüglich des ersten linksrekursiven Nichtterminals definiere (das heißt, nur B E) gefolgt vom Schwanz T, oder der leer sein könnte:

    E --> P T
    T --> B E T |

    (Beachten Sie die leere Alternative für den Schwanz).

  4. 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 Estattdessen Pinnerhalb 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 Estatt Pin der ersten produktion für P.

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 Pfür E, aber ich kenne keine rechtliche Umwandlung zu rechtfertigen. Vielleicht wissen Sie, was der letzte fehlende Schritt ist?

SasQ
quelle
Bitte verwenden Sie LaTeX zum Formatieren. Siehe hier für eine Grundierung . (Siehe hier für eine Diskussion über die Eignung von LaTeX in diesem Fall.)
Raphael

Antworten:

8

Der fehlende Schritt:

E --> P T
T --> B E T |

schreibe E in T um:

E --> P T
T --> B P T T | 

Vereinfache T:

E --> P T
T --> B P T | 

Gleichwertig:

E --> P T
T --> {B P}

Und da bist du ja.

kena
quelle
1
Danke für eine gute Antwort :-) Jetzt sehe ich, was ich vermisst habe: Ich habe es umgekehrt ersetzt und das war das Problem. Trotzdem verstehe ich ein kleines Stück nicht: Woher weißt du, dass du das Ts sicher zu einem zusammenführen kannst T? 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.)
SasQ
Übrigens, warum wurde dieser Beitrag von cstheory.sx hierher verschoben und was ist der Unterschied? Ich würde gerne wissen, um Fehler in Zukunft zu vermeiden.
SasQ
2
@SasQ CSTheory ist nur für Fragen auf Forschungsebene in der theoretischen Informatik gedacht. Weitere Informationen finden Sie in den FAQ von CSTheory.
Juho
1
@SasQ: generiert und . Allgemeiner ist für jede Sprache. Beachten Sie, dass das leere Wort als rechte Seite von entscheidender Bedeutung ist. Dies gilt nicht für alle Grammatikfragmente, da . x * T x T | ε L * L * = L * L ε L + L +L +TxTTεxTxTεLL=LLεL+L+L+
Raphael
@ Raphael: Hat das etwas mit der Idempotenzregel für zu tun *? Ich habe das in "Dragon Book" (3.3, S.91) gesehen x** = x*. Ist das die gleiche Regel, die Sie verwendet haben?
SasQ