Análisis de 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 los años 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 se acerca más a cómo tiende a realizarse el reconocimiento de cadenas en la práctica, por ejemplo, mediante un analizador de descenso 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 Lojban ) donde múltiples alternativas de interpretación pueden desambiguarse localmente, 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 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 normalmente se consideraría que coincide 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] : Sección 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 toda la expresión de análisis a la que se hace referencia se proporcionara 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 coincidente se llama 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 gramáticas de expresión de análisis son meramente terminología, mantenida principalmente porque son casi ubicuas en las discusiones sobre algoritmos de análisis .

Sintaxis

Tanto la sintaxis abstracta como la concreta de expresiones de análisis se ven en la literatura y en este artículo. La sintaxis abstracta es esencialmente una fórmula matemática y se usa principalmente en contextos teóricos, mientras que las expresiones de análisis de sintaxis concreta podrían usarse directamente para controlar un analizador . La sintaxis concreta primaria es la definida por Ford, ^{[1] : Fig.1} aunque muchas herramientas tienen su propio dialecto. Otras herramientas ^[3] pueden estar más cerca de utilizar una codificación nativa de un lenguaje de programación de expresiones de análisis 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 sintaxis concreta, los terminales se colocan entre comillas (simples o dobles), mientras que los identificadores que no están entre comillas denotan no terminales:

 "terminal"  No terminal  'otra terminal'

En la sintaxis abstracta no existe una distinción formalizada; en cambio, cada símbolo se define supuestamente como terminal o no terminal, pero una convención común es usar 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 .(punto) es una expresión de análisis que coincide con cualquier terminal.
• Los corchetes alrededor de 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 guión con los puntos finales del rango antes y después. (A diferencia del caso de las expresiones regulares, las clases de caracteres entre corchetes no tienen ^negación; en cambio, ese final se puede obtener a través de no predicados).
• Algunos dialectos tienen notación adicional para clases de caracteres predefinidas, como letras, dígitos, signos de puntuación o espacios; De nuevo, esto es similar a la situación en las expresiones regulares.

En sintaxis abstracta, estas formas suelen formalizarse como no terminales cuya definición exacta se omite por brevedad; 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, alternativamente, pueden expresarse mediante expresiones de análisis compuestas. Ejemplos de esto incluyen:

• la cadena vacía ε (como expresión de análisis, coincide con cada cadena y no consume caracteres),
• final de la entrada E (el equivalente de sintaxis concreto es !.), y
• fracaso (no coincide con nada). ${\displaystyle \bot }$

En la sintaxis concreta, los terminales entre comillas y entre corchetes tienen barras de escape invertidas, de modo que se puede escribir " avance de línea o retorno de carro[\n\r] " . La contraparte de sintaxis abstracta de un terminal entrecomillado de longitud mayor que uno sería la secuencia de esos terminales; "bar"es lo mismo que "b" "a" "r". La sintaxis concreta primaria no asigna ningún significado distinto a los terminales dependiendo de si usan comillas simples o dobles, pero algunos dialectos tratan a uno como que distingue entre mayúsculas y minúsculas y al otro como que no distingue entre 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 : ! mi
• Grupo : ( e )

Las prioridades del operador son las siguientes, basadas en 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

 Identificador  FLECHA IZQUIERDA  Expresión

es Identifierel no terminal que se define y 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 haciendo una asignación o definición de lo no terminal. Otra forma de entenderlo es como contraste con la flecha que apunta hacia la derecha → utilizada en las reglas de una gramática libre de contexto ; Al analizar expresiones, 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 desde hasta el 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 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 señalar 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 an Expressionno debe ir seguido de a LEFTARROW. Sin embargo, algunos dialectos pueden permitir un terminador explícito o requerirlo directamente ^[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 desde '0'hasta '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 deseada por la izquierda de estas operaciones (no tratan con la asociatividad en absoluto y debe manejarse en el paso de posprocesamiento después del análisis), y la regla de Potencia (por refiriéndose a sí mismo a la derecha) da como resultado la asociatividad deseada por la derecha del exponente. También tenga en cuenta que una regla como (con la intención de lograr 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)?

Semántica

La diferencia fundamental entre gramáticas libres de contexto y gramáticas de expresión de análisis es que el operador de elección del PEG es ordenado . Si la primera alternativa tiene éxito, se ignora la segunda alternativa. Por 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 translitera directamente a un PEG, cualquier ambigüedad en el primero se resuelve seleccionando de manera determinista un árbol de análisis de los posibles análisis. Al elegir cuidadosamente el orden en que se especifican las alternativas gramaticales, un programador tiene un gran control sobre qué árbol de análisis se selecciona.

El análisis de gramáticas de expresiones también agrega 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, proporcionan una poderosa función sintáctica de anticipación y desambiguación, en particular cuando reordenar 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 de descenso 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 proporciona, o
• falla , 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 produce un resultado de error. Una expresión de análisis atómico que consta de una cadena vacía siempre tiene éxito trivialmente sin consumir ninguna entrada.

Una expresión de análisis atómico que consta de un A no terminal representa una llamada recursiva a la función A no terminal . 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 ₁ e ₂ primero invoca e ₁ y, si e ₁ tiene éxito, posteriormente invoca e _{2 en el resto de la cadena de entrada que} e ₁ no ha consumido y devuelve el resultado. Si e ₁ o e ₂ falla, 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, entonces el operador de elección retrocede a la posición de entrada original en la que invocó e ₁ , pero luego llama a e ₂ en su lugar, devolviendo el resultado de e _{2 .}

Los operadores cero o más , uno o más y opcional consumen cero o más, una o más, o cero o una repeticiones consecutivas 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 con avidez , consumiendo la mayor cantidad de información posible y nunca retrocediendo. (Los comparadores de expresiones regulares pueden comenzar haciendo coincidir con avidez, 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 cualquier caso nunca consume ninguna entrada .

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

Más ejemplos

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

S  ←  'si'  C  'entonces'  S  'si no'  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.

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

La expresión de análisis coincide y consume el texto "foo", pero sólo si va seguido del texto "bar". La expresión de análisis coincide con el texto "foo", pero sólo si no va seguida del texto "bar". La expresión coincide con una única "a", pero sólo 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 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 . La siguiente gramática de expresiones de análisis describe el lenguaje clásico no libre de 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  ! . ¿Un  ←  'un'  Un ?  'b' B  ←  'b'  B ?  'C'

Implementación de analizadores a partir de gramáticas de expresiones

Cualquier gramática de expresión de análisis se puede convertir directamente en un analizador de descenso 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 al convertir su analizador de descenso 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 de descenso 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 en la mayoría de las veces 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 de descenso recursivo memorizados desde al menos 1993. ^[6] Este análisis del rendimiento de un analizador packrat supone que hay suficiente memoria disponible para contener todos los resultados memorizados; en la práctica, si no hay suficiente memoria, es posible que algunas funciones de análisis deban invocarse más de una vez en la misma posición de entrada y, en consecuencia, el analizador podría tardar más que el tiempo lineal.

También es posible construir analizadores LL y LR a partir de gramáticas de expresiones de análisis, ^{[ cita necesaria ]} con un mejor rendimiento en el peor de los casos que un analizador de descenso recursivo sin memorización, pero entonces se pierde la capacidad ilimitada de anticipación del formalismo gramatical. Por lo tanto, no todos los lenguajes que se pueden expresar mediante gramáticas de expresión de análisis pueden ser analizados por analizadores LL o LR.

Análisis PEG ascendente

Un analizador pika ^[7] 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 la recursividad por la izquierda, permitiendo que las reglas recursivas por la izquierda se utilicen directamente en la gramática sin tener que reescribirse en una forma no recursiva por la izquierda, y también transmite capacidades óptimas de recuperación de errores en el analizador, lo que históricamente resultó difícil de lograr. para analizadores de descenso recursivo.

Ventajas

No se requiere compilación

Muchos algoritmos de análisis requieren un paso de preprocesamiento en el que la gramática se compila primero en un formato ejecutable opaco, a menudo una especie de autómata. El análisis de expresiones se puede ejecutar directamente (aunque normalmente sigue siendo recomendable transformar los PEG legibles por humanos que se muestran en este artículo a un formato más nativo, como S-expressions , antes de evaluarlos).

Comparado con 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 poderosos. En particular, pueden manejar la recursividad ilimitada y, por lo tanto, hacer coincidir los paréntesis hasta una profundidad de anidamiento arbitraria; En el mejor de los casos, las expresiones regulares pueden realizar un seguimiento del anidamiento hasta una profundidad fija, porque un autómata finito (que tiene un conjunto finito de estados internos) sólo puede distinguir un número finito de profundidades de anidamiento diferentes. En términos más teóricos, (el lenguaje de todas las cadenas de cero o más , seguidas 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}$

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

Aquí AB !.está la expresión inicial. La !.parte exige que la entrada termine después de AB, diciendo "no hay siguiente carácter"; a diferencia de las expresiones regulares, que tienen restricciones mágicas $o \Zpara esto, las expresiones de análisis pueden expresar el final de la entrada usando solo las primitivas básicas.

Las expresiones de análisis *, +, y son similares a las de las expresiones regulares, pero la diferencia es que éstas operan estrictamente en un modo codicioso. ?En última instancia, esto se debe a /que se trata de una elección ordenada. Una consecuencia es que algo puede coincidir como una expresión regular que no coincide con una 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 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" haciendo [ab]?coincidir la cadena vacía va explícitamente en contra de la semántica del análisis de expresiones; Este no es un caso límite 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

está diciendo efectivamente "desde el 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 de las operaciones de repetición.

En comparación con 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 adecuado. ^[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 el sentido formal estricto, es probable que los PEG sean incomparables con los CFG, pero en la práctica hay muchas cosas que los PEG pueden hacer y que los CFG puros no pueden, aunque 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 " colgante más " en C, C++ y Java, mientras que el análisis basado en CFG a menudo necesita una regla fuera de la gramática para resolverlas. 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, probablemente entre tiempo cuadrático y cúbico).

Un ejemplo clásico de lenguaje formal que probablemente no está libre de contexto es el lenguaje : un número arbitrario de s es seguido 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 coincida, el primer tramo de s debe ir seguido de un número igual de s, y además tiene que coincidir donde las s cambian a s, lo que significa que esas s van seguidas de 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 de PEG normalmente se lleva a cabo mediante el análisis packrat , que utiliza la memorización ^{[10] [11]} para eliminar pasos de análisis redundantes. El análisis de Packrat requiere un almacenamiento interno proporcional al tamaño total de entrada, en lugar de a la profundidad del árbol de análisis como ocurre con los analizadores LR. Si se trata de 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 ya tendrá un tamaño proporcional al tamaño total de entrada. Si, en cambio, el análisis se proporciona 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. Se puede diseñar una gramática de expresión de análisis de modo que sólo después de consumir la entrada completa el analizador descubra que necesita retroceder hasta el principio, ^[12] lo que nuevamente podría requerir un almacenamiento proporcional al tamaño total de la entrada.

Para 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 en el código fuente escrito a mano, la profundidad de anidamiento de expresiones tiene un límite constante y bastante independiente de la longitud del programa, porque las expresiones anidadas más allá de una cierta profundidad tienden a ser refactorizadas . 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 entrada. ^[14]

Modelo computacional

Para lograr una complejidad general lineal, el almacenamiento utilizado para la memorización debe además proporcionar un acceso en tiempo constante amortizado a los elementos de datos individuales memorizados. En la práctica, eso no es un problema (por ejemplo, una tabla hash de tamaño dinámico logra esto), pero utiliza aritmética de punteros , por lo que se supone que tiene una máquina de acceso aleatorio . Las discusiones teóricas sobre estructuras de datos y algoritmos tienen una tendencia tácita a suponer un modelo más restringido (posiblemente el del cálculo lambda , posiblemente el de Scheme ), donde una tabla dispersa debe construirse utilizando árboles y el acceso a los elementos de datos no es un 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 packrat: dependen de operaciones aparentemente de mala reputación.

Visto al revés, esto dice que los analizadores packrat aprovechan el poder computacional fácilmente disponible en sistemas de la vida real, que los algoritmos de análisis más antiguos no saben emplear.

Recursión izquierda indirecta

Un PEG se denomina 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 provocan 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 de packrat, se debe eliminar la recursividad por la izquierda.

Significado práctico

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

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

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 hacer repeticiones sin recursividad:

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

Una diferencia radica en los árboles de sintaxis abstracta generados: con recursividad cada Sumuno Argspuede tener como máximo dos hijos, pero con repetición puede haber muchos arbitrariamente. Si las etapas posteriores del procesamiento requieren que dichas listas de elementos secundarios se reformulen como árboles con grados acotados , por ejemplo, las instrucciones del microprocesador para la suma generalmente solo permiten dos operandos, entonces se impondrían propiedades como la asociatividad por la izquierda después de la etapa de análisis dirigido por PEG.

Por lo tanto, es prácticamente menos probable que la recursividad por la izquierda cause problemas a un analizador PEG packrat que, digamos, a un analizador libre de contexto LL(k), a menos que uno insista en usar modismos libres de contexto. Sin embargo, no todos los casos de recursividad tienen que ver con la repetición.

Recursión 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 / Valuesignificaría primero intentar ver como Sum(ya que analizamos de arriba hacia abajo), segundo intentar ver como Producty solo un tercer intento ver como. Value– en lugar de mediante el anidamiento 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

Desafortunadamente, hacer coincidir an Exprrequiere probar si Sumcoincide, mientras que hacer coincidir a Sumrequiere probar si Exprcoincide. Debido a que el término aparece en la posición más a la izquierda, estas reglas constituyen 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 recursividad patológica). Sin embargo, las reglas recursivas por la izquierda siempre se pueden reescribir para eliminar la recursividad por la izquierda. ^{[2] [15]} Por ejemplo, la siguiente regla CFG recursiva a la izquierda:

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

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

cadena de un  ←  'a' +

El proceso de reescribir reglas indirectamente recursivas por la izquierda es complejo en algunos analizadores packrat, especialmente cuando están involucradas acciones semánticas.

Con algunas modificaciones, el análisis tradicional de packrat puede admitir la recursión directa hacia la izquierda, ^{[5] [16] [17]} pero hacerlo resulta en una pérdida de la propiedad de análisis de tiempo lineal ^[16] 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 OMeta ^[16] admite la recursividad izquierda directa e indirecta completa sin complejidad adicional (pero nuevamente, con una pérdida de complejidad de tiempo lineal), mientras que todos los analizadores GLR admiten la recursividad izquierda.

Comportamiento inesperado

Una primera impresión común de los PEG es que parecen CFG con ciertas características convenientes (operadores de repetición *+?como en expresiones regulares y predicados de anticipación &!) además de opciones ordenadas para 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 en realidad es un lenguaje regular (el de cadenas de un número impar de x).

Es instructivo descubrir exactamente qué hace un analizador PEG cuando intenta hacer coincidir

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

contra la cuerda xxxxxq. Como era de esperar, intenta recursivamente hacer coincidir el no terminal Sen posiciones crecientes en esta cadena, hasta que falla la coincidencia con el q, y luego comienza a retroceder. Esto es lo siguiente:

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, lo que produce una coincidencia de longitud 1. ↑ Pos.4: La primera rama de S falla, la segunda rama tiene éxito, lo que produce una coincidencia de longitud 1. ↑ Pos.3: La primera rama de S tiene éxito, lo que produce una coincidencia de longitud 3. ↑ Pos.2: La primera rama de S falla, porque después del partido S a las 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, lo que produce una coincidencia de longitud 3.

Hacer coincidir una expresión de análisis es codicioso , en el sentido de que el primer éxito encontrado es el único que se considera. Incluso si localmente las opciones más largas se ordenan primero, no hay garantía de que esta coincidencia codiciosa encuentre la coincidencia más larga a nivel global.

Detección de ambigüedades e influencia del orden de las reglas en el lenguaje que coincide

Los generadores de analizadores LL(k) y LR(k) no podrán completarse cuando la gramática de entrada sea ambigua. Esta es una característica del caso común en el que la gramática pretende ser inequívoca pero es defectuosa. Un generador de analizador PEG resolverá ambigüedades no deseadas primero en la coincidencia, lo que puede ser arbitrario y conducir a análisis sorprendentes.

El orden de las producciones en una gramática PEG afecta no sólo a la resolución de la ambigüedad, sino también al lenguaje coincidente . 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 y ): ${\displaystyle G_{1}}$ ${\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 siempre se toma la primera opción si la cadena de entrada... comienza con 'a'. . ^[1] Específicamente, (es decir, el idioma coincidente con ) incluye la entrada "ab", pero no la incluye. Por lo tanto, agregar una nueva opción a una gramática PEG puede eliminar cadenas del idioma que coincidan; por ejemplo, es la adición de una regla a la gramática de producción única  , que contiene una cadena que no coincide con . Además, construir una gramática que coincida a partir de gramáticas PEG no siempre es una tarea trivial. Esto contrasta marcadamente con los CFG, en los 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})}$ ${\displaystyle G_{1}}$ ${\displaystyle L(G_{2})}$ ${\displaystyle G_{2}}$A = "a" "b" ${\displaystyle G_{2}}$ ${\displaystyle L(G_{1})\cup L(G_{2})}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle L(G_{1})\cup L(G_{2})}$

S → inicio ( G1 ) | inicio ( G2 )    

Teoría del análisis de gramáticas de expresiones.

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

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

Indecidibilidad del vacío

A diferencia del caso de las gramáticas libres de 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 postal se reduce a una instancia del problema de decidir si un lenguaje de expresión de análisis está vacío.

Recuerde que una instancia del problema de correspondencia postal consta de 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, seamos cadenas arbitrarias, separadas por pares, igualmente largas, de símbolos terminales (ya con símbolos distintos en el alfabeto de símbolos terminales, la longitud es suficiente) y considere la gramática de expresión de análisis. ${\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 usa solo PEG desde la versión 3.10. ^[19] El lenguaje de programación jq utiliza un formalismo estrechamente relacionado con PEG.

Ver también

• Gramática booleana libre de 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
• Combinador de analizadores

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 de Packrat: simple, potente, perezoso, de tiempo lineal, perla funcional" (PDF) . Avisos ACM SIGPLAN . 37 (9). doi :10.1145/583852.581483.
3. Sirthias, Mathías. "Parboiled: construcción de reglas en Java" . Consultado el 13 de enero de 2024 .
4. Kupries, Andreas. "pt::peg_language - Tutorial de lenguaje PEG". Código fuente de la biblioteca Tcl . Consultado el 14 de enero de 2024 .
5. 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 .
6. Merritt, Doug (noviembre de 1993). "Descenso recursivo transparente". Compiladores del grupo Usenet . Consultado el 4 de septiembre de 2009 .
7. Hutchison, Luke AD (2020). "Análisis de Pika: el análisis a la inversa resuelve los problemas de recuperación de errores y recursividad izquierda". arXiv : 2005.06444 [cs.PL].
8. Los CFG se pueden utilizar para describir la sintaxis de lenguajes de programación comunes hasta el nivel de caracteres, pero hacerlo es bastante engorroso, porque la regla estándar de tokenización de que un token consta de 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 realizar un seguimiento de qué tipo de carácter tiene. estar en el límite. Si hay diferentes tipos de caracteres que no son espacios en blanco, eso se suma a posibles variantes por no terminal, lo que aumenta significativamente la gramática. ${\displaystyle 3}$ ${\displaystyle 3^{2}=9}$
9. Lee, Lillian (enero de 2002). "El análisis gramatical rápido y libre de 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 análisis y gramáticas de expresiones 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 en el sentido de que “en este archivo, la coma es un separador decimal , entonces, ¿todas esas llamadas a funciones f(3,14*r) que pensabas tenían dos argumentos? No lo hacen. Ahora regrese al inicio de la entrada y analícela toda nuevamente”. Podría decirse que eso sería un mal diseño del lenguaje de entrada, pero el punto es que las gramáticas de expresión de análisis son lo suficientemente poderosas para manejar esto, simplemente 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 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 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 gráficos dispersos con . ${\displaystyle O(|V|^{3})}$ ${\displaystyle O(|V|*|E|)}$ ${\displaystyle |E|\in O(|V|)}$
15. Ah, 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 Packrat pueden admitir la recursividad hacia la izquierda" (PDF) . Actas del simposio ACM SIGPLAN 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. Consultado el 2 de octubre de 2008 .
17. Steinmann, Ruedi (marzo de 2009). "Manejo de la recursión izquierda en analizadores 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 .

enlaces externos

• Convertir una expresión de cadena en una expresión lambda usando un analizador de expresiones
• La página de análisis de Packrat y gramáticas de expresiones de análisis
• El lenguaje construido Lojban tiene una gramática PEG bastante grande que permite un análisis inequívoco del texto en Lojban.
• Una implementación ilustrativa de un esquema PEG en Guile