Operator-Präzedenz-Parser

Operator-Präzedenz-Parser

$$Id: op.tex,v 1.3 2003/12/08 14:26:47 joe Exp $$

Ausdruck -> Literal | ( Ausdruck ) 
   | Ausdruck + Ausdruck
   | Ausdruck * Ausdruck | ...

Eingabe: $A_1 o_1 A_2 o_2 A_3 o_3 A_4$

können nicht sofort ausrechnen, Benutzen Keller für Zwischenresultate.

Entscheide zw. Push (warten) und Pop (rechnen) anhand der Präzedenz der Operatoren (müssen mit gekellert werden).

Operator-Grammatiken

Def: eine CFG heißt Operator-Grammatik, falls für jede Regel $(l \to r) \in R$ gilt:

• $r \neq \epsilon$
• $r$ enthält keine direkt benachbarten Variablen

Wir benutzen Prioritäts-Relationen $<$ auf Terminalen.

Für Wort $c w \$$ (mit Links- und Rechtsmarkierung):

Füge Relationen zwischen Terminalen ein (üebrspringe dabei Variablen): z. B. $c < a_1 < a_2 > \ldots a_n > \$$

Suche am weitesten links stehendes $>$, dann das nächste davon links stehende $<$, wende Regel auf Teilwort $< \ldots >$ an.

Implementierung mit Stack

Konstruiere Ableitungsbaum zu geg. Operator-Grammatik mit Präzedenz

Interface Stack: push(), pop(), top, Interface Eingabe (Scanner): next()

push ('c'); -- linke Rand-Markierung
Token n = next ();
while (('c' != top) || ('$' != n)) {
  if ( top < n ) {
    push (n); n = next ();
  } else {
    while ( top > n ) { pop (); }
  }
}

Bemerkungen

stark vereinfacht. Es fehlen:

• Syntaxbaum bauen/semantisch Aktion ausführen
• Assoziativität (Links, Rechts, keine)
• Fehlerbehandlung

Aufgaben (Praktikum):

• Welche Präzedenz entspricht der üblichen Arithmetik (Operatoren $+, -, *, /, \uparrow$)?
• Welche Präzedenz bekommen Klammern?
• (Kombination mit Parser mit rekursivem Abstieg, für Funktions-Aufrufe in Ausdrücken?)

Übung (10./12. 12. 03) Op-Präzedenz-Parser

$$Id: bastelop.tex,v 1.1 2003/12/10 10:13:39 joe Exp $$

Dateien hier: http://www.imn.htwk-leipzig.de/~waldmann/ws03/compilerbau/programme/parser/

kompilieren mit: gmake, erzeugt Echse: operator

ausführen: echo "1 + 2 * 3 + 4" | ./operator

• semantische Aktionen (Rechnungen) hinzufügen.

  Dazu stack.[ch] erweitern (für Zwischenergebnisse).

  (Neuer Datenbereich int valstack [],
  aber alter Stack-Pointer.)

• Klammern, Bsp 3 - 4 * (5 + 6)
• Fehlererkennung, Bsp 3 + 5 * / 6
• Assoziativität, Bsp 10 - 8 - 2, 2 ^ 3 ^ 2