Theoretische Informatik
Kontextfreie Grammatik
Der wichtigste Grammatiktyp ist die kontextfreie Grammatik. Eine kontextfreie Grammatik entspricht einer Typ-2-Grammatik der Chomsky-Hierarchie. Kontextfreie Grammatiken sind ausdrucksstark genug für Programmiersprachen und ermöglichen zugleich effiziente Parsing-Verfahren.
Definition
Definition: Sei G = (V, T, P, S) eine Grammatik, wobei V die Menge der Variablen ist, T die Menge der Terminalzeichen, P die Menge der Produktionen und S das Startsymbol. Sei ferner A = V ∪ T das Gesamtalphabet.
Eine Produktion heißt kontextfrei, wenn sie von der Form
X
u
mit X ∈ V und u ∈ A* ist.
Die Grammatik G heißt kontextfrei, wenn jede ihrer Produktionen kontextfrei ist.
Eine Sprache heißt kontextfrei, wenn es eine kontextfreie Grammatik gibt, die sie erzeugt.
Die Produktionen einer kontextfreien Grammatik zeichnen sich also dadurch aus, dass auf ihrer linken Seite stets nur eine einzelne Variable steht. Auf der rechten Seite darf ein beliebiges Wort stehen, auch das leere Wort. Die Bezeichnung kontextfrei rührt daher, dass die Ersetzung Xu 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 aXbaub eine kontextsensitive Produktion, die eine Ersetzung von X durch u nur im Kontext a...b erlaubt.
Beispiele
Beispiel: Die kontextfreie Grammatik mit den Produktionen
| S | | aSb | ε |
erzeugt die Sprache { anbn | n ∈ ℕ0 }.
Beispiel: Die kontextfreie Grammatik mit den Produktionen
| expr | | term | term + expr |
| term | | factor | factor * term |
| factor | | number | - number | ( expr ) |
| number | | digit |
| digit | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
erzeugt die Sprache aller arithmetischen Ausdrücke mit einstelligen Zahlen und den Operationen Addition, Multiplikation sowie Vorzeichenumkehr. Die Variablen der Grammatik sind hier Wortsymbole wie expr, term usw. Das Startsymbol ist expr.
Kontextfreie Sprachen
Sprachen, die von kontextfreien Grammatiken erzeugt werden, heißen der Einfachheit halber kontextfreie Sprachen. Um zu zeigen, dass eine Sprache kontextfrei ist, genügt es, eine kontextfreie Grammatik anzugeben, die diese Sprache erzeugt. Wir werden sehen, dass es auch noch eine andere Möglichkeit gibt, und zwar einen nichtdeterministischen Stackautomaten anzugeben, der die Sprache erkennt.
Für den Beweis, dass eine Sprache nicht kontextfrei ist, steht als Hilfsmittel ähnlich wie bei den regulären Sprachen ein Pumping-Lemma für kontextfreie Sprachen, auch uvwxy-Theorem genannt, zur Verfügung. Eine einfache Sprache, die nicht kontextfrei ist, ist die Sprache { anbncn | n ∈ ℕ }.
Die kontextfreien Sprachen bilden eine Sprachklasse der Chomsky-Hierarchie, daher werden sie auch als Typ-2-Sprachen bezeichnet.
Normalformen kontextfreier Grammatiken
Auf der linken Seite einer kontextfreien Produktion steht stets eine einzelne Variable. Auf der rechten Seite steht ein beliebiges Wort. Was geschieht, wenn der Form der rechten Seite Beschränkungen auferlegt werden? Wird dadurch die Ausdrucksstärke der Grammatik eingeschränkt?
Wir haben bereits gesehen, dass die Beschränkung der rechten Seite der Produktionen auf die Form aY oder a oder ε mit a ∈ T und Y ∈ V die Ausdrucksstärke der Grammatik einschränkt, nämlich auf die regulären Sprachen oder Typ-3-Sprachen.
Eine scheinbar geringfügige Lockerung dieser Beschränkung, indem statt aY auch aY0 ... Yk-1 zugelassen wird, führt zu keiner Einschränkung der Ausdrucksstärke der Grammatik. Grammatiken in dieser Form, der sogenannten Greibach-Normalform, sind geeignet, beliebige kontextfreie Sprachen zu erzeugen.
Eine andere wichtige Normalform für kontextfreie Grammatiken ist die Chomsky-Normalform. Bei der Chomsky-Normalform stehen auf der rechten Seite jeder Produktion entweder nur genau zwei Variablen oder ein einzelnes Terminalzeichen. Als Ausnahme ist die Produktion Sε erlaubt, um das leere Wort zu erzeugen.
Weiter mit: [Chomsky-Normalform] [Stackautomat] [Kontextsensitive Grammatik] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 26.01.2003 Updated: 16.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden