Análisis de la gramática de expresiones

Tipo de gramática para describir lenguajes formales

En informática , una gramática de expresión de análisis ( 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, las 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 es más cercano a cómo el reconocimiento de cadenas tiende a realizarse en la práctica, por ejemplo, por un analizador descendente recursivo .

A diferencia de los CFG, los PEG no pueden ser ambiguos ; una cadena tiene exactamente un árbol de análisis válido o ninguno. Se conjetura que existen lenguajes libres de contexto que no pueden ser reconocidos por un PEG, pero esto aún no está demostrado. ^[1] Los PEG son adecuados para analizar lenguajes informáticos (y lenguajes humanos artificiales como el lojban ) donde se pueden desambiguar localmente múltiples alternativas de interpretación, pero es menos probable que sean útiles para analizar lenguajes naturales donde la desambiguación puede tener que ser global. ^[2]

Definición

Una expresión de análisis es un tipo de patrón con el que cada cadena puede coincidir o no . En caso de coincidencia, hay un prefijo único de la cadena (que puede ser la cadena completa, la cadena vacía o algo intermedio) que ha sido consumido por la expresión de análisis; este prefijo es lo que uno normalmente consideraría que ha coincidido con la expresión. Sin embargo, si una cadena coincide con una expresión de análisis puede (debido a los predicados de anticipación) depender de partes de ella que vienen después de la parte consumida. Un lenguaje de expresión de análisis es un conjunto de todas las cadenas que coinciden con alguna expresión de análisis específica. ^{[1] : Sec.3.4}

Una gramática de expresión de análisis es una colección de expresiones de análisis con nombre, que pueden hacer referencia entre sí. El efecto de una de esas referencias en una expresión de análisis es como si se diera la expresión de análisis completa a la que se hace referencia en lugar de la referencia. Una gramática de expresión de análisis también tiene una expresión inicial designada ; una cadena coincide con la gramática si coincide con su expresión inicial.

Un elemento de una cadena que coincide se denomina símbolo terminal o terminal para abreviar. Del mismo modo, los nombres asignados a las expresiones de análisis se denominan símbolos no terminales o no terminales para abreviar. Estos términos serían descriptivos para las gramáticas generativas , pero en el caso de las gramáticas de expresiones de análisis son meramente terminología, que se mantiene principalmente porque son casi omnipresentes en las discusiones sobre algoritmos de análisis .

Sintaxis

En la literatura y en este artículo se pueden ver sintaxis abstractas y concretas de expresiones de análisis sintáctico. La sintaxis abstracta es esencialmente una fórmula matemática y se utiliza principalmente en contextos teóricos, mientras que las expresiones de análisis sintáctico de sintaxis concreta se pueden utilizar directamente para controlar un analizador sintáctico . La sintaxis concreta principal es la definida por Ford, ^{[1] : Fig.1} aunque muchas herramientas tienen su propio dialecto de esta. Otras herramientas ^[3] pueden estar más cerca de utilizar una codificación nativa del lenguaje de programación de expresiones de análisis sintáctico de sintaxis abstracta como su sintaxis concreta.

Expresiones de análisis atómico

Los dos tipos principales de expresiones de análisis que no contienen otra expresión de análisis son los símbolos terminales individuales y los símbolos no terminales. En la sintaxis concreta, los terminales se colocan entre comillas (simples o dobles), mientras que los identificadores que no están entre comillas indican no terminales:

 "terminal"  No terminal  'otra terminal'

En la sintaxis abstracta no hay una distinción formalizada, sino que cada símbolo se define supuestamente como terminal o no terminal, pero una convención común es utilizar mayúsculas para los no terminales y minúsculas para los terminales.

La sintaxis concreta también tiene varias formas para clases de terminales:

• Un .(período) es una expresión de análisis que coincide con cualquier terminal individual.
• Los corchetes que encierran una lista de caracteres [abcde]forman una expresión de análisis que coincide con uno de los caracteres numerados. Al igual que en las expresiones regulares , estas clases también pueden incluir rangos [0-9A-Za-z]escritos como un guion con los puntos finales del rango antes y después de él. (A diferencia del caso de las expresiones regulares, las clases de caracteres entre corchetes no tienen ^negación; ese final puede obtenerse mediante predicados no).
• Algunos dialectos tienen notación adicional para clases predefinidas de caracteres, como letras, dígitos, signos de puntuación o espacios; esto es similar a la situación en las expresiones regulares.

En la sintaxis abstracta, estas formas suelen formalizarse como no terminales cuya definición exacta se omite para abreviar; en Unicode, hay decenas de miles de caracteres que son letras. Por el contrario, las discusiones teóricas a veces introducen una sintaxis abstracta atómica para conceptos que pueden expresarse alternativamente utilizando expresiones de análisis compuestas. Algunos ejemplos de esto incluyen:

• la cadena vacía ε (como expresión de análisis, coincide con todas las cadenas y no consume caracteres),
• fin de la entrada E (el equivalente sintáctico concreto es !.), y
• fallo (no coincide con nada). ${\displaystyle \bot }$

En la sintaxis concreta, las terminales entre comillas y corchetes tienen barras invertidas de escape, de modo que se puede escribir " salto de línea o retorno de carro[\n\r] " . La contraparte de sintaxis abstracta de una terminal entre comillas de longitud mayor que uno sería la secuencia de esas terminales; "bar"es lo mismo que "b" "a" "r". La sintaxis concreta primaria no asigna un significado distinto a las terminales según si usan comillas simples o dobles, pero algunos dialectos tratan una como sensible a mayúsculas y minúsculas y la otra como insensible a mayúsculas y minúsculas.

Expresiones de análisis compuestas

Dadas las expresiones de análisis existentes e , e ₁ y e ₂ , se puede construir una nueva expresión de análisis utilizando los siguientes operadores:

• Secuencia : e ₁ e ₂
• Elección ordenada : e ₁ / e ₂
• Cero o más : e *
• Uno o más : e +
• Opcional : e ?
• Predicado-y : & e
• No predicado : ! e
• Grupo : ( e )

Las prioridades de los operadores son las siguientes, según la Tabla 1 en: ^[1]

Gramáticas

En la sintaxis concreta, una gramática de expresión de análisis es simplemente una secuencia de definiciones no terminales, cada una de las cuales tiene la forma

  Expresión del identificador LEFTARROW 

El Identifieres el no terminal que se está definiendo, y el Expressiones la expresión de análisis a la que se define como referencia. El LEFTARROWvaría un poco entre dialectos, pero generalmente es una flecha que apunta hacia la izquierda o un símbolo de asignación, como <-, ←, :=o =. Una forma de entenderlo es precisamente como hacer una asignación o definición del no terminal. Otra forma de entenderlo es como un contraste con la flecha que apunta hacia la derecha → utilizada en las reglas de una gramática libre de contexto ; con expresiones de análisis, el flujo de información va de la expresión al no terminal, no del no terminal a la expresión.

Como objeto matemático, una gramática de expresión de análisis es una tupla , donde es el conjunto de símbolos no terminales, es el conjunto de símbolos terminales, es una función de al conjunto de expresiones de análisis en , y es la expresión de análisis inicial. Algunos dialectos de sintaxis concreta dan la expresión inicial explícitamente, ^[4] pero la sintaxis concreta primaria en cambio tiene la regla implícita de que el primer no terminal definido es la expresión inicial. ${\displaystyle (N,\Sigma ,P,e_{S})}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle N\cup \Sigma }$ ${\displaystyle e_{S}}$

