Ψ Die Informatikseite

Menü
Unterabschnitte

Definition von Begriffen für eine verbale Definition von LR(0)-Grammatiken

Griff

Jedes Wortpaar $(xy,y)$ mit $x,y\in(V\cup\Sigma)^{*}$ für das es eine Rechtsableitung der Form

\begin{displaymath}S\Rightarrow_{R}^{*}xAz\Rightarrow_{R}xyz\end{displaymath}

gibt, heißt Griff von $xyz$. Wenn klar ist, an welcher Stelle die Regel $A\rightarrow y$ greift, so kann man auch nur Griff $y$ von $xyz$ sagen.

Rechtssatzform

Sei $G$ eine CFG. Alle Wörter

\begin{displaymath}t\in(V\cup\Sigma)^{*}\end{displaymath}

die aus dem Startsymbol durch eine Rechtsableitung generiert werden können ( $S\Rightarrow_{R}^{*}t$), heißen Rechtssatzform. Eine Rechtssatzform ist also eine Menge.