Analizador LR simple

En informática, un Simple LR o SLR analizador es un tipo de analizador LR con pequeñas tablas de análisis y un algoritmo generador de analizador relativamente simple. Al igual que con otros tipos de analizadores LR(1), un analizador SLR es bastante eficiente para encontrar el único análisis de abajo hacia arriba correcto 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 analizador LALR y analizador LR canónico tienen métodos idénticos y tablas similares en el momento del análisis; difieren solo en los algoritmos de análisis de gramática matemática utilizados por la herramienta generadora del analizador. Los generadores SLR y LALR crean tablas de tamaño idéntico y estados de analizador idénticos. Los generadores SLR aceptan menos gramáticas que los generadores LALR como yacc y Bison. Muchos lenguajes informáticos no se ajustan fácilmente a las restricciones de SLR tal como están. Doblar la gramática natural del idioma en forma de gramática SLR requiere más compromisos y piratería gramatical. 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 complicadas. Los métodos SLR siguen siendo un paso de aprendizaje útil en las clases universitarias sobre la teoría del compilador.

SLR y LALR fueron desarrollados por Frank DeRemer como los primeros usos prácticos de la teoría del analizador LR de Donald Knuth. Las tablas creadas para gramáticas reales por métodos LR completos eran poco prácticas, más grandes que la mayoría de las memorias de computadora de esa década, con 100 veces o más estados de analizador que los métodos SLR y LALR.

Conjuntos anticipados

Para comprender las diferencias entre SLR y LALR, es importante comprender sus muchas similitudes y cómo ambos toman decisiones de reducción de turnos. (Consulte el artículo Analizador de LR ahora para obtener información detallada, hasta la sección sobre conjuntos anticipados de reducciones).

La única diferencia entre SLR y LALR es cómo sus generadores calculan los conjuntos anticipados 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 de SLR calculan esa anticipación mediante un método de aproximación fácil 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 algún 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 de terminal que pueden seguir inmediatamente a alguna aparición de S. En la tabla de análisis, cada reducción a S usa Follow(S) como su conjunto de búsqueda anticipada LR(1). Dichos conjuntos de seguimiento también son utilizados por generadores para analizadores de arriba hacia abajo LL. Una gramática que no tiene conflictos de cambio/reducción o reducción/reducción cuando se usan conjuntos de seguimiento se denomina gramática SLR.

Los generadores LALR calculan conjuntos anticipados mediante un método más preciso basado en la exploración del gráfico de estados del analizador y sus transiciones. Este método considera el contexto particular del estado actual del analizador. Personaliza el manejo de cada aparición gramatical de alguna S no terminal. Consulte el artículo Analizador LALR para obtener más detalles sobre este cálculo. Los conjuntos anticipados 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 tiene conflictos de tabla cuando se usan conjuntos de seguimiento SLR, pero no tiene conflictos cuando se usan conjuntos de seguimiento LALR, se denomina gramática LALR.

Ejemplo

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

Construir la tabla action y goto como se hace para los analizadores LR(0) daría los siguientes conjuntos de elementos y tablas:

Tema 0

S → • E

+ E → • 1 E

+ E → • 1

Tema 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Tema 2

S → E •

Tema 3

E → 1 E •

Las tablas action y goto:

Como se puede observar, existe un conflicto de reducción de desplazamiento para el estado 1 y la terminal '1'. Esto ocurre porque, cuando se crea la tabla de acciones para un analizador LR(0), las acciones de reducción se insertan fila por fila. Sin embargo, al usar un conjunto de seguimiento, se pueden agregar acciones de reducción con una granularidad más fina. El siguiente conjunto para esta gramática:

Solo se debe agregar una reducción a una columna de acción en particular si esa acción está en el conjunto de seguimiento asociado con esa reducción. Este algoritmo describe si se debe agregar una acción de reducción a una columna de acción:

función debe añadirse(reducirAcción, acción) {
ruleNumber = reduceAction.value;
ruleSymbol = rules[ruleNumber].leftHandSide;
retorno (acción en seguimientoSet(ruleSymbol))
}

por ejemplo, mustBeAdded(r2, "1& #34;) 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 usar mustBeAdded en cada acción de reducción en la tabla de acciones, el resultado es una tabla de acciones sin conflictos: