Kontextfreie Grammatik

Eine Grammatik analog der Typ-2-Grammatik der Chomsky-Hierarchie wird als kontextfreie Grammatik bezeichnet. Programmiersprachen können in wesentlichen syntaktischen Eigenschaften durch kontextfreie Grammatiken beschrieben werden.

Das Modell der kontextfreien Grammatiken in der Sprachbeschreibung erlaubt, die Analyse bzw. Synthese der Sätze der Sprache durch Zerlegung in voneinander unabhängige Abschnitte vorzunehmen. Der Verzicht auf den Kontext vereinfacht somit die Struktur der Grammatik.

Eine Grammatik ist ein Quadrupel G = (N,T,R,S) mit

  • der endlichen Menge von Symbolen, auch Nichtterminale, Nonterminals oder Variablen genannt,
  • der endlichen Menge von sprachbildenden terminalen Zeichen, den Terminalen T,
  • der endlichen Menge R von Produktionsregeln, auch Produktionen oder Regeln genannt und
  • dem Startsymbol S eines Satzes.

Dabei gilt zudem:

  • die Nichtterminale N und die Terminale sind disjunkt (das bedeutet elementfremd),
  • das Startsymbol S ist Teil der Menge der Nonterminals N und
  • für das Gesamtalphabet gilt A = N u T.
Kontextfreie Grammatik

Kontextfreie Grammatik

Das bedeutet, dass die Produktionsregeln einer kontextfreien Grammatik dadurch gekennzeichnet sind, dass auf deren linker Seite stets nur eine Variable steht. Die Bezeichnung kontextfrei rührt daher, dass die Ersetzung X durch u in jedem Kontext zulässig ist; d.h. wenn X irgendwo in einem Wort w vorkommt, darf es durch u ersetzt werden. Im Gegensatz dazu ist etwa aXb durch aub eine kontextsensitive Produktion, die eine Ersetzung von X durch u nur im Kontext a..b erlaubt.

Die kontextfreien Grammatiken sind für die Theorie der Programmiersprachen und die damit eng verbundenen Fragen der syntaktischen Analyse auf Grund ihrer übersichtlichen Struktur sehr bedeutungsvoll und bereits weitgehend untersucht worden. Die bekannten Programmiersprachen können in ihren wesentlichen syntaktischen Eigenschaften durch kontextfreie Grammatiken beschrieben wird. Die Sprachimplementierungen gehen von der Definition der Syntax der Programmiersprachen durch eine kontextfreie Grammatik aus, durch die ein Syntaxanalyse- Algorithmus festgelegt wird.

Informationen zum Artikel
Deutsch: Kontextfreie Grammatik
Englisch: contextless grammar
Veröffentlicht: 25.04.2010
Wörter: 293
Tags: Entwicklung, Codierung
Links: Analog, Chomsky-Hierarchie, Programmiersprache, Sprache, Zeichen
Übersetzung: EN
Sharing: