ANTLR meldet Fehler und ich denke, es sollte in der Lage sein, Eingabe mit Backtracking

Question

Ich habe eine einfache Grammatik, die zum größten Teil funktioniert, aber an einem Ort meldet Fehler und ich denke, es sollte nicht, weil es gelöst werden kann Rückverfolgung verwenden.

Hier ist der Teil, der problematisch ist. Diese

command: object message_chain; 
object: ID; 
message_chain: unary_message_chain keyword_message? 
      | binary_message_chain keyword_message? 
      | keyword_message; 
unary_message_chain: unary_message+; 
binary_message_chain: binary_message+; 
unary_message: ID; 
binary_message: BINARY_OPERATOR object; 
keyword_message: (ID ':' object)+; 

ist vereinfachte Version, Objekt ist komplexer (es kann aufgrund anderer Befehl, Rohwert und so weiter, aber das Teil funktioniert gut). Problem ist in message_chain, in erster Alternative. Für Eingabe wie obj unary1 unary2 funktioniert es gut, aber für die Eingabe wie obj unary1 unary2 keyword1:obj2 ist Trys keyword1 als unäre Nachricht und schlägt fehl, wenn es : erreicht. Ich würde denken, dass es dieser Situation Parser zurückverfolgen würde und dass es gibt : und erkennen, dass das Keyword-Nachricht ist.

Wenn ich Keyword-Nachricht nicht optional machen, funktioniert es gut, aber ich brauche Schlüsselwort-Nachricht als optional.

Parser findet eine Schlüsselwortnachricht, wenn sie in der zweiten Alternative (binary_message) und der dritten Alternative (nur keyword_message) ist. So etwas wie das gibt gute Ergebnisse: 1 + 2 + 3 Keyword1:Value

Was fehlt mir? Backtracking wird in Optionen auf true gesetzt und funktioniert in anderen Fällen in derselben Grammatik.

Danke.

Answer 1

Dies ist nicht wirklich ein Fall für PEG-Backtracking, weil bei Ausfall nur in unvollständigen Ableitungen zu Entscheidungspunkten zurückkehrt. Für die Eingabe obj unary1 unary2 keyword1:obj2 mit einem Token-Lookahead könnte keyword1 von unary_message_chain verbraucht werden. Der Fehler tritt möglicherweise nicht vor keyword_message auf, und als nächstes würde die zweite Alternative von message_chain, d. H. binary_message_chain, versucht werden, so dass die korrekte Syntaxanalyse fehlte.

Da jedoch diese Grammatik LL (2) ist, sollte es möglich sein, Lookahead zu erweitern, um zu vermeiden, keyword1 von innerhalb unary_message_chain zu verbrauchen. Haben Sie versucht, k=2 explizit festzulegen, ohne Backtracking?