Kann mich jemand aufklären, warum ein rekursiver Abstiegsparser mit Backtracking, der die Produktionen und S → a a (in dieser Reihenfolge) versucht, die durch die Grammatik S → a S a | gebildete Sprache nicht erkennt a a .
Es scheint nur Wörter aus der Sprache zu analysieren n ≥ 1 } .
Ich habe einen solchen Parser mit diesem ABNF-Parser-Generator mit der Produktionsregel generiert, S = "a" S "a" / "aa"
und der Parser erkennt das Wort aaaaaa
beispielsweise nicht.
Ich würde erwarten, dass die Produktion bis die Verkettung der Endknoten des Analysebaums von links mit 7 beginnt , und dann den Analysebaum hinaufgehen und stattdessen die Produktion S → a a auswählen, bis der Baum aussieht so was:a
S
/ | \
a S a
/ | \
a S a
/ \
a a
context-free
formal-grammars
compilers
parsers
meribold
quelle
quelle
aaaaaa
.aaaaaa
sollte analysiert werden und nicht. Aberaaaa
analysiert. Sie haben anscheinend Recht mit Potenzen von 2. Das Ding muss abgehört werden. es analysiert nuraa
mitS = "aa" / "a" [S] "a"
. Können Sie verfolgen, was der Parser tut?Antworten:
Dies ist keine gute Antwort, aber die Analysebäume passen nicht zu den normalen Kommentaren.
Der Analysebaum hat jedoch die folgende Form:
oder wenn Sie diese Präsentation bevorzugen, mit den Terminals in verschiedenen Zeilen
Ich habe überprüft, ob der ABNF-Parser-Generator nicht zu funktionieren scheint, aber ich weiß nicht, wie ich verfolgen soll, was er tut.
Es ist ein bisschen überraschend, eine so aufwändige Site um einen Buggy-Parser herum zu haben, der außerdem eine völlig uninteressante Parsing-Technik verwendet.
Nach einem weiteren Blick darauf:
Ich glaube, ich habe eine Ursache für das Problem gefunden. Die eckigen Klammern bedeuten optional .
Ihre Grammatik sollte also entweder
S = "a" S "a" / "aa"
oder geschrieben seinS = "a" [S] "a"
. Dann scheint es richtig zu funktionieren.Aber das System geht anscheinend verloren, wenn es zweimal dieselbe Regel in verschiedenen Formen gibt. Ich bin mir nicht sicher warum.
Ich habe keine Seite gefunden, auf der diese syntaktischen Probleme zur Angabe der Grammatik erläutert werden.
Ich betrachte diesen Buggy immer noch.
quelle
S ::= 'a'<S>'a' | 'a''a'
aaaaaa
Bei der VerwendungS = "a" S "a" / "aa"
wird immer noch nicht analysiert , aber Sie scheinen mit den Klammern Recht zu haben.S = "a" S "a" / "aa"
... Ich habe zu schnell getestet und auf "Generieren" geklickt, anstatt zu analysieren.s1()
true
s()
s2()
Erwägen Sie, das Wort
aaaaaa
erneut zu analysieren . An einem Punkt sieht der Analysebaum folgendermaßen aus:s()
true
S
Ich neige dazu, dies als Problem bei meiner Implementierung zu betrachten und nicht als Rückverfolgung von Parsern rekursiver Abstammung im Allgemeinen.
quelle
Es ist eine Funktion, kein Fehler
Sehen Sie sich genau an, wann und wo Backtracking stattfindet:
Der entscheidende Punkt hierbei ist, dass der Parser nach der Position zurückverfolgt, an der das letzte übereinstimmende Zeichen gefunden wurde. Deshalb "springt" es von Baum 11 mit l = aaaaaaaa zum 12. Baum mit l = aaaa, indem es S -> aa bei l [7] verwendet.
quelle