Der Parser dient dazu zu erkennen, ob ein Eingabewort
![$w$](img65.png)
in der Sprache enthalten ist.
Wir zerlegen
![$w$](img65.png)
wie folgt
wobei
![$w_{1}$](img733.png)
der schon vom Parser gelesene Teil ist und
![$z_{?}$](img712.png)
der noch nicht gelesene.
Der aktuelle Kellerinhalt ist das Wort
![$(v\in(V\cup\Sigma)^{*}$](img734.png)
, welches durch das Zurückverfolgen der Rechtsableitung ermittelt wurde:
Der Parser entscheidet nun nichtdeterministisch, welche der folgenden Aktionen ausgeführt werden:
- ACCEPT: Sobald das im Keller gespeicherte Wort
ist, kann akzeptiert werden.
- REDUCE: Eine Reduktion für die Regel
wird angewendet, so daß das auf dem Keller stehende gekellerte Wort
anstatt
ist.
- SHIFT: Ein weiteres Zeichen wird aus dem noch unbekannten Wort gelesen und auf den Keller gelegt.
- ERROR: Es wird erkannt, daß das Wort nicht in der Sprache enthalten ist und es gibt eine Fehlermeldung.