Analizador con cambio de desplazamiento

Un analizador sintáctico shift-reduce es una clase de métodos de análisis sintáctico ascendentes , eficientes y basados ​​en tablas, para lenguajes de programación y otras notaciones definidas formalmente por una gramática . Los métodos de análisis sintáctico más comúnmente utilizados para analizar lenguajes de programación , análisis sintáctico LR y sus variaciones, son métodos shift-reduce. ^[1] Los analizadores sintácticos de precedencia utilizados antes de la invención del análisis sintáctico LR también son métodos shift-reduce. Todos los analizadores sintácticos shift-reduce tienen efectos externos similares, en el orden incremental en el que construyen un árbol de análisis sintáctico o invocan acciones de salida específicas.

Un analizador con desplazamiento y reducción escanea y analiza el texto de entrada en una pasada hacia adelante sobre el texto, sin retroceder. 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 esta pasada, el analizador ha acumulado una lista de subárboles o frases del texto de entrada que ya se han analizado. Esos subárboles aún no están unidos porque el analizador aún no ha llegado al extremo correcto del patrón de sintaxis que los combinará.

Considere la cadena A = B + C * 2.

En el paso 7 del ejemplo, solo se ha analizado "A = B +". Solo existe la esquina inferior izquierda sombreada del árbol de análisis. Ninguno de los nodos del árbol de análisis numerados del 8 al 7 existe todavía. Los nodos 1, 2, 6 y 7 son las raíces de los subárboles aislados que cubren todos los elementos del 1 al 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 cambio-reducción funciona realizando una combinación de pasos de cambio y pasos de reducción, de ahí el nombre.

• Un paso de desplazamiento avanza un símbolo en el flujo de entrada. Ese símbolo desplazado se convierte en un nuevo árbol de análisis de un solo nodo.
• Un paso de reducción aplica una regla gramatical completada a algunos de los árboles de análisis recientes, uniéndolos como un solo árbol con un nuevo símbolo raíz.

El analizador continúa con estos pasos hasta que se ha consumido toda la entrada y todos los árboles de análisis se han 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 búsqueda anticipada actual y el texto restante sin analizar. La siguiente acción del analizador se determina mediante el símbolo o símbolos de la pila situados más a la derecha y el símbolo de búsqueda anticipada. La acción se lee desde una tabla que contiene todas las combinaciones sintácticamente válidas de símbolos de pila y de búsqueda anticipada.

Véase ^[2] para un ejemplo más sencillo.

Una gramática es el conjunto de patrones o reglas de sintaxis para el lenguaje de entrada. No cubre todas las reglas del lenguaje, como el tamaño de los números o el uso coherente de nombres y sus definiciones en el contexto de todo el programa. Los analizadores con función shift-reduce utilizan una gramática independiente del 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 coincidir A = B + C*2podría ser:

Asignar ← id = Sumas

Sumas ← Sumas + Productos

Sumas ← Productos

Productos ← Productos * Valor

Productos ← Valor

Valor ← int

Valor ← id

Los símbolos terminales de la gramática son los símbolos de múltiples caracteres o "tokens" que un escáner léxico encuentra en el flujo de entrada . 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 le importan los espacios en blanco o los saltos de línea. La gramática usa estos símbolos terminales pero no los define. Siempre están en el extremo inferior del árbol de análisis.

Los términos en mayúsculas como Sumas son símbolos no terminales . Son nombres de conceptos o patrones en el lenguaje. Se definen 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 aplique alguna regla gramatical. Algunos no terminales se definen con dos o más reglas; estos son patrones alternativos. Las reglas pueden hacer referencia a sí mismas. Esta gramática utiliza reglas recursivas para manejar operadores matemáticos repetidos. Las gramáticas para lenguajes completos utilizan reglas recursivas para manejar listas, expresiones entre paréntesis y declaraciones anidadas.

Cualquier lenguaje de programación puede describirse mediante varias gramáticas diferentes. La gramática de un analizador sintáctico de desplazamiento-reducción debe ser inequívoca en sí misma o debe estar complementada con reglas de precedencia que permitan desempatar. 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 sintáctico basado en tablas tiene todo su conocimiento sobre la gramática codificado en datos inmutables llamados tablas de analizador sintáctico. El código de programa del analizador sintáctico es un bucle genérico simple que se aplica sin cambios a muchas gramáticas e idiomas. Las tablas se pueden elaborar 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 sintácticos como Bison . ^[3] Las tablas de analizador sintáctico suelen ser mucho más grandes que la gramática. En otros analizadores sintácticos que no están basados ​​en tablas, como el descenso recursivo , cada construcción del lenguaje se analiza mediante una subrutina diferente, especializada en la sintaxis de esa construcción.

El analizador con desplazamiento y reducción es eficiente porque no requiere retroceder. Su tiempo total de ejecución se escala 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 se equivocan. ^{[ cita requerida ]}

Para evitar adivinar, el analizador con desplazamiento y reducción a menudo mira hacia delante (a la derecha en textos de izquierda a derecha) al siguiente símbolo escaneado antes de decidir qué hacer con los símbolos escaneados anteriormente. El analizador léxico trabaja un símbolo por delante del resto del analizador. El símbolo de búsqueda anticipada también se denomina "contexto de la derecha" para cada decisión de análisis. (En raras ocasiones, se pueden utilizar dos o más símbolos de búsqueda anticipada, aunque la mayoría de las gramáticas prácticas se pueden diseñar para utilizar un símbolo de búsqueda anticipada).

Un analizador con desplazamiento-reducción espera hasta que haya escaneado y analizado todas las partes de algún constructo antes de decidir cuál es el constructo combinado. 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 búsqueda anticipada, 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 cosas que aparecen mucho más tarde a la derecha.

Las reducciones reorganizan los elementos analizados más recientemente, es decir, aquellos que se encuentran inmediatamente a la izquierda del símbolo de búsqueda anticipada. De modo que la lista de elementos ya analizados 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 solo sobre los fragmentos de análisis más nuevos y más a la derecha. (Esta pila de análisis acumulativa es muy diferente a la pila de análisis predictiva que crece hacia la izquierda que utilizan los analizadores descendentes ).

Cuando una regla gramatical como

Productos ← Productos * Valor

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 manejador . El paso de reducción reemplaza el manejador "Productos * Valor" por el no terminal del lado izquierdo, en este caso un Productos más grande. Si el analizador construye árboles de análisis completos, entonces los tres árboles para Productos internos, * y Valor se combinan por una nueva raíz de árbol para los Productos más grandes. De lo contrario, los detalles semánticos de los Productos internos y Valor se envían a algún paso posterior del compilador, o se combinan y se 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 encuentre allí nuevos ejemplos de reglas gramaticales completados. 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 pila de análisis superior y símbolo de búsqueda anticipada. Esa siguiente acción debe ser única: desplazamiento o reducción, pero no ambas. (Esto implica algunas limitaciones adicionales en la gramática, más allá de ser inequívoca). Los detalles de la tabla varían en gran medida entre los diferentes tipos de analizadores con desplazamiento y reducción.

En los analizadores de precedencia , el extremo derecho de los manejadores 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 búsqueda anticipada. En el ejemplo anterior, int e id pertenecen a niveles gramaticales internos en comparación con el delimitador de sentencia ; . Por lo tanto, se considera que tanto int como id tienen mayor precedencia que ; y se deben reducir a otra cosa siempre que estén seguidos de ; . Existen diferentes variedades de analizadores de precedencia, cada uno con diferentes formas de encontrar el extremo izquierdo del manejador y elegir la regla correcta a aplicar:

• Analizador de precedencia de operadores , un método numérico muy simple que funciona para expresiones pero no para la sintaxis general del programa.
• Analizador de precedencia simple , utiliza una gran tabla MxN para encontrar los extremos derecho e izquierdo. Se utiliza en PL360 . ^[5] No maneja lenguajes de programación comunes.
• Analizador de precedencia débil, utiliza la tabla de precedencia solo para encontrar los extremos derechos de los identificadores. Maneja más gramáticas que la precedencia simple. ^[6]
• Analizador de precedencia extendida.

• Analizador de precedencia de estrategia mixta, utilizado por la versión original de XPL . Amplía los "dobles", inherentes a cualquier reconocedor de precedencia, para incluir "triples". Menos potente que SLR. Generalmente tiene tablas muy grandes incluso para lenguajes relativamente pequeños como el propio XPL debido a la gran cantidad de "triples" que se requieren para reconocer gramáticas fuera de los límites impuestos por los métodos de precedencia. ^[7]

