- (Typ 0) aufzählbare Sprachen
(beliebige Grammatiken, Turingmaschinen)
- (Typ 1) kontextsensitive Sprachen
(monotone Grammatiken, linear beschränkte Automaten)
- (Typ 2) kontextfreie Sprachen
(kontextfreie Grammatiken, Kellerautomaten)
- (Typ 3) reguläre Sprachen
(rechtslineare Grammatiken, reguläre Ausdrücke, endliche Automaten)
Tokenklassen sind meist reguläre Sprachen.
Programmiersprachen werden kontextfrei beschrieben
(mit Zusatzbedingungen).
Johannes Waldmann
2008-01-23
