Compilerbau: die syntaktische Analyse
Willemers Informatik-Ecke

Die syntaktische Analyse kann eine kontextfreie Sprache erkennen und arbeitet auf der Basis eines Kellerautomaten.

Aus dem Strom der Tokens, die der Scanner ihm liefert, bildet der Parser einen Ableitungsbaum. Am Beispiel sieht man, wie aus einem einfachen mathematischen Ausdruck ein Baum entsteht:

6*4+3*5

+
/ \
* *
/ \ / \
6 4 3 5
Da ein Baum eine rekursive Datenstruktur ist, erklärt sich auch, warum ein Kellerautomat, also ein Automat mit einem Stack benötigt wird.