Come funziona il backtracking in peg.js (con esempio)?

Question

ho definito il seguente minimo Peg.js grammatica:

start = "A1"/"A123" 

che si può provare in the sandbox.

Mi sarei aspettato che corrispondesse "A1" e "A123" (secondo la mia idea di come funziona il backtracking). Ma non è questo il caso: la grammatica riconosce "A1" ma non "A123".

Nota: Non sto cercando per il consiglio "invertire l'ordine dei termini", come nel relativo domanda How to transform a simple grammar into something which works in PEG.js (expected "a" but "a" found). Piuttosto, sto cercando di capire il comportamento che sto vedendo e perché il backtracking di Peg.js non si applica in questo caso. Per una spiegazione del motivo per cui l'inversione dell'ordine dei miei termini non aiuta, vedi l'esempio più realistico di seguito.

---

Per un esempio più realistico, considerano le unità parsing. Una grammatica dovrebbe riconoscere le unità metriche (come "m", "mol") con prefissi facoltativi, come "mm", "mmol", così come le unità non metriche come "yr", "settimana" o "mo".

La seguente grammatica Peg.js non riconoscerà "mol" perché viene interrotta consumando "mo" e non torna indietro. (Cambiare l'ordine dei termini non aiuta, anzi, farà sì che "mo" di essere riconosciuto a scapito di "mol" o "mmol".)

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

posso fare la cosa analoga in Antlr con buon successo:

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

Answer 1

il problema è con il concetto di backtracking. I parser PEG non eseguono il backtrack come altri parser ricorsivi o Prolog do. Piuttosto, di fronte a una scelta, un parser PEG proverà tutte le opzioni fino a quando non ci riuscirà. Una volta che ci riesce, si impegnerà a farlo indipendentemente da come è stata invocata la regola.

Dal Wikipedia article:

differenza nelle grammatiche context-free e le espressioni regolari, tuttavia, questi operatori si comportano sempre avidamente, consuma tanto input come possibile e mai backtracking.

Quello che chiedi nel caso complesso è lo stesso che è stato chiesto in this question. La risposta finora è Sì: devi modificare le regole nelle grammatiche PEG per assicurarti che l'opzione più lunga venga sempre trovata per prima, anche se il risultato è una grammatica un po 'più brutta.

Un modo per ottimizzare le grammatiche PEG è quello di utilizzare lookaheads (che è uno dei motivi principali per cui lookaheads sono descritte in PEG):

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

Questo legato alla progettazione. Spetta a te specificare corretto o regole che verranno utilizzate per la corrispondenza.

La citazione dall'originale white paper:

Questi strumenti non fanno disegno sintassi del linguaggio facile, naturalmente. Nel punto di dover determinare se due alternative possibili in un CFG sono ambigue, i PEG presentano progettisti di linguaggio con l'analoga sfida per determinare se due alternative in un'espressione '/' possono essere riordinate senza influire sulla lingua. Questa domanda è spesso ovvia, ma a volte non lo è, ed è indecidibile in generale. Come per la scoperta dell'ambiguità nei CFG, tuttavia, abbiamo la speranza di trovare gli algoritmi automatici per identificare la sensibilità degli ordini o l'insensibilità in situazioni comuni, con .

In questo semplice caso PEG.js potrebbe essere un po 'più intelligente e riconoscere che le regole specificate sono ambigue. Probabilmente vale la pena di scrivere l'autore allo ask.