Analizador SLR (con ejemplos)

Requisito previo: analizador LR

Analizadores LR:
es una técnica eficiente de análisis de sintaxis de abajo hacia arriba que se puede usar para analizar grandes clases de gramática libre de contexto y se denomina análisis LR (0). 
L representa el escaneo de izquierda a derecha
R representa la derivación más a la derecha en sentido inverso
0 representa el no. de símbolos de entrada de anticipación
 

Ventajas del análisis LR:

• Reconoce prácticamente todas las construcciones del lenguaje de programación para las que se puede escribir CFG.
• Es capaz de detectar errores sintácticos.
• Es un método de análisis eficiente que reduce el desplazamiento sin retroceso.

Tipos de métodos de análisis de LR:

1. cámara réflex
2. CLR
3. LALR

Analizador SLR:
SLR es LR simple. Es la clase más pequeña de gramática que tiene pocos estados. SLR es muy fácil de construir y es similar al análisis de LR. La única diferencia entre el analizador SLR y el analizador LR(0) es que en la tabla de análisis LR(0), existe la posibilidad de un conflicto de ‘desplazamiento reducido’ porque estamos ingresando ‘reducir’ correspondiente a todos los estados terminales. Podemos resolver este problema ingresando ‘reduce’ correspondiente a SEGUIMIENTO de LHS de producción en el estado de terminación. Esto se llama colección de elementos SLR(1)

Pasos para construir la tabla de análisis SLR:

1. Escritura de gramática aumentada
2. LR(0) colección de elementos a encontrar
3. Encuentra SEGUIMIENTO de LHS de producción
4. Definición de 2 funciones: ir a [lista de terminales] y acción [lista de no terminales] en la tabla de análisis

EJEMPLO: construya una tabla de análisis LR para la gramática libre de contexto dada

 S–>AA   
 A–>aA|b

Solución:

PASO 1: encuentre la gramática
aumentada La gramática aumentada de la gramática dada es: –

 S’–>.S [0ª producción]    
 S–>.AA [1ª producción]     
 A–>.aA [2ª producción]      
 A–>.b [3ª producción]

PASO 2: busque la colección de elementos LR(0)
A continuación se muestra la figura que muestra la colección de elementos LR(0). Vamos a entender todo uno por uno.

Los terminales de esta gramática son {a,b}.
Los no terminales de esta gramática son {S,A}

REGLA: 
si algún no terminal tiene ‘ . ‘ precediéndolo, tenemos que escribir toda su producción y agregar ‘ . ‘ anterior a cada una de sus producciones.

REGLA: 
de cada estado al siguiente estado, el ‘ . ‘ cambia a un lugar a la derecha.

• En la figura, I0 consiste en gramática aumentada.
• Io va a I1 cuando ‘ . ‘ de la producción 0 se desplaza hacia la derecha de S(S’->S.). este estado es el estado aceptado. S es visto por el compilador.
• Io va a I2 cuando ‘ . ‘ de la 1ª producción se desplaza hacia la derecha (S->AA) . A es visto por el compilador
• I0 va a I3 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador.
• I0 va a I4 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . b es visto por el compilador.
• I2 va a I5 cuando ‘ . ‘ de la 1ª producción se desplaza hacia la derecha (S->AA.) . A es visto por el compilador
• I2 va a I4 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . b es visto por el compilador.
• I2 va a I3 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador.
• I3 va a I4 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . b es visto por el compilador.
• I3 va a I6 cuando ‘ . ‘ de 2ª producción está desplazada hacia la derecha (A->aA.) . A es visto por el compilador
• I3 va a I3 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador.

PASO 3 – 
Encuentra SEGUIMIENTO de LHS de producción

SEGUIR(S)=$
SEGUIR(A)=a,b,$

Para encontrar SEGUIMIENTO de no terminales, lea el conjunto de seguimiento en el análisis de sintaxis.

PASO 4- 
Definición de 2 funciones: ir a [lista de no terminales] y acción [lista de terminales] en la tabla de análisis. A continuación se muestra la tabla de análisis de SLR.

• $es por defecto un no terminal que toma el estado de aceptación.
• 0,1,2,3,4,5,6 denota I0,I1,I2,I3,I4,I5,I6
• I0 da A en I2, por lo que se agrega 2 a la columna A y 0 filas.
• I0 da S en I1, por lo que se agrega 1 a la columna S y 1 fila.
• de manera similar, 5 se escribe en una columna y 2 filas, 6 se escribe en una columna y 3 filas.
• I0 da un en I3 .así que S3 (cambio 3) se agrega a una columna y 0 fila.
• I0 da b en I4, por lo que S4 (cambio 4) se agrega a la columna b y la fila 0.
• De manera similar, S3 (turno 3) se agrega en una columna y 2,3 filas, S4 (turno 4) se agrega en una columna b y 2,3 filas.
• I4 se reduce al estado como ‘. ‘ está al final. I4 es la 3ra producción de gramática(A–>.b).LHS de esta producción es A. FOLLOW(A)=a,b,$. escriba r3(reducido 3) en las columnas de a,b,$y 4ta fila
• I5 se reduce al estado como ‘. ‘ está al final. I5 es la primera producción de gramática (S–>.AA). LHS de esta producción es S.
  FOLLOW(S)=$. escribe r1(reducido 1) en la columna de $y 5ta fila
• I6 es un estado reducido como ‘. ‘ está al final. I6 es la segunda producción de gramática (A–>.aA). El LHS de esta producción es A.
  FOLLOW(A)=a,b,$. escribe r2(reducido 2) en las columnas de a,b,$y 6ta fila