Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Präfixeigenschaft Aufwärts: LR(0)-Grammatiken Vorherige Seite: Verbale Definition von LR(0)-Grammatik   Inhalt

Eindeutigkeit

Jede LR(0)-Grammatik ist eindeutig.

Sei $G$ eine LR(0)-Grammatik. Zu jeder Rechtssatzform $t\not= S$ gibt es ein eindeutig bestimmtes Tupel $(x,y,z,A)$, so daß folgende Bedingungen erfüllt sind:

  • $x,y\in(V\cup\Sigma)^{*}$ $z\in\Sigma^{*}$ und $A\in V$
  • $A\rightarrow y$ ist eine Regel in $G$
  • $t=xyz$
  • $xAz$ ist eine Rechtssatzform
Aus der Definition der LR(0)-Bedingungen folgt, daß $A\rightarrow y$ einzigste Regel ist, um $y$ wieder rückwärts abzuleiten. Aus der Definition folgt, daß $xAz$ einzigster Griff von $(xy,y)$ ist. Somit gibt es nur einen einzigen Rückwärtsableitungspfad.
$\Rightarrow$ Jede LR(0)-Grammatik ist eindeutig

Damit ist gezeigt, daß LR(0)-Sprachen von einem deterministischen Kellerautomaten entschieden werden können.