5. Kontextfreie Sprachen

5.1 Ableitungen und Ableitungsbäume

Definition (Ableitung) Sei \(G\) eine Grammatik mit Startsymbol \(S\). Die Ableitung eines Wortes \(\alpha\) ist eine Sequenz von Wortformen \( w_0, w_1, \dots, w_n\) mit \(w_0 = S, w_n = \alpha\) und \(w_{i-1} \Longrightarrow w_i\).

Das folgende Beispiel ist Beispiel 3.22 aus dem Buch von Aho und Ullman. Wir betrachten die klassische kontextfreie Grammatik für arithmetische Ausdrücke mit Klammerung: \begin{align*} (1)\ E \rightarrow & E + T \\ (2)\ E \rightarrow & T \\ (3)\ T \rightarrow & T * F \\ (4)\ T \rightarrow & F \\ (5)\ F \rightarrow & (E) \\ (6)\ F \rightarrow & a \\ \end{align*} wobei \(E\) das Startsymbol ist. Hier ist ein Beispiel einer Ableitung von \(a * (a+a)\) von der obigen Grammatik. \begin{align*} E & \stackrel{2}{\Longrightarrow} T \stackrel{3}{\Longrightarrow} T * F \stackrel{4}{\Longrightarrow} F * F \stackrel{6}{\Longrightarrow} a * F & \\ & \stackrel{5}{\Longrightarrow} a * (E) \stackrel{1}{\Longrightarrow} a * (E + T) \stackrel{2}{\Longrightarrow} a * (T + T) & \\ & \stackrel{4}{\Longrightarrow} a * (F + T) \stackrel{6}{\Longrightarrow} a * (a + T) \stackrel{4}{\Longrightarrow} a * (a + F) \stackrel{6}{\Longrightarrow} a * (a + a) & \end{align*} Insbesondere ist es eine Linksableitung, das heißt, in jedem Schritt wird das am weitesten links stehende Nichtterminal expandiert. In der Tat reicht es, nur die Nummer der angewandten Regel anzugeben (da ja klar ist, welches Nichtterminal expandiert werden muss). Die obige Ableitung kann also kompakt durch die Zahlenfolge 23465124646 repräsentiert werden.

Betrachten wir im Folgenden ein weiteres Beispiel einer Ableitung, in diesem Falle eine Rechtsableitung, in der in jedem Schritt das am weitesten rechts stehende Nichtterminal expandiert wird:

\begin{align*} E & \stackrel{2}{\Longrightarrow} T \stackrel{3}{\Longrightarrow} T * F \stackrel{5}{\Longrightarrow} T * (E) \stackrel{1}{\Longrightarrow} T * (E+T) \stackrel{4}{\Longrightarrow} T * (E+F) & \\ & \stackrel{6}{\Longrightarrow} T * (E+a) \stackrel{2}{\Longrightarrow} T * (T + a) \stackrel{4}{\Longrightarrow} T * (F + a) & \\ & \stackrel{6}{\Longrightarrow} T * (a + a) \stackrel{4}{\Longrightarrow} F * (a + a) \stackrel{6}{\Longrightarrow} a * (a + a) & \end{align*} Rechtsableitungen können auch kompakt als Zahlenfolge repräsentiert werden. Allerdings geben wir Rechtsableitungen immer in umgekehrter Reihenfolge an, also von hinten nach vorne, in diesem Falle also nicht 2351... sondern 64642641532.

Beachten Sie, dass wir es hier mit einer eindeutigen Grammatik zu tun haben, es also nur einen Syntaxbaum gibt:

Rechtsableitung und Linksableitung sowie deren Codierung als Zahlenfolge spiegeln also nur zwei verschiedene Weisen wieder, den Baum auszugeben.

def treeToLeftDerivation (tree):                        
  print tree.ruleAtRoot (bzw. drucke nur die Nummer der Regel)
  for child in tree.children (from left ro right):
      treeToLeftDerivation(child)

def treeToRightDerivation (tree):                        
  for child in tree.children (from left ro right):
      treeToLeftDerivation(child)
  print tree.ruleAtRoot (bzw. drucke nur die Nummer der Regel)

Beachten Sie, dass wir in beiden Fällen die Liste Kinder von links nach rechts durchgehen.