www.wikidata.de-de.nina.az

LR k Grammatik In der theoretischen Informatik und dem Compilerbau bezeichnet eine spezielle kontextfreie Grammatik welc

LR(k)-Grammatik

In der theoretischen Informatik und dem Compilerbau bezeichnet LR(k)-Grammatik eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR-Parsers bildet.

Man nennt eine kontextfreie Grammatik -Grammatik, wenn jeder Reduktionsschritt eindeutig durch Symbole der Eingabe (sogenannter Lookahead) bestimmt ist. Das bedeutet, die Frage, zu welchem Nichtterminalsymbol mit welcher Regel als nächstes reduziert werden soll, kann eindeutig mit Hilfe der nächsten Symbole der Eingabe bestimmt werden.

Ein Unterschied der Sprachklasse, die mit -Grammatiken beschrieben werden kann, zeigt sich nur für die beiden Fälle und . Die Ausdrucksstärke von kontextfreien Grammatiken wird von nicht erreicht. Damit gibt es für alle kontextfreie Grammatiken, zu denen es keine äquivalente -Grammatiken gibt, zum Beispiel eine inhärent mehrdeutige Sprache. Man nennt die durch -Grammatiken definierte Sprachklasse auch deterministisch kontextfreie Sprachen.

(DPDA = Deterministic Push-Down Automaton, PDA = Push-Down Automaton)

Formale Definition LR(k)-Grammatik Bearbeiten

Eine kontextfreie Grammatik ist -Grammatik genau dann, wenn für alle Rechtsreduktionen der Form

mit und gilt:

, sowie

Siehe auch Bearbeiten

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der theoretischen Informatik und dem Compilerbau bezeichnet LR k Grammatik eine spezielle kontextfreie Grammatik welche die Grundlage eines LR Parsers bildet Man nennt eine kontextfreie Grammatik L R k displaystyle mathrm LR k Grammatik wenn jeder Reduktionsschritt eindeutig durch k displaystyle k Symbole der Eingabe sogenannter Lookahead bestimmt ist Das bedeutet die Frage zu welchem Nichtterminalsymbol mit welcher Regel als nachstes reduziert werden soll kann eindeutig mit Hilfe der nachsten k displaystyle k Symbole der Eingabe bestimmt werden Ein Unterschied der Sprachklasse die mit L R k displaystyle mathrm LR k Grammatiken beschrieben werden kann zeigt sich nur fur die beiden Falle k 0 displaystyle k 0 und k gt 0 displaystyle k gt 0 Die Ausdrucksstarke von kontextfreien Grammatiken wird von L R 1 displaystyle mathrm LR 1 nicht erreicht Damit gibt es fur alle k N displaystyle k in mathbb N kontextfreie Grammatiken zu denen es keine aquivalente L R k displaystyle mathrm LR k Grammatiken gibt zum Beispiel eine inharent mehrdeutige Sprache Man nennt die durch L R k displaystyle mathrm LR k Grammatiken definierte Sprachklasse auch deterministisch kontextfreie Sprachen L L R 0 L L R 1 L L R 2 L D P D A L P D A displaystyle mathcal L mathrm LR 0 subsetneq mathcal L mathrm LR 1 mathcal L mathrm LR 2 cdots mathcal L mathrm DPDA subsetneq mathcal L mathrm PDA DPDA Deterministic Push Down Automaton PDA Push Down Automaton Formale Definition LR k Grammatik BearbeitenEine kontextfreie Grammatik G N S P S displaystyle G left N Sigma P S right nbsp ist L R k displaystyle mathrm LR left k right nbsp Grammatik genau dann wenn fur alle Rechtsreduktionen der Form a b w displaystyle alpha beta w nbsp r a A w displaystyle Leftarrow r alpha Aw nbsp r displaystyle Leftarrow r nbsp S displaystyle S nbsp g d x displaystyle gamma delta x nbsp r g B x displaystyle Leftarrow r gamma Bx nbsp r displaystyle Leftarrow r nbsp mit w x S a b g d N S A B N displaystyle w x in Sigma alpha beta gamma delta in N cup Sigma A B in N nbsp und f i r s t a b k a b w f i r s t a b k g d x displaystyle first alpha beta k alpha beta w first alpha beta k gamma delta x nbsp gilt a g displaystyle alpha gamma nbsp A B displaystyle A B nbsp sowie b d displaystyle beta delta nbsp Siehe auch BearbeitenLL k Grammatik LL ParserWeblinks BearbeitenLR k Analyse fur Pragmatiker ausfuhrliche Beschreibung der LR Analyse und der Unterformen LR 0 SLR 1 LALR 1 LR 1 Abgerufen von https de wikipedia org w index php title LR k Grammatik amp oldid 220007274