Die folgende einfache "Taschenrechnerausdruck" Grammatik (BNF) kann leicht mit dem trivialen rekursiven Abstiegs-Parser analysiert werden, der prädiktiv LL (1):
ist %Vor%Weil es immer ausreicht, das nächste Token zu sehen, um die auszuwählende Regel zu kennen. Angenommen, ich füge die folgende Regel hinzu:
%Vor%Für die Interaktion mit dem Taschenrechner in der Befehlszeile mit Variablen wie folgt:
%Vor% Stimmt es, dass ich nicht einen einfachen LL (1) -Predictive Parser verwenden kann, um <command> -Regeln zu analysieren? Ich habe versucht, den Parser dafür zu schreiben, aber es scheint, dass ich mehr Tokens weiterleiten muss. Ist die Lösung Backtracking zu verwenden, oder kann ich einfach LL (2) implementieren und immer zwei Tokens nach vorne schauen?
Wie man mit RD-Parser-Generatoren dieses Problem behandelt (zB ANTLR)?
Das Problem mit
%Vor% ist, dass, wenn Sie <id> "sehen", Sie nicht sagen können, ob es der Beginn einer Zuweisung (zweite Regel) oder ein " <factor> " ist. Sie werden nur wissen, wann Sie das nächste Token lesen werden.
AFAIK ANTLR ist LL (*) (und kann auch Ratte-Pack-Parser erzeugen, wenn ich mich nicht irre), also wird es wahrscheinlich mit dieser Grammatik umgehen, wenn man zwei Token gleichzeitig betrachtet.
Wenn Sie mit der Grammatik spielen können, würde ich vorschlagen, entweder ein Schlüsselwort für die Zuweisung hinzuzufügen (z. B. let x = 8 ):
oder verwenden Sie die = zur Bewertung:
Das Problem ist, dass die Grammatik:
%Vor%ist keine wechselseitig rekursive Prozedur. Für einen rekursiven anständigen Parser müssen Sie ein nicht-rekursives Äquivalent bestimmen.
rdentato posts zeigt, wie Sie das beheben können, vorausgesetzt, Sie können mit der Grammatik spielen. Dieser Powerpoint beschreibt das Problem etwas genauer und zeigt, wie es korrigiert werden kann: Ссылка
ANTLR 3 verwendet einen "LL (*)" Parser im Gegensatz zu einem LL (k) Parser, so dass es nach vorne schaut, bis es das Ende der Eingabe erreicht, wenn es ohne Rückverfolgung einen speziell optimierten deterministischen endlichen Automaten (DFA) verwenden muss.
Tags und Links compilation parsing recursive-descent