Eine Grammatik vom Typ 3 in der Chomsky-Hierarchie wird als reguläre 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 Typ 2, 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.
Reguläre Grammatik, Typ 3 Grammatik:
Alle Produktionen haben die Form:
Diese Grammatiken nennt man auch einseitig linear, links- bzw. rechtslinear.