Konzepte der Syntaxanalyse

Sprachdarstellung durch Grammatiken

Grammatikregeln werden in EBNF notiert, moderner ist die Darstellung mit -> statt ::=. Das kann dauch auch sinnvoll zur Ableitungsrelation => erweitert werden.

Die lexikalische Analyse kann schon mit regulären Grammatiken erledigt werden, die Sprachklasse entspricht den regulären Ausdrücken bzw endlichen Automaten, was man einfach zeigen kann. (->Übungen)

Grammatikalisch richtige Sätze einer Sprache - im Spezialfall syntktisch korrekte Programme - sind die Wörter, die sich aus dem Startsymbol ableiten lassen:

L(G) = { w | S =>* w }

Programme mit eindeutiger Bedeutung gewinnt man am einfachsten, wenn schon die syntaktische Ableitung - der Strukturbaum - eindeutig ist. Gilt das für alle Wörter ener Grammatik, redet man auch von eindeutiger Grammatik

Erzeugen des Strukturbaums

Man kann eine Strukturbaum durch wildes Probieren oder geordnetes Probieren (top-down oder bottom-up backtracking Verfahren) erstellen. Das ist zwar i.a. keineswegs effizient, aber immerhin.

Für Backtracking muss man sich merken, was man schon hatte. Will man das mit Automaten realisieren, benötigt man also einen Automaten mit Gedächnis, z.Bsp. einen Kellerautomaten. Wir betachten das Konzept genauer, weil man das deterministisch ausbauen kann.