Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Tabellarische Aufführung der Abschlußeigenschaften Aufwärts: LR(0)-Grammatiken Vorherige Seite: Präfixeigenschaft   Inhalt

Nichtdeterministischer LR(0)-Parser

Der Parser dient dazu zu erkennen, ob ein Eingabewort $w$ in der Sprache enthalten ist.
Wir zerlegen $w$ 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$ $(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 $S$ 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 $xA$ anstatt $xy$ 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.