En informática , un analizador sintáctico LR simple o SLR es un tipo de analizador sintáctico LR con tablas de análisis pequeñas y un algoritmo generador de analizador sintáctico relativamente simple. Al igual que con otros tipos de analizadores sintácticos LR(1), un analizador sintáctico SLR es bastante eficiente para encontrar el único análisis sintáctico correcto de abajo a arriba en un solo escaneo de izquierda a derecha sobre el flujo de entrada, sin conjeturas ni retrocesos. El analizador sintáctico se genera mecánicamente a partir de una gramática formal para el lenguaje.
El analizador sintáctico SLR y los métodos más generales LALR y Canonical LR tienen métodos idénticos y tablas similares en el momento del análisis; difieren solo en los algoritmos de análisis gramatical matemático utilizados por la herramienta generadora de analizadores sintácticos. 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 de computación no se ajustan fácilmente a las restricciones de SLR, tal como están. Convertir la gramática natural del lenguaje en la forma de gramática SLR requiere más concesiones y trucos 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 complicadas. Los métodos SLR siguen siendo un paso de aprendizaje útil en las clases universitarias sobre teoría de compiladores.
Tanto SLR como LALR fueron desarrollados por Frank DeRemer como los primeros usos prácticos de la teoría del analizador sintáctico LR de Donald Knuth . [ cita requerida ] 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 requerida ] .
Para entender las diferencias entre SLR y LALR, es importante entender sus muchas similitudes y cómo ambos toman decisiones de desplazamiento-reducción. (Consulte el artículo Analizador de LR para obtener más información sobre este tema, hasta la sección sobre los conjuntos de anticipación de las 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 completada.
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 de los analizadores individuales. 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 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 utiliza Follow(S) como su conjunto de anticipación LR(1). Dichos conjuntos de seguimiento también son utilizados por los generadores para analizadores de arriba hacia abajo 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 los 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 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 los conjuntos aproximados calculados por los generadores SLR (y, por lo tanto, mejores que ellos). Si una gramática tiene conflictos de tabla cuando utiliza conjuntos de seguimiento SLR, pero no tiene conflictos cuando utiliza 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 acción y la tabla goto como se hace para los analizadores LR(0) daría como resultado los siguientes conjuntos de elementos y tablas:
Las tablas de acción y de acceso:
Como se puede observar, existe un conflicto de desplazamiento-reducción 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 por fila. Sin embargo, al utilizar un conjunto de seguimiento, las acciones de reducción se pueden agregar con mayor granularidad. El conjunto de seguimiento para esta gramática:
Solo es necesario 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 mustBeAdded(reduceAction, acción) { ruleNumber = reduceAction.value; ruleSymbol = reglas[ruleNumber].leftHandSide; 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 siguiente de E. Por el contrario, mustBeAdded(r2, "$")es verdadero, porque "$" está en el conjunto siguiente 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: