Zur Themenübersicht     

Wir arbeiten zuerst wieder mit der ungünstigen
Grammatik 1:     S ::= ( )      Regel1
                         S ::= ( S )   Regel2
                         S ::= S S    Regel3

Ausgehend vom Startsymbol S ergibt sich durch zweifache Regelanwendung z.B. folgender Syntaxbaum:

Im linken Teil kommt man schnell zu wohldefinierten Klammerpaaren, im rechten Teil muss man tiefer im Baum absteigen, bis man zu einem Ausdruck kommt, der nur aus Terminalsymbolen besteht. Durch Backtracking ist es nun möglich, diesen Baum rekursiv nach dem zu erkennenden Ausdruck zu durchsuchen. Rekursionsende sind dabei die Blätter des Baumes oder innere Knoten, die mit Sicherheit nicht mehr zu dem gesuchten Ausdruck führen können. Der Einfachheit halber können dies die inneren Knoten sein, bei denen der hergeleitete Ausdruck länger als der zu erkennende ist.

Die Suche im Baum beginnt natürlich an der Wurzel. Der erzeugte Ausdruck ist dann S. Die Suche wird dann realisiert, indem jeweils zuerst das am weitesten links stehende Nichtterminalsymbol S nach Regel 1 durch ein Klammerpaar ( ) ersetzt wird. Führt dieser Weg nicht zum gesuchten Ausdruck, wird das S nun mit Regel 2 durch ( S ) und danach gegebenenfalls durch S S ersetzt. 

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