El ANTLR article estaba equivocado acerca de PEG.
LL (*) es un subconjunto de DCFG (Gramática libre de contexto determinista), que es un subconjunto de CFG (Gramática libre de contexto).
PEG puede expresar de contexto gramáticas sensibles como A{n}B{n}C{n}
, en los que A
y B
y C
todo ocurre n
veces. Aquí está la definición:
s := &(x C) A+ y/ε
x := A x B/A B
y := B y C/B C
Pero no hay manera de definir la gramática en tales CFG (la prueba implica lema de la bomba). Entonces PEG no es un subconjunto de CFG. Si PEG es superconjunto de CFG? No lo sé.
Dos diferencias clave entre LL (*) y PEG:
LL (*) sólo pueden Lookahead un patrón DFA, mientras que PEG puede Lookahead un patrón recursivo. Por ejemplo, en PEG puedes buscar parásitos anidados mientras LL (*) no puede.
El operador elección /
en PEG es la elección de prioridad (o "posesivo"), lo que significa que si usted tiene la regla A/AB
, nunca alcanza el lado derecho AB
. En LL (*) para una regla A | AB
, es posible hacer coincidir AB
.
Si usted tiene una gramática PEG sin una búsqueda hacia delante, o su patrón de búsqueda hacia delante se puede reducir en un DFA, entonces puede ser traducido a LL (*). Si no, no es posible.
Su gramática PEG aún no está correcta. También analizará A {n} B {n + 1} C {n + 1}. – CoronA
@CoronA Gracias por señalar, edité la respuesta con gramática actualizada para garantizar que una C ocurra inmediatamente después de A {n} B {n}. – luikore