Diskussion:LR(k)-Grammatik

unverständlich

Der Artikel ist unverständlich. Dies ist keine wissenschaftliche Fachzeitung. Es muss am Anfang kurz und verständlich (!!) gesagt werden, was eine Grammatik und was kontextfrei und was ein Parser jedenfalls *in etwa* bedeuten soll, wie das einzuordnen ist. Interne Links dazu können nicht schaden. Es geht nicht an, dass man lange braucht, um zu merken, dass es nichts mit Grammatik zu tun hat. Nicht jeder ist Informatiker-Freak. Dasselbe gilt für Unterartikel PaCo 22:37, 21. Sep 2005 (CEST)

was eine grammatik ist steht bei grammatik, was kontextfrei ist steht bei kontextfrei, und rate mal wo was zu parser steht. es ist nicht möglich, hier nochmal die halbe informatik zu erklären. unumstritten ist schon klar, daß der artikel keine leichte kost ist. nur leider muß man sich aber um exaktheit bemühen und da geht es nicht ohne definitionen und formeln; alles andere wäre unspezifisch.

Mindestens elf Jahre nach obiger Diskussion: Der erste Teil des Artikels mag so weit in Ordnung sein, aber der zweite ist es meines Erachtens nicht. Ich persönlich könnte mich problemlos durch die formale Definition durchbeißen und sie verstehen, aber in Hinblick auf WP:OMA sollte man unbedingt auch beschreiben, was die Definition denn anschaulich aussagt. Theoretische Informatiker finden vielleicht Gefallen an dem Zeichensalat aus ${\Leftarrow }_{r}$, ${first}_{\left|\alpha \beta \right|+k}$, griechischen Buchstaben usw., aber für den normalsterblichen Leser (ja sogar für den Ottonormalinformatiker, meiner Meinung nach) ist das nicht hilfreich. Selbst wenn man den formalen Apparat stehen lässt, sollte man wenigstens eine Referenz einfügen, was die $first$-Mengen sind. Die Definition gibt’s zum Beispiel in dem schon verlinkten Skript von Andreas Kunert. (Nebenbemerkung: Typographisch korrekt ist $first$ auch nicht, da nicht die Variablen $f$, $i$, $r$, $s$ und $t$ gemeint sind, sondern der Operator $\operatorname {first}$.) Leider bin ich nicht gut im anschaulichen Erklären formaler Definitionen, sonst würde ich das selbst erledigen. --92.230.34.253 20:16, 13. Mär. 2017 (CET)

Rechtableitung

Ich hab mal die Erläuterung des LR(k)-Kriteriums etwas geändert. Hierbei auf Reduktionen Bezug zu nehmen, ist nicht korrekt, da Reduktion ein Begriff aus der Automatentheorie ist. Bei formalen Sprachen wie den LR(k)-Sprachen muß man von Rechtsableitungen sprechen. Tombox, 1.4.2006

Danke, dass Du Dich um den Artikel kümmern möchtest, aber Du solltest Dich vielleicht erst in die Thematik einarbeiten, bevor Du etwas änderst. das 'R' in 'LR' steht für Rechtsreduktion! Knuth, Papers Comp. Lang., S. 314. --Rtc 04:33, 1. Apr 2006 (CEST)

Unschlüssigkeit?

"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." Ist das jetzt ein logischer Schluss den ich nicht verstehe oder ist da irgendwas falsch? Vielleicht LR(k) statt LR(1)?

Du zitierst den Schluss unvollständig. Es fehlt die Prämisse "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$." --rtc 21:06, 16. Nov. 2007 (CET)

Ich habe auch lange gerätselt, was dieser Satz hier bedeutet: "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." Hmm? Und wenn man das nicht versteht, erkennt man auch keinen Zusammnehang zu den folgenden Aussagen.

Vielleicht wäre es so besser: "LR(k) ist eine Eigenschaft von Grammatiken, nicht der durch sie erzeugten Sprachen. Die Menge der Sprachen, für die es eine LR(0)-Grammatik gibt, ist echt enthalten in der Menge der Sprachen, für die es eine LR(1) Grammatik gibt, während für jedes k>0 und l>0 die Menge der (durch LR(k)- bzw. LR(l)-Grammatiken) erzeugbaren Sprachen diesselbe ist." - falls das so gemeint ist. (nicht signierter Beitrag von 188.100.199.199 (Diskussion) 12:42, 18. Dez. 2015 (CET))

Definition korrekt?

Sorry, aber: ist die Definition, wie sie im Artikel angegeben ist, eigentlich korrekt? Im wesentlichen steht da doch: es darf nur eine einzige Rechtsableitung beginnend vom Startsymbol geben. Muss nicht noch etwas in der Art $\alpha \beta =\gamma \delta$ vorausgesetzt werden, bevor ich schließen können muss, dass die zwei angewandten Regeln bereits gleich sind? (nicht signierter Beitrag von 83.135.94.197 (Diskussion | Beiträge) 12:57, 24. Mär. 2010 (CET))

Woraus schließt Du "es darf nur eine einzige Rechtsableitung beginnend vom Startsymbol geben"? Und wo liest Du einen Schluss hinsichtlich Gleichheit von zwei angewandten Regeln? --rtc 17:08, 24. Mär. 2010 (CET)

Okay, nochmal ausführlicher. Die Definition im Artikel lautet doch (ich vereinfache es mal für den Fall LR(k=0)):

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

$\alpha \beta w\Leftarrow _{r}\alpha Aw$	$\Leftarrow _{r}^{*}$
			$S$
$\gamma \delta x\Leftarrow _{r}\gamma Bx$	$\Leftarrow _{r}^{*}$

mit $w,x\in \Sigma ^{*};\alpha ,\beta ,\gamma ,\delta \in (N\cup \Sigma )^{*};A,B\in N$ gilt, dass

$\alpha =\gamma$, $A=B$ sowie $\beta =\delta$

Und hier ist eine Grammatik, die doch wohl LR(0) ist:

$S\rightarrow A$, $A\rightarrow a$, $A\rightarrow b$.

Diese Grammatik wäre aber nach der Definition, desseiden ich übersehe etwas, nicht LR(0). Denn ich habe zwei Rechtsableitungen: $a\Leftarrow _{r}A\Leftarrow _{r}S$ und $a\Leftarrow _{r}A\Leftarrow _{r}S$, wobei offentsichtlich nicht gilt, dass $\beta =a=b=\gamma$. Das kann doch nicht sein?

Ich hätte gedacht, dass man noch so etwas wie $\alpha \beta =\gamma \delta$ zusätzlich zu der Bedingung an die Firstmengen fordern müsste!(nicht signierter Beitrag von 83.135.94.197 (Diskussion) 22:37, 24. Mär. 2010 (CET))

Gut gesehen; eine IP hat vor knapp 2 Jahren den Artikel subtil vandaliert [1]. Ich habe den Vandalismus beseitigt. --rtc 22:37, 24. Mär. 2010 (CET)