Me pregunto si ANTLR v3, que presenta su algoritmo de análisis interno como "LL (*)" es completamente representativo de los analizadores de PEG (gramática de la expresión de análisis).LL (*) versus analizadores PEG: ¿cuál es la diferencia?
¿Hay alguna diferencia?
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.
Según las herramientas enumeradas here antlr es un representante lleno de un analizador de PEG:
antlr, un generador de analizadores sintácticos bien establecida por Terence Parr, soporta amplias características de PEG y combina packrat análisis con técnicas de análisis sintáctico LL .
Existen algunas extensiones de Packrat recursivas a la izquierda, que aparentemente no son compatibles con ANTLR. –
En antlr puede habilitar el retroceso global sobre todas las reglas de producción en su gramática, de modo que para k >= 1 se podría analizar más o menos el mismo que el PEG. Por supuesto, debido a todo el retroceso potencial, el tiempo de ejecución del analizador se degrada. A cambio de (algo) de memoria, también podría habilitar la memoria, haciendo que se comporte como un analizador de paquetes, capaz de analizar la entrada en tiempo lineal.
Así que no, no hay mucha diferencia w.r.t ANTLR y PEG/Packrat (con las opciones correctas habilitadas!).
ANTLR y PEG no son lo mismo. Es una pregunta muy teórica, y creo que será lo mejor para ti consultar el documento this escrito por Terrence Parr donde señala exactamente las diferencias entre ANTLR y PEG y algunas ventajas de la estrategia de análisis ANTLR LL (*). No quiero darme la libertad de parafrasear lo que escribió allí, pero es mejor que leas todo el documento.
404-ed. ¿Puedes proporcionar un enlace actualizado? – chakrit
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