Direkt zum Inhalt

Lexikon der Mathematik: Bottom-up-Analyse

Klasse von ableitungsorientierten Analyseverfahren für kontextfreie Sprachen, die ein Wort w analysieren, indem von w ausgehend versucht wird, Regeln der Grammatik rückwärts anzuwenden.

Ziel ist die Reduzierung des Wortes zum Startsymbol der Grammatik. Für beliebige kontextfreie Sprachen gibt es ein nichtdeterministisches Bottom-up-Analyseverfahren auf der Basis von Kellerautomaten. Dort werden durch Shift-Schritte Teile des Wortes in den Keller übernommen und durch Reduktionsschritte rechte Seiten von Regeln, die den Kelleranfang bilden, durch die linke Regelseite ersetzt.

Die Auswahl der Aktionen erfolgt nichtdeterministisch. Die Analyse ist erfolgreich, wenn die Eingabe vollständig gelesen und der Kellerinhalt zum Startsymbol reduziert werden kann. Für LR(k)-Grammatiken kann die Aktionsauswahl deterministisch erfolgen.

Die Bottom-up-Analyse liefert eine Rechtsableitung.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos