Diskussion:LL(k)-Grammatik

mich würde interessieren, wie sich die Mächtigkeit der LL(k)-Grammatiken zu den deterministisch kontextfreien Grammatiken verhält. Im Text wird nur von den mächtigeren kontextfreien Grammatiken gesprochen. Im LR(k)-Grammatik Artikel ist das Verhältniss zu den det. ktf. Grammatiken erwähnt.

habs eingefügt, gruß --Murkel ^(anmurkeln) 12:11, 25. Sep 2006 (CEST)

wäre hilfreich, wenn die berechnung von first und follow nochmal auf deutsch danebenstünden -- es scheint mir ein grundlegens problem von mathematikern und informatikern zu sein, dass sie ihre sicher schön anzusehenden formeln nicht in verständliches deutsch übertragen könnene; deswegen bin ich nämlich hier gelandet, weil mein script sich gleichermassen in kauderwelsch verliert ...

Das Beispiel sollte doch keine LL Gramatik sein. Die Schnittmenge der Anfangssymbole sollte disjunkt sein. Es ist sonst für einen LL (1) Parser nicht möglich zu unterscheiden ob E, T oder F vorliegt. Gruß gekolis

zur deterministischen regelauswahl werden nicht E, T und F herangezogen, sondern die entsprechenden lockahead-mengen. diese sind verschieden. gruss --Murkel ^(anmurkeln) 15:28, 20. Sep. 2007 (CEST)

warum gehört im beispiel zu den follow1-mengen von T, T' und F jedesmal ")"? des erschliesst sich mir nicht und ich finde auch anderswo keine plausible erklärung.

also, nimm das nichtterminal T, dann kannst du die folgende ableitungsreihenfolge generieren: T -> FT' -> F -> (E) -> (TE') -> (T) und damit follow1(T) = follow1((T)). nun kannst du die def. der follow-menge anwenden und erhälst das gewünschte ergebnis, wenn alpha = (, beta = T und gamma = ). gruss --Murkel ^(anmurkeln) 00:04, 17. Jun. 2008 (CEST)

Fehler

Kann es sein, dass Follow(E) das Epsilon nicht enthält? Eigentlich sollte es nur das Terminal ")" sein... Fehler??? (nicht signierter Beitrag von 78.49.104.128 (Diskussion | Beiträge) 13:17, 19. Jul 2009 (CEST))

ist korrigiert, gruß -- Murkel ^(anmurkeln) 15:07, 19. Jul. 2009 (CEST)

kollidiert allerdings ziemlich stark mit der Tatsache, dass eine Follow-Menge prinzipiell kein Epsilon enthalten kann - siehe z.B. Definition in unten verlinkter Quelle; habe jetzt leider keine Zeit, das gesamte Beispiel zu Korrigieren, bin vor allem verwundert, wie man Follow-Mengen ohne Eingabeendesymbol ($) verwenden kann -- 141.20.1.224 16:36, 14. Apr. 2010 (CEST)

Wenn man die Regeln aus dem Buch Compiler Prinzipien, Techniken Werkzeuge anwendet ist das Beispiel ist falsch: Follow-Mengen können generell kein Epsilon enthalten, außerdem fehlt das ($). -- Benutzer:fholler 17:39, 31. Jan. 2011 (CEST)

genau überblicke ich die ursachen jetzt nicht mehr. zwei punkte sind mir aufgefallen: erstens basiert die im artikel verwendete version auf startseparierten grammatiken und zweitens sind rechte regelseiten nur aus epsilon erlaubt. gruß --Murkel ^(anmurkeln) 16:25, 16. Apr. 2010 (CEST)

Ist doch wirst, ob man es $ oder ε nennt. --Chricho ¹ 11:26, 3. Feb. 2011 (CET)

Nej ist es nicht, Epsilon steht für die Leere Zeichenmenge die in vielen Grammatiken vorkommt, $ ist das Endsymbol welches immer in der Follow-Menge des Startsymbols ist. In dem Artikel ist auch nicht beschrieben das Epsilon durch $ vertauscht wird (falls dies wirklich beabsichtigt ist), niemand kann es erahnen, kann genauso gut sein dass die Follow-Mengen falsch aufgestellt wurden. -- Benutzer:fholler 13:40 09. Feb. 2011 (CEST)

Unterschied zu LF(k)

Ich verstehe den Unterschied einfach nicht:

Eine reduzierte kontextfreie Grammatik ist LF(k)-Grammatik genau dann, wenn für alle Nichtterminalsymbole A, für alle Produktionen $A\to \beta$ und $A\to \gamma$ mit $\beta \neq \gamma$ gilt: $first_{k}(\{\beta \}follow_{k}(A))\cap first_{k}(\{\gamma \}follow_{k}(A))=\emptyset .$.

Eine kontextfreie Grammatik ist LL(k)-Grammatik genau dann, wenn für alle Nichtterminalsymbole $A$, für alle Produktionen $A\to \beta$ und $A\to \gamma$ mit $\beta \neq \gamma$ und $S\Rightarrow _{l}^{*}wA\alpha$ gilt: $first_{k}(\beta \alpha )\cap first_{k}(\gamma \alpha )=\emptyset$. $(w\in \Sigma ^{*};\alpha ,\beta ,\gamma \in (N\cup \Sigma )^{*};A\in N)$

Die Alphas in den Ableitungen S in der LL(k) Definition tauchen doch genauso in der LF(k) Definition in Form der Follow-Menge auf, wo liegt jetzt der Unterschied? Naja, bei LL(k) müssen β und γ im selben Kontext benutzt werden, die Frage ist nun, wann das einen Unterschied macht, ich sehe schon, dass das irgendwie auf etwas leicht anderes hinausläuft, bei LF(k) steckt man alle Follows unter einen Hut und bei LL(k) nicht, aber eine Beispielgrammitik, die LL(k) aber nicht LF(k) ist wäre doch sehr hilfreich, um das nachvollziehen zu können… --Chricho 18:03, 9. Nov. 2010 (CET)

Reduzierte kontextfreie Grammatik?

Was ist eine reduzierte kontextfreie Grammatik? -- UKoch 02:05, 14. Apr. 2011 (CEST) -> in einer reduzierten kontextfreien Grammatik dürfen nur Nichtterminale vorkommen, die:
- vom Startsymbol aus erreichbar sind
- und sich zu Wort(en) aus dem Eingabealphabet ableiten lassen (indirekt)

Bsp:
S -> A | B
A -> a
C -> c

C ist unerreichbar (1), B ist unproduktiv (2)
die reduzierte kontextfreie Grammatik ist dann:
S -> A
A -> a

siehe Güting Erwig Übersetzerbau
--164.40.234.167 (16:46, 4. Jun. 2013 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)