Diskussion:Earley-Algorithmus

Dyck Grammatik

So wie Dyck-Grammatik jetzt ist, ergibt sie wenig Sinn. Der Ausdruck ()()() liegt dann nicht in der Sprache. Besser wäre

S -> A

A -> e | (A)A

Das Beispiel ist an mehreren Stellen falsch!

Die Regel S -> ()(A) gibt es z.B. nicht, und somit auch kein Item (S -> (*)(A),0)!

Wenn das neue Beispiel für mathematische Ausdrücke noch etwas detailierter beschrieben ist, würde ich vorschlagen, das Dyck-Beispiel zu löschen. Die Dyck-Sprache ist unanschaulich und ich habe keine Lust die Fehler zu korrigieren. −−Christian Schirm 15:23, 19. Jan. 2010 (CET)

Habe Dyck-Beispiel entfernt.−-Christian Schirm 01:58, 20. Jan. 2010 (CET)

Algorithmus

Der Voraussage-Schritt ist falsch: Es wird nicht (X ->u*wv,i) sondern (A -> *w,i) hinzugefügt.

Ich habs mal ganz umformuliert mit "...". Ist übersichtlicher.--Christian Schirm 19:04, 18. Jan. 2010 (CET)

Earley für Programmiersprachen

Die Idee den Earley-Algorithmus für konventionelle Programmiersprachen zu verwenden ist aus meiner Sicht kritisch. Er ist dafür viel zu langsam. Die Stärke des Algorithmus ist aus meiner Sicht die Möglichkeit sämtliche kontextfreien Sprachen akzeptieren zu können und nicht nur eine Teilmenge (wie z.B. LR und LL).

Der Hinweis darauf, dass man eigentlich kontextsensitve Programmiersprachen besser erst mit einem Earley-Algorithmus analysiert ist dann völlig an der Realität vorbei. Streng genommen mögen die meisten Programmiersprachen kontextsensitiv sein, aber ich kenne keine einzige, die jemals eine korrekte kontextsensitive Grammatik formuliert hätte. Es ist eigentlich üblich, dass die Grammatik deterministisch kontextfrei (LL,LR o.ä.) ist und dass der kontextsensitive Teil über die Semantische Analyse erledigt wird. Man kommt somit in der Praxis weder mit Early noch mit kontextsensitiven Sprachen in Berührung.

Eventuell sollte man den Abschnitt nochmal überarbeiten, sodass das Wortproblem nicht anhand von Programmiersprachen erklärt wird (für die das Wortproblem und kontextsensitive Sprachen völlig irrelevant sind), sondern auf abstrakterem, akademischerem Level. Etherial (Diskussion) 07:16, 2. Mär. 2018 (CET)

Ich stimme zu.

In der Tat lässt die Selbstverständlichkeit, mit der nach der Einleitung dann gleich im ersten Abschnitt „Verwendung“ zum Earley-Algorithmus übergegangen wird, wohl manchen Leser mutmaßen, dieser wäre sozusagen die sich immer natürlich anbietende Lösung des Wortproblems für kfL und speziell Programmiersprachen, obwohl doch seine Komplexität in der Regel zu groß ist.

Kanonisch ist wohl eher, dass man deren Grammatiken bei Bedarf (mindestens zu so etwas Einfachem wie) zu LALR(1) transformiert und einen LR(1)- oder sogar einen LL(1)-Parser nutzt.

Im Grunde stören hier ksG sogar, da sie gar nicht nach Earley geparst werden können und die von Prögrammiersprachen „herführende“ Veranschaulichung, denn das war wohl das Motiv, einen nur irritierenden Ausgangspunkt hat. Earley schluckt jede kfG, etwa auch mehrdeutige, die man ja bei Programmiersprachen überhaupt nicht goutiert, das ist sein einziger großer Vorzug, für engere Sprachklassen wie oben genannt dagegen ist er zu umständlich.

Beim Umbau aber bitte achtsam vorgehen – die Artikel zu formalen und Programmiersprachen haben eine lange Editionshistorie, in der man gerade das oft vermisst.

--Silvicola ^Disk 08:11, 2. Mär. 2018 (CET)