Chomsky's Hierarchie

Je nach den Einschränkungen möglicher Produktionsformen lassen sich folgende Typen von Grammatiken unterscheiden:

Typ 0 keine Einschränkungen

Typ 1 kontext-sensitiv: alpha A = alpha omega . mit A V_N und alpha , , omega V^*.

Typ 2 kontext-frei: A = omega . mit A V_N und omega V^*.

Typ 3 regulär:

A = .

A = a .

A = a B .

mit A, B V_N und a V_T.

Programmiersprachen sind (mit wenigen Ausnahmen) kontextfrei, einzelne Symbole von Programmiersprachen (z.B. Zahlenkonstanten oder Namen) regulär.

Der Begriff der ``kontextfreien Sprachen'' wurde zuerst von Chomsky 1956 geprägt in einer Arbeit über natürliche Sprachen.

Mit BNF und EBNF können kontextfreie Sprachen definiert werden.