Gramática analizando una expresión

Una gramática de análisis de expresiones (gramática PB) es un tipo de gramática formal analítica que describe un lenguaje formal en términos de un conjunto de reglas para reconocer cadenas de lenguaje. Una gramática que analiza una expresión es esencialmente un analizador descendente recursivo en una forma puramente esquemática que solo expresa la sintaxis y es independiente de la implementación o uso particular del analizador. Las gramáticas de análisis de expresiones son similares a las expresiones regulares y las gramáticas libres de contexto (CFG) en la notación Backus-Naur , pero tienen una interpretación diferente.

A diferencia de las gramáticas COP, las gramáticas PB no pueden ser ambiguas : si se analiza una cadena, entonces hay exactamente un árbol de análisis. Esto hace que las gramáticas RE sean adecuadas para lenguajes informáticos, pero no para lenguajes naturales.

Definición

Formalmente, la gramática que analiza una expresión consta de:

• un conjunto finito de N símbolos no terminales ;
• un conjunto finito Σ de símbolos terminales que no se cruza con N ;
• un conjunto finito P de reglas de inferencia ;
• expresión e S , llamada expresión inicial .

Cada regla de inferencia de P tiene la forma A ← e, donde A es un símbolo no terminal y e es una expresión de análisis. Una expresión de análisis es una expresión jerárquica similar a una expresión regular que se construye así:

1. Una expresión de análisis atómico consta de:
   • cualquier carácter terminal,
   • cualquier símbolo no terminal, o
   • cadena vacía ε.
2. Dadas las expresiones de análisis e, e 1 y e 2 , las siguientes sentencias generan nuevas expresiones de análisis:
   • Secuencia: e 1 e 2
   • Selección ordenada: e 1 / e 2
   • Cero o más: e*
   • Uno o más: e+
   • Opcional: e?
   • Y predicado: &e
   • NO predicado: !e

La diferencia fundamental entre una gramática PB y una gramática COP es que el operador de elección de la gramática PB está ordenado . Si la primera alternativa funciona, todas las siguientes se ignoran . Por lo tanto, la elección ordenada no es conmutativa, a diferencia de las definiciones de libros de gramáticas independientes del contexto y expresiones regulares. La selección ordenada es similar al operador de corte suave en algunos lenguajes de programación lógicos.

Como consecuencia, al convertir un CFG directamente en un RTG, cualquier ambigüedad se resuelve de forma determinista a favor de uno de los posibles árboles de análisis. Al elegir cuidadosamente el orden en que se especifican las alternativas gramaticales, el programador puede obtener un control considerable sobre qué árbol de análisis sintáctico se elige.

Al igual que las gramáticas booleanas independientes del contexto, las gramáticas RE tienen predicados AND y NOT. Ayudan a desambiguar aún más si el reordenamiento de las alternativas no puede producir el árbol de análisis deseado.

Interpretación de expresiones de análisis

Cada no terminal en una gramática PB es esencialmente una función de analizador en un analizador de descenso recursivo, y la expresión de analizador correspondiente es el "código" de esa función. Cada función de análisis toma una cadena como entrada y produce uno de los siguientes resultados:

• éxito, en cuyo caso la función puede opcionalmente avanzar o "devorar" uno o más caracteres de la cadena de entrada
• un chapuzón en el que la entrada no se consume.

Un no terminal puede tener éxito sin absorber entrada, y este estado es diferente del fracaso.

Una expresión de análisis atómico que consta de un solo terminal tiene éxito si el primer carácter de la cadena de entrada coincide y lo consume. De lo contrario, el resultado no es exitoso. Una expresión atómica de una cadena vacía siempre tiene éxito sin consumirse. Una expresión atómica que consiste en el no terminal A es una llamada recursiva a la función no terminal A.

El operador de secuencia e 1 e 2 primero llama a e 1 y, si e 1 tiene éxito, entonces llama a e 2 en la parte de la cadena que e 1 no ha consumido y devuelve el resultado. Si e 1 o e 2 fallan, entonces el operador de secuencia e 1 e 2 también falla .

La declaración de selección e 1 / e 2 primero llama a e 1 y, si e 1 tiene éxito, devuelve su resultado. De lo contrario, si e 1 falla, la declaración de selección restaura la cadena de entrada al estado anterior a llamar a e 1 y llama a e 2 , devolviendo su resultado.

Los operadores cero o más, uno o más y opcionales consumen cero o más, uno o más, o cero o una aparición consecutiva de su subexpresión e , respectivamente . A diferencia de los CFG y las expresiones regulares, estos operadores siempre son codiciosos y consumen tantas instancias de entrada como pueden. (Las expresiones regulares comienzan con avidez, pero luego fallan y tratan de encontrar una secuencia más corta). Por ejemplo, la expresión a* siempre consumirá todas las a disponibles, y la expresión (a* a) siempre fallará porque después de ejecutar la primera parte de a*, no quedan a para la segunda.

