Formale Sprachen: Chomsky-Hierarchie

• (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).