Mi chiedo se ANTLR v3, che presenta il suo algoritmo di parsing interno come "LL (*)" sia pienamente rappresentativo dei parser PEG (parsing expression grammar).LL (*) rispetto ai parser PEG: qual è la differenza?
C'è una differenza?
Il ANTLR article si sbagliava su PEG.
LL (*) è un sottoinsieme di DCFG (Deterministic Context Free Grammar), che è un sottoinsieme di CFG (Context Free Grammar).
PEG può esprimere grammatiche sensibili al contesto come A{n}B{n}C{n}, in cui A e B e C presentino n volte. Ecco la definizione:
s := &(x C) A+ y/ε
x := A x B/A B
y := B y C/B C
Ma non v'è alcun modo per definire quali grammatica CFG (la prova prevede pompa lemma). Quindi PEG non è sottoinsieme CFG. Se PEG è superset di CFG? Non lo so.
Due differenze fondamentali tra LL (*) e PEG:
LL (*) possono lookahead solo un modello DFA, mentre PEG può lookahead un modello ricorsivo. Ad esempio, in PEG puoi guardare i paramenti annidati in testa mentre LL (*) non può.
L'operatore scelta / nel PEG è scelta prioritaria (o "possessivo"), il che significa che se si dispone di regola A/AB, non raggiunge mai il lato destro AB. In LL (*) per una regola A | AB, è possibile associare AB.
Se si dispone di una grammatica PEG senza un lookahead, o il vostro modello lookahead può essere ridotto in un DFA, allora può essere tradotto in LL (*). In caso contrario, non è possibile.
Secondo gli strumenti elencati here ANTLR è un rappresentante pieno di un parser PEG:
ANTLR, un generatore di parser consolidata da Terence Parr, supporta numerose funzioni PEG e combina packrat analisi con tecniche di parsing LL .
Esistono alcune estensioni Packrat left-recursive, che, apparentemente, non sono supportate da ANTLR. –
In ANTLR è possibile abilitare backtracking globale su tutte le regole di produzione nella tua grammatica, in modo che per k >= 1 si potrebbe analizzare più o meno la stessa di PEG di. Ovviamente, a causa di tutto il potenziale backtracking, il tempo di esecuzione del parser si degrada. Al costo di (alcuni) memoria è anche possibile abilitare la memoizzazione, facendolo comportarsi come un parser Packrat, in grado di analizzare l'input in tempo lineare.
Quindi no, non c'è molta differenza tra ANTLR e PEG/Packrat (con le opzioni giuste abilitate!).
ANTLR e PEG non sono uguali. È una domanda piuttosto teorica, e penso che sarebbe meglio per voi fare riferimento al documento this scritto da Terrence Parr in cui egli punta esattamente le differenze tra ANTLR e PEG e alcuni vantaggi della strategia di analisi ANTLR LL (*). Non voglio darmi la libertà di parafrasare ciò che ha scritto lì, ma è meglio per voi leggere l'intero documento.
404-ed. Puoi fornire un link aggiornato? – chakrit
La tua grammatica PEG non è ancora corretta. Analizzerà anche A {n} B {n + 1} C {n + 1}. – CoronA
@CoronA Grazie per aver segnalato, ho modificato la risposta con la grammatica aggiornata per garantire che C si verifichi subito dopo A {n} B {n}. – luikore