Theoretische Informatik - Begriffsdefinition: Reduktion

Nächste Seite: Definition LR(0)-Grammatik Aufwärts: LR(0)-Grammatiken Vorherige Seite: Eigenschaften von LR(0)-Grammatiken Inhalt

Begriffsdefinition: Reduktion

Gibt es in der Grammatik die Regel $A\rightarrow y$ , so kann

$\begin{displaymath}xyz_{?}\end{displaymath}$

(wobei $z_{?}$ der noch nicht gelesene Teil des Wortes ist) nach

$\begin{displaymath}xAz_{?}\end{displaymath}$

reduziert werden.

Hier wird uns anschaulich die Eigenschaft einer LR(0)-Grammatik klar. Eine LR(0)-Grammatik muß so aufgebaut sein, daß solche Reduktionen klappen. D.h. es muß immer eine Regel eindeutig bestimmt sein, mit der reduziert wird, so daß wir letztendlich in linearer Zeit überprüfen können, ob da Wort in der Sprache ist.