Analizador LR simple

En informática , un analizador LR simple (o SLR) es un tipo de analizador LR con tablas de análisis pequeñas y un algoritmo generador de analizadores relativamente sencillo. Al igual que otros tipos de analizadores LR(1), un analizador SLR es muy eficiente para encontrar el análisis correcto de abajo hacia arriba en un solo escaneo de izquierda a derecha sobre el flujo de entrada, sin conjeturas ni retrocesos. El analizador se genera mecánicamente a partir de una gramática formal del lenguaje.

SLR y los métodos más generales LALR parser y Canonical LR parser tienen métodos idénticos y tablas similares en tiempo de análisis; solo difieren en los algoritmos de análisis de gramática matemática que utiliza la herramienta generadora de analizadores. Los generadores SLR y LALR crean tablas del mismo tamaño y estados de analizador idénticos. Los generadores SLR aceptan menos gramáticas que los generadores LALR como yacc y Bison . Muchos lenguajes de programación no se ajustan fácilmente a las restricciones de SLR tal cual. Adaptar la gramática natural del lenguaje a la forma de gramática SLR requiere más concesiones y modificaciones gramaticales. Por lo tanto, los generadores LALR se han vuelto mucho más utilizados que los generadores SLR, a pesar de ser herramientas algo más complejas. Los métodos SLR siguen siendo un paso útil en el aprendizaje de las clases universitarias sobre teoría de compiladores.

SLR y LALR fueron desarrollados por Frank DeRemer como los primeros usos prácticos de la teoría del analizador LR de Donald Knuth . ^{[ 1 ] [ 2 ]} Las tablas creadas para gramáticas reales mediante métodos LR completos eran impracticablemente grandes, mayores que la mayoría de las memorias de las computadoras de esa década, con 100 veces o más estados de analizador que los métodos SLR y LALR. ^{[ 3 ]}

Para comprender las diferencias entre SLR y LALR, es importante entender sus numerosas similitudes y cómo ambos toman decisiones de desplazamiento y reducción. (Para obtener más información, consulte el artículo "LR parser now", hasta la sección sobre conjuntos de anticipación de reducciones ).

La única diferencia entre SLR y LALR radica en cómo sus generadores calculan los conjuntos de símbolos de entrada que deberían aparecer a continuación, siempre que se encuentre y se reduzca alguna regla de producción completa.

Los generadores SLR calculan esa anticipación mediante un método de aproximación sencillo basado directamente en la gramática, ignorando los detalles de los estados y transiciones individuales del analizador. Esto ignora el contexto particular del estado actual del analizador. Si un símbolo no terminal S se usa en varios lugares de la gramática, SLR trata esos lugares de la misma manera en lugar de manejarlos individualmente. El generador SLR calcula Follow(S), el conjunto de todos los símbolos terminales que pueden seguir inmediatamente a alguna ocurrencia de S . En la tabla de análisis, cada reducción a S usa Follow(S) como su conjunto de anticipación LR(1). Estos conjuntos follow también son utilizados por los generadores para analizadores LL descendentes. Una gramática que no tiene conflictos shift/reduce o reduce/reduce cuando usa conjuntos follow se llama gramática SLR .

Los generadores LALR calculan conjuntos de anticipación mediante un método más preciso basado en la exploración del grafo de estados del analizador y sus transiciones. Este método considera el contexto particular del estado actual del analizador y personaliza el manejo de cada ocurrencia gramatical de algún S no terminal. Consulte el artículo "Analizador LALR" para obtener más detalles sobre este cálculo. Los conjuntos de anticipación calculados por los generadores LALR son un subconjunto de (y, por lo tanto, mejores que) los conjuntos aproximados calculados por los generadores SLR. Si una gramática presenta conflictos de tabla al usar conjuntos de seguimiento SLR, pero no presenta conflictos al usar conjuntos de seguimiento LALR, se denomina gramática LALR.

Una gramática que puede ser analizada por un analizador SLR pero no por un analizador LR(0) es la siguiente:

(0) S → E

(1) E → 1 E

(2) E → 1

La construcción de la tabla de acciones y de destino, como se hace para los analizadores LR(0), daría como resultado los siguientes conjuntos de elementos y tablas:

Conjunto de elementos 0

S → • E

+ E → • 1 E

+ E → • 1

Conjunto de artículos 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Conjunto de artículos 2

S → E •

Conjunto de artículos 3

E → 1 E •

Las tablas de acciones y destinos:

Como se puede observar, existe un conflicto de desplazamiento-reducción para el estado 1 y el terminal '1'. Esto ocurre porque, al crear la tabla de acciones para un analizador LR(0), las acciones de reducción se insertan fila por fila. Sin embargo, mediante el uso de un conjunto de seguimiento, las acciones de reducción se pueden agregar con mayor precisión. El conjunto de seguimiento para esta gramática es el siguiente:

Una acción de reducción solo debe agregarse a una columna de acción específica si dicha acción se encuentra en el conjunto de seguimiento asociado a esa reducción. Este algoritmo describe si una acción de reducción debe agregarse a una columna de acción:

función mustBeAdded(reduceAction, acción) { ruleNumber = reduceAction.value; Símbolo de regla = reglas[número de regla].ladoIzquierdo; devolver (acción en followSet(ruleSymbol)) }

Por ejemplo, mustBeAdded(r2, "1")es falso, porque el lado izquierdo de la regla 2 es "E", y 1 no está en el conjunto de seguimiento de E. Por el contrario, mustBeAdded(r2, "$")es verdadero, porque "$" está en el conjunto de seguimiento de E.

Al utilizar mustBeAdded en cada acción de reducción en la tabla de acciones, el resultado es una tabla de acciones libre de conflictos:

• Analizador LR
• Analizador LL
• Analizador LALR
• gramática SLR