Analizador de Packrat

Tipo de analizador

El analizador Packrat es un tipo de analizador que comparte similitudes con el analizador descendente recursivo en su construcción. Sin embargo, se diferencia porque toma gramáticas de expresión de análisis (PEG) como entrada en lugar de gramáticas LL . ^[1]

En 1970, Alexander Birman sentó las bases para el análisis sintáctico de Packrat al introducir el "esquema de reconocimiento TMG" (TS) y el "TS generalizado" (gTS). El TS se basaba en el compilador-compilador TMG de Robert M. McClure, y el gTS se basaba en el compilador-compilador META de Dewey Val Schorre . El trabajo de Birman fue refinado posteriormente por Aho y Ullman, y renombrado como lenguaje de análisis sintáctico descendente (TDPL) y TDPL generalizado (GTDPL), respectivamente. Estos algoritmos fueron los primeros de su tipo en emplear un análisis sintáctico descendente determinista con retroceso. ^{[2] [3]}

Bryan Ford desarrolló los PEG como una expansión de GTDPL y TS. A diferencia de los CFG , los PEG son inequívocos y pueden coincidir bien con los lenguajes orientados a máquinas. Los PEG, de manera similar a GTDPL y TS, también pueden expresar todos los LL(k) y LR(k) . Bryan también presentó Packrat como un analizador que utiliza técnicas de memorización sobre un analizador PEG simple. Esto se hizo porque los PEG tienen una capacidad ilimitada de anticipación que da como resultado un analizador con un rendimiento temporal exponencial en el peor de los casos. ^{[2] [3]}

Packrat lleva un registro de los resultados intermedios de todas las funciones de análisis recursivas entre sí. Cada función de análisis se llama solo una vez en una posición de entrada específica. En algunos casos de implementación de packrat, si no hay suficiente memoria, es posible que sea necesario llamar a ciertas funciones de análisis varias veces en la misma posición de entrada, lo que hace que el analizador tarde más que el tiempo lineal. ^[4]

Sintaxis

El analizador packrat toma como entrada la misma sintaxis que los PEG: un PEG simple se compone de símbolos terminales y no terminales, posiblemente intercalados con operadores que componen una o varias reglas de derivación. ^[2]

Símbolos

• Los símbolos no terminales se indican con letras mayúsculas (por ejemplo, ) ${\displaystyle \{S,E,F,D\}}$
• Los símbolos terminales se indican con minúsculas (por ejemplo, ) ${\displaystyle \{a,b,z,e,g\}}$
• Las expresiones se indican con letras griegas minúsculas (por ejemplo, ) ${\displaystyle \{\alpha ,\beta ,\gamma ,\omega ,\tau \}}$
  • Las expresiones pueden ser una mezcla de símbolos terminales, símbolos no terminales y operadores.

Operadores

Normas

Una regla de derivación está compuesta por un símbolo no terminal y una expresión . ${\displaystyle S\rightarrow \alpha }$

Una expresión especial es el punto de inicio de la gramática. ^[2] En caso de que no se especifique, se utiliza la primera expresión de la primera regla. ${\displaystyle \alpha _{s}}$ ${\displaystyle \alpha _{s}}$

El analizador considera que una cadena de entrada es aceptada si se la reconoce. Como efecto secundario, el analizador puede reconocer una cadena incluso si no se la ha consumido por completo. ^[2] ${\displaystyle \alpha _{s}}$ ${\displaystyle x}$

Un caso extremo de esta regla es que la gramática coincide con cualquier cadena. ${\displaystyle S\rightarrow x*}$

Esto se puede evitar reescribiendo la gramática como ${\displaystyle S\rightarrow x*!.}$

Ejemplo

${\displaystyle {\begin{cases}S\rightarrow A/B/D\\A\rightarrow {\textbf {'a'}}\ S\ {\textbf {'a'}}\\B\rightarrow {\textbf {'b'}}\ S\ {\textbf {'b'}}\\D\rightarrow ({\textbf {'0'}}-{\textbf {'9'}})?\end{cases}}}$

Esta gramática reconoce un palíndromo sobre el alfabeto , con un dígito opcional en el medio. ${\displaystyle \{a,b\}}$

Las cadenas de ejemplo aceptadas por la gramática incluyen: y . ${\displaystyle {\textbf {'aa'}}}$ ${\displaystyle {\textbf {'aba3aba'}}}$

Recursión izquierda

La recursión por la izquierda ocurre cuando una producción gramatical se refiere a sí misma como su elemento más a la izquierda, ya sea directa o indirectamente. Dado que Packrat es un analizador descendente recursivo, no puede manejar la recursión por la izquierda directamente. ^[5] Durante las primeras etapas de desarrollo, se descubrió que una producción que es recursiva por la izquierda se puede transformar en una producción recursiva por la derecha. ^[6] Esta modificación simplifica significativamente la tarea de un analizador Packrat. No obstante, si hay una recursión por la izquierda indirecta involucrada, el proceso de reescritura puede ser bastante complejo y desafiante. Si los requisitos de complejidad de tiempo se relajan de lineal a superlineal , es posible modificar la tabla de memorización de un analizador Packrat para permitir la recursión por la izquierda, sin alterar la gramática de entrada. ^[5]

Combinador iterativo

El combinador iterativo , , necesita especial atención cuando se utiliza en un analizador Packrat. De hecho, el uso de combinadores iterativos introduce una recursión secreta que no registra los resultados intermedios en la matriz de resultados. Esto puede llevar a que el analizador funcione con un comportamiento superlineal. Este problema se puede resolver aplicando la siguiente transformación: ^[1] ${\displaystyle \alpha +}$ ${\displaystyle \alpha *}$

Con esta transformación se pueden memorizar adecuadamente los resultados intermedios.

Técnica de memorización

La memorización es una técnica de optimización en informática que tiene como objetivo acelerar los programas mediante el almacenamiento de los resultados de llamadas a funciones costosas. Esta técnica funciona básicamente almacenando en caché los resultados de modo que cuando se vuelvan a producir las mismas entradas, simplemente se devuelva el resultado almacenado en caché, evitando así el lento proceso de volver a calcular. ^[7] Al utilizar el análisis sintáctico y la memorización de Packrat, cabe destacar que la función de análisis para cada no terminal se basa únicamente en la cadena de entrada. No depende de ninguna información recopilada durante el proceso de análisis. Esencialmente, las entradas de la tabla de memorización no afectan ni dependen del estado específico del analizador en un momento dado. ^[8]

El análisis de Packrat almacena los resultados en una matriz o una estructura de datos similar que permite búsquedas e inserciones rápidas. Cuando se encuentra una producción, se verifica la matriz para ver si ya se ha producido. Si es así, se recupera el resultado de la matriz. Si no, se evalúa la producción, se inserta el resultado en la matriz y luego se devuelve. ^[9] Al evaluar la matriz completa en un enfoque tabular, se requeriría espacio. ^[9] Aquí, representa el número de no terminales y representa el tamaño de la cadena de entrada. ${\displaystyle m*n}$ ${\displaystyle \Theta (mn)}$ ${\displaystyle m}$ ${\displaystyle n}$

En una implementación ingenua, toda la tabla se puede derivar de la cadena de entrada comenzando desde el final de la cadena.

El analizador Packrat se puede mejorar para actualizar solo las celdas necesarias en la matriz a través de una visita en profundidad de cada árbol de subexpresiones. En consecuencia, usar una matriz con dimensiones de es a menudo un desperdicio, ya que la mayoría de las entradas permanecerían vacías. ^[5] Estas celdas están vinculadas a la cadena de entrada, no a los no terminales de la gramática. Esto significa que aumentar el tamaño de la cadena de entrada siempre aumentaría el consumo de memoria, mientras que la cantidad de reglas de análisis solo cambia la peor complejidad espacial. ^[1] ${\displaystyle m*n}$

Operador de corte

Se ha introducido en Packrat otro operador llamado cut para reducir aún más su complejidad espacial promedio. Este operador utiliza las estructuras formales de muchos lenguajes de programación para eliminar derivaciones imposibles. Por ejemplo, el análisis sintáctico de las sentencias de control en un lenguaje de programación estándar es mutuamente excluyente a partir del primer token reconocido, p. ej., . ^[10] ${\displaystyle \{if,do,while,switch\}}$

Cuando un analizador Packrat utiliza operadores de corte, limpia eficazmente su pila de retroceso. Esto se debe a que un operador de corte reduce la cantidad de alternativas posibles en una elección ordenada. Al agregar operadores de corte en los lugares correctos en la definición de una gramática, el analizador Packrat resultante solo necesita una cantidad casi constante de espacio para la memorización. ^[10]

El algoritmo

Boceto de una implementación de un algoritmo Packrat en un pseudocódigo similar a Lua. ^[5]

