imported>Aka: typografische Anführungszeichen

2024-04-06T12:47:40Z

typografische Anführungszeichen

Neue Seite

'''Bottom-up-Parser''' oder '''Aufwärtsparser''' sind [[Analyse]]-Werkzeuge für [[formale Sprache]]n.

Im Regelfall wird ein [[Parser]] als Teil eines Übersetzungsprogramms von einer Sprache in eine andere eingesetzt. Bei [[Programmiersprache]]n ist ein solches Übersetzungsprogramm Teil eines [[Compiler]]s.
Ein Parser prüft auch die [[Konformität]] bzw. das Einhalten des Regelwerks einer Sprache: Er gibt [[Warnung]]en und [[Fehlermeldung]]en aus, wenn der Eingangstext nicht regelkonform ist.

Ein Bottom-up-Parser arbeitet ausgehend von der kleinsten vorgefundenen Einheit („Bottom“) in Richtung des größeren Zusammenhangs („up“).

Der Bottom-up-Parser implementiert die Strategie des Bottom-up-[[Parsing]]s (datengeleitetes Parsing).
Bei dieser wird von den [[Token (Übersetzerbau)|Token]] (Wörtern) des Eingabesatzes ausgehend versucht, nach und nach größere [[Syntax|syntaktische]] Strukturen aufzubauen, bis man schließlich beim [[Startsymbol]] der [[Grammatik]] angelangt ist.

Wichtige Unterklassen sind
* Shift-Reduce-Parsing wie [[LR-Parser|LR(k)-Parsing]]
* [[Operator-Präzedenz-Parsing]]

== Beispiel ==
Gegeben sei eine [[kontextfreie Grammatik]] mit folgenden [[Produktionsregel]]n:
# [[Satz (Grammatik)|S]] → [[Nominalphrase|NP]] [[Verbalphrase|VP]]
# [[Verbalphrase|VP]] → [[Verb|V]] [[Nominalphrase|NP]]
# [[Nominalphrase|NP]] → Donald
# [[Nominalphrase|NP]] → Daisy
# [[Verb|V]] → liebt

Das [[Startsymbol]] sei [[Satz (Grammatik)|S]].

Der Satz, der durch den Bottom-up-Parser analysiert werden soll, sei „Daisy liebt Donald“. Der [[Stapelspeicher|Stapel]] des Parsers ist anfänglich leer. Die Schritte eines Shift-Reduce-Parsers sehen so aus:

{| class="wikitable"
!Eingabe
!Stapel
!Aktion
!Angewandte Regeln
|-
| Daisy liebt Donald
|
| Start
|
|-
| liebt Donald
| Daisy
| Lege Wort „Daisy“ auf den Stapel
|
|-
| liebt Donald
| NP
| Reduziere „Daisy“ zu NP mit Regel 4.
| 4
|-
| Donald
| NP liebt
| Lege Wort „liebt“ auf den Stapel
| 4
|-
| Donald
| NP V
| Reduziere „liebt“ zu V mit Regel 5.
| 4 5
|-
|
| NP V Donald
| Lege Wort „Donald“ auf den Stapel
| 4 5
|-
|
| NP V NP
| Reduziere „Donald“ zu NP mit Regel 3.
| 4 5 3
|-
|
| NP VP
| Reduziere die Folge V NP auf dem Stapel zu VP mit Regel 2.
| 4 5 3 2
|-
|
| S
| Reduziere die Folge NP VP auf dem Stapel zu S mit Regel 1.
| 4 5 3 2 1
|-
|}

Es gibt keine weiteren Wörter mehr im Eingabesatz, auf dem [[Stapelspeicher|Stapel]] liegt das [[Startsymbol]], der Satz wurde daher durch den Parser unter Ausgabe der Regelfolge ''4 5 3 2 1'' akzeptiert.

[[Kategorie:Compilerbau]]

Bottom-up-Parser - Versionsgeschichte

imported>Aka: typografische Anführungszeichen