Algorithmische Umsetzung von Kellerautomaten

Die Syntaxanalyse von Wörtern kann - wie bekannt - nach der Top-Down bzw. Bottom-Up Methode erfolgen. Will man das Wort Top-Down analysieren, kann man je nach Grammatik eine rekursive Analyse bzw. eine Analyse mit Vorausschau (look ahead) durchführen.

Bei der rekursiven Analyse wird mithilfe des Backtrackingverfahrens der richtige Syntaxbaum aufgebaut. Die Auswahl der gewählten Ersetzung ist also nicht vom nächsten Eingabezeichen abhängig. Als Beispiel sei die folgende Grammatik für wohlgeformte Klammerterme gegeben:

G1 = (VN,VT,P,S)
VN = {S}
VT = {(,)}
P = {S -> () | (S) | SS}

Betrachten wir die Linksableitung des Wortes "((()())())":

S -> (S) -> (SS) -> ((S)S) -> ((SS)S) -> ((()S)S) -> ((()())S) -> ((()())())

Diese Herleitung wird von einem Kellerautomaten nachvollzogen, indem er beim Akzeptieren des Wortes wie folgt vorgeht:

Restliches Eingabewort  Kellerinhalt  Ersetzungsregel
                              S#      S -> (S)
       ((()())())#          (S)#
        (()())())#           S)#      S -> SS
        (()())())#          SS)#      S -> (S)
        (()())())#        (S)S)#
         ()())())#         S)S)#      S -> SS
         ()())())#        SS)S)#      S -> ()
         ()())())#       ()S)S)#
           ())())#         S)S)#      S -> ()
           ())())#        ())S)#
              ())#           S)#      S -> ()
              ())#          ())#
                 #             #

Die Auswahl der jeweiligen Regel erfolgt gleichsam spontan; der Automat weiß sozusagen intuitiv, welche Regel er jeweils anwenden muss. In Gestalt eines nichtdeterministischen Algorithmus:

push(#), push(S)
solange top(keller) ungleich # wiederhole
  falls top(keller) gleich
    S: dann pop, push[(S)] oder push[SS] oder push[()]
    (: dann pop, lies nächstes Eingabezeichen
    ): dann pop, lies nächstes Eingabezeichen
  ende falls
ende wiederhole

Ein Programm, das diesen Kellerautomaten realisiert, muss den in obigem Algorithmus steckenden Nichtdeterminismus dadurch überwinden, dass es immer dann, wenn es aufgrund der Anwendung einer falschen Regel in eine Sackgasse geraten ist, zum jeweils letzten Wahlpunkt zurücksetzt (Backtracking). Es startet eine rekursive Suchprozedur, welche alle drei Syntaxregeln aufruft und damit einen Baum mit Verzweigungsordnung 3 traversiert (recursive descent parser).

Bei dem oben betrachteten Verfahren hängt die benötigte Zeit für die Syntaxanalyse davon ab, in welchem Teil des Baumes die betrachtete Klammerstruktur erzeugt wird. Insbesondere für falsche Klammerfolgen muss der gesamte Baum durchlaufen werden, was bei einigermaßen tiefen Bäumen schon einige Zeit dauern kann. Dieses Problem kann bei der benutzten Grammatik auch nicht gelöst werden, da erst nach dem Lesen der gesamten Klammerfolge entschieden werden kann, ob der Baum mit einer Ersetzung S -> (S) oder S -> SS beginnt. Selbst ein einmaliges Lesen der gesamten Klammerfolge reicht nicht, denn die Argumentation lässt sich auf jeden weiteren Schritt des Analyseprozesses übertragen. Bei dem gewählten Regelsystem muss also für jede Regelanwendung die gesamte Klammerfolge gelesen werden. Damit ist die benutzte Grammatik für praktische Anwendungen unbrauchbar.

Für eine effiziente Syntaxanalyse wäre es günstig, wenn nach dem Lesen des jeweils nächsten Zeichens der Klammerstruktur entschieden werden könnte, welcher Weg im Baum zu nehmen ist. Dafür wird eine Grammatik benötigt, die sich das Einfügen oder Anhängen weiterer Klammersysteme "offenhält". Die folgende Grammatik leistet dies

G2 = (VN,VT,P,S)
VN = {S}
VT = {(,)}
P = {S -> (S)S | nichts}

Damit kann man durch die Vorausschau um ein Zeichen (look ahead) bei jeder gelesenen öffnenden Klammer eine Zeichenfolge erzeugen, in der noch alle Möglichkeiten enthalten sind. Beim Lesen schließender Klammern werden die überflüssigen Nichtterminalsymbole wieder entfernt. Ist das Ende der zu analysierenden Klammerstruktur erreicht, so werden die noch "überhängenden" Nichtterminalsymbole ebenfalls entfernt. Diese Grammatik analysiert eine Klammerstruktur so, dass bei jedem Analyseschritt eine anzuwendende Regel gefunden wird. Der Zeitbedarf hängt damit nur von der Länge der Klammerzeichenfolge ab und nicht von der Stellung dieser Zeichenfolge im Syntaxbaum.

Für LR(1)- und LL(1)-Grammatiken lässt sich der Analyseprozess tabellarisch beschreiben. Bezeichnen wir den Analysestring als Keller, dann ist es sinnvoll, die schon richtig erzeugten Zeichen aus dem zu analysierenden Wort und dem Keller zu entfernen. So ergibt sich aus dem nächsten Eingabezeichen und dem obersten Kellerzeichen jeweils die anzuwendende Regel.

Dieselbe Sprache kann also durch unterschiedliche Grammatiken beschrieben werden. Sind diese Grammatiken kontextfrei, so ist sichergestellt, dass sie überhaupt analysiert werden können, etwa durch einen Kellerautomaten. Durch die Wahl einer besonderen Grammatik kann dann erreicht werden, dass das Wortproblem (also die Frage, ob ein Satz zu einer gegebenen Sprache gehört) in vertretbarer Zeit entschieden werden kann.