Diskussion:Deterministisch kontextfreie Sprache

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 8 Jahren von 141.3.44.17 in Abschnitt Mächtigkeit von LALR- und SLR-Parsern
Zur Navigation springen Zur Suche springen

Unter den Abschlusseigenschaften war aufgeführt, dass DCFL abgeschlossen unter Epsilon-freien Homomorphismen ist. Hab's geändert. Hier dazu das Gegenbeispiel:

DCFL sind nicht abgeschlossen unter Anwendung Epsilon-freier Homomorphismen.
DP = deterministischer Kellerautomat
DP = DCFL

h sei ein Epsilon-freier Homomorphismus:

Dann gilt:

(Der vorstehende, nicht signierte Beitrag stammt von 84.186.34.230 (DiskussionBeiträge) 1:56, 21. Mar 2007) -- PvQ Bewertung - Portal 01:57, 21. Mär. 2007 (CET)Beantworten

DCFL vs. LR(k)

[Quelltext bearbeiten]

Im Artikel steht:

Jede LR(k)-Grammatik beschreibt eine deterministisch-kontextfreie Sprache. Strenggenommen gilt die Umkehrung zwar nicht, denn es gibt deterministisch-kontextfreie Sprachen, die keine LR(0)-Sprachen sind (d.h. nicht als LR(0)-Grammatik darstellbar sind), jedoch lassen sie sich durch Einführung einer eindeutigen Markierung für das Wortende in eine solche überführen.

Das ist Unfug; die Umkehrung ist doch: Für jede deterministisch kontextfreie Sprache L gibt es ein k, so dass L eine LR(k)-Sprache ist. Und die gilt. Trotzdem sollte der Hinweis auf die LR(0)-Sprachen bleiben. Wenn niemand was dagegen hat, ändere ich den Artikel entsprechend. -- UKoch 22:58, 9. Jun. 2011 (CEST)Beantworten

Hab's jetzt geändert. -- UKoch 18:12, 3. Aug. 2011 (CEST)Beantworten

Mächtigkeit von LALR- und SLR-Parsern

[Quelltext bearbeiten]

Im Abschnitt "Verhältnis zu anderen Sprachklassen" steht:

Da die Konstruktion eines LR-Parsers aus einer LR(1)-Grammatik für eine deterministisch kontextfreie Sprache häufig zu sehr großen Parse-Tabellen führt, werden in der Praxis leichte Einschränkungen vorgenommen, die zu geringerer Mächtigkeit führen. Die beiden Einschränkungen dieser Art sind LALR- und SLR-Parser.

Worauf bezieht sich dabei die Mächtigkeit? Auf Sprachebene gilt doch LR(k)=LALR(k)=SLR(k)=LR(1)=LALR(1)=SLR(1). --141.3.44.17 17:16, 25. Mai 2016 (CEST)Beantworten