Finalmente, el predicado AND y el predicado NOT implementan predicados sintácticos. La expresión & e llama a la subexpresión e , y devuelve éxito si e tiene éxito y falla en caso contrario, pero nunca consume entrada. Asimismo, la expresión ! e tiene éxito si e falla, y falla si e tiene éxito, nuevamente sin absorber la entrada. Debido a que la expresión e puede ser una construcción arbitrariamente compleja que se puede evaluar "por adelantado" sin consumir la cadena de entrada, estos predicados brindan poderosas herramientas sintácticas de preparación y eliminación de ambigüedades.

Ejemplos

La siguiente gramática RW reconoce fórmulas matemáticas con cuatro operaciones en números enteros no negativos.

Valor ← [0-9]+ / '(' Expr ')' Producto ← Valor (('*' / '/') Valor)* Suma ← Producto (('+' / '-') Producto)* Expr ← Suma

En el ejemplo anterior, los caracteres terminales son caracteres de texto representados por caracteres entre comillas simples, como '('y ')'. Un rango [0-9]es una abreviatura de diez caracteres que representan los números del 0 al 9. (Esta es la misma sintaxis que para las expresiones regulares). Los símbolos no terminales son símbolos para los que existen reglas de salida: Valor , Producto , Suma y Expr .

Los ejemplos a continuación no tienen comillas para mejorar la legibilidad. Las letras minúsculas son caracteres terminales y las cursivas mayúsculas no son terminales. Los analizadores reales de gramática PB requieren comillas.

La expresión de análisis (a/b)* coincide y consume secuencias de longitud arbitraria de a y b. Regla S ← a S ? b describe un lenguaje simple libre de contexto . La siguiente gramática RW describe un lenguaje clásico, no libre de contexto :

S ← &(A 'c') 'a'+ B !('a' / 'b' / 'c') A ← 'a' A? 'b' B ← 'b' B? 'C'

La siguiente regla recursiva coincide con una declaración if/then/else de C estándar, de modo que un bloque else opcional siempre coincide con el if más interno. (En una gramática libre de contexto, esto conduciría a la clásica ambigüedad de otra cosa pendiente).

S ← 'si' C 'entonces' S 'más' S / 'si' C 'entonces' S

La expresión de análisis foo &(bar) coincide y consume el texto "foo", pero solo si va seguido del texto "bar". La expresión de análisis foo !(bar) consume el texto "foo" solo si no va seguido de "bar". La expresión !(a+ b) a toma un solo carácter "a", pero solo si no es el primero en una secuencia de longitud arbitraria de a seguida de b.

La siguiente regla recursiva corresponde a un comentario de Pascal anidado. Los caracteres de comentario se encierran entre comillas simples para distinguirlos de los operadores RVG.

Empezar ← '(*' Fin ← '*)' C ← Comienzo N* Fin N ← C / (!Empezar !Terminar Z) Z ← cualquier carácter único

Implementación de analizadores de gramática RW

Cualquier gramática RH se puede convertir directamente en un analizador mediante descenso recursivo. Debido a la capacidad ilimitada de análisis previo, el analizador resultante puede ejecutarse, en el peor de los casos, en tiempo exponencial.

Al recordar el resultado de los pasos de análisis intermedios y asegurarse de que cada función del analizador no se llame más de una vez para una posición dada de los datos de entrada, es posible transformar cualquier gramática PB en un analizador Packrat que siempre se ejecuta en tiempo lineal en el costo de un aumento significativo en los costos de memoria.

Un analizador packrat es un tipo de analizador que funciona de manera similar al descenso recursivo, excepto que, al analizar, recuerda los resultados intermedios de todas las llamadas a funciones de análisis mutuamente recursivas. Debido a esto, el analizador packrat puede analizar muchas gramáticas libres de contexto y cualquier gramática PB (incluidas algunas que generan lenguajes no libres de contexto) en tiempo lineal [1] .

También es posible construir un analizador LL y un analizador LR para gramáticas RW, pero en este caso se pierde la capacidad de análisis previo sin restricciones.

Ventajas

Los REGRAM son buenos sustitutos de las expresiones regulares porque son estrictamente más potentes. Por ejemplo, una expresión regular es fundamentalmente incapaz de encontrar pares de paréntesis coincidentes porque no es recursiva, a diferencia de una gramática RE.

Cualquier gramática RH se puede analizar en tiempo lineal utilizando el analizador packrat como se describe anteriormente.

Los analizadores de idiomas representados por gramáticas COP, como los analizadores LR, requieren un paso de análisis léxico especial que divide la entrada según espacios, puntuación, etc. Esto es necesario porque estos analizadores utilizan el análisis previo para procesar algunos CFG en tiempo lineal. Las gramáticas RW no requieren un paso de análisis léxico separado, y las reglas para ello se pueden establecer junto con otras reglas gramaticales.

Muchas gramáticas COP contienen ambigüedades significativas, incluso cuando se supone que describen lenguajes de un solo valor. El problema de "colgar más" en C, C++ y Java es un ejemplo de este fenómeno. Estos problemas suelen resolverse aplicando una regla externa a la gramática. En una gramática de PB, estas ambigüedades nunca surgen debido a la priorización.

