En informática , un analizador sintáctico simple LR o SLR es un tipo de analizador sintáctico LR con pequeñas tablas de análisis sintáctico y un algoritmo generador de analizador sintáctico relativamente simple. Al igual que con otros tipos de analizador 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 para el idioma.
SLR y los métodos más generales El analizador LALR y el analizador 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 del generador del analizador sintáctico. 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 computadora no se ajustan fácilmente a las restricciones de SLR, tal cual. Conversión de la gramática natural del idioma en gramática SLRla forma requiere más compromisos y piratería gramatical. Así que 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.
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 por 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 de analizador que los métodos SLR y LALR. [ cita requerida ] .
Conjuntos de anticipación
Para comprender las diferencias entre SLR y LALR, es importante comprender sus muchas similitudes y cómo ambos toman decisiones de reducción de cambios. (Consulte el artículo Analizador de LR ahora para conocer los 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 se reduzca alguna regla de producción completa .
Los generadores 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 se usa 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 funciona SLR Follow(S)
, el conjunto de todos los símbolos terminales que puede seguir inmediatamente alguna ocurrencia de S . En la tabla de análisis, cada reducción a S usa Seguir (S) como su conjunto de anticipación LR (1). Estos conjuntos de seguimiento también los utilizan los generadores de analizadores sintácticos de arriba hacia abajo LL. Una gramática que no tiene cambios / reducir o reducir / reducir conflictos cuando se usan conjuntos de seguimiento 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 gráfico de los estados del analizador sintáctico y sus transiciones. Este método considera el contexto particular del estado actual del analizador. 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 tiene conflictos de tablas cuando se utilizan conjuntos de seguimiento SLR, pero no tiene conflictos cuando se utilizan 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
La construcción de la tabla action y goto como se hace para los analizadores LR (0) daría los siguientes conjuntos de elementos y tablas:
- Conjunto de elementos 0
- S → • E
- + E → • 1 E
- + E → • 1
- Conjunto de elementos 1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- Conjunto de elementos 2
- S → E •
- Conjunto de elementos 3
- E → 1 E •
Las tablas de acción y goto:
acción | ir | ||
---|---|---|---|
Expresar | 1 | PS | mi |
0 | s1 | 2 | |
1 | s1 / r2 | r2 | 3 |
2 | acc | ||
3 | r1 | r1 |
Como se puede observar, existe un conflicto de reducción-desplazamiento 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 usar un conjunto de seguimiento, se pueden agregar acciones de reducción con mayor granularidad. El siguiente conjunto para esta gramática:
símbolo | S | mi | 1 |
---|---|---|---|
siguiente | PS | PS | 1, $ |
Una reducción solo necesita agregarse a una columna de acción en particular si esa acción está en el siguiente conjunto asociado con esa reducción. Este algoritmo describe si se debe agregar una acción de reducción a una columna de acción:
function mustBeAdded (reduceAction, action) { ruleNumber = reduceAction.value; ruleSymbol = reglas [número de regla] .leftHandSide; return (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 siguiente conjunto de E. Por el contrario, mustBeAdded(r2, "$")
es cierto, porque "$" está en el siguiente conjunto 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:
acción | ir | ||
---|---|---|---|
Expresar | 1 | PS | mi |
0 | s1 | 2 | |
1 | s1 | r2 | 3 |
2 | acc | ||
3 | r1 |