Top-Down/Bottom-Up (Wiederholung)

Top-Down/Bottom-Up

$$Id: tdbu.tex,v 1.1 2003/12/17 12:34:10 joe Exp $$

Parsen durch rekursiver Abstieg ist top-down-Methode, erzeugt Links-Ableitung.

Operator-Präzedenz-Parsen ist bottom-up-Methode, erzeugt Rechts-Ableitung. (Beispiel!)

Beide Methoden lesen die Eingabe von links!

Top-Down/Bottom-Up und Eindeutigkeit

Für effizientes Parsen möchte man kein Backtracking, also Eindeutigkeit (der Auswahl der anzuwendenden Regel).

Das ist bei Top-Down-Parsern eine starke Einschränkung, aber bei Bottom-Up-Parsern nicht so gravierend:

diese können Entscheidungen ,,in die Zukunft``verschieben, indem Zwischenergebnisse auf dem Stack gespeichert werden.

Shift und Reduce

$$Id: shiftreduce.tex,v 1.1 2003/12/17 12:34:10 joe Exp $$

LR-Parser: deterministischer endlicher Automat mit Keller.

Kellerinhalt: $s_0 X_1 s_1 X_2 \ldots X_m s_m$

(abwechselnd Zustand und Zeichen)

Konfiguration: (Kellerinhalt, Rest der Eingabe $a_i a_{i+1} \ldots a_n$)

repräsentiert (rechts-)abgeleitete Satzform

$$X_1 X_2 \ldots X_m a_i a_{i+1} \ldots a_n$$

action$(s_m, a_i)$ kann sein:

• shift $s$: zu $(\ldots X_m s_m a_i s, a_{i+1} \ldots)$
• reduce $A \to b$: zu $(\ldots X_{m-r} s_{m-r} A s, a_i a_{i+1} \ldots)$,

  wobei $\vert b\vert=r$ und $s=$jump$(s_m, a_i)$.