Eine Grammatik vom Typ 1 in der Chomsky-Hierarchie wird als kontextsensitive Grammatik bezeichnet. Diese Formen von Grammatiken sind von ihrer Komplexität her nicht so effizient handhabbar, so dass sie bei der Beschreibung von Programmiersprachen keine Rolle spielen. Für den praktischen Einsatz genügen Typ 3 und Typ2 - reguläre und kontextfreie - Grammatiken - der Chomsky-Hierarchie, welche nicht so komplex sind.
In natürlichen Sprachen definiert die der Sprache zugeordnete Grammatik die Menge der korrekten und in der Sprache zulässigen Sätze. Analog hierzu werden auch Programmiersprachen mit Hilfe von Grammatiken beschrieben. Dadurch können nicht nur Sprachen beschrieben werden, sondern auch eine Klassifizierung von Sprachen bezüglich der für das Entwickeln von Programmiersprachen wesentlichen Eigenschaften vornehmen. Dies führt zu einer Hierarchie von Sprachklassen, der sogenannten Chomsky-Hierarchie.
Alphabet: Ein Alphabet A ist eine endliche Menge von Zeichen.
Grammatik: Eine Grammatik G ist ein 4-Tupel (T,N,P,s). Dabei bezeichnet:
- T die Menge der Terminalsymbole, das sind die Grundelemente der Sprache,
- N die Menge der Nichtterminale,
- P die Menge der Produktionen der Form a?b, mit deren Hilfe ein Syntaxbaum entwickelt wird. Jede Produktion besteht aus einer linken und einer rechten Seite bezüglich eines Herleitungspfeils. Die rechte Seite einer Produktion wird aus dem Nichtterminal auf der linken Seite hiergeleitet. Beispiel: Block »BEGIN Statement-Liste END;
- s bezeichnet das Startsymbol der Grammatik, aus dem jeder Satz in einer Sprache hergeleitet werden kann,
- V = T(u)N bezeichnet die Vereinigungsmenge der terminalen und nichtterminalen Symbole und
- V* bezeichnet die Strings über V
Die obige Definition hat den folgenden Hintergrund: Die Terminalsymbole sind die Grundelemente der Sprache. Bei Programmiersprachen sind das z.B. die Schlüsselworte wie Begin, End oder die arithmetischen Operatoren. Aus Terminalsymbolen können entsprechend den Konstruktionsregeln Sätze zusammengestellt werden. Die Konstruktionsregeln werden in Verbindung mit Grammatiken als Produktionen bezeichnet, da diese angeben, dass aus der linken Seite der Produktion die rechte Seite hergeleitet werden kann.
Kontextsensitive Grammatik, Typ 1 Grammatik: Alle Produktionen haben folgende Form:
Dabei ist die Länge von a kleiner gleich der Länge von b. Aus diesem Grund heißen diese Sprachen kontextsensitiv, da auf der linken Seite von Produktionen auch Terminalsymbole stehen können.