Wie funktioniert Backtracking in peg.js (mit Beispiel)?

Question

Ich habe die folgende minimale Peg.js Grammatik definiert:

start = "A1"/"A123" 

, die Sie in the sandbox versuchen.

Ich hätte erwartet, "A1" sowie "A123" (nach meiner Vorstellung, wie Backtracking funktioniert) zu entsprechen. Aber das ist nicht der Fall: Die Grammatik erkennt "A1", aber nicht "A123".

Hinweis: Ich bin nicht auf der Suche nach dem Rat "umkehren Sie die Reihenfolge Ihrer Begriffe" wie in der verwandten Frage How to transform a simple grammar into something which works in PEG.js (expected "a" but "a" found). Ich versuche vielmehr, das Verhalten, das ich sehe, zu verstehen, und warum Peg.js 'Backtracking in diesem Fall nicht anwendbar ist. Für eine Erklärung, warum die Umkehrung der Reihenfolge meiner Begriffe nicht hilft, siehe das realistischere Beispiel unten.

---

Um ein realistischeres Beispiel zu erhalten, betrachten Sie Einheitenparsing. Eine Grammatik sollte metrische Einheiten (wie "m", "mol") mit optionalen Präfixen wie "mm", "mmol", sowie nichtmetrischen Einheiten wie "Jahr", "Woche" oder "Mo" erkennen.

Die folgende Peg.js-Grammatik wird "mol" nicht erkennen, weil sie "mo" austrickst und nicht zurückgeht. (Änderung der Reihenfolge der Begriffe hilft nicht, oder vielmehr bewirkt „mo“ auf Kosten der „mol“ erkannt werden oder „mmol“.)

start = nonmetric/metric/prefix metric 
metric = "mol"/"l"/"m"/"g" 
nonmetric = "yr"/"mo"/"week"/"day"/"hour" 
prefix = "m"/"k"/"c" 

Ich kann tun, um die analoge Sache in Antlr mit gutem Erfolg:

grammar units; 
start : nonmetric | metric | prefix metric; 
metric : 'mol' | 'l' | 'm' | 'g'; 
nonmetric : 'yr' | 'mo' | 'week' | 'day' | 'hour'; 
prefix : 'm' | 'k' | 'c'; 

Answer 1

das Problem ist mit dem Konzept der Rückzieher. PEG-Parser werden nicht wie andere Recursive-Descent-Parser oder Prolog zurückgesetzt. Wenn Sie mit einer Auswahl konfrontiert werden, versucht ein PEG-Parser jede Option, bis einer erfolgreich ist. Sobald es einem gelingt, wird es sich darauf festlegen, egal wie die Regel aufgerufen wurde.

Vom Wikipedia article:

Anders als in kontextfreien Grammatiken und reguläre Ausdrücke, aber diese Operatoren immer gierig verhalten, wie viel Input wie möglich raubend und nie Rückzieher.

Was Sie in dem komplexen Fall fragen, ist das gleiche, das in this question gefragt wird. Die Antwort ist Ja: Sie müssen die Regeln in PEG-Grammatiken anpassen, um sicherzustellen, dass die längste Option immer zuerst abgeglichen wird, auch wenn das Ergebnis eine etwas hässlichere Grammatik ist.

Eine Möglichkeit PEG Grammatiken zu zwicken ist Lookaheads zu verwenden (das ist einer der Hauptgründe, warum Lookaheads in PEG gekennzeichnet sind):

start = nonmetric/metric/prefix metric 
metric = "mol"/"l"/!"mo" "m"/"g" 
nonmetric = "yr"/!"mol" "mo"/"week"/"day"/"hour" 
prefix = !("mol"/"mo") "m"/"k"/"c" 

Answer 2

Das ist von Entwurf. Es liegt an Ihnen, das richtige order oder Regeln, die für das Matching verwendet werden.

Das Zitat aus dem ursprünglichen white paper:

Diese Tools Sprachsyntax Design einfach nicht, natürlich machen. In Ort der zu bestimmen, ob zwei mögliche Alternativen in einer CFG mehrdeutig sind, präsentieren PEGs Sprache Designer mit der analogen Herausforderung der Bestimmung, ob zwei Alternativen in einem '/' Ausdruck kann neu geordnet werden, ohne die Sprache zu beeinflussen. Diese Frage ist oft offensichtlich, aber manchmal nicht, und ist im Allgemeinen unentschlossen. Wie bei der Entdeckung von Mehrdeutigkeit in CFGs, haben wir jedoch die Hoffnung, automatische Erkennung von Ordnungsempfindlichkeit oder in konservativen Situationen konservative finden.

In diesem einfachen Fall könnte die PEG.js etwas schlauer sein und erkennen, dass die von Ihnen angegebenen Regeln nicht eindeutig sind. Wahrscheinlich lohnt sich ask der Autor.