Nichtdeterministischer LR(0)-Parser ::: Theoretische Informatik

Nichtdeterministischer LR(0)-Parser

Der Parser dient dazu zu erkennen, ob ein Eingabewort

in der Sprache enthalten ist.
Wir zerlegen

wie folgt

$\begin{displaymath}w=w_{1}z_{?}\end{displaymath}$

wobei $w_{1}$ der schon vom Parser gelesene Teil ist und $z_{?}$ der noch nicht gelesene.
Der aktuelle Kellerinhalt ist das Wort

$(v\in(V\cup\Sigma)^{*}$ , welches durch das Zurückverfolgen der Rechtsableitung ermittelt wurde:

$\begin{displaymath}v\Rightarrow_{R}^{*}w_{1}\end{displaymath}$

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 $A\rightarrow y$ 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.