Vale la pena notar que el dialecto primario de gramáticas de expresión de análisis de sintaxis concreta no tiene un terminador de definición explícito o un separador entre definiciones, aunque es habitual comenzar una nueva definición en una nueva línea; el LEFTARROWde la siguiente definición es suficiente para encontrar el límite, si se agrega la restricción de que un no terminal en un Expressionno debe ser seguido por un LEFTARROW. Sin embargo, algunos dialectos pueden permitir un terminador explícito, o directamente requerirlo ^[4] .

Ejemplo

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]es un atajo para los diez caracteres de '0'a '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 tiene que manejarse en el paso de posprocesamiento después del análisis), y la regla de Potencia (al referirse a sí misma a la derecha) da como resultado la asociatividad derecha deseada del exponente. Tenga en cuenta también que una regla como (con la intención de lograr la asociatividad izquierda) causaría una recursión infinita, por lo que no se puede utilizar en la práctica aunque se puede expresar en la gramática.Sum ← Sum (('+' / '-') Product)?

Semántica

La diferencia fundamental entre las gramáticas libres de contexto y las gramáticas de análisis de expresiones es que el operador de elección de PEG es ordenado . Si la primera alternativa tiene éxito, se ignora la segunda alternativa. Por lo tanto, la elección ordenada no es conmutativa , a diferencia de la elección desordenada 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 eligiendo de manera determinista un árbol de análisis entre los análisis 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.

Las gramáticas de expresiones de análisis también agregan los predicados sintácticos and y not . Debido a que pueden usar una subexpresión arbitrariamente compleja para "mirar hacia adelante" en la cadena de entrada sin consumirla realmente, brindan una poderosa función de desambiguación y de búsqueda sintáctica hacia adelante, en particular cuando la reordenación 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 representa esencialmente una función de análisis en un analizador descendente recursivo , y la expresión de análisis 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 opcionalmente avanzar o consumir uno o más caracteres de la cadena de entrada que se le suministra, o
• fallo , en cuyo caso no se consume ninguna entrada.

Una expresión de análisis atómico que consta de un único 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 éxito de manera trivial sin consumir ninguna entrada.

Una expresión de análisis atómico que consta de una A no terminal representa una llamada recursiva a la función no terminal A. Una función no terminal puede tener éxito sin consumir realmente ninguna entrada, y esto se considera un resultado distinto del fracaso.

El operador de secuencia e ₁ e ₂ primero invoca e ₁ y, si e ₁ tiene éxito, invoca posteriormente e ₂ en el resto de la cadena de entrada que no haya sido consumida por e ₁ y devuelve el resultado. Si e ₁ o e ₂ fallan, entonces la expresión de secuencia e ₁ e ₂ falla (no consume ninguna entrada).

El operador de elección e ₁ / e ₂ primero invoca e ₁ y, si e ₁ tiene éxito, devuelve su resultado inmediatamente. De lo contrario, si e ₁ falla, el operador de elección retrocede a la posición de entrada original en la que invocó e ₁ , pero luego invoca e ₂ en su lugar y devuelve el resultado de e _{2 .}

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 repetición consecutiva de su subexpresión e , respectivamente. Sin embargo, a diferencia de las gramáticas libres de contexto y las expresiones regulares , estos operadores siempre se comportan de manera voraz , consumiendo la mayor cantidad de entrada posible y nunca retrocediendo. (Los comparadores de expresiones regulares pueden comenzar con una coincidencia voraz, pero luego retrocederán e intentarán coincidencias más cortas si no logran coincidir). 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 y & e invoca la subexpresión e , y luego tiene éxito si e tiene éxito y falla si e falla, pero en ninguno de los casos consume ninguna entrada .

La expresión no predicativa ! e tiene éxito si e falla y falla si e tiene éxito, nuevamente sin consumir ninguna entrada en ninguno de los casos.

Más ejemplos

La siguiente regla recursiva coincide con las instrucciones if/then/else estándar de estilo C de tal manera que la cláusula "else" opcional siempre se vincula con la "if" más interna, 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 pendiente de else ).

S  ←  'si'  C  'entonces'  S  'de lo contrario'  S  /  'si'  C  'entonces'  S

La siguiente regla recursiva coincide con la sintaxis de comentarios anidados de estilo Pascal. (* which can (* nest *) like this *)Recuerde que .coincide con cualquier carácter individual.

C  ←  Inicio  N *  Fin Inicio  ←  '(*' Fin  ←  '*)' N  ←  C  /  ( ! Inicio  ! Fin  . )

La expresión de análisis coincide y consume el texto "foo", pero solo si va seguido del texto "bar". La expresión de análisis coincide con el texto "foo", pero solo si no va seguido del texto "bar". La expresión coincide con una sola "a", pero solo si no forma parte de una secuencia arbitrariamente larga de a seguidas de una b.foo &(bar)foo !(bar)!(a+ b) a

La expresión de análisis compara y consume una secuencia de longitud arbitraria de a y b. La regla de producción describe el "lenguaje coincidente" simple e independiente del contexto . La siguiente gramática de expresión de análisis describe el lenguaje clásico no independiente del contexto :('a'/'b')* S ← 'a' ''S''? 'b' ${\displaystyle \{a^{n}b^{n}:n\geq 1\}}$ ${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 1\}}$

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 expresiones

Cualquier gramática de expresión de análisis se puede convertir directamente en un analizador descendente recursivo . ^[5] Sin embargo, debido a la capacidad ilimitada de anticipación que proporciona el formalismo gramatical, el analizador resultante podría exhibir un rendimiento temporal exponencial en el peor de los casos.

Es posible obtener un mejor rendimiento para cualquier gramática de expresión de análisis convirtiendo su analizador descendente recursivo en un analizador packrat , que siempre se ejecuta en tiempo lineal , a costa de requisitos de espacio de almacenamiento sustancialmente mayores. Un analizador packrat ^[5] es una forma de analizador similar a un analizador descendente recursivo en construcción, excepto que durante el proceso de análisis memoriza los resultados intermedios de todas las invocaciones de las funciones de análisis mutuamente recursivas , asegurando que cada función de análisis solo se invoque como máximo una vez en una posición de entrada dada. 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 idiomas libres de contexto) en tiempo lineal. Se conocen ejemplos de analizadores descendentes recursivos memorizados desde al menos 1993. ^[6] Este análisis del rendimiento de un analizador packrat supone que hay suficiente memoria disponible para almacenar todos los resultados memorizados; En la práctica, si no hay suficiente memoria, algunas funciones de análisis podrían tener que invocarse más de una vez en la misma posición de entrada y, en consecuencia, el analizador podría tardar más que un tiempo lineal.

También es posible construir analizadores sintácticos LL y LR a partir de gramáticas de expresión de análisis sintáctico, ^{[ cita requerida ]} con un mejor rendimiento en el peor de los casos que un analizador sintáctico descendente recursivo sin memorización, pero entonces se pierde la capacidad ilimitada de búsqueda anticipada del formalismo gramatical. Por lo tanto, no todos los lenguajes que se pueden expresar utilizando gramáticas de expresión de análisis sintáctico pueden analizarse con analizadores sintácticos LL o LR.

Análisis PEG de abajo hacia arriba

Un analizador sintáctico pika ^[7] utiliza programación dinámica para aplicar reglas PEG de abajo hacia arriba y de derecha a izquierda, lo que es el inverso del orden de descenso recursivo normal de arriba hacia abajo y de izquierda a derecha. El análisis sintáctico en orden inverso resuelve el problema de recursión por la izquierda, lo que permite que las reglas recursivas por la izquierda se utilicen directamente en la gramática sin tener que reescribirlas en una forma no recursiva por la izquierda, y también confiere al analizador capacidades óptimas de recuperación de errores, lo que históricamente resultó difícil de lograr para los analizadores sintácticos de descenso recursivo.

Ventajas

No requiere compilación

Muchos algoritmos de análisis requieren un paso de preprocesamiento en el que la gramática se compila primero en una forma ejecutable opaca, a menudo algún tipo de autómata. Las expresiones de análisis se pueden ejecutar directamente (aunque normalmente sigue siendo recomendable transformar las expresiones PEG legibles por humanos que se muestran en este artículo en un formato más nativo, como S-expressions , antes de evaluarlas).

En comparación con las expresiones regulares

En comparación con las expresiones regulares puras (es decir, que describen un lenguaje reconocible mediante un autómata finito ), los PEG son mucho más potentes. En particular, pueden manejar recursión ilimitada y, por lo tanto, hacer coincidir paréntesis hasta una profundidad de anidación arbitraria; las expresiones regulares, en el mejor de los casos, pueden realizar un seguimiento de la anidación hasta una profundidad fija, porque un autómata finito (que tiene un conjunto finito de estados internos) solo puede distinguir un número finito de profundidades de anidación diferentes. En términos más teóricos, (el lenguaje de todas las cadenas de cero o más ', seguido de un número igual de s) no es un lenguaje regular, pero se ve fácilmente que es un lenguaje de expresión de análisis, que coincide con la gramática ${\displaystyle \{a^{n}b^{n}\}_{n\geqslant 0}}$ ${\displaystyle a}$ ${\displaystyle b}$

inicio  ←  AB  ! . AB  ←  ( 'a'  AB  'b' ) ?

Aquí AB !.está la expresión inicial. La !.parte obliga a que la entrada termine después del carácter AB, diciendo "no hay un siguiente carácter"; a diferencia de las expresiones regulares, que tienen restricciones mágicas $o \Z, por lo tanto, las expresiones de análisis pueden expresar el final de la entrada utilizando solo los primitivos básicos.

Los *, +, y ?de las expresiones de análisis son similares a los de las expresiones regulares, pero la diferencia es que funcionan estrictamente en modo voraz. Esto se debe, en última instancia, a que /se trata de una elección ordenada. Una consecuencia es que algo puede coincidir como expresión regular pero no como expresión de análisis:

[ab]?[bc][cd]

es tanto una expresión regular válida como una expresión de análisis válida. Como expresión regular, coincide con bc, pero como expresión de análisis no coincide, porque [ab]?coincidirá con b, luego [bc]coincidirá con c, sin dejar nada para [cd], por lo que en ese punto la coincidencia de la secuencia falla. "Intentar de nuevo" con match [ab]?la cadena vacía va explícitamente en contra de la semántica de las expresiones de análisis; este no es un caso extremo de un algoritmo de coincidencia particular, sino que es el comportamiento buscado.

Incluso las expresiones regulares que dependen del no determinismo se pueden compilar en una gramática de expresión de análisis, al tener un no terminal separado para cada estado del DFA correspondiente y codificar su función de transición en las definiciones de estos no terminales.

A  ←  'x'  B  /  'y'  C

En realidad, está diciendo "del estado A se pasa al estado B si el siguiente carácter es x, pero al estado C si el siguiente carácter es y", pero esto funciona porque el no determinismo se puede eliminar dentro del ámbito de los lenguajes regulares. No haría uso de las variantes de expresión de análisis sintáctico de las operaciones de repetición.

En comparación con las gramáticas libres de contexto

Los PEG se pueden dar cómodamente en términos de caracteres, mientras que las gramáticas libres de contexto (CFG) generalmente se dan en términos de tokens, lo que requiere un paso adicional de tokenización antes del análisis propiamente dicho. ^[8] Una ventaja de no tener un tokenizador separado es que diferentes partes del lenguaje (por ejemplo, minilenguajes integrados ) pueden tener fácilmente diferentes reglas de tokenización.

En sentido estricto, es probable que los PEG no se puedan comparar con los CFG, pero en la práctica hay muchas cosas que los PEG pueden hacer y que los CFG puros no pueden, mientras que es difícil encontrar ejemplos de lo contrario. En particular, los PEG se pueden diseñar para resolver ambigüedades de forma nativa, como el problema de " dangling else " en C, C++ y Java, mientras que el análisis basado en CFG a menudo necesita una regla fuera de la gramática para resolverlos. Además, cualquier PEG se puede analizar en tiempo lineal utilizando un analizador packrat, como se describió anteriormente, mientras que el análisis según un CFG general es asintóticamente equivalente ^[9] a la multiplicación de matrices booleanas (por lo tanto, es probable que se encuentre entre el tiempo cuadrático y el cúbico).

Un ejemplo clásico de un lenguaje formal que se puede demostrar que no es independiente del contexto es el lenguaje : un número arbitrario de s son seguidos por un número igual de s, que a su vez son seguidos por un número igual de s. Este también es un lenguaje de expresión de análisis, que coincide con la gramática ${\displaystyle \{a^{n}b^{n}c^{n}\}_{n\geqslant 0}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

inicio  ←  AB  'c' * AB  ←  'a'  AB  'b'  /  & ( BC  ! . ) BC  ←  ( 'b'  BC  'c' ) ?

Para ABque haya una coincidencia, el primer tramo de s debe ser seguido por un número igual de s, y además tiene que coincidir donde s cambia a s, lo que significa que esas s son seguidas por un número igual de s. ${\displaystyle a}$ ${\displaystyle b}$BC ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle c}$

Desventajas

Consumo de memoria

El análisis PEG se lleva a cabo normalmente mediante el análisis packrat , que utiliza la memorización ^{[10] [11]} para eliminar los pasos de análisis redundantes. El análisis packrat requiere un almacenamiento interno proporcional al tamaño total de la entrada, en lugar de a la profundidad del árbol de análisis como con los analizadores LR. Si esta es una diferencia significativa depende de las circunstancias; si el análisis es un servicio proporcionado como una función , entonces el analizador habrá almacenado el árbol de análisis completo hasta que lo devuelva, y ese árbol de análisis normalmente ya tendrá un tamaño proporcional al tamaño total de la entrada. Si el análisis se proporciona en cambio como un generador , entonces uno podría salirse con la suya manteniendo solo partes del árbol de análisis en la memoria, pero la viabilidad de esto depende de la gramática. Una gramática de expresión de análisis se puede diseñar de modo que solo después de consumir la entrada completa el analizador descubra que necesita retroceder al principio, ^[12] lo que nuevamente podría requerir un almacenamiento proporcional al tamaño total de la entrada.

En el caso de las gramáticas recursivas y algunas entradas, la profundidad del árbol de análisis puede ser proporcional al tamaño de la entrada, ^[13] 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. Sin embargo, en muchos dominios, por ejemplo, el código fuente escrito a mano, la profundidad de anidación de expresiones tiene un límite efectivamente constante bastante independiente de la longitud del programa, porque las expresiones anidadas más allá de cierta profundidad tienden a refactorizarse . Cuando no es necesario mantener el árbol de análisis completo, un análisis más preciso tendría en cuenta la profundidad del árbol de análisis por separado del tamaño de la entrada. ^[14]

Modelo computacional

Para alcanzar una complejidad lineal global, el almacenamiento utilizado para la memorización debe proporcionar además un acceso amortizado en tiempo constante a los elementos de datos individuales memorizados. En la práctica, esto no es un problema (por ejemplo, una tabla hash de tamaño dinámico lo consigue), pero hace uso de la aritmética de punteros , por lo que supone tener una máquina de acceso aleatorio . Las discusiones teóricas sobre estructuras de datos y algoritmos tienen una tendencia tácita a presuponer un modelo más restringido (posiblemente el del cálculo lambda , posiblemente el de Scheme ), donde una tabla dispersa tiene que construirse utilizando árboles, y el acceso a los elementos de datos no es en tiempo constante. Los algoritmos de análisis tradicionales, como el analizador LL , no se ven afectados por esto, pero se convierte en una penalización para la reputación de los analizadores de Packrat: se basan en operaciones de aparente mala reputación.

Visto desde el otro lado, esto indica que los analizadores sintácticos Packrat aprovechan la potencia computacional disponible en los sistemas de la vida real, que los algoritmos de análisis más antiguos no saben cómo utilizar.

Recursión indirecta por la izquierda

Se dice que un PEG está bien formado ^[1] si no contiene reglas recursivas por 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 sintáctico de arriba hacia abajo de izquierda a derecha, dichas reglas causan una regresión infinita: el análisis sintáctico 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 recursión por la izquierda.

Importancia práctica

La recursión directa, ya sea izquierda o derecha, es importante en las gramáticas libres de contexto, porque la recursión es la única forma de describir la repetición:

Suma  →  Término  |  Suma  '+'  Término  |  Suma  '-'  Término Argumentos  →  Arg  |  Arg  ','  Argumentos

Las personas capacitadas en el uso de gramáticas libres de contexto a menudo llegan a los PEG esperando usar los mismos modismos, pero el análisis de expresiones puede realizar repeticiones sin recursión:

Suma  ←  Término  (  '+'  Término  /  '-'  Término  ) * Args  ←  Arg  (  ','  Arg  ) *

Una diferencia radica en los árboles de sintaxis abstracta generados: con la recursión, cada uno Sumde ellos Argspuede tener como máximo dos hijos, pero con la repetición puede haber tantos como se desee. Si las etapas posteriores del procesamiento requieren que dichas listas de hijos se reformulen como árboles con un grado acotado, por ejemplo, las instrucciones de microprocesador para la adición normalmente solo permiten dos operandos, entonces se impondrían propiedades como la asociatividad izquierda después de la etapa de análisis dirigido por PEG.

Por lo tanto, es prácticamente menos probable que la recursión por la izquierda genere problemas en un analizador sintáctico PEG packrat que, por ejemplo, en un analizador sintáctico LL(k) libre de contexto, a menos que uno insista en usar expresiones idiomáticas libres de contexto. Sin embargo, no todos los casos de recursión tienen que ver con la repetición.

Recursión por la izquierda sin repetición

Por ejemplo, en la gramática aritmética anterior, podría parecer tentador expresar la precedencia de los operadores como una cuestión de elección ordenada ( Sum / Product / Valuelo que significaría que primero intentaríamos ver como Sum(ya que analizamos de arriba hacia abajo), segundo intentaríamos ver como Producty solo tercero intentaríamos ver como Value) en lugar de hacerlo mediante la anidación de definiciones. Esta gramática (no bien formada) busca mantener el orden de precedencia solo en una línea:

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

Lamentablemente, para hacer coincidir un valor , Expres necesario comprobar si Sumcoincide un valor, mientras que para hacer coincidir un valor, Sumes necesario comprobar si Exprcoincide un valor. Como el término aparece en la posición más a la izquierda, estas reglas forman una definición circular que no se puede resolver. (Existen definiciones circulares que se pueden resolver, como en la formulación original del primer ejemplo, pero se requiere que dichas definiciones no presenten recursión patológica). Sin embargo, las reglas de recursión por la izquierda siempre se pueden reescribir para eliminar la recursión por la izquierda. ^{[2] [15]} Por ejemplo, la siguiente regla CFG de recursión por la izquierda:

cadena-de-un  ←  cadena-de-un  'un'  |  'un'

se puede reescribir en un PEG usando el operador más:

cadena-de-un  ←  'un' +

El proceso de reescribir reglas recursivas indirectas a la izquierda es complejo en algunos analizadores packrat, especialmente cuando hay acciones semánticas involucradas.

Con algunas modificaciones, el análisis tradicional de Packrat puede admitir la recursión izquierda directa, ^{[5] [16] [17]} pero al hacerlo se pierde la propiedad de análisis lineal en tiempo ^[16] que generalmente es la justificación para usar PEG y el análisis de Packrat en primer lugar. Solo el algoritmo de análisis OMeta ^[16] admite la recursión izquierda directa e indirecta completa sin complejidad adicional (pero nuevamente, con una pérdida de la complejidad lineal en tiempo), mientras que todos los analizadores GLR admiten la recursión izquierda.

Comportamiento inesperado

Una primera impresión común de los PEG es que se parecen a los CFG con ciertas características de conveniencia (operadores de repetición *+?como en expresiones regulares y predicados de búsqueda anticipada &!) más una elección ordenada para la desambiguación. Esta comprensión puede ser suficiente cuando el objetivo es crear un analizador para un lenguaje, pero no es suficiente para discusiones más teóricas sobre el poder computacional del análisis de expresiones. En particular, el no determinismo inherente a la elección desordenada |de gramáticas libres de contexto la hace muy diferente de la elección ordenada determinista /.

El problema del punto medio

Los analizadores 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 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 instructivo determinar exactamente qué hace un analizador PEG cuando intenta hacer coincidir

S  ←  'x'  S  'x'  /  'x'

contra la cadena xxxxxq. Como se esperaba, intenta de forma recursiva hacer coincidir el no terminal Sen posiciones crecientes en esta cadena, hasta que no logra la coincidencia con q, y luego comienza a retroceder. Esto sucede de la siguiente manera:

Posición: 123456 Cadena: xxxxxq Resultados: ↑ Pos.6: Ninguna rama de S coincide ↑ Pos.5: La primera rama de S falla, la segunda rama tiene éxito, produciendo una coincidencia de longitud 1. ↑ Pos.4: La primera rama de S falla, la segunda rama tiene éxito, produciendo una coincidencia de longitud 1. ↑ Pos.3: La primera rama de S tiene éxito, produciendo una coincidencia de longitud 3. ↑ Pos.2: La primera rama de S falla, porque después de la coincidencia S en 3 viene una q. La segunda rama tiene éxito y produce una coincidencia de longitud 1. ↑ Pos.1: La primera rama de S tiene éxito, produciendo una coincidencia de longitud 3.

La comparación con una expresión de análisis es codiciosa , en el sentido de que el primer resultado positivo encontrado es el único que se tiene en cuenta. Incluso si localmente las opciones se ordenan de la más larga primero, no hay garantía de que esta comparación codiciosa encuentre la coincidencia más larga a nivel global.

Detección de ambigüedad e influencia del orden de las reglas en el lenguaje que se utiliza

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 del caso común de que la gramática esté destinada a ser inequívoca pero sea defectuosa. Un generador de analizadores sintácticos PEG resolverá ambigüedades no deseadas con la primera coincidencia, lo que puede ser arbitrario y dar lugar a análisis sorprendentes.

El orden de las producciones en una gramática PEG afecta no solo la resolución de la ambigüedad, sino también el lenguaje con el que se relaciona . Por ejemplo, considere el primer ejemplo de PEG en el artículo de Ford ^[1] (ejemplo reescrito en la notación pegjs.org/online y etiquetado como ⁠ ⁠ ${\displaystyle G_{1}}$ y ⁠ ⁠ ${\displaystyle G_{2}}$ ):

• :​ ${\displaystyle G_{1}}$​  A = "a" "b" / "a"
• :​ ${\displaystyle G_{2}}$​  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, ⁠ ⁠ ${\displaystyle L(G_{1})}$ (es decir, el idioma coincidente con ⁠ ⁠ ${\displaystyle G_{1}}$ ) incluye la entrada "ab", pero ⁠ ⁠ ${\displaystyle L(G_{2})}$ no. Por lo tanto, agregar una nueva opción a una gramática PEG puede eliminar cadenas del idioma coincidente, por ejemplo , ⁠ ⁠ ${\displaystyle G_{2}}$ 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 ⁠ ⁠ ${\displaystyle G_{2}}$ . Además, construir una gramática para que coincida ⁠ ⁠ ${\displaystyle L(G_{1})\cup L(G_{2})}$ a partir de gramáticas PEG ⁠ ⁠ ${\displaystyle G_{1}}$ y ⁠ ⁠ ${\displaystyle G_{2}}$ 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 se puede construir una gramática (potencialmente ambigua) para ⁠ ⁠ ${\displaystyle L(G_{1})\cup L(G_{2})}$

S → inicio ( G1 ) | inicio ( G2 )    

Teoría del análisis sintáctico de gramáticas de expresiones

Es un problema abierto dar un ejemplo concreto de un lenguaje libre de contexto que no pueda ser reconocido por una gramática de expresiones de análisis. ^[1] En particular, está abierto si una gramática de expresiones de análisis puede reconocer el lenguaje de palíndromos. ^[18]

La clase de lenguajes de expresión de análisis está cerrada bajo la intersección y el complemento de conjuntos, por lo tanto también bajo la unión de conjuntos. ^{[1] : Sec.3.4}

Indecidibilidad del vacío

En marcado contraste con el caso de las gramáticas independientes del contexto, no es posible generar elementos de un lenguaje de expresión de análisis a partir de su gramática. De hecho, es algorítmicamente indecidible si el lenguaje reconocido por una gramática de expresión de análisis está vacío. Una razón para esto es que cualquier instancia del problema de correspondencia de Post se reduce a una instancia del problema de decidir si un lenguaje de expresión de análisis está vacío.

Recordemos que una instancia del problema de correspondencia de Post consiste en una lista de pares de cadenas (de símbolos terminales). El problema es determinar si existe una secuencia de índices en el rango tal que . Para reducir esto a una gramática de expresión de análisis, sean cadenas arbitrarias de símbolos terminales de igual longitud y distintas por pares (ya con símbolos distintos en el alfabeto de símbolos terminales, la longitud es suficiente) y consideremos la gramática de expresión de análisis Cualquier cadena que coincida con el no terminal tiene la forma para algunos índices . Del mismo modo, cualquier cadena que coincida con el no terminal tiene la forma . Por lo tanto, cualquier cadena que coincida con tendrá la forma donde . ${\displaystyle (\alpha _{1},\beta _{1}),(\alpha _{2},\beta _{2}),\dotsc ,(\alpha _{n},\beta _{n})}$ ${\displaystyle \{k_{i}\}_{i=1}^{m}}$ ${\displaystyle \{1,\dotsc ,n\}}$ ${\displaystyle \alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}=\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}}$ ${\displaystyle \gamma _{0},\gamma _{1},\dotsc ,\gamma _{n}}$ ${\displaystyle 2}$ ${\displaystyle \lceil \log _{2}(n+1)\rceil }$ $${\displaystyle {\begin{aligned}S&\leftarrow \&(A\,!.)\&(B\,!.)(\gamma _{1}/\dotsb /\gamma _{n})^{+}\gamma _{0}\\A&\leftarrow \gamma _{0}/\gamma _{1}A\alpha _{1}/\dotsb /\gamma _{n}A\alpha _{n}\\B&\leftarrow \gamma _{0}/\gamma _{1}B\beta _{1}/\dotsb /\gamma _{n}B\beta _{n}\end{aligned}}}$$ ${\displaystyle A}$ ${\displaystyle \gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}}$ ${\displaystyle k_{1},k_{2},\dotsc ,k_{m}}$ ${\displaystyle B}$ ${\displaystyle \gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}}$ ${\displaystyle S}$ ${\displaystyle \gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\rho }$ ${\displaystyle \rho =\alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}=\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}}$

Uso práctico

• Implementación de referencia de Python CPython introdujo un analizador PEG en la versión 3.9 como alternativa al analizador LL(1) y utiliza solo PEG a partir de la versión 3.10. ^[19]

• El lenguaje de programación jq utiliza un formalismo estrechamente relacionado con PEG.

• Los autores de Lua crearon LPeg, una biblioteca de coincidencia de patrones que utiliza PEG en lugar de expresiones regulares , ^[20] así como el módulo re que implementa una sintaxis similar a una expresión regular utilizando la biblioteca LPeg. ^[21]

Véase también

• Gramática booleana independiente del contexto
• Lenguaje de descripción del compilador (CDL)
• Gramática formal
• Expresión regular
• Lenguaje de análisis de arriba hacia abajo
• Comparación de generadores de analizadores sintácticos
• Combinador de analizador sintáctico

Referencias

1. 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.
2. Ford, Bryan (septiembre de 2002). "Análisis sintáctico de Packrat: una perla funcional, simple, potente y perezosa en tiempo lineal" (PDF) . ACM SIGPLAN Notices . 37 (9). doi :10.1145/583852.581483.
3. Sirthias, Mathias. "Parboiled: construcción de reglas en Java". GitHub . Consultado el 13 de enero de 2024 .
4. Kupries, Andreas. "pt::peg_language - Tutorial del lenguaje PEG". Código fuente de la biblioteca Tcl . Consultado el 14 de enero de 2024 .
5. Ford, Bryan (septiembre de 2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Tesis). Instituto Tecnológico de Massachusetts . Consultado el 27 de julio de 2007 .
6. Merritt, Doug (noviembre de 1993). "Transparent Recursive Descent". Grupo de Usenet comp.compilers . Consultado el 4 de septiembre de 2009 .
7. Hutchison, Luke AD (2020). "Análisis de Pika: el análisis inverso resuelve los problemas de recursión por la izquierda y recuperación de errores". arXiv : 2005.06444 [cs.PL].
8. Los CFG se pueden utilizar para describir la sintaxis de los lenguajes de programación más comunes hasta el nivel de caracteres, pero hacerlo es bastante complicado, porque la regla de tokenización estándar de que un token consiste en la secuencia consecutiva más larga de caracteres del mismo tipo no encaja bien con el lado no determinista de los CFG. Para formalizar que el espacio en blanco entre dos tokens adyacentes es obligatorio si los caracteres a ambos lados del límite del token son letras, pero opcional si no son letras, un CFG necesita múltiples variantes de la mayoría de los no terminales, para llevar un registro de qué tipo de carácter tiene que estar en el límite. Si hay diferentes tipos de caracteres que no son espacios en blanco, eso suma posibles variantes por no terminal, lo que infla significativamente la gramática. ${\displaystyle 3}$ ${\displaystyle 3^{2}=9}$
9. Lee, Lillian (enero de 2002). "El análisis gramatical rápido e independiente del contexto requiere una multiplicación rápida de matrices booleanas". J. ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242.
10. Ford, Bryan. "La página de gramática de expresión y análisis sintáctico de Packrat". BFord.info . Consultado el 23 de noviembre de 2010 .
11. Jelliffe, Rick (10 de marzo de 2010). "¿Qué es un analizador Packrat? ¿Qué son los derivados de Brzozowski?". Archivado desde el original el 28 de julio de 2011.
12. Por ejemplo, al final de la entrada podría haber una directiva que diga “en este archivo, la coma es un separador decimal , entonces todas esas llamadas de función f(3,14*r) que usted pensó que tenían dos argumentos? No los tienen. Ahora regrese al comienzo de la entrada y analice todo nuevamente”. Podría decirse que ese sería un diseño deficiente del lenguaje de entrada, pero el punto es que las gramáticas de expresión de análisis son lo suficientemente potentes para manejar esto, puramente como una cuestión de sintaxis.
13. por ejemplo, la expresión LISP (x (x (x (x ....))))
14. Esto es similar a una situación que surge en los algoritmos de grafos : 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 tiene en cuenta el número de aristas como un parámetro separado asigna al algoritmo Bellman–Ford un tiempo de , que es cuadrático para grafos dispersos con . ${\displaystyle O(|V|^{3})}$ ${\displaystyle O(|V|*|E|)}$ ${\displaystyle |E|\in O(|V|)}$
15. Aho, AV; Sethi, R.; Ullman, JD (1986). Compiladores: principios, técnicas y herramientas . Boston, MA, EE. UU.: Addison-Wesley Longman . ISBN 0-201-10088-6.
16. Warth, Alessandro; Douglass, James R.; Millstein, Todd (enero de 2008). "Los analizadores sintácticos Packrat pueden admitir la recursión por la 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. ISBN . 9781595939777. Recuperado el 2 de octubre de 2008 .
17. Steinmann, Ruedi (marzo de 2009). "Manejo de la recursión por la izquierda en analizadores sintácticos Packrat" (PDF) . n.ethz.ch . Archivado desde el original (PDF) el 6 de julio de 2011.
18. Loff, Bruno; Moreira, Nelma; Reis, Rogerio (14 de febrero de 2020). "El poder computacional de analizar gramáticas de expresiones". arXiv : 1902.08272 [cs.FL].
19. "PEP 617 – Nuevo analizador PEG para CPython | peps.python.org". peps.python.org . Consultado el 16 de enero de 2023 .
20. Ierusalimschy, Roberto (10 de marzo de 2009). "Una herramienta de búsqueda de patrones de texto basada en gramáticas de expresión de análisis sintáctico". Software: práctica y experiencia . 39 (3): 221–258. doi :10.1002/spe.892. ISSN  0038-0644.
21. Ierusalimschy, Roberto. "LPeg.re - Sintaxis Regex para LPEG". www.inf.puc-rio.br .

Enlaces externos

• Convertir una expresión de cadena en una expresión lambda mediante un analizador de expresiones
• Página de análisis sintáctico y gramática de expresiones de Packrat
• El lenguaje construido Lojban tiene una gramática PEG bastante amplia que permite un análisis sin ambigüedades del texto Lojban.
• Una implementación ilustrativa de un sistema PEG en Guile