Los analizadores de precedencia tienen limitaciones en cuanto a las gramáticas que pueden manejar. Ignoran la mayor parte de la pila de análisis al tomar decisiones. Solo consideran los nombres de los símbolos más importantes, no el contexto completo de dónde aparecen esos símbolos en la gramática. 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 por desplazamiento y reducción, que maneja 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 las acciones de cambio. Esta pila es posteriormente extraída (hacia arriba) por las acciones de reducción (y que simultáneamente apilan un nuevo estado). 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 LR canónico . Los analizadores Look-Ahead LR y Simple LR implementan variantes simplificadas de este último que han reducido significativamente los requisitos de memoria. ^{[9] [10]} Investigaciones recientes han identificado métodos por los cuales los analizadores LR canónicos pueden implementarse con requisitos de tabla drásticamente reducidos en comparación con el algoritmo de construcció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 suelen implementarse de forma que una REDUCCIÓN dé como resultado una LLAMADA a una subrutina cerrada que es externa a la máquina de estados y que realiza una función que está 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 estados invariante y una parte de semántica variante. Esta distinción fundamental fomenta el desarrollo de analizadores de alta calidad que son excepcionalmente confiables.

Dado un estado de pila específico y un símbolo de anticipación, existen exactamente cuatro acciones posibles: ERROR, SHIFT, REDUCE y STOP (en adelante 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 terminal) y el estado de pila actual a la izquierda del punto (y que generalmente corresponde a un símbolo no terminal).

Por razones prácticas, incluido un mayor rendimiento, las tablas suelen ampliarse con una matriz auxiliar bastante 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:

00 b representa ERROR

01 b representa SHIFT

10 b representa REDUCIR

11 b representa STOP

(STOP es un caso especial de SHIFT). La matriz completa generalmente incluye principalmente configuraciones ERROR, una cantidad definida por la gramática de configuraciones SHIFT y REDUCE y una configuración STOP.

En los sistemas de programación que admiten la especificación de valores en sistema numérico cuaternario (base 4, dos bits por dígito cuaternario), como XPL, estos se codifican, por ejemplo:

"(2)… 0 …" representa ERROR

"(2)… 1 …" representa SHIFT

"(2)… 2 …" representa REDUCIR

"(2)… 3 …" representa STOP

Las tablas SHIFT y REDUCE se implementan por separado de la matriz. La matriz auxiliar se "sonda" sólo para el estado actual y el símbolo de búsqueda anticipada. La matriz (auxiliar) está "completa", mientras que las tablas (shift y reduce) pueden ser realmente "dispersas", y se pueden lograr eficiencias significativas mediante la "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 de terminal de búsqueda anticipada están dentro de la gramática del sujeto, y representa el final del programa:

⊥ <programa> • ⊥

siendo imposible DESPLAZARSE más allá del ⊥ final para alcanzar, conceptualmente

⊥ <programa> ⊥ •

ERROR, entonces, representa una configuración donde el estado en la parte superior de la pila y el símbolo terminal de búsqueda anticipada no están dentro de la gramática en cuestión. Esto presenta una oportunidad para invocar un procedimiento de recuperación de errores, tal vez, en su forma más simple, para descartar el símbolo terminal de búsqueda anticipada y leer el siguiente símbolo terminal, pero son posibles muchas otras acciones programadas, incluida la poda de la pila o descartar el símbolo terminal de búsqueda anticipada y podar la pila (y en un caso patológico, generalmente es posible obtener

⊥ <programa> • ⊥

donde <programa> consiste únicamente en una "declaración nula" ).

En la mayoría de los casos, la pila se precarga deliberadamente, es decir, se inicializa, con

⊥ • <programa> ⊥

donde se supone que el ⊥ inicial ya ha sido reconocido. Esto, entonces, representa el comienzo del programa y, por lo tanto, evita tener una configuración START separada, que es, conceptualmente

• ⊥ <programa> ⊥

⊥ es un símbolo pseudo-terminal especial agregado mecánicamente a la gramática, así como <program> es un símbolo pseudo-no terminal especial agregado mecánicamente a la gramática (si el programador no incluyó explícitamente <program> en la gramática, entonces <program> se agregaría automáticamente a la gramática en nombre del programador).

Claramente, un analizador de este tipo tiene exactamente 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.