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:
(abwechselnd Zustand und Zeichen)
Konfiguration: (Kellerinhalt, Rest der Eingabe )
repräsentiert (rechts-)abgeleitete Satzform
action kann sein:
wobei und jump.