En informática , un analizador LR o SLR simple 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 ascendente correcto en un único 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 idioma.
SLR y los métodos más generales del analizador LALR y del analizador Canonical LR tienen métodos idénticos y tablas similares en el momento del análisis; solo difieren en los algoritmos de análisis de gramática matemática utilizados por la herramienta generadora de analizadores. Los generadores SLR y LALR crean tablas de idéntico 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 informáticos no se ajustan fácilmente a las restricciones de SLR, tal como están. Transformar la gramática natural del lenguaje en forma de gramática SLR requiere más compromisos y hackeos gramaticales. Por eso 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 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 . [ cita necesaria ] Las tablas creadas para gramáticas reales mediante métodos LR completos eran imprácticamente grandes, más grandes que la mayoría de las memorias de computadora de esa década, con 100 veces o más estados del analizador que los métodos SLR y LALR. [ cita necesaria ] .
Para comprender las diferencias entre SLR y LALR, es importante comprender sus muchas similitudes y cómo ambos toman decisiones para reducir turnos. (Consulte el artículo Analizador LR ahora para conocer esos antecedentes, hasta la sección sobre conjuntos de anticipación de reducciones ).
La única diferencia entre SLR y LALR es cómo sus generadores calculan los conjuntos de símbolos de entrada anticipados que deberían aparecer a continuación, siempre que se encuentre y 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 se utiliza algún símbolo no terminal S en varios lugares de la gramática, SLR trata esos lugares de la misma manera en lugar de manejarlos individualmente. El generador SLR calcula el conjunto de todos los Follow(S)símbolos terminales que pueden seguir inmediatamente a alguna aparición de S. En la tabla de análisis, cada reducción a S utiliza Follow(S) como su conjunto de anticipación LR(1). Estos conjuntos de seguimiento también los utilizan los generadores para analizadores de arriba hacia abajo de LL. Una gramática que no tiene conflictos de desplazamiento/reducción o reducción/reducción cuando se utilizan conjuntos de seguimiento se denomina gramática SLR .
Los generadores LALR calculan conjuntos de anticipación mediante un método más preciso basado en la exploración del gráfico de los 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 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 tiene conflictos de tabla cuando se utilizan conjuntos de seguimiento SLR, pero no tiene conflictos cuando se utilizan 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:
La construcción de la tabla de acciones y de ir a como se hace para los analizadores LR(0) daría los siguientes conjuntos de elementos y tablas:
Las tablas de acción y de ir a:
Como se puede observar, existe un conflicto de desplazamiento-reducción para el estado 1 y el terminal '1'. Esto ocurre porque, cuando se crea la tabla de acciones para un analizador LR(0), las acciones de reducción se insertan por fila. Sin embargo, al utilizar 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 es necesario agregar una reducción a una columna de acción 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 ser agregada (reducir acción, acción) { númeroRegla = reducirAcción.valor; símboloRegla = reglas[NúmeroRegla].ladoManoIzquierdo; retorno (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 cierto, 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 libre de conflictos: