ANTLR: Muster Gier und alternative Reihenfolge

Question

Ich versuche zu verstehen, welche Alternativen in ANTLR Regeln bevorzugen, wenn mehrere übereinstimmen. Gemäß this answer sind Alternativen in Lexer-Regeln ungeordnet, außer wenn nach einem nicht-gierigen Muster (*?, +?, ??). Zum Beispiel diese Grammatik:

lexer grammar Test; 

X : 'z'*? (FOO | FOOBAR); 
fragment FOO: 'foo'; 
BAR: 'bar'; 
fragment FOOBAR: 'foobar'; 

gegebene Eingabe "foobar" entspricht zwei Token: X "foo" und BAR "bar", weil Alternativen in X geordnet. Wenn wir 'z'*? entfernen oder es sogar in einen gierigen 'z'* ändern, werden Alternativen wieder ungeordnet und das einzige übereinstimmende Token ist X "foobar".

Allerdings, wenn ich die Regeln Parser Regeln ändern:

grammar Test; 

x : 'z'*? (foo | foobar); 
foo: 'foo'; 
bar: 'bar'; 
foobar: 'foobar'; 

greediness auf 'z' scheinen gar nicht Materie. Gegeben Eingang „foobar“, Regel x folgt die zweite Alternative und verbraucht den gesamten Eingang, Baum produzierte (x (foobar "foobar"))

Die Frage ist: gibt es eine definitive Dokumentation, wie Lexer und Parser Regeln Eingang verbrauchen und welche Spiele sie bevorzugen, wenn mehrere Sind möglich?

Answer 1

gibt es eine definitive Dokumentation, wie Lexer und Parser Regeln Eingangs verbrauchen und welche Spiele sie es vorziehen, wenn mehrere sind möglich?

Definitive Dokumentation (außer den Quelltext zu lesen):

1) Sam Harwell des (der Autor) Kommentare in Stackoverflow

2) Terence Parr Buch für ANTLR4

Und für Ihre Die vollständige Interpretation der Parserregeln finden Sie in Terence Parrs Buch:

Kapitel 15.6 Wi ldcard Operator und Nongreedy Subrules-> Nongreedy Lexer Unterregeln

Nachdem innerhalb einer lexikalischen Regel durch einen nongreedy Subrule Kreuzung, alle Entscheidung von da an zu machen ist „erstes Spiel gewinnt.“ Für Beispiel alternative ‚ab‘ in der Regel rechte Seite .*? ('a' | 'ab') ist dead code und kann niemals abgeglichen werden. Wenn die Eingabe ab ist, entspricht die erste Alternative, 'a', dem ersten Zeichen und ist daher erfolgreich. ('a' | 'ab') von selbst auf der rechten Seite einer Regel entspricht der zweite Alternative für die Eingabe ab. Diese Eigenart ergibt sich aus einer nichtgeredeten Designentscheidung, die zu kompliziert ist, um hier näher zu kommen.

Also für eine komplette Grammatik wie folgt aus:

grammar TestGrammar; 
test:XXX EOF; 
WS: [ \t\f]+ -> channel(1); 
CRLF: '\r'? '\n' -> channel(1); 
XXX : 'z'*? (FOO | FOOBAR) {System.out.println(getText());}; 

fragment FOO: 'foo'; 
fragment BAR: 'bar'; 
fragment FOOBAR: 'foobar'; 

Für eine Eingabe wie zfoo. Sie wird durch die XXX-Regel in Token umgewandelt und der Lexer-Aktionsausgang bestätigt dies. Für Eingabe zfoobar.Die ersten 4 Zeichen zfoo werden immer noch durch die Regel XXX als unerkannte Tokens wegen der oben erwähnten Regel "First match wins" als Token behandelt.

Und für Nicht-gierige Parser Unterregeln:

Nongreedy Parser Unterregeln

Nongreedy Unterregeln und Platzhalter sind auch nützlich innerhalb Parser „Fuzzy-Parsing“, wo das Ziel ist es, Extrakt Informationen zu tun aus eine Eingabedatei, ohne die vollständige Grammatik angeben zu müssen. Im Gegensatz zu Nicht-Lexikon Entscheidungen treffen die Parser immer global richtige Entscheidungen. Ein Parser trifft nie eine Entscheidung, die letztendlich dazu führt, dass eine gültige Eingabe später während des Parse fehlschlägt. Hier ist die zentrale Idee: nongredy Parser Unterregeln die kürzeste Folge von Token, die eine erfolgreiche Parser für einen gültigen Eingabesatz bewahrt.

Die Sortierung wird den Unterregeln nicht auferlegt.