Zur Themenübersicht     

Syntaxbäume für wohldef. Klammerpaare
und
Erkennen durch einen Kellerautomaten

Mit einer Grammatik 1

Zur Erinnerung hier noch einmal die 
Sprachdefinition für wohldefinierte Klammerpaare:

Terminale :        T = { ( , ) }

Nichtterminale : N = { S }     Der Einfachheit halber lassen wir die spitzen Klammern weg

Grammatik 1:     S ::= ( )      Regel1
                         S ::= ( S )   Regel2
                         S ::= S S    Regel3

 

Die Herleitung des Ausdrucks  ( ( ) ( ) )  mit Hilfe eines Syntaxbaumes (Regeln in grün) sieht so aus:

 

Wir machen uns die Herleitung noch einmal ganz langsam klar:

Wir beginnen mit dem Startsymbol :

S

Ersetzen von S nach Regel 2 liefert

(S)

Ersetzen von S nach Regel 3 liefert

(SS)

Regel 1 für das linke S liefert:

(( )S)

noch einmal Regel 1 liefert das gewünschte Ergebnis:

(( )( ))

Algorithmus:

Der Algorithmus zum Herleiten eines wohldef. Klammerpaares lautet:

Im letzten Teil erkennen wir einen rekursiven Algorithmus. Daraus ergibt sich, dass das Erkennen durch rekursive Prozeduren oder mit Hilfe eines Stacks durchzuführen ist. Das eigentliche Problem liegt offensichtlich darin, die jeweils geeignete Regel zu finden.

Das Erkennen durch rekursive Prozeduren (der sog. rekursive Abstieg im Syntaxbaum) behandeln wir später. Im Rahmen der Automatentheorie beschäftigen wir uns zuerst mit dem Erkennen durch einen Kellerautomaten. (= Automat mit Stack)

Erkennen mit Hilfe eines Kellerautomaten:

Die Arbeitsweise ist vom Prinzip einfach: Auf den Keller legen wir immer den noch nicht bearbeiteten rechten Teil des bisher aus dem Startsymbol hergeleiteten Ausdrucks. Der noch nicht bearbeitete Teil ist immer der rechte Teil des Ausdrucks ab dem ersten Nichtterminalsymbol. 

Der zu erkennende Ausdruck muss natürlich auf dem Eingabeband liegen. Damit ergibt sich folgender Algorithmus für den Kellerautomaten:

  • Nimm das erste Eingabezeichen (EZ) vom Eingabeband
  • Lege das Startsmbol der Grammatik in den Keller
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
    • WENN es ein Nichtterminalsymbol ist
    • DANN  lege die Zeichen der passenden Regel nacheinander 
      auf den Keller
                (Wenn es keine passende Regel gibt, 
                gehört die Eingabefolge nicht zur Sprache!)
    • SONST vergleiche das Eingabezeichen mit dem Kellerzeichen
                 (Wenn immer die passenden Regeln genommen wurden,
                  dann müssen die Zeichen übereinstimmen)
      • WENN die Zeichen übereinstimmen
      • DANN gehe zum nächsten Eingabezeichen
      • SONST gehört die Eingabefolge nicht zur Sprache

Der Algorithmus ist so formuliert, dass er nicht nur für wohldefinierte Klammerpaare sondern für jede kontextfreie Sprache anwendbar ist.

Wir gehen den Algorithmus am Beispiel des Ausdrucks ( ( ) ( ) ), dessen Syntaxbaum oben dargestellt ist, einmal gaaaanz langsam durch. 
Dafür sollten Sie sich allerdings die Reihenfolge der Regeln aus dem Syntaxbaum merken:

Regel 3, Regel 2, Regel 1, Regel 1

Anfangszustand:
Auf dem Eingabeband liegt die Zeichenfolge ( ( ) ( ) ). 
Das aktuelle Zeichen ist jeweils rot markiert.
Auf dem Keller liegt das Startsymbol der Grammatik:
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

S 
 
    • WENN es ein Nichtterminalsymbol ist
    • DANN  lege die Zeichen der passenden Regel (2) nacheinander auf den Keller
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

S 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

( 
 
    • WENN es ein Terminalsymbol ist
    • DANN  ...
    • SONST 
        • WENN die Zeichen übereinstimmen
        • DANN gehe zum nächsten Eingabezeichen
Eingabeband
( ( ) ( ) )  		 EZ

(
®(

 KZ

( 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

S 
 
    • WENN es ein Nichtterminalsymbol ist
    • DANN  lege die Zeichen der passenden Regel (3) nacheinander auf den Keller.
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

S 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

S 
 
    • WENN es ein Nichtterminalsymbol ist
    • DANN  lege die Zeichen der passenden Regel (2) nacheinander auf den Keller.
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

S 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )  		 EZ

(

 KZ

( 
 
    • WENN es ein Terminalsymbol ist
    • DANN  ...
    • SONST 
      • WENN die Zeichen übereinstimmen
      • DANN gehe zum nächsten Eingabezeichen
Eingabeband
( ( ) ( ) )  		 EZ

(
®)

 KZ

( 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )   		 EZ

)

 KZ

) 
 
    • WENN es ein Terminalsymbol ist
    • DANN  ...
    • SONST 
      • WENN die Zeichen übereinstimmen
      • DANN gehe zum nächsten Eingabezeichen
Eingabeband ändert sich!
( ( ) ( ) )  		 EZ

)
®(

 KZ

)
 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )   		 EZ

(

 KZ

S 
 
    • WENN es ein Nichtterminalsymbol ist
    • DANN  lege die Zeichen der passenden Regel (1) nacheinander auf den Keller.
Eingabeband
( ( ) ( ) )   		 EZ

(

 KZ

S 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )   		 EZ

(

 KZ

( 
 
    • WENN es ein Terminalsymbol ist
    • DANN  ...
    • SONST 
      • WENN die Zeichen übereinstimmen
      • DANN gehe zum nächsten Eingabezeichen
Eingabeband
( ( ) ( ) )  		 EZ

)
®)

 KZ

( 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )  		 EZ

)

 KZ

) 
 
    • WENN es ein Terminalsymbol ist
    • DANN  ...
    • SONST 
      • WENN die Zeichen übereinstimmen
      • DANN gehe zum nächsten Eingabezeichen
Eingabeband
( ( ) ( ) )  		 EZ

)
®)

 KZ

)
 
 
  • SOLANGE noch Eingabezeichen vorhanden UND der Keller nicht leer ist
    • nimm das oberste Kellerzeichen (KZ) vom Keller
Eingabeband
( ( ) ( ) )  		 EZ

)

 KZ

) 
 
    • WENN es ein Terminalsymbol ist
    • DANN  ...
    • SONST 
      • WENN die Zeichen übereinstimmen
      • DANN gehe zum nächsten Eingabezeichen
Eingabeband
( ( ) ( ) ) _ 		 EZ

)

 KZ

) 

Wenn Sie sich bis hier hin durchgearbeitet haben, dann dürfen Sie auch dies erfreuliche Ergebnis genießen  ;-) :

Das Eingabeband ist leer, 
Der Keller ist leer

à Die Eingabezeichenfolge wurde akzeptiert

Sie fragen sich: Woher weiß der Automat, welche Regel er jeweils anwenden muß?

Super !! Das ist eine entscheidende Frage, der wir uns nun zuwenden werden (wollen??):

Zur Themenübersicht  
Zum Seitenanfang 
Zur vorigen Seite         Zur nächsten Seite  

    © 2000 LK 12 If und G. Kubitz  Hannah-Arendt-Gymnasium, Lengerich