Wie fang ich da am besten an?
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
[Parsing] Early-Parser
Ich weiß, bin a bissl spät dran, aber hab im Moment nicht grade viel Zeit übrig.
Wir sollen ja so nen tollen Early-Parser in Java machen, aber ich kapier das Ding irgendwie nicht. Ist zwar eine halbwegs verständliche Anleitung in den Folien gegeben, aber es ist doch was anderes, eine natürlichsprachliche Folge von Anweisungen nahezu beliebiger Komplexität mit einem intelligenten Gehirn abzuarbeiten oder das ganze einem dummen Computer in einer sehr begrenzten und gar nicht toleranten oder gar intelligenten Sprache wie Java vorzugeben. Alleine die Punkte in den Regeln weiß ich schon nicht so recht in Programmcode zu fassen, und erst recht nicht sowas wie “für alle weiteren Kanten auch noch ausführen, bis keine mehr dazukommen”. Das schreit doch geradezu nach einer KI oder stattdessen mind. 1000 Codezeilen.
Kann mir da jemand etwas auf die Sprünge helfen, dass ich die Aufgabe doch noch abgeben kann? 
Fertige oder teilweise fertige Implementierungen scheint’s im Internet keine zu geben, da kennt nichtmal jemand den Early-Algorithmus…
Na dann hoffe ich mal, dass diese Aufgabe nicht von einem sehr begrenzten und gar nicht tolaranten oder gar intelligenten Programmierer bearbeitet wird
;-))
yupp, verstehe deine situation 
mein algo sieht im kern so aus:
- startregeln in E(0,0) eintragen
- for i = 0 bis input.length (also für jeden knoten im earley chart graphen)
2.1 predict bei spalte i bis nix mehr geht
2.2 einmal scannen bitte. falls damit regeln inaktiv werden, complete()n. falls durch dieses complete weitere regeln inaktiv sind, rekursiv runter.
das predict guckt alle regeln an der spalte i an, also alle regeln, die beim chartknoten i enden. du brauchst die regeln, die rechts neben dem punkt ein nichtterminal haben. für dieses nichtterminal fügst du neue regeln bei E(i,i) ein, die dieses nichtterminal als linke seite haben.
das scan nimmt das nächste eingabezeichen. es sucht danach alle regeln in spalte i, die dieses zeichen als zeichen rechts neben dem punkt haben. für jede dieser regeln wird rechts neben dieser regel eine neue eingefügt, die den punkt eins nach rechts geshiftet hat. ich ruf für jede neu eingefügt regel einmal complete auf. brauch ich eigentlich nicht, aber naja.
das complete bekommt bei mir die zeile und spalte der regel, die inaktiv geworden ist, sowie die regel selber. es guckt daraufhin, welche regeln mit dieser weiter vervollständigt werden können. das sind alle inaktiven regeln, die bei dem chartknoten enden, bei der die frisch complete()te regel beginnt.
shit, dachte, ich hab den intus … :-/ doch schwieriger als gedacht.
unter http://wwwcip/~sisthank/earley/table0.html
liegt ein parse von parse von a*b+c mit der grammatik
[quote]S → . E
E → . E Mal E
E → . T
T → . T Plus T
T → . a_
T → . b_
T → . c_
Mal → . *_
Mal → . /_
Plus → . +_
Plus → . -_[/quote]
HTH
Aha, klingt irgendwie immer noch recht “umgangssprachlich”…
Also ich hab mittlerweile die Folien in einen Pseudocode übersetzt:
Input: Grammatik, Chart, Satz
Init:
∀ Grammatik.Regeln Like S → * As Regel
Chart[0, 0].Add (S, ε, Regel.RechteSeite)
Wiederhole
Predict(0, 0)
so lange countof Chart.Add > 0 (bedeutet: solange in der Schleife etwas in die Chart eingefügt wurde)
∀ gültigen Chartzellen (i, j):
Scan(i, j - 1)
Wiederhole
Predict (?) (hier ist noch ne Lücke)
Complete
so lange countof Chart.Add > 0
Auswertung:
Falls Chart[0, n].Enthält (S, *, ε)
Akzeptiere Satz
sonst
Akzeptiere Satz nicht
Ende.
Predict(zeile, spalte):
∀ Chart[zeile, spalte].Regel Like (A, a, B b) As CRegel
∀ Grammatik.Regel Like B → * As GRegel
Chart[spalte, spalte].Add (B, ε, GRegel.RechteSeite)
Scan(zeile, spalte):
∀ Chart(zeile, spalte - 1).Regel Like (A, a, Satz[spalte] b) As Regel
Chart[zeile, spalte].Add (A, a Satz[spalte], b)
[u]Complete/u:
∀ gültigen Chartzellen (i, j)
∀ gültigen Chartzellen (j, k)
Falls Chart[i, j].Enthält (A, a, B b) mit Chart[j, k].Enthält (B, *, ε)
Chart[i, k].Add (A, a B, b)
Gültige Chartzellen sind die der oberen Hälfte inkl. der Hauptdiagonalen.
Die Punktschreibweise hab ich in meiner Theorie so gelöst, dass ich alle 3 Komponenten als Teile eines Tripels speichere, was besserer ist mir nicht eingefallen. S → a . b sieht dann so aus: (S, a, b). Wie machst du das?
Außerdem ist das jetzt bloß ein Recogniser, kein Parser. Hoffe wir sollen keinen Parser machen…
hey noch genauer gehts net oder soll ich code posten 
der parser ist dann nicht weiter schwer. ich hab nur ein prob da ich alles gegen die vorgabe 1 gecodet hab :] nya.
ich hab von CFRule eine klasse CFRuleItem abgeleitet. die kennt die position (als integer); dazu ne methode advanceDot() und getSymbolNextToDot().
das scan gefällt mir nicht. wenn du mal vom graphen ausgehst, dann braucht scan nur einen parameter, und zwar die position, ab der gescant werden soll. predict ebenso.
??? also wie willst du durch das chart laufen? muss noch mal kurz überlegen …
das complete() sieht ok aus; geht halt immer übers komplette chart, aber was solls.
Naja, der Algorithmus ist alles andere als effizient, aber wenn er mal läuft, bin ich froh!
Ja, also nur die Spalte an Predict und Scan übergeben und die laufen dann für sich alle Zeile durch?
Naja, alle gültigen Chartzellen sind halt alle Zeilen und Spalten die oben rechts in der Hälfte liegen. Durchlaufen geht mit 2 for-Schleifen. Oder was meintest du?
Und zum Parser: Ich hab doch keine Ahnung, welche der Einträge ich jetzt brauche, um sie in den Baum zu schreiben. Der wird ja übervoll wenn ich die ganze Chart in den Ableitungsbaum übertrage!
die spalte s reicht. die korresponidert nämlich mit allen regeln, die bei position s enden. bei mir jedenfalls, da ich deinen algo noch nicht durchdrungen hab 
ich bin nur ein bisschen verwirrt weil ich nicht verstehe obs mit dem einmaligen durchlaufen durchs chart gemacht ist. im kern geh ich am eingabe symbolarray entlang, das muss bei dir ja auch irgendwie drinne sein?!
Keine Ahnung, ich hab mich an den Folien gehalten, was auch immer die genau tun. Werd schon sehen, ob’s geht. Ansonsten gibt’s halt nen ln -s /yves/brain EarlyParser.java 
ach siehe da folie 59?
Genau die. Seite 56-59.
shit ich hab den algo aus dem chart abgeleitet … muss ich wohl gepennt haben 
ich nehm mal an, wenn der in den folien steht wird er wohl richtig sein 
so und zuguter letzt funktioniert mein parser auch noch nicht mal mit regeln die auf der rechten seite terminale und nichtterminale haben
jedenfalls kommen da keine parsebäume raus …
ähh hatte ich gesagt das der parser nach dem recognizer leicht zu implementieren ist?!
ein irrtum.