Analizador CLR (con ejemplos)

Analizadores LR:
es una técnica eficiente de análisis de sintaxis de abajo hacia arriba que se puede utilizar para analizar grandes clases de gramática libre de contexto y se denomina análisis LR (k). 
L representa el escaneo de izquierda a derecha
R representa la derivación más a la derecha en sentido inverso
k 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áticos.
• 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 CLR:
el analizador CLR significa analizador LR canónico. Es un analizador LR más potente. Hace uso de símbolos de anticipación. Este método utiliza un gran conjunto de elementos denominados elementos LR(1). La principal diferencia entre los elementos LR(0) y LR(1) es que, en los elementos LR(1), es posible llevar más información en un estado, lo que descartará estados de reducción inútiles. Esta información adicional se incorpora al estado mediante el símbolo de anticipación. La sintaxis general se convierte en [A->∝.B, a]
donde A->∝.B es la producción y a es un terminal o marcador del extremo derecho $
LR(1) elementos=LR(0) elementos + mirar hacia adelante

¿Cómo agregar lookahead con la producción?
CASO 1 –

A->∝.BC, a 

Supongamos que esta es la producción número 0. Ahora, desde ‘ . ‘ precede a B, así que también tenemos que escribir las producciones de B.

B->.D [1st production]

Supongamos que esta es la producción de B. La mirada hacia el futuro de esta producción se da cuando miramos producciones anteriores, es decir, la producción 0. Lo que sea que esté después de B, encontramos PRIMERO (de ese valor), que es la anticipación de la primera producción. Entonces, aquí en la producción 0, después de B, C está allí. suponga PRIMERO (C) = d, luego la primera producción se convierte en

B->.D, d

CASO 2 –
Ahora bien, si la 0ª producción fuera así,

A->∝.B, a 

Aquí, podemos ver que no hay nada después de B. Por lo tanto, la anticipación de la producción 0 será la anticipación de la producción 1. es decir-

B->.D, a

CASO 3 –
Suponga una producción A->a|b

A->a,$ [0th production]
A->b,$ [1st production]

Aquí, la primera producción es parte de la producción anterior, por lo que la anticipación será la misma que la de su producción anterior.
Estas son las 2 reglas de mirar hacia adelante.

Pasos para construir la tabla de análisis de CLR:

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

EJEMPLO 
Construya una tabla de análisis CLR para la gramática libre de contexto dada

S-->AA    
A-->aA|b

Solución :
PASO 1 – Encuentra gramática aumentada

La gramática aumentada de la gramática dada es: –

S'-->.S ,$   [0th production]    
S-->.AA ,$ [1st production]    
A-->.aA ,a|b [2nd production]      
A-->.b ,a|b [3rd production]

Apliquemos la regla de anticipación a las producciones anteriores.

• La previsión inicial siempre es $
• Ahora, la primera producción nació debido a ‘. ‘ Antes de ‘S’ en la 0.ª producción. No hay nada después de ‘S’, por lo que la anticipación de la 0.ª producción será la anticipación de la 1.ª producción. es decir: S–>.AA ,$
• Ahora, la segunda producción nació debido a ‘. ‘ Antes de ‘A’ en la primera producción.Después de ‘A’, está ‘A’. Entonces, PRIMERO(A) es a,b
  Por lo tanto, la mirada hacia el futuro para la segunda producción se convierte en a|b.
• Ahora, la 3.ª producción es parte de la 2.ª producción. Por lo tanto, la mirada hacia el futuro será la misma.

PASO 2: busque la colección de elementos LR(1)
A continuación se muestra la figura que muestra la colección de elementos LR(1). 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-

1. Si algún no terminal tiene ‘ . ‘ precediéndolo, tenemos que escribir toda su producción y agregar ‘ . ‘ anterior a cada una de sus producciones.
2. de cada estado al siguiente estado, el ‘ . ‘ cambia a un lugar a la derecha.
3. Todas las reglas de anticipación se aplican aquí.

