Reguläre Grammatik

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.
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.

Reguläre Grammatik, Typ 3 Grammatik:

Alle Produktionen haben die Form:

Produktionsformen der regulären Grammatik

Produktionsformen der regulären Grammatik

Diese Grammatiken nennt man auch einseitig linear, links- bzw. rechtslinear.

Informationen zum Artikel
Deutsch: Reguläre Grammatik
Englisch: regular grammar
Veröffentlicht: 09.04.2012
Wörter: 344
Tags: Entwicklung, Codierung
Links: Chomsky-Hierarchie, Programmiersprache, Indium, Sprache, Sprache
Übersetzung: EN
Sharing: