Analizadores SLR, CLR y LALR | conjunto 3 – Part 1

En este artículo, estamos discutiendo el analizador SLR, el analizador CLR y el analizador LALR, que son las partes del analizador Bottom Up. 
Analizador SLR El analizador SLR es similar al analizador LR(0) excepto por la entrada reducida. Las producciones reducidas se escriben únicamente en el SEGUIMIENTO de la variable cuya producción se reduce. 
Construcción de la tabla de análisis SLR –

1. Construcción C = { yo ₀ , yo ₁ , ……. I _n }, la colección de conjuntos de elementos LR(0) para G’.
2. El estado i se construye a partir de Ii. Las acciones de análisis para el estado i se determinan de la siguiente manera:
   • Si [ A -> ?.a? ] está en I _i y GOTO(I _i , a) = I _j , luego establezca ACTION[i, a] en «shift j». Aquí debe haber una terminal.
   • Si [A -> ?.] está en I _i , entonces configure ACTION[i, a] para “reducir A -> ?” para todo a en SEGUIR(A); aquí A puede no ser S’.
   • Si [S -> S.] está en I _i , luego establezca action[i, $] en «aceptar». Si las reglas anteriores generan acciones en conflicto, decimos que la gramática no es SLR.
3. Las transiciones goto para el estado i se construyen para todos los no terminales A usando la regla: si GOTO( I _i , A ) = I _j entonces GOTO [i, A] = j.
4. Todas las entradas no definidas por las reglas 2 y 3 se convierten en error.

Por ejemplo: si en la tabla de análisis tenemos varias entradas, se dice que hay un conflicto.

Consider the grammar E -> T+E | T
                     T ->id
    Augmented grammar - E’ -> E
                E -> T+E | T
                T -> id

 

Nota 1 : para GATE no tenemos que dibujar la tabla, en el gráfico GOTO solo busque la reducción y los cambios que ocurren juntos en un estado. En el caso de dos reducciones, si el seguimiento de ambas producciones reducidas tiene algo común entonces dará como resultado múltiples entradas en la tabla, por lo tanto, no SLR. En el caso de un turno y una reducción, si hay una operación GOTO desde ese estado en un terminal que es el seguimiento de la producción reducida, dará como resultado múltiples entradas, por lo tanto, no SLR. 

Nota 2 : todas las gramáticas SLR no son ambiguas, pero hay muchas gramáticas no ambiguas que no son SLR. 
CLR PARSER En el método SLR estábamos trabajando con elementos LR(0)). En el análisis CLR usaremos elementos LR(1). El elemento LR(k) se define como un elemento que utiliza anticipaciones de longitud k. Por lo tanto, el elemento LR(1) se compone de dos partes: el elemento LR(0) y la anticipación asociada con el elemento. Los analizadores LR(1) son analizadores más potentes. Para los elementos LR(1) modificamos la función Closure y GOTO. 
Operación de cierre 

Closure(I)
repeat 
    for (each item [ A -> ?.B?, a ] in I )
        for (each production B -> ? in G’)
          for (each terminal b in FIRST(?a))
            add [ B -> .? , b ] to set I;
until no more items are added to I;
return I;

Entendámoslo con un ejemplo:

  
Ir a la operación

Goto(I, X)
Initialise J to be the empty set;
for ( each item A -> ?.X?, a ] in I )
    Add item A -> ?X.?, a ] to se J;   /* move the dot one step */
return Closure(J);    /* apply closure to the set */

P.ej-

  
LR(1) artículos

Void items(G’)
Initialise C to { closure ({[S’ -> .S, $]})};
Repeat
    For (each set of items I in C)
        For (each grammar symbol X)
            if( GOTO(I, X) is not empty and not in C)
                Add GOTO(I, X) to C;
Until no new set of items are added to C;

Construcción del gráfico GOTO

• Estado I ₀ – cierre del elemento LR(1) aumentado.
• Utilizando I ₀ encuentre toda la colección de conjuntos de elementos LR(1) con la ayuda de DFA
• Convertir tabla de análisis de DFA a LR(1)

Construcción de la tabla de análisis CLR – Entrada – gramática aumentada G’

1. Construcción C = { yo ₀ , yo ₁ , ……. I _n } , la colección de conjuntos de elementos LR(0) para G’.
2. El estado i se construye a partir de Ii. Las acciones de análisis para el estado i se determinan de la siguiente manera: i) Si [ A -> ?.a?, b ] está en I _i y GOTO(I _i , a) = I _j , entonces establezca ACTION[i, a] en “cambio j”. Aquí debe haber una terminal. ii) Si [A -> ?. , a] está en I _i , A ≠ S, luego configure ACTION[i, a] para “reducir A -> ?”. iii) Si [S -> S. , $] está en I _i , luego establezca la acción [i, $] en «aceptar». Si las reglas anteriores generan acciones en conflicto, decimos que la gramática no es CLR.
3. Las transiciones goto para el estado i se construyen para todos los no terminales A usando la regla: si GOTO( I _i , A ) = I _j entonces GOTO [i, A] = j.
4. Todas las entradas no definidas por las reglas 2 y 3 se convierten en error.

P.ej:

Consider the following grammar 
    S -> AaAb | BbBa
    A -> ?
    B -> ?
    Augmented grammar - S’ -> S
                  S -> AaAb | BbBa
                  A -> ?
                  B -> ?
    GOTO graph for this grammar will be - 

 

Nota : si un estado tiene dos reducciones y ambas tienen la misma anticipación, habrá varias entradas en la tabla de análisis y, por lo tanto, un conflicto. Si un estado tiene una reducción y hay un cambio de ese estado en una terminal igual que la anticipación de la reducción, entonces generará múltiples entradas en la tabla de análisis y, por lo tanto, un conflicto. 
LALR PARSER El analizador LALR es igual que el analizador CLR con una diferencia. En el analizador CLR, si dos estados difieren solo en la anticipación, combinamos esos estados en el analizador LALR. Después de la minimización, si la tabla de análisis no tiene conflicto, la gramática también es LALR. P.ej:

consider the grammar S ->AA
                     A -> aA | b
    Augmented grammar - S’ -> S
                        S ->AA
                        A -> aA | b

 
Notas importantes 1. Aunque el analizador CLR no tiene conflicto de RR, LALR puede contener conflicto de RR. 2. Si número de estados LR(0) = n1, número de estados SLR = n2, número de estados LALR = n3, número de estados CLR = n4 entonces, n1 = n2 = n3 <= n4 
 

Este artículo es una contribución de Parul Sharma