Desventajas

Consumo de memoria

El análisis de una gramática de PB generalmente lo realiza un analizador packrat que recuerda los pasos de análisis adicionales. Dicho análisis requiere que los datos se almacenen en proporción a la longitud de la entrada, a diferencia de la profundidad del árbol de análisis para los analizadores LR. Esta es una ganancia significativa en muchas áreas: por ejemplo, el código escrito por humanos tiende a tener una profundidad de anidamiento casi constante, independientemente de la longitud del programa; las expresiones más profundas que una cierta cantidad generalmente se refactorizan.

Para algunas gramáticas y algunas entradas, la profundidad del árbol de análisis puede ser proporcional a la longitud de la entrada, por lo que para una evaluación que no tenga en cuenta esta medida, un analizador packrat puede parecer tan bueno como un analizador LR. Esto es similar a la situación con los algoritmos de grafos: Bellman-Ford y Floyd-Warshall tienen un tiempo de ejecución ( ) si solo se considera el número de vértices. Sin embargo, un análisis más preciso, teniendo en cuenta el número de aristas, muestra el tiempo de ejecución del algoritmo Bellman-Ford , que es solo cuadrático al tamaño de la entrada, no cúbico.

Recurrencia indirecta a la izquierda

Las gramáticas RE no pueden contener reglas recursivas a la izquierda que se llamen a sí mismas sin avance de línea. Por ejemplo, en la gramática aritmética descrita anteriormente, me gustaría mover algunas reglas para que la precedencia del producto y la suma puedan expresarse en una línea:

Valor ← [0-9.]+ / '(' Expr ')' Producto ← Expr (('*' / '/') Expr)* Suma ← Expr (('+' / '-') Expr)* Expr ← Producto / Suma / Valor

El problema aquí es que para obtener un acierto para Expr , debe verificar si Product se dispara , y para verificar Product , primero debe verificar Expr . Y esto es imposible.

Sin embargo, las reglas recursivas por la izquierda siempre se pueden reescribir para eliminar la recursividad por la izquierda. Por ejemplo, una regla recursiva por la izquierda puede repetir alguna expresión indefinidamente, como en la regla de gramática CF:

cadena-de-a ← cadena-de-a 'a' | 'a'

Esto se puede reescribir en una gramática PB usando el operador +:

cadena-de-a ← 'a'+

Con algunas modificaciones, es posible hacer que un analizador packrat normal admita la recursividad izquierda directa [1] [2] [3] .

Sin embargo, el proceso de reescribir reglas indirectas recursivas a la izquierda es difícil, especialmente cuando tienen lugar acciones semánticas. Aunque teóricamente es posible, no hay ningún analizador RW que admita la recursividad izquierda indirecta, mientras que todos los analizadores GLR sí lo hacen.

Sutiles errores gramaticales

Para expresar una gramática como una gramática PB, su autor debe convertir todas las instancias de elección no determinista en elección ordenada. Desafortunadamente, este proceso es propenso a errores y, a menudo, da como resultado gramáticas que analizan incorrectamente algunas de las entradas.

Expresividad

Los analizadores de Packrat no pueden analizar algunas gramáticas inequívocas, como las siguientes [4] :

S ← 'x' S 'x' | 'X'

Desarrollo

Las gramáticas RE son nuevas y no se utilizan mucho. Las expresiones regulares y las gramáticas COP, por otro lado, existen desde hace décadas, el código que las analiza se ha mejorado y optimizado, y los programadores tienen experiencia en su uso.

Enlaces

• Medeiros, Sergio; Jerusalemschy, Roberto (2008). "Una máquina de análisis de PEG". proc. del simposio de 2008 sobre lenguajes dinámicos . ACM . páginas. Artículo 2. DOI : 10.1145/1408681.1408683 . ISBN 978-1-60558-270-2 . Parámetro obsoleto utilizado |coauthors=( ayuda )

Notas

1. ↑ 1 2 Ford, Bryan Packrat Análisis: un algoritmo práctico de tiempo lineal con retroceso . Instituto de Tecnología de Massachusetts (septiembre de 2002). Fecha de acceso: 27 de julio de 2007. Archivado desde el original el 2 de abril de 2012. (indefinido)
2. ↑ Alessandro Warth, James R. Douglass, Todd Millstein. Los analizadores Packrat pueden admitir la  recursividad izquierda . - Instituto de Investigación Puntos de Vista, 2008. - Enero.
3. ↑ Ruedi Steinmann. Manejo de recursividad izquierda en Packrat Parsers  (neopr.) . - 2009. - Marzo. Archivado desde el original el 6 de julio de 2011. Copia archivada (enlace no disponible) . Consultado el 17 de junio de 2009. Archivado desde el original el 6 de julio de 2011. (indefinido) 
4. ↑ Bryan Ford. Perla funcional: análisis de Packrat: tiempo simple, potente, perezoso y lineal  (inglés)  : revista. — 2002.