Problem der Syntax-Analyse

Bei der Syntax-Analyse gibt es zwei prinzipielle Methoden:

Top-Down-Parsing: Beginnend from Startsymbol S werden in Abhängigkeit von der Eingabe Schritt für Schritt Ersetzungen durchgeführt, so daß wir am Ende eine Folge von Terminals haben, die der Eingabe entspricht.

Bottom-Up-Parsing: Die Eingabe wird in eine Folge von Terminals verwandelt, die nach und nach unter umgekehrten Verwendung der Produktionsregeln so reduziert wird, daß nur das Startsymbol S übrig bleibt.

Unabhängig von der Wahl der Methode ist das Problem in der generellen Form nicht trivial. Es wird sogar nur durch die Verwendung ziemlich enger Restriktionen überhaupt entscheidbar.

Aus der Anwendung der Produktionsregeln ergibt sich (implizit oder explizit) eine Baumstruktur, die für die Interpretation der Eingabe genutzt werden kann.

Die mit Abstand einfachste Methode zur Syntax-Analyse (sofern anwendbar) ist das recursive descent parsing, mit der sich Top-Down-Parser bauen lassen. Dies ist auch die einzige Methode, die im Rahmen dieser Vorlesung näher vorgestellt wird...