Un analizador de reducción de desplazamiento es una clase de métodos de análisis ascendentes eficientes basados en tablas para lenguajes informáticos y otras notaciones definidas formalmente por una gramática . Los métodos de análisis más comúnmente utilizados para analizar lenguajes de programación , el análisis LR y sus variaciones, son los métodos de reducción de desplazamiento. [1] Los analizadores de precedencia utilizados antes de la invención del análisis LR también son métodos de reducción de desplazamiento. Todos los analizadores de reducción de desplazamiento tienen efectos externos similares, en el orden incremental en el que construyen un árbol de análisis o llaman a acciones de salida específicas.
Un analizador de reducción de desplazamiento escanea y analiza el texto de entrada en una sola pasada sobre el texto, sin realizar copias de seguridad. El analizador construye el árbol de análisis de forma incremental, de abajo hacia arriba y de izquierda a derecha, sin adivinar ni retroceder. En cada punto de este paso, el analizador ha acumulado una lista de subárboles o frases del texto de entrada que ya han sido analizados. Esos subárboles aún no están unidos porque el analizador aún no ha llegado al extremo derecho del patrón de sintaxis que los combinará.
Considere la cuerda A = B + C * 2.
En el paso 7 del ejemplo, sólo se analizó "A = B +". Sólo existe la esquina inferior izquierda sombreada del árbol de análisis. Ninguno de los nodos del árbol de análisis numerados 8 y superiores existe todavía. Los nodos 1, 2, 6 y 7 son las raíces de subárboles aislados que cubren todos los elementos 1 a 7. El nodo 1 es la variable A, el nodo 2 es el delimitador =, el nodo 6 es el sumando B y el nodo 7 es el operador +. Estos cuatro nodos raíz se mantienen temporalmente en una pila de análisis. La parte restante sin analizar del flujo de entrada es "C * 2".
Un analizador de desplazamiento-reducción funciona haciendo una combinación de pasos de desplazamiento y pasos de reducción, de ahí el nombre.
El analizador continúa con estos pasos hasta que se haya consumido toda la entrada y todos los árboles de análisis se hayan reducido a un solo árbol que representa una entrada legal completa.
En cada paso del análisis, todo el texto de entrada se divide en la pila de análisis, el símbolo de anticipación actual y el texto restante sin analizar. La siguiente acción del analizador está determinada por los símbolos de la pila más a la derecha y el símbolo de anticipación. La acción se lee de una tabla que contiene todas las combinaciones sintácticamente válidas de símbolos de pila y de anticipación.
Consulte [2] para ver un ejemplo más simple.
Una gramática es el conjunto de patrones o reglas de sintaxis para el idioma de entrada. No cubre todas las reglas del lenguaje, como el tamaño de los números o el uso consistente de nombres y sus definiciones en el contexto de todo el programa. Los analizadores de reducción de desplazamiento utilizan una gramática libre de contexto que se ocupa únicamente de patrones locales de símbolos.
Un ejemplo de gramática como un pequeño subconjunto del lenguaje Java o C capaz de hacer coincidencias A = B + C*2podría ser:
Los símbolos terminales de la gramática son los símbolos de varios caracteres o "tokens" que se encuentran en el flujo de entrada mediante un escáner léxico . Aquí estos incluyen = + * e int para cualquier constante entera, e id para cualquier nombre de identificador. A la gramática no le importan los valores int o la ortografía de id , ni tampoco los espacios en blanco o los saltos de línea. La gramática utiliza estos símbolos terminales pero no los define. Siempre están en el extremo inferior y tupido del árbol de análisis.
Los términos en mayúscula como Sums son símbolos no terminales . Estos son nombres de conceptos o patrones en el idioma. Están definidos en la gramática y nunca aparecen en el flujo de entrada. Siempre están por encima de la parte inferior del árbol de análisis. Solo ocurren como resultado de que el analizador aplica alguna regla gramatical. Algunos no terminales se definen con dos o más reglas; estos son patrones alternativos. Las reglas pueden referirse a sí mismas. Esta gramática utiliza reglas recursivas para manejar operadores matemáticos repetidos. Las gramáticas de lenguajes completos utilizan reglas recursivas para manejar listas, expresiones entre paréntesis y declaraciones anidadas.
Cualquier lenguaje informático determinado puede describirse mediante varias gramáticas diferentes. La gramática de un analizador de reducción de desplazamientos debe ser inequívoca en sí misma o complementarse con reglas de precedencia de desempate. Esto significa que solo hay una forma correcta de aplicar la gramática a un ejemplo legal determinado del lenguaje, lo que da como resultado un árbol de análisis único y una secuencia única de acciones de desplazamiento/reducción para ese ejemplo.
Un analizador basado en tablas tiene todo su conocimiento sobre la gramática codificado en datos inmutables llamados tablas del analizador. El código del programa del analizador es un bucle genérico simple que se aplica sin cambios a muchas gramáticas e idiomas. Las tablas pueden elaborarse a mano para los métodos de precedencia. Para los métodos LR, las tablas complejas se derivan mecánicamente de una gramática mediante alguna herramienta generadora de analizadores como Bison . [3] Las tablas del analizador suelen ser mucho más grandes que la gramática. En otros analizadores que no se basan en tablas, como el descenso recursivo , cada construcción del lenguaje es analizada por una subrutina diferente, especializada en la sintaxis de esa construcción.
El analizador de reducción de turnos es eficiente porque no implica realizar copias de seguridad. Su tiempo total de ejecución aumenta linealmente con la longitud de la entrada y el tamaño del árbol de análisis completo. Otros métodos de análisis que retroceden pueden tardar un tiempo exponencial cuando adivinan mal. [ cita necesaria ]
Para evitar adivinar, el analizador de desplazamiento-reducción a menudo mira hacia adelante (hacia la derecha en el texto de izquierda a derecha) al siguiente símbolo escaneado antes de decidir qué hacer con los símbolos escaneados previamente. El escáner léxico trabaja un símbolo por delante del resto del analizador. El símbolo de anticipación también se denomina "contexto derecho" para cada decisión de análisis. (Rara vez se pueden utilizar dos o más símbolos de anticipación, aunque la mayoría de las gramáticas prácticas pueden diseñarse para utilizar un símbolo de anticipación).
Un analizador de reducción de desplazamiento espera hasta haber escaneado y analizado todas las partes de alguna construcción antes de comprometerse con cuál es la construcción combinada. Luego, el analizador actúa inmediatamente sobre la combinación en lugar de esperar más. En el ejemplo del árbol de análisis anterior, la frase B se reduce a Valor y luego a Productos y Sumas en los pasos 3 a 6 tan pronto como se ve + en la anticipación, en lugar de esperar más para organizar esas partes del árbol de análisis. Las decisiones sobre cómo manejar B se basan únicamente en lo que el analizador y el escáner ya han visto, sin considerar las cosas que aparecen mucho más tarde a la derecha.
Las reducciones reorganizan los elementos analizados más recientemente, es decir, los que se encuentran inmediatamente a la izquierda del símbolo de anticipación. Entonces, la lista de cosas ya analizadas actúa como una pila . Esta pila de análisis crece hacia la derecha. La base o parte inferior de la pila está a la izquierda y contiene el fragmento de análisis más antiguo y más a la izquierda. Cada paso de reducción actúa sólo en los fragmentos de análisis más recientes y situados más a la derecha. (Esta pila de análisis acumulativo es muy diferente a la pila de análisis predictiva que crece hacia la izquierda utilizada por los analizadores de arriba hacia abajo ).
Cuando una regla gramatical como
Cuando se aplica, la parte superior de la pila contiene los árboles de análisis "... Productos * Valor". Esta instancia encontrada del lado derecho de la regla se llama identificador . El paso de reducción reemplaza el identificador "Productos * Valor" por el no terminal del lado izquierdo, en este caso un Productos más grande. Si el analizador crea árboles de análisis completos, entonces los tres árboles para Productos internos, * y Valor se combinan mediante una nueva raíz de árbol para los Productos más grandes. De lo contrario, los detalles semánticos de los Productos y Valor internos se envían a algún paso posterior del compilador, o se combinan y guardan en el nuevo símbolo de Productos. [4]
El analizador sigue aplicando reducciones en la parte superior de la pila de análisis mientras siga encontrando allí ejemplos recién completados de reglas gramaticales. Cuando ya no se pueden aplicar más reglas, el analizador desplaza el símbolo de anticipación a la pila de análisis, escanea un nuevo símbolo de anticipación y vuelve a intentarlo.
Las tablas del analizador muestran qué hacer a continuación, para cada combinación legal de símbolos de la pila de análisis superior y símbolo de anticipación. Esa próxima acción debe ser única; cambiar o reducir, pero no ambos. (Esto implica algunas limitaciones adicionales en la gramática, además de ser inequívoco). Los detalles de la tabla varían mucho entre los diferentes tipos de analizadores de reducción de desplazamiento.
En los analizadores de precedencia , el extremo derecho de los identificadores se encuentra comparando el nivel de precedencia o la rigidez gramatical de los símbolos de la pila superior con el del símbolo de anticipación. En el ejemplo anterior, int e id pertenecen a niveles gramaticales internos en comparación con el delimitador de declaración ; . Por lo tanto, se considera que int e id tienen mayor prioridad que ; y debe reducirse a otra cosa siempre que vaya seguido de ; . Existen diferentes variedades de analizadores de precedencia, cada uno con diferentes formas de encontrar el extremo izquierdo del identificador y elegir la regla correcta a aplicar:
Los analizadores de precedencia están limitados en las gramáticas que pueden manejar. Ignoran la mayor parte de la pila de análisis al tomar decisiones. Consideran sólo los nombres de los símbolos superiores, no el contexto completo de en qué parte de la gramática aparecen ahora esos símbolos. La precedencia requiere que las combinaciones de símbolos de apariencia similar se analicen y utilicen de manera idéntica en toda la gramática, sin embargo, esas combinaciones ocurren independientemente del contexto.
Los analizadores LR son una forma más flexible de análisis de reducción de desplazamiento y manejan muchas más gramáticas. [8]
Los analizadores LR funcionan como una máquina de estados , realizando una transición de estado para cada acción de cambio o reducción. Estos emplean una pila donde el estado actual es empujado (hacia abajo) por acciones de cambio. Esta pila luego aparece mediante acciones de reducción. Este mecanismo permite al analizador LR manejar todas las gramáticas deterministas libres de contexto, un superconjunto de gramáticas de precedencia. El analizador LR está completamente implementado por el analizador Canonical LR . Los analizadores Look-Ahead LR y Simple LR implementan variantes simplificadas que han reducido significativamente los requisitos de memoria. [9] [10] Investigaciones recientes han identificado métodos mediante los cuales se pueden implementar analizadores LR canónicos con requisitos de tabla drásticamente reducidos en comparación con el algoritmo de creación de tablas de Knuth. [11]
Ya sea LR, LALR o SLR, la máquina de estados básica es la misma; sólo las tablas son diferentes, y estas tablas casi siempre se generan mecánicamente. Además, estas tablas generalmente se implementan de manera que REDUCE da como resultado una LLAMADA a una subrutina cerrada que es externa a la máquina de estados y que realiza una función implícita en la semántica de la regla gramatical que se está REDUCIENDO. Por lo tanto, el analizador se divide en una parte de máquina de estado invariante y una parte de semántica variante. Esta distinción fundamental fomenta el desarrollo de analizadores de alta calidad que sean excepcionalmente confiables.
Dado un estado de pila específico y un símbolo de anticipación, existen precisamente cuatro acciones posibles: ERROR, SHIFT, REDUCE y STOP (en lo sucesivo denominadas configuraciones). La presencia de un punto, •, en una configuración representa la posición de anticipación actual, con el símbolo de anticipación mostrado a la derecha del punto (y que siempre corresponde a un símbolo de terminal) y el estado actual de la pila a la izquierda del punto. (y que normalmente corresponde a un símbolo no terminal).
Por razones prácticas, incluido un mayor rendimiento, las tablas generalmente se amplían con una matriz auxiliar algo grande de símbolos de dos bits, obviamente comprimidos en cuatro símbolos de dos bits, un byte, para un acceso eficiente en máquinas orientadas a bytes, a menudo codificados como :
(DEJA de ser un caso especial de SHIFT). La matriz completa generalmente incluye principalmente configuraciones ERROR, un número definido gramaticalmente de configuraciones SHIFT y REDUCE y una configuración STOP.
En los sistemas de programación que admiten la especificación de valores en el sistema numérico cuaternario (base 4, dos bits por dígito cuaternario), como XPL, estos se codifican como, por ejemplo:
Las tablas SHIFT y REDUCE se implementan por separado de la matriz. La matriz auxiliar es "sondeada" sólo para el estado actual y el símbolo de anticipación. La matriz (auxiliar) está "llena", mientras que las tablas (desplazar y reducir) pueden ser muy "escasas", y se pueden lograr eficiencias significativas mediante una "descomposición" óptima de esas tablas SHIFT y REDUCE (ERROR y STOP no necesitan tablas ).
Las configuraciones SHIFT y REDUCE son obvias, a partir de la definición básica de un analizador SHIFT-REDUCE.
STOP, entonces, representa una configuración donde el estado en la parte superior de la pila y el símbolo del terminal de anticipación están dentro de la gramática del sujeto, y representa el final del programa:
siendo imposible CAMBIAR más allá del ⊥ final para alcanzar, conceptualmente
ERROR, entonces, representa una configuración donde el estado en la parte superior de la pila y el símbolo del terminal de anticipación no están dentro de la gramática del tema. Esto presenta una oportunidad para invocar un procedimiento de recuperación de errores, quizás, en su forma más simplista, para descartar el símbolo de terminal de anticipación y leer el siguiente símbolo de terminal, pero son posibles muchas otras acciones programadas, incluida la poda de la pila o el descarte de la anticipación. símbolo terminal y podando la pila (y en un caso patológico, generalmente es posible obtener
donde <programa> consta sólo de una "declaración nula" ).
En la mayoría de los casos, la pila está precargada intencionalmente, es decir, inicializada, con
por lo que se supone que la ⊥ inicial ya ha sido reconocida. Esto, entonces, representa el comienzo del programa y, por lo tanto, evita tener una configuración de INICIO separada, que es, conceptualmente
⊥ es un símbolo pseudo-terminal especial agregado mecánicamente a la gramática, al igual que <programa> es un símbolo pseudo-no terminal especial agregado mecánicamente a la gramática (si el programador no incluyó explícitamente <programa> en la gramática, entonces <programa> se agregaría automáticamente a la gramática en nombre del programador).
Claramente, un analizador de este tipo tiene precisamente una configuración START (implícita) y una configuración STOP (explícita), pero puede tener, y generalmente tiene, cientos de configuraciones SHIFT y REDUCE, y quizás miles de configuraciones ERROR.
{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )