LR(k)-Grammatik

LR(k)-Grammatik

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

Man nennt eine kontextfreie Grammatik LR(k)-Grammatik, wenn jeder Reduktionsschritt eindeutig durch k Symbole der Eingabe (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 k Symbole der Eingabe bestimmt werden.

Ein Unterschied der Sprachklasse, die mit LR(k)-Grammatiken beschrieben werden kann, zeigt sich nur für die beiden Fälle k = 0 und k > 0. Die Ausdrucksstärke von kontextfreien Grammatiken wird von LR(1) nicht erreicht. Damit gibt es kontextfreie Grammatiken, die für kein k LR(k)-Grammatiken sind, zum Beispiel die inhärent mehrdeutigen Sprachen. Man nennt die durch LR(k)-Grammatiken definierte Sprachklasse auch deterministisch kontextfreie Sprachen.

\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

Eine kontextfreie Grammatik G = \left(N,\Sigma,P,S\right) ist \mathrm{LR}\left(k\right)-Grammatik genau dann, wenn für alle Rechtsreduktionen der Form

αβw \Leftarrow_r \alpha A w \Leftarrow_r^*
S
γδx \Leftarrow_r \gamma B x \Leftarrow_r^*

mit w,x \in \Sigma^*; \alpha,\beta,\gamma,\delta \in (N \cup \Sigma)^*; A,B \in N und first | αβ | + k(αβw) = first | αβ | + k(γδx) gilt:

α = γ, A = B sowie β = δ

Siehe auch

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Grammatik (Begriffsklärung) — Grammatik (griechisch γραμματική, von γράμμα „der Buchstabe“) bezeichnet: Grammatik, einen Teil der Sprachwissenschaft formale Grammatik, ein mathematisches Modell in der theoretischen Informatik Grammatik (artes liberales), ein Gebiet der… …   Deutsch Wikipedia

  • Grammatik (Band) — Grammatik ist eine polnische Hip Hop Gruppe aus Warschau. Sie wurde 1997 gegründet, ihr Stil ist betont ruhig, als Samples nutzen sie bevorzugt Fragmente klassischer Musik. Bekannt wurde sie im Jahr 2000 mit der EP EP+ und dem Album Światła… …   Deutsch Wikipedia

  • Grammatik — Grammatik, 1) bei den Griechen u. Römern die Anweisung in den Wissenschaften (Grammăta), s. Grammatiker; 2) der Inbegriff u. die wissenschaftliche Darstellung der Regeln, wonach eine Sprache gesprochen u. geschrieben wird. Die Allgemeine G.… …   Pierer's Universal-Lexikon

  • Grammatik — Sf std. (11. Jh.), mhd. gramatic(a), ahd. grammatih Entlehnung. Entlehnt aus l. (ars) grammatica Sprachlehre , dieses aus gr. grammatikḗ (téchnē), zu gr. grámma n. Geschriebenes, Buchstabe , einer Ableitung von gr. gráphein einritzen, schreiben …   Etymologisches Wörterbuch der deutschen sprache

  • Grammatik von heute — [Network (Rating 5600 9600)] Auch: • Grammatik für heute …   Deutsch Wörterbuch

  • Grammatik für heute — [Network (Rating 5600 9600)] Auch: • Grammatik von heute …   Deutsch Wörterbuch

  • Grammátik — (griech., Sprachlehre) ist die Gesamtheit der Regeln über die Laute (s. Lautlehre) und Formen (s. Flexion) einer Sprache und über die Aneinanderreihung der Wörter zu Sätzen (s. Syntax). Grammatiker war bei den alten Griechen soviel wie Philolog,… …   Meyers Großes Konversations-Lexikon

  • Grammátik — (grch.), Sprachlehre, die Darstellung des vorhandenen Materials einer Sprache, ihres Baues und der Gesetze ihrer Entwicklung und Veränderung. Die wissenschaftliche G. zerfällt gewöhnlich in 1) Lautlehre, 2) Stammbildungslehre, 3) Wortbildungs… …   Kleines Konversations-Lexikon

  • Grammatik — Grammatik, griech., Sprachlehre, die systematische Zusammenstellung der Regeln, nach welchen eine Sprache gebaut ist; die allgem. G. behandelt diejenigen Hauptformen, welche auf den allg. Gesetzen des menschl. Vorstellens beruhend, sich in allen… …   Herders Conversations-Lexikon

  • Grammatik — (Teil der Sprachwissenschaft, der sich mit den sprachlichen Formen und ihrer Funktion beschäftigt; auch Bezeichnung für ein Lehrbuch der Sprachlehre): Das Wort (mhd. grammatic‹a›, ahd. gram‹m›atik) ist entlehnt aus lat. (ars) grammatica… …   Das Herkunftswörterbuch

  • Grammatik — [Network (Rating 5600 9600)] …   Deutsch Wörterbuch

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”