En informática , una gramática de expresión sintáctica ( PEG ) es un tipo de gramática formal analítica , es decir, describe un lenguaje formal en términos de un conjunto de reglas para reconocer cadenas en el lenguaje. El formalismo fue introducido por Bryan Ford en 2004 [1] y está estrechamente relacionado con la familia de lenguajes de análisis de arriba hacia abajo introducidos a principios de la década de 1970. Sintácticamente, los PEG también se parecen a las gramáticas libres de contexto.(CFG), pero tienen una interpretación diferente: el operador de elección selecciona la primera coincidencia en PEG, mientras que es ambiguo en CFG. Esto está más cerca de cómo el reconocimiento de cadenas tiende a realizarse en la práctica, por ejemplo, mediante un analizador sintáctico descendente recursivo .
A diferencia de los CFG, los PEG no pueden ser ambiguos ; si una cadena analiza, tiene exactamente un árbol de análisis válido . Se conjetura que existen lenguajes libres de contexto que no pueden ser reconocidos por un PEG, pero esto aún no está probado. [1] Los PEG son adecuados para analizar lenguajes informáticos (y lenguajes humanos artificiales como Lojban ), pero no lenguajes naturales donde el rendimiento de los algoritmos PEG es comparable a los algoritmos CFG generales como el algoritmo Earley . [2]
Definición
Sintaxis
Formalmente, una gramática de expresión de análisis consiste en:
- Un conjunto finito N de símbolos no terminales .
- Un conjunto Σ finito de símbolos terminales que es disjuntos de N .
- Un conjunto P finito de reglas de análisis .
- Una expresión e S denominada expresión inicial .
Cada regla de análisis sintáctico en P tiene la forma A ← e , donde A es un símbolo no terminal ye es una expresión de análisis sintáctico . Una expresión de análisis es una expresión jerárquica similar a una expresión regular , que se construye de la siguiente manera:
- Una expresión de análisis sintáctico atómico consta de:
- cualquier símbolo de terminal,
- cualquier símbolo no terminal, o
- la cadena vacía ε.
- Dado cualquier existente analizar expresiones e , e 1 , y e 2 , una nueva expresión de análisis sintáctico puede construirse utilizando los siguientes operadores:
- Secuencia : e 1 e 2
- Elección ordenada : e 1 / e 2
- Cero o más : e *
- Uno o más : e +
- Opcional : e ?
- Y-predicado : & e
- No predicado :! mi
Semántica
La diferencia fundamental entre las gramáticas libres de contexto y las gramáticas de expresión es que el operador de elección del PEG está ordenado . Si la primera alternativa tiene éxito, la segunda alternativa se ignora. Por tanto, la elección ordenada no es conmutativa , a diferencia de la elección no ordenada como en las gramáticas libres de contexto. La elección ordenada es análoga a los operadores de corte suave disponibles en algunos lenguajes de programación lógica .
La consecuencia es que si un CFG se transcribe directamente a un PEG, cualquier ambigüedad en el primero se resuelve seleccionando determinísticamente un árbol de análisis sintáctico de los análisis sintácticos posibles. Al elegir cuidadosamente el orden en el que se especifican las alternativas gramaticales, un programador tiene un gran control sobre qué árbol de análisis se selecciona.
Al igual que las gramáticas booleanas libres de contexto , las gramáticas de expresión también añaden los predicados and y no sintácticos . Debido a que pueden usar una subexpresión arbitrariamente compleja para "mirar hacia adelante" en la cadena de entrada sin consumirla realmente, brindan una potente función de búsqueda y desambiguación sintáctica , en particular cuando el reordenamiento de las alternativas no puede especificar el árbol de análisis exacto deseado.
Interpretación operativa de expresiones de análisis
Cada no terminal en una gramática de expresión de análisis sintáctico representa esencialmente una función de análisis sintáctico en un analizador sintáctico descendente recursivo , y la expresión de análisis sintáctica correspondiente representa el "código" que comprende la función. Cada función de análisis toma conceptualmente una cadena de entrada como argumento y produce uno de los siguientes resultados:
- éxito , en el que la función puede avanzar opcionalmente o consumir uno o más caracteres de la cadena de entrada que se le proporciona, o
- falla , en cuyo caso no se consume ninguna entrada.
Una expresión de análisis sintáctico atómico que consta de un solo terminal (es decir, literal) tiene éxito si el primer carácter de la cadena de entrada coincide con ese terminal y, en ese caso, consume el carácter de entrada; de lo contrario, la expresión arroja un resultado de error. Una expresión de análisis atómico que consta de la cadena vacía siempre tiene un éxito trivial sin consumir ninguna entrada.
Una expresión de análisis sintáctico atómica que consiste en un no terminal A representa un recursiva llamada a la función no terminal A . Un no terminal puede tener éxito sin consumir realmente ninguna entrada, y esto se considera un resultado distinto del fracaso.
El operador de secuencia e 1 e 2 primero invoca e 1 , y si e 1 tiene éxito, posteriormente invoca e 2 en el resto de la cadena de entrada dejada sin consumir por e 1 , y devuelve el resultado. Si e 1 o e 2 fallan, entonces la expresión de secuencia e 1 e 2 falla (no consume entrada).
El operador de elección e 1 / e 2 primero invoca e 1 , y si e 1 tiene éxito, devuelve su resultado inmediatamente. De lo contrario, si e 1 falla, entonces el operador de elección retrocede a la posición de entrada original en la que invocaba e 1 , pero luego llama a e 2 , devolviendo el resultado de e 2 .
El cero-o-más , de una sola o-más , y opcionales operadores consumen cero o más, uno o más, o cero o uno repeticiones consecutivas de su sub-expresión e , respectivamente. Sin embargo, a diferencia de las gramáticas libres de contexto y las expresiones regulares , estos operadores siempre se comportan con avidez , consumiendo tanta información como sea posible y nunca retrocediendo. (Los comparadores de expresiones regulares pueden comenzar haciendo coincidir codiciosamente, pero luego retrocederán e intentarán coincidencias más cortas si no coinciden). Por ejemplo, la expresión a * siempre consumirá tantas a como estén disponibles consecutivamente en la cadena de entrada, y la expresión (a * a) siempre fallará porque la primera parte (a *) nunca dejará ninguna a para que la segunda parte coincida.
La expresión de predicado and & e invoca la subexpresión e , y luego tiene éxito si e tiene éxito y falla si e falla, pero en cualquier caso nunca consume ninguna entrada .
¡La expresión de no predicado ! Tiene éxito si e falla y falla si e tiene éxito, nuevamente sin consumir ninguna entrada en ambos casos.
Ejemplos de
Este es un PEG que reconoce fórmulas matemáticas que aplican las cinco operaciones básicas a números enteros no negativos.
Expr ← Suma Suma ← Producto (( '+' / '-' ) Producto ) * Producto ← Potencia (( '*' / '/' ) Potencia ) * Potencia ← Valor ( '^' Potencia ) ? Valor ← [ 0-9 ] + / '(' Expr ')'
En el ejemplo anterior, los símbolos terminales son caracteres de texto, representados por caracteres entre comillas simples, como '('
y ')'
. El rango [0-9]
también es un atajo para diez caracteres, que indica cualquiera de los dígitos del 0 al 9. (Esta sintaxis de rango es la misma que la sintaxis utilizada por las expresiones regulares ). Los símbolos no terminales son los que se expanden a otras reglas: Valor , Potencia , Producto , Suma y Expr . Tenga en cuenta que las reglas Suma y Producto no conducen a la asociatividad izquierda deseada de estas operaciones (no tratan la asociatividad en absoluto, y debe manejarse en el paso de posprocesamiento después del análisis sintáctico) y la regla de potencia (por refiriéndose a sí mismo a la derecha) da como resultado la asociatividad a la derecha deseada del exponente. También tenga en cuenta que una regla como (con la intención de lograr la asociatividad por la izquierda) causaría una recursividad infinita, por lo que no se puede usar en la práctica aunque se pueda expresar en la gramática.Sum ← Sum (('+' / '-') Product)?
La siguiente regla recursiva coincide con las declaraciones estándar if / then / else de estilo C de tal manera que la cláusula opcional "else" siempre se une al "if" más interno, debido a la priorización implícita del operador '/'. (En una gramática libre de contexto , esta construcción produce la clásica ambigüedad colgando else ).
S ← 'si' C 'entonces' S 'si no' S / 'si' C 'entonces' S
La siguiente regla recursiva coincide tipo Pascal comentario anidado sintaxis, (* which can (* nest *) like this *)
. Los símbolos de comentario aparecen entre comillas simples para distinguirlos de los operadores PEG.
Inicio ← '(*' Fin ← '*)' C ← Inicio N * Fin N ← C / ( ! Inicio ! Fin Z ) Z ← cualquier carácter individual
La expresión de análisis coincide y consume el texto "foo", pero solo si va seguida de la "barra" de texto. La expresión análisis coincide con el texto "foo", pero sólo si es no seguida por la "barra" de texto. La expresión coincide con una sola "a", pero solo si no forma parte de una secuencia arbitrariamente larga de a seguida de una b.foo &(bar)
foo !(bar)
!(a+ b) a
La expresión de análisis coincide y consume una secuencia de longitud arbitraria de a y b. La regla de producción describe el "lenguaje coincidente" simple y libre de contexto.('a'/'b')*
S ← 'a' ''S''? 'b'
. La siguiente gramática de expresión de análisis describe el lenguaje clásico sin contexto:
S ← & ( A 'c' ) 'a' + B ! . ¿A ← 'a' A ? 'b' B ← 'b' B ? 'C'
Implementación de analizadores a partir del análisis de gramáticas de expresión
Cualquier gramática de expresión de análisis se puede convertir directamente en un analizador de descenso recursivo . [3] Sin embargo, debido a la capacidad de búsqueda anticipada ilimitada que proporciona el formalismo gramatical, el analizador sintáctico resultante podría exhibir un rendimiento de tiempo exponencial en el peor de los casos.
Es posible obtener un mejor rendimiento para cualquier gramática de expresión de análisis sintáctico convirtiendo su analizador sintáctico descendente recursivo en un analizador sintáctico packrat , que siempre se ejecuta en tiempo lineal , a costa de requisitos de espacio de almacenamiento sustancialmente mayores. Un analizador packrat [3] es una forma de analizador similar a un analizador sintáctico descendente recursivo en construcción, excepto que durante el proceso de análisis sintáctico memoriza los resultados intermedios de todas las invocaciones de las funciones de análisis recursivas mutuamente , asegurando que cada función de análisis sintáctico solo se invoca en la mayoría una vez en una posición de entrada determinada. Debido a esta memorización, un analizador packrat tiene la capacidad de analizar muchas gramáticas libres de contexto y cualquier gramática de expresión de análisis (incluidas algunas que no representan lenguajes libres de contexto) en tiempo lineal. Se conocen ejemplos de analizadores sintácticos descendentes recursivos memorizados desde al menos desde 1993. [4] Este análisis del rendimiento de un analizador sintáctico packrat supone que hay suficiente memoria disponible para contener todos los resultados memorizados; en la práctica, si no hay suficiente memoria, algunas funciones de análisis pueden tener que invocarse más de una vez en la misma posición de entrada y, en consecuencia, el analizador puede tardar más que un tiempo lineal.
También es posible crear analizadores sintácticos LL y analizadores sintácticos LR a partir del análisis sintáctico de gramáticas de expresión, con un mejor rendimiento en el peor de los casos que un analizador sintáctico descendente recursivo, pero luego se pierde la capacidad de búsqueda anticipada ilimitada del formalismo gramatical. Por lo tanto, no todos los lenguajes que se pueden expresar mediante el análisis sintáctico de gramáticas de expresión pueden ser analizados por analizadores LL o LR.
Ventajas
En comparación con las expresiones regulares puras (es decir, sin referencias inversas), los PEG son estrictamente más potentes, pero requieren mucha más memoria. Por ejemplo, una expresión regular intrínsecamente no puede encontrar un número arbitrario de pares coincidentes de paréntesis, porque no es recursiva, pero un PEG sí. Sin embargo, un PEG requerirá una cantidad de memoria proporcional a la longitud de la entrada, mientras que un comparador de expresiones regulares requerirá solo una cantidad constante de memoria.
Cualquier PEG se puede analizar en tiempo lineal usando un analizador packrat, como se describió anteriormente.
Muchos CFG contienen ambigüedades, incluso cuando están destinados a describir lenguajes inequívocos. El problema de " colgar más " en C, C ++ y Java es un ejemplo. Estos problemas a menudo se resuelven aplicando una regla fuera de la gramática. En un PEG, estas ambigüedades nunca surgen debido a la priorización.
Desventajas
Consumo de memoria
El análisis sintáctico PEG se realiza normalmente mediante el análisis sintáctico de packrat , que utiliza la memorización [5] [6] para eliminar los pasos de análisis sintácticos redundantes. El análisis sintáctico de Packrat requiere un almacenamiento proporcional al tamaño de entrada total, en lugar de la profundidad del árbol de análisis sintáctico como ocurre con los analizadores sintácticos LR. Ésta es una diferencia significativa en muchos dominios: por ejemplo, el código fuente escrito a mano tiene una profundidad de anidación de expresiones efectivamente constante independientemente de la longitud del programa; las expresiones anidadas más allá de una cierta profundidad tienden a refactorizarse.
Para algunas gramáticas y algunas entradas, la profundidad del árbol de análisis puede ser proporcional al tamaño de entrada, [7] por lo que tanto un analizador LR como un analizador packrat parecerán tener el mismo rendimiento asintótico en el peor de los casos. Un análisis más preciso tendría en cuenta la profundidad del árbol de análisis por separado del tamaño de entrada. Esto es similar a una situación que surge en los algoritmos de gráficos : el algoritmo Bellman-Ford y el algoritmo Floyd-Warshall parecen tener el mismo tiempo de ejecución () si solo se considera el número de vértices. Sin embargo, un análisis más preciso que tenga en cuenta el número de aristas como un parámetro separado asigna al algoritmo de Bellman-Ford un tiempo de, que es cuadrática para gráficos dispersos con .
Recursividad indirecta por la izquierda
Un PEG se llama bien formado [1] si no contiene reglas recursivas a la izquierda , es decir, reglas que permiten que un no terminal se expanda a una expresión en la que el mismo no terminal aparece como el símbolo más a la izquierda. Para un analizador de arriba hacia abajo de izquierda a derecha, tales reglas causan una regresión infinita: el análisis expandirá continuamente el mismo no terminal sin avanzar en la cadena.
Por lo tanto, para permitir el análisis sintáctico de packrat, se debe eliminar la recursividad por la izquierda. Por ejemplo, en la gramática aritmética anterior, sería tentador cambiar algunas reglas para que el orden de precedencia de productos y sumas se pudiera expresar en una línea:
Valor ← [ 0-9. ] + / '(' Expr ')' Producto ← Expr (( '*' / '/' ) Expr ) * Suma ← Expr (( '+' / '-' ) Expr ) * Expr ← Producto / Suma / Valor
En esta nueva gramática, hacer coincidir un Expr requiere probar si un Producto coincide, mientras que hacer coincidir un Producto requiere probar si un Expr coincide. Debido a que el término aparece en la posición más a la izquierda, estas reglas conforman una definición circular que no se puede resolver. (Existen definiciones circulares que pueden resolverse, como en la formulación original del primer ejemplo, pero se requiere que tales definiciones no muestren recursividad patológica). Sin embargo, las reglas de recursividad por la izquierda siempre se pueden reescribir para eliminar la recursividad por la izquierda. [2] [8] Por ejemplo, la siguiente regla CFG recursiva a la izquierda:
cadena-de-a ← cadena-de-una 'a' | 'a'
se puede reescribir en un PEG usando el operador más:
cadena-de-a ← 'a' +
El proceso de reescribir reglas recursivas indirectamente a la izquierda es complejo en algunos analizadores de paquetes, especialmente cuando están involucradas acciones semánticas.
Con algunas modificaciones, el análisis tradicional de packrat puede admitir la recursividad directa a la izquierda, [3] [9] [10] pero hacerlo da como resultado una pérdida de la propiedad de análisis de tiempo lineal [9], que generalmente es la justificación para usar PEG y el análisis de packrat. en primer lugar. Sólo el algoritmo de análisis sintáctico OMeta [9] admite la recursión izquierda directa e indirecta total sin complejidad adicional concomitante (pero nuevamente, con una pérdida de la complejidad de tiempo lineal), mientras que todos los analizadores GLR admiten la recursión izquierda.
Poder expresivo
Los analizadores de PEG packrat no pueden reconocer algunas reglas CFG no deterministas e inequívocas, como las siguientes: [2]
S ← 'x' S 'x' | 'X'
Ni los algoritmos de análisis sintáctico LL (k) ni LR (k) son capaces de reconocer este ejemplo. Sin embargo, esta gramática puede ser utilizada por un analizador CFG general como el algoritmo CYK . Sin embargo, el lenguaje en cuestión puede ser reconocido por todos estos tipos de analizadores, ya que de hecho es un lenguaje regular (el de cadenas de un número impar de x).
Es un problema abierto dar un ejemplo concreto de un lenguaje libre de contexto que no puede ser reconocido por una gramática de expresión de análisis sintáctico. [1]
Detección de ambigüedad e influencia del orden de las reglas en el lenguaje que coincide
Los generadores de analizadores sintácticos LL (k) y LR (k) no se completarán cuando la gramática de entrada sea ambigua. Esta es una característica en el caso común de que la gramática no sea ambigua pero sea defectuosa. Un generador de analizadores sintácticos PEG resolverá las ambigüedades no deseadas antes de que coincidan primero, que pueden ser arbitrarias y dar lugar a análisis sorprendentes.
El orden de las producciones en una gramática PEG afecta no solo a la resolución de la ambigüedad, sino también al lenguaje emparejado . Por ejemplo, considere el primer ejemplo de PEG en el artículo de Ford [1] (ejemplo reescrito en notación pegjs.org/online, y etiquetado como G1 y G2):
- G1:
A = "a" "b" / "a"
- G2:
A = "a" / "a" "b"
Ford señala que la segunda alternativa en la última regla PEG nunca tendrá éxito porque la primera opción siempre se toma si la cadena de entrada ... comienza con 'a'. . [1] Específicamente, (es decir, el idioma que coincide con G1) incluye la entrada "ab", pero no es. Por lo tanto, agregar una nueva opción a una gramática PEG puede eliminar cadenas del idioma coincidente, por ejemplo, G2 es la adición de una regla a la gramática de producción única A = "a" "b"
, que contiene una cadena que no coincide con G2. Además, la construcción de una gramática que coincidade las gramáticas PEG G1 y G2 no siempre es una tarea trivial. Esto está en marcado contraste con CFG, en el que la adición de una nueva producción no puede eliminar cadenas (aunque puede introducir problemas en forma de ambigüedad), y una gramática (potencialmente ambigua) para se puede construir
S → inicio ( G1 ) | inicio ( G2 )
Análisis PEG ascendente
Un analizador sintáctico pika [11] utiliza programación dinámica para aplicar reglas PEG de abajo hacia arriba y de derecha a izquierda, que es el inverso del orden de descenso recursivo normal de arriba hacia abajo, de izquierda a derecha. El análisis en orden inverso resuelve el problema de recursividad por la izquierda, permitiendo que las reglas recursivas por la izquierda se usen directamente en la gramática sin ser reescritas en una forma no recursiva por la izquierda, y también transmite capacidades óptimas de recuperación de errores en el analizador, que históricamente resultó difícil de lograr para analizadores sintácticos de descenso recursivos.
Ver también
- Lenguaje de descripción del compilador (CDL)
- Gramática formal
- Expresión regular
- Idioma de análisis de arriba hacia abajo
- Comparación de generadores de analizadores sintácticos
- Combinador de analizador
- Pitón
Referencias
- ↑ a b c d e f Ford, Bryan (enero de 2004). "Análisis de gramáticas de expresión: una base sintáctica basada en el reconocimiento" (PDF) . Actas del 31º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . ACM . págs. 111-122. doi : 10.1145 / 964001.964011 . ISBN 1-58113-729-X.
- ^ a b c Ford, Bryan (septiembre de 2002). "Análisis de Packrat: simple, potente, perezoso, lineal, perla funcional" (PDF) . Avisos ACM SIGPLAN . 37 (9). doi : 10.1145 / 583852.581483 .
- ^ a b c Ford, Bryan (septiembre de 2002). Análisis de Packrat: un algoritmo práctico de tiempo lineal con retroceso (tesis). Instituto de Tecnología de Massachusetts . Consultado el 27 de julio de 2007 .
- ^ Merritt, Doug (noviembre de 1993). "Descenso recursivo transparente" . Compiladores de comp . Del grupo Usenet . Consultado el 4 de septiembre de 2009 .
- ^ Ford, Bryan. "La página de gramática de expresiones de análisis y análisis de Packrat" . BFord.info . Consultado el 23 de noviembre de 2010 .
- ^ Jelliffe, Rick (10 de marzo de 2010). "¿Qué es un Packrat Parser? ¿Qué son los derivados de Brzozowski?" . Archivado desde el original el 28 de julio de 2011.
- ^ por ejemplo, la expresión LISP (x (x (x (x ....))))
- ^ Aho, AV; Sethi, R .; Ullman, JD (1986). Compiladores: principios, técnicas y herramientas . Boston, MA, EE.UU .: Addison-Wesley Longman .
- ^ a b c Warth, Alessandro; Douglass, James R .; Millstein, Todd (enero de 2008). "Los analizadores de Packrat pueden soportar la recursividad izquierda" (PDF) . Actas del simposio ACM SIGPLAN de 2008 sobre evaluación parcial y manipulación de programas basada en semántica . PEPM '08. ACM . págs. 103-110. doi : 10.1145 / 1328408.1328424 . Consultado el 2 de octubre de 2008 .
- ^ Steinmann, Ruedi (marzo de 2009). "Manejo de la recursividad izquierda en analizadores Packrat" (PDF) . n.ethz.ch . Archivado desde el original (PDF) el 6 de julio de 2011.
- ^ Hutchison, Luke AD (2020). "Análisis de Pika: el análisis en reversa resuelve la recursividad izquierda y los problemas de recuperación de errores". arXiv : 2005.06444 .
enlaces externos
- Convertir una expresión de cadena en una expresión lambda usando un analizador de expresiones
- Página de gramática de expresiones de análisis y análisis de Packrat
- El lenguaje construido Lojban tiene una gramática PEG bastante grande que permite un análisis sin ambigüedades del texto Lojban.
- Una implementación ilustrativa de un esquema PEG in Guile