Kleines Nachschlagewerk Informatik
Kontextfreie Sprachen
Worum geht es?
Reguläre Sprachen haben einfache Ersetzungs-/Produktionsregeln. Man wird feststellen, dass man damit geschachtelte Klammerausdrücke nicht darstellen kann. Es soll gezeigt werden, wie eine Grammatik aussehen kann, die derartiges ermöglicht.
Produktionsregeln
Es gilt: Auf der linken Seite steht ein Nichtterminalsymbol. Dieses kann durch ein Terminal-, ein Nichtterminal oder verschiedene Kombinationen aus Terminal- und Nichtterminalsymbolen ersetzt werden. Die Einschränkung der regulären Sprachen, das rechts nur ein TS oder eine Kombination TS-NTS stehen darf, wird also aufgehoben.

Damit sind solche Ersetzungsregeln möglich:

      A -> BC
      A -> aBc
      A -> BCd
      usw.
            


Es gibt eine Normalform nach Chomsky, welche die Möglichkeiten nicht einschränkt. Bei ihr gilt, dass rechts nur zwei Nichtterminalsymbole oder ein Terminalsymbol stehen dürfen.

      A -> BC
      A -> d
            
Beispiel - Klammern
Klammern können geschachtelt sein, es müssen jedoch immer aufgehende und schließende Klammern zueinander passen.

Betrachtet man nur die Klammern, ergeben sich folgende Beispiele: () oder (()) oder ()()(()). Das Startsymbol kann also in zwei Klammern enden oder in ein System aus geschachtelten Klammern. Die Ersetzungsregeln sind S->() und S->(S). Damit kann man Klammern schachteln, nicht jedoch aneinander setzen. Dazu benötigt man eine dritte Regel: S->SS.

      S -> SS
      S -> (S)
      S -> ()
            
Das Beispiel wurde dem Buch Modrow: Theoretsiche Informatik mit Delphi entnommen. Nachfolgende Grafik soll die Analyse mit beiden Regelsystemen zeigen.



Von der Grammatik zum Automaten
Der zur kontextfreien Grammatik äquivalente Automat ist der Kellerautomat. Wie man am Klammerbeispiel sieht, braucht man nur ein Kellerzeichen, die aufgehende Klammer. Eine schließende Klammer entfernt einfach ein Zeichen.





JFlap bietet auch Parsetabellen, die einem zum aktuell bearbeiteten Zeichen die Speicherinhalt zeigen.



Programmiersprachen
Programmiersprachen sind (i.A.) kontextfreie Sprachen. Somit kann ihre Syntax z.B. in BNF dargestellt werden.