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.