INPUT ( n )  – devuelve el carácter en la posición nREGLA ( R  :  Regla ,  P  :  Posición  )  entrada  =  GET_MEMO ( R , P )  -- devuelve el número de elementos que coincidieron previamente en la regla R en la posición P  si  entrada  ==  nil  entonces  devuelve  EVAL ( R ,  P );  fin  devuelve  entrada ;EVAL ( R  :  Regla ,  P  :  Posición  )  inicio  =  P ;  para  elección  en  R. elecciones - Devuelve una lista de opciones acc = 0 ;  para símbolo en elección entonces - Devuelve cada elemento de una regla, terminal y no terminal si símbolo . es_terminal entonces si INPUT ( inicio + acc ) == símbolo . terminal entonces acc = acc + 1 ; - Se encontró la terminal correcta omitir pasarla de lo contrario romper ; fin de lo contrario res = REGLA ( símbolo . no terminal , inicio + acc ); - Intenta reconocer un no terminal en la posición inicio+acc SET_MEMO ( símbolo . no terminal , inicio + acc , res ); - También memorizamos el fallo con un valor especial fallar si res == fallar entonces romper ; fin acc = acc + res ; fin si símbolo == elección . último - Verificamos si hemos coincidido con el último símbolo en una elección si es así devolver devolver acc ; fin fin devolver fallar ; - Si no hay coincidencia de elección devolver fallar                                                               

Ejemplo

Dado el siguiente contexto, una gramática libre que reconoce expresiones aritméticas simples compuestas de dígitos individuales intercalados por suma, multiplicación y paréntesis.

${\displaystyle {\begin{cases}S\rightarrow A\\A\rightarrow M\ {\textbf {'+'}}\ A\ /\ M\\M\rightarrow P\ {\textbf {'*'}}\ M\ /\ P\\P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ D\\D\rightarrow ({\textbf {'0'}}-{\textbf {'9'}})\end{cases}}}$

Denotado con el terminador de línea podemos aplicar el algoritmo packrat ${\displaystyle \dashv }$

Implementación

Véase también

• Algoritmo CYK
• Gramática libre de contexto
• Algoritmos de análisis
• Analizador sintáctico Earley

Referencias

1. Ford, Bryan (2006). "Análisis de Packrat: tiempo lineal, simple, potente y perezoso". arXiv : cs/0603077 .
2. Ford, Bryan (1 de enero de 2004). "Análisis de gramáticas de expresiones". Actas del 31.º simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . POPL '04. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 111–122. doi :10.1145/964001.964011. ISBN 978-1-58113-729-3. Número de identificación del sujeto  7762102.
3. Flodin, Daniel. "Una comparación entre el análisis de Packrat y el análisis de Shift-Reduce convencional en gramáticas y entradas del mundo real" (PDF) .
4. Mizushima, Kota; Maeda, Atusi; Yamaguchi, Yoshinori (6 de mayo de 2010). "Los analizadores sintácticos Packrat pueden manejar gramáticas prácticas en un espacio mayoritariamente constante". Actas del 9.º taller ACM SIGPLAN-SIGSOFT sobre análisis de programas para herramientas de software e ingeniería. ACM. pp. 29–36. doi :10.1145/1806672.1806679. ISBN 978-1-4503-0082-7.S2CID14498865  .​
5. Warth, Alessandro; Douglass, James R.; Millstein, Todd (7 de enero de 2008). "Los analizadores sintácticos Packrat pueden admitir la recursión por la izquierda". Actas del simposio ACM SIGPLAN de 2008 sobre evaluación parcial y manipulación de programas basada en semántica . PEPM '08. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 103–110. doi :10.1145/1328408.1328424. ISBN 978-1-59593-977-7. Número de identificación del sujeto  2168153.
6. Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D., eds. (2007). Compiladores: principios, técnicas y herramientas (2.ª ed.). Boston Munich: Pearson Addison-Wesley. ISBN 978-0-321-48681-3.
7. Norvig, Peter (1991-03-01). "Técnicas de memorización automática con aplicaciones al análisis sintáctico libre de contexto". Computational Linguistics . 17 (1): 91–98. ISSN  0891-2017.
8. Dubroy, Patrick; Warth, Alessandro (23 de octubre de 2017). "Análisis incremental de packrat". Actas de la 10.ª Conferencia internacional ACM SIGPLAN sobre ingeniería del lenguaje de software . SLE 2017. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 14–25. doi :10.1145/3136014.3136022. ISBN 978-1-4503-5525-4.S2CID 13047585  .
9. Science, Revista internacional de investigación científica en; Ijsrset, Ingeniería y tecnología. "Un estudio de Packrat Parser". Un estudio de Packrat Parser .
10. Mizushima, Kota; Maeda, Atusi; Yamaguchi, Yoshinori (6 de mayo de 2010). "Los analizadores sintácticos Packrat pueden manejar gramáticas prácticas en un espacio mayoritariamente constante". Actas del 9.º taller ACM SIGPLAN-SIGSOFT sobre análisis de programas para herramientas de software e ingeniería . PASTE '10. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 29–36. doi :10.1145/1806672.1806679. ISBN 978-1-4503-0082-7.S2CID14498865  .​
11. Bifurcación mantenida de PEG.js

Enlaces externos

• Análisis de Packrat: tiempo lineal, sencillo, potente y perezoso
• Análisis de gramáticas de expresión: una base sintáctica basada en el reconocimiento