Analizador sintáctico de desplazamiento-reducción

Un analizador sintáctico de desplazamiento-reducción es una clase de métodos de análisis sintáctico ascendentes eficientes, 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 utilizados para analizar lenguajes de programación , el análisis LR y sus variantes, son métodos de desplazamiento-reducción. ^{[ 1 ]} Los analizadores sintácticos de precedencia utilizados antes de la invención del análisis LR también son métodos de desplazamiento-reducción. Todos los analizadores sintácticos de desplazamiento-reducción tienen efectos externos similares, en el orden incremental en el que construyen un árbol de análisis sintáctico o llaman a acciones de salida específicas.

Un analizador sintáctico de desplazamiento-reducción escanea y analiza el texto de entrada en una sola pasada hacia adelante, 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 han sido analizadas. Estos subárboles aún no se han unido porque el analizador aún no ha llegado al extremo correcto del patrón sintáctico que los combinará.

Consideremos 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 en adelante existe todavía. Los nodos 1, 2, 6 y 7 son las raíces de 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 porción restante sin analizar del flujo de entrada es "C * 2".

Un analizador sintáctico de desplazamiento-reducción funciona realizando una combinación de pasos de desplazamiento y pasos de reducción, de ahí su 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 sintáctico de un solo nodo.
• Un paso de Reducción aplica una regla gramatical completa a algunos de los árboles de análisis sintáctico recientes, uniéndolos en un solo árbol con un nuevo símbolo raíz.

El analizador continúa con estos pasos hasta que se haya procesado toda la entrada y todos los árboles de análisis se hayan reducido a un único árbol que represente una entrada válida completa.

Una gramática es el conjunto de patrones o reglas sintácticas del lenguaje de entrada. No abarca 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 del programa completo. Los analizadores sintácticos de desplazamiento-reducción 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 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 varios caracteres o «tokens» que encuentra un analizador léxico en el flujo de entrada . En este caso, incluyen = + * e int para cualquier constante entera, e id para cualquier nombre de identificador. A la gramática no le importan los valores de int ni 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 se encuentran en la parte inferior del árbol de análisis sintáctico.

Los términos en mayúsculas, como «Sumas», son símbolos no terminales . Estos son nombres para conceptos o patrones del lenguaje. Se definen en la gramática y nunca aparecen directamente en el flujo de entrada. Siempre se encuentran por encima de la raíz del árbol de análisis sintáctico. Solo aparecen como resultado de la aplicación de alguna regla gramatical por parte del analizador sintáctico. 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 sentencias 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 o complementarse con reglas de precedencia para desempatar. Esto significa que solo existe una forma correcta de aplicar la gramática a un ejemplo válido del lenguaje, lo que da como resultado un árbol de análisis sintáctico ú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 análisis. El código del programa del analizador es un bucle genérico simple que se aplica sin cambios a muchas gramáticas y lenguajes. Las tablas pueden elaborarse manualmente 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 análisis sintáctico suelen ser mucho más grandes que la gramática. En otros analizadores sintácticos 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 en particular.

El analizador sintáctico de desplazamiento-reducción es eficiente porque no requiere retroceso. 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 sintáctico que utilizan retroceso pueden tardar un tiempo exponencial cuando cometen errores de predicción.

Para evitar adivinar, el analizador sintáctico de desplazamiento-reducción suele mirar hacia adelante (a la derecha en textos de izquierda a derecha) al siguiente símbolo analizado antes de decidir qué hacer con los símbolos analizados previamente. El analizador 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. (En raras ocasiones, se pueden usar dos o más símbolos de anticipación, aunque la mayoría de las gramáticas prácticas se pueden diseñar para usar uno solo).

Un analizador sintáctico de desplazamiento-reducción espera a haber escaneado y analizado todas las partes de una construcción antes de determinar cuál es la construcción combinada. 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 encuentra + 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 elementos que aparecen mucho más adelante 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 anticipación. Así, la lista de elementos ya analizados actúa como una pila . Esta pila crece hacia la derecha. La base o parte inferior de la pila se encuentra a la izquierda y contiene el fragmento de análisis más antiguo y situado más a la izquierda. Cada paso de reducción actúa únicamente sobre los fragmentos de análisis más recientes y situados más a la derecha. (Esta pila de análisis acumulativa es muy diferente de la pila de análisis predictiva que crece hacia la izquierda, utilizada por los analizadores descendentes ).

Cuando una regla gramatical como

Productos ← Productos * Valor

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 construye árboles de análisis completos, 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 internos y Valor se envían a una pasada posterior del compilador , o se combinan y se guardan en el nuevo símbolo Productos. ^{[ 4 ]}

El analizador sintáctico sigue aplicando reducciones a la parte superior de la pila de análisis mientras siga encontrando nuevos ejemplos de reglas gramaticales completas. Cuando ya no se pueden aplicar más reglas, el analizador desplaza el símbolo de anticipación a la pila de análisis, busca un nuevo símbolo de anticipación e intenta de nuevo.

Las tablas del analizador sintáctico indican qué hacer a continuación para cada combinación válida de símbolos de la pila de análisis sintáctico superior y símbolo de anticipación. Esta 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 la falta de ambigüedad). Los detalles de la tabla varían considerablemente entre los diferentes tipos de analizadores sintácticos de desplazamiento y reducción.

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 sentencia ; . Por lo tanto, tanto int como id se consideran de mayor precedencia que ; y deben reducirse a otra cosa cuando van seguidos de ; . Existen diferentes variedades de analizadores de precedencia, cada una con distintas maneras de encontrar el extremo izquierdo del identificador y elegir la regla correcta que se debe aplicar:

• Analizador de precedencia de operadores , un método numérico muy simple que funciona para expresiones pero no para la sintaxis general de los programas.
• Analizador de precedencia simple , utiliza una tabla MxN grande para encontrar los extremos derecho e izquierdo. Se utiliza en PL360 . ^{[ 5 ]} No admite lenguajes de programación comunes.
• Analizador sintáctico 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 extendido.

• Analizador de precedencia de estrategia mixta, utilizado por la versión original de XPL . Extiende 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 sintácticos basados ​​en precedencia tienen limitaciones en cuanto a las gramáticas que pueden procesar. Ignoran la mayor parte de la pila de análisis al tomar decisiones. Solo consideran los nombres de los símbolos superiores, no el contexto completo de su ubicación en la gramática. La precedencia exige que las combinaciones de símbolos similares se analicen y utilicen de forma idéntica en toda la gramática, independientemente del contexto.

Los analizadores LR son una forma más flexible de análisis de desplazamiento-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 desplazamiento o reducción. Estos emplean una pila donde el estado actual se apila (hacia abajo) mediante acciones de desplazamiento. Esta pila se despliega (hacia arriba) posteriormente mediante acciones de reducción (y que simultáneamente apilan un nuevo estado). Este mecanismo permite que el analizador LR maneje todas las gramáticas deterministas libres de contexto, un superconjunto de las gramáticas de precedencia. El analizador LR está completamente implementado por el analizador LR canónico . Los analizadores LR de anticipación y LR simple implementan variantes simplificadas del mismo que tienen requisitos de memoria significativamente reducidos. ^{[ 9 ] [ 10 ]} Investigaciones recientes han identificado métodos mediante 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; solo difieren las tablas, que casi siempre se generan mecánicamente. Además, estas tablas suelen implementarse de forma que una operación REDUCE dé como resultado una llamada a una subrutina cerrada externa a la máquina de estados, 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 estados invariante y una parte de semántica variable. Esta distinción fundamental fomenta el desarrollo de analizadores de alta calidad y excepcional fiabilidad.

Dado un estado de pila y un símbolo de anticipación específicos, existen cuatro acciones posibles: ERROR, DESPLAZAMIENTO, REDUCCIÓN y DETENCIÓN (en adelante, denominadas configuraciones). La presencia de un punto, •, en una configuración representa la posición actual de anticipación, con el símbolo de anticipación a la derecha del punto (que siempre corresponde a un símbolo terminal) y el estado actual de la pila a la izquierda del punto (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 algo grande de símbolos de dos bits, obviamente comprimida en cuatro símbolos de dos bits, un byte, para un acceso eficiente en máquinas orientadas a bytes, a menudo codificada como:

00 b representa ERROR

01 b representa DESPLAZAMIENTO

10 b representa REDUCIR

11 b representa STOP

(STOP es un caso especial de SHIFT). El conjunto completo generalmente incluye principalmente configuraciones ERROR, un número definido 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 el sistema numérico cuaternario (base 4, dos bits por dígito cuaternario), como XPL, estos se codifican, por ejemplo, de la siguiente manera:

"(2)… 0 …" representa ERROR

"(2)… 1 …" representa DESPLAZAMIENTO

"(2)… 2 …" representa REDUCIR

"(2)… 3 …" representa STOP

Las tablas SHIFT y REDUCE se implementan por separado del array. El array auxiliar se consulta únicamente para obtener el estado actual y el símbolo de anticipación. El array (auxiliar) está "lleno", mientras que las tablas (SHIFT y REDUCE) pueden estar muy "dispersas", y se pueden lograr eficiencias significativas mediante la "descomposición" óptima de dichas tablas (ERROR y STOP no requieren 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 terminal de anticipación se encuentran dentro de la gramática del sujeto, y representa el final del programa:

⊥ <programa> • ⊥

siendo imposible DESPLAZAR 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 anticipación no están dentro de la gramática del sujeto. Esto presenta una oportunidad para invocar un procedimiento de recuperación de errores, quizás, en su forma más simple, para descartar el símbolo terminal de anticipación y leer el siguiente símbolo terminal, pero son posibles muchas otras acciones programadas, incluyendo podar la pila, o descartar el símbolo terminal de anticipación y podar la pila (y en un caso patológico, generalmente es posible obtener

⊥ <programa> • ⊥

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

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

⊥ • <programa> ⊥

por lo que 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 de INICIO separada, que es, conceptualmente

• ⊥ <programa> ⊥

⊥ es un símbolo pseudoterminal especial que se agrega mecánicamente a la gramática, al igual que <program> es un símbolo pseudono terminal especial que se agrega mecánicamente a la gramática (si el programador no incluyera explícitamente <program> en la gramática, entonces <program> se agregaría automáticamente a la gramática en nombre del programador).

Evidentemente, dicho analizador tiene precisamente una configuración de INICIO (implícita) y una configuración de PARADA (explícita), pero puede tener, y normalmente tiene, cientos de configuraciones de DESPLAZAMIENTO y REDUCCIÓN, y quizás miles de configuraciones de ERROR.