Kontextfreie Grammatiken

Category: 

Eine Kontextfreie Grammatik ist eine formale Grammatik, bei der immer genau ein Nichtterminalsymbol auf eine beliebig lange Folge von Terminalen und Nichtterminalen abgeleitet wird. KFGs sind insbesondere im Zusammenhang von Programmiersprachen wichtig, da deren Syntax durch eine KFG beschrieben wird.

Definition

Eine Kontextfreie Grammatik $G$ ist ein 4-Tupel $(N, T, P, S)$ mit den folgenden Eigenschaften:

  • Startsymbol $S \in N$
  • Nichtterminale $N$ und Terminale $T$ sind disjunkte Alphabete
  • $P$ ist eine endliche Teilmenge von $N \times (N \cup T)*$ und bezeichnet die Menge der Produktionen.

Nichtterminale sind Symbole aus dem Alphabet, welche durch Produktionen ersetzt werden und nicht im finalen Satz auftreten. Terminale hingegen dürfen nicht ersetzt werden und treten im finalen Satz auf.
Die Regeln einer KFG sind von der folgenden Form:
$A \rightarrow \alpha$ mit $A \in N, \alpha \in (N \cup T)*$
Das heißt auf der linken Seite einer Produktion steht immer exakt ein Nichtterminal, während auf der rechten Seite beliebig viele Nichtterminale und Terminale stehen.

Beispiel:
$S \rightarrow aSb$
$S \rightarrow \epsilon$ (ist das "leere" Zeichen)
Mit diesen beiden Produktionen wird die folgende Sprache definiert: $\{ a^n b^n \vert n \ge 0\}$.
Dieselbe Sprache lässt sich vereinfacht auch so schreiben:
$S \rightarrow aSb | \epsilon$ ( | entspricht "oder")

Häufig werden Produktionen auch so geschrieben: $S ::= \alpha$
Außerdem hat es sich eingebürgert, Nichtterminale groß zu schreiben und Terminale klein. Häufig werden dann auch die einfachen Anführungszeichen weggelassen. Also z.B. a anstatt 'a'.

Programmiersprachen Beispiel

Schauen wir uns nun ein etwas komplexeres Beispiel an, welches bereits an Programmiersprachen angelehnt ist.

G = ( N, T, P, S ) mit
N = { Program, StmtList, Stmt, While, If, Print, Cond, CondOp, StringOrIdent }
T = { 'while', '{', '}', 'if', 'print', '<', '>', '>=', '<=', '==', '!=', string, ident }
S = Program

P = {
  Program ::= StmtList
  StmtList ::= Stmt StmtList
  StmtList ::=
  Stmt ::= While | If | Print
  While ::= 'while' Cond '{' StmtList '}'
  If ::= 'if' Cond '{' StmtList '}'
  Print ::= 'print' StringOrIdent
  StringOrIdent ::= string | ident
  Cond ::= ident CondOp ident
  CondOp ::= '>' | '<' | '>=' | '<=' | '==' | '!='
}

Diese KFG ist nun in der Lage einfache Programme wie das folgende zu erkennen:

while a>b {
  if x==y {
    print "x ist gleich y"
  }
}

Auswertung eines Satzes

Um nun zu überprüfen ob ein Satz, wie z.B. das obige Programmbeispiel, auch von der Grammatik erzeugt werden kann, nutzt man häufig Ableitungsbäume.
Dabei beginnt man mit dem Startsymbol und wendet verschiedene Produktionen an, um schließlich den Satz zu erhalten. Die Blattknoten des Baumes liefern dabei die Terminale.

Schauen wir uns dazu noch ein anderes Beispiel an. Die Sprache der Palindrome. Ein Palindrom ist ein Wort, welches von vorne und hinten gelesen dasselbe ergibt.

S ::= 'a' S 'a' | 'b' S 'b'
S ::= 'a' | 'b' | $\epsilon$

Überprüfen wir nun ob "abba" ein Palindrom ist:

S => aSa => abSba => abba
//oder als Ableitungsbaum:
   S
  /|\
 a S a
  /|\
 b S b
   |
   $\epsilon$

Mehrdeutigkeit von Grammatiken

Eine Grammatik ist mehrdeutig, wenn man denselben Satz durch mehrere verschiedene Ableitungsbäume erzeugen kann. Betrachten wir dazu die Sprache, welche Zahlen addieren kann:

Expr ::= Expr '+' Expr
Expr ::= Number

Diese Sprache kann nun denselben Satz über mehrere Wege erzeugen. Ein kurzes Beispiel ist der Satz "1+2+3".

Diese Grammatik kann nun leicht eindeutig gemacht werden, indem man den Baum nur in eine Richtung wachsen lässt.

Expr ::= Number '+' Expr
Expr ::= Number

Nun kann der Baum nur noch nach rechts wachsen, da der linke Teil immer direkt zu Number abgeleitet wird.

Einschränkungen

Kontextfreie Grammatik haben die Einschränkung, das auf der linken Seite einer Produktion immer nur exakt ein Nichtterminal auftreten darf. Was passiert nun wenn man die rechte Seite einschränkt?
Je nach Einschränkung wird dadurch die Ausdrucksfähigkeit eingeschränkt, jedoch kann dies auch zu einem viel einfacheren Parser führen.
Drei besondere Einschränkungen sind reguläre Grammatiken, Chomsky-Normalform und die Greibach-Normalform.

Reguläre Grammatiken

Genau genommen unterscheidet man diese wiederum in rechtsregulär und linksregulär, wobei meist die rechtsreguläre Form genutzt wird, wodurch diese meist nur mit regulär bezeichnet wird.
Die rechte Seite einer Produktion darf höchstens ein Terminal und ein Nichtterminal enthalten. Die Reihenfolge dieser hängt davon ab, ob die Grammatik rechts- oder linksregulär ist.
Genauer gesagt müssen die Produktionen die folgende Form haben:
$A \rightarrow b B$ mit Terminal $b$ und Nichtterminal $B$ (bzw. $A \rightarrow B b$ bei linksregulären Grammatiken)
$A \rightarrow b$ mit Terminal $b$
$A \rightarrow \epsilon$

Für jede rechtsreguläre Grammatik existiert eine linksreguläre Grammatik, welche die selbe Sprache erzeugt und umgekehrt.

Es gibt nicht für jede kontextfreie Grammatik eine äquivalente reguläre Grammatik. Beispielsweise kann man die Sprache $L=\{a^n b^n \}$ nicht durch eine reguläre Grammatik erzeugen.

Chomsky-Normalform

Zu jeder Kontextfreien Sprache gibt es eine Grammatik in Chomsky-Normalform. Dadurch sind beide gleich mächtig.
Um der Chomsky-Normalform zu genügen, müssen die Produktionen von der folgenden Form sein:
$A \rightarrow BC$ mit $B,C \in N$
$A \rightarrow a$ mit $a \in T$
$S \rightarrow \epsilon$ (nur erlaubt, wenn $S$ niemals auf der rechten Seite einer Regel auftaucht)
Weniger formel ausgedrückt bedeutet das, dass ein Nichtterminal entweder auf exakt zwei andere Nichtterminale oder auf exakt ein Terminal abgeleitet wird. Die Ausnahme bildet das Startsymbol S, welches auch auf $\epsilon$ abgebildet werden darf, aber nur, wenn S niemals auf der rechten Seite einer Produktion auftaucht.

Greibach-Normalform

Wie auch schon bei der Chomskyform, gilt auch hier, dass jede kontextfreie Sprache in die Greibachform umgewandelt werden kann.
Eine Grammatik $G$ ist in Greibach-Normalform, wenn alle Produktionen aus $P$ die Form $A \rightarrow b B_1 ... B_k$ mit $k \ge 0$ haben, wobei $b$ ein Terminal ist und die $B_i$ für $i \in \{1,...,k\} $ Nichtterminale sind. Anders ausgedrückt bedeutet dies, das jede Produktion ein Nichtterminal auf ein genau Terminal, gefolgt von beliebig vielen Nichtterminalen abbildet. Außerdem darf nur das Startsymbol auf $\epsilon$ abgebildet werden, dies aber auch nur, wenn das Startsymbol niemals auf der rechten Seite einer Produktion auftaucht.

Auf den folgenden Seiten sind nun noch Aufgaben zu kontextfreien Grammatik zu finden.