• 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 de aceptación. S es visto por el compilador. Dado que I1 es parte de la producción 0, la anticipación es la misma, es decir, $
• Io va a I2 cuando ‘ . ‘ de la 1ª producción se desplaza hacia la derecha (S->AA) . A es visto por el compilador. Dado que I2 es parte de la primera producción, la anticipación es la misma, es decir, $.
• I0 va a I3 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador. Dado que I3 es parte de la segunda producción, la previsión es la misma, es decir, a|b.
• I0 va a I4 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . b es visto por el compilador. Dado que I4 es parte de la tercera producción, la anticipación es la misma, es decir, a | b.
• I2 va a I5 cuando ‘ . ‘ de la 1ª producción se desplaza hacia la derecha (S->AA.) . A es visto por el compilador. Dado que I5 es parte de la primera producción, la anticipación es la misma, es decir, $.
• I2 va a I6 cuando ‘ . ‘ de 2ª producción se desplaza hacia la derecha (A->aA) . A es visto por el compilador. Dado que I6 es parte de la segunda producción, la anticipación es la misma, es decir, $.
• I2 va a I7 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . A es visto por el compilador. Dado que I6 es parte de la tercera producción, la anticipación es la misma, es decir, $.
• I3 va a I3 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador. Dado que I3 es parte de la segunda producción, la previsión es la misma, es decir, a|b.
• I3 va a I8 cuando ‘ . ‘ de 2ª producción está desplazada hacia la derecha (A->aA.) . A es visto por el compilador. Dado que I8 es parte de la segunda producción, la anticipación es la misma, es decir, a|b.
• I6 va a I9 cuando ‘ . ‘ de 2ª producción está desplazada hacia la derecha (A->aA.) . A es visto por el compilador. Dado que I9 es parte de la segunda producción, la anticipación es la misma, es decir, $.
• I6 va a I6 cuando ‘ . ‘ de la 2ª producción se desplaza hacia la derecha (A->aA) . a es visto por el compilador. Dado que I6 es parte de la segunda producción, la anticipación es la misma, es decir, $.
• I6 va a I7 cuando ‘ . ‘ de la 3ª producción se desplaza hacia la derecha (A->b.) . b es visto por el compilador. Dado que I6 es parte de la tercera producción, la anticipación es la misma, es decir, $.

PASO 3  : definición de 2 funciones: ir a [lista de terminales] y acción [lista de no terminales] en la tabla de análisis. A continuación se muestra la tabla de análisis de CLR

• $es por defecto un no terminal que toma el estado de aceptación.
• 0,1,2,3,4,5,6,7,8,9 denota I0,I1,I2,I3,I4,I5,I6,I7,I8,I9
• I0 da A en I2, por lo que se agrega 2 a la columna A y 0 a la fila.
• I0 da S en I1, por lo que se agrega 1 a la columna S y la primera fila.
• de manera similar, 5 se escribe en la columna A y la segunda fila, 8 se escribe en la columna A y la tercera fila, 9 se escribe en la columna A y la sexta fila.
• I0 da a en I3, por lo que S3 (desplazamiento 3) se agrega a una columna y 0 a una 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, se agrega S6 (cambio 6) en la columna ‘a’ y la fila 2,6, S7 (cambio 7) se agrega en la columna b y la fila 2,6, S3 (cambio 3) se agrega en la columna ‘a’ y 3 fila, S4 (cambio 4) se agrega en la columna b y la fila 3.
• I4 se reduce como ‘. ‘ está al final. I4 es la 3ra producción de gramática. Así que escribe r3(reduce 3) en las columnas anticipadas. La anticipación de I4 son a y b, así que escribe R3 en las columnas a y b.
• I5 se reduce como ‘ . ‘ está al final. I5 es la 1ra producción de gramática. Así que escribe r1(reduce 1) en las columnas anticipadas. La anticipación de I5 es $, así que escriba R1 en la columna $.
• De manera similar, escriba R2 en la columna a, b y la octava fila, escriba R2 en la columna $y la novena fila.