De abajo hacia arriba o Desplazamiento Reducir analizadores | conjunto 2 – Part 1

En este artículo, estamos discutiendo el analizador Bottom Up.
Analizadores Bottom Up / Shift Reduce Parsers
Cree el árbol de análisis desde las hojas hasta la raíz. El análisis de abajo hacia arriba se puede definir como un intento de reducir la string de entrada w al símbolo de inicio de la gramática al rastrear las derivaciones más a la derecha de w a la inversa.
P.ej.

Clasificación de los analizadores de abajo hacia arriba

Un análisis de reducción de cambio general es el análisis de LR. La L representa la exploración de la entrada de izquierda a derecha y la R representa la construcción de una derivación más a la derecha a la inversa.
Beneficios del análisis LR:

1. Muchos lenguajes de programación utilizan algunas variaciones de un analizador LR. Cabe señalar que C++ y Perl son excepciones.
2. LR Parser se puede implementar de manera muy eficiente.
3. De todos los analizadores que escanean sus símbolos de izquierda a derecha, los analizadores LR detectan errores sintácticos lo antes posible.

Aquí veremos la construcción del gráfico GOTO de la gramática usando las cuatro técnicas de análisis sintáctico LR. Para resolver preguntas en GATE tenemos que construir el GOTO directamente para la gramática dada para ahorrar tiempo.

Analizador LR(0)
Necesitamos dos funciones:
Closure()
Goto()

Gramática aumentada
Si G es una gramática con símbolo de inicio S, entonces G’, la gramática aumentada para G, es la gramática con nuevo símbolo de inicio S’ y una producción S’ -> S. El propósito de esta nueva producción inicial es indicar a el analizador cuando debe dejar de analizar y anunciar la aceptación de la entrada.
Sea una gramática S -> AA
A -> aA | b
La gramática aumentada para la gramática anterior será
S’ -> S
S -> AA
A -> aA | b

Elementos LR(0)
Un LR(0) es el elemento de una gramática G es una producción de G con un punto en alguna posición en el lado derecho.
S -> ABC produce cuatro elementos
S -> .ABC
S -> A.BC
S -> AB.C
S -> ABC.
La producción A -> ε genera solo un artículo A -> .ε

Operación de cierre :
si I es un conjunto de elementos para una gramática G, entonces el cierre (I) es el conjunto de elementos construido a partir de I por las dos reglas:

1. Inicialmente, cada elemento en I se agrega al cierre (I).
2. Si A -> α.Bβ está en cierre (I) y B -> γ es una producción, agregue el elemento B -> .γ a I, si aún no está allí. Aplicamos esta regla hasta que no se puedan agregar más elementos al cierre (I).

Por ejemplo:

Operación Ir a :
Ir a (I, X) = 1. Agregue I moviendo el punto después de X.
                      2. Aplique el cierre al primer paso.

Construcción del grafo GOTO-

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

Construcción de la tabla de análisis LR(0) :

• La función de acción toma como argumentos un estado i y un terminal a (o $, el marcador final de entrada). El valor de ACCIÓN[i, a] puede tener una de cuatro formas:
  1. Shift j, donde j es un estado.
  2. Reducir A -> β.
  3. Aceptar
  4. Error
• Extendemos la función GOTO, definida en conjuntos de elementos, a estados: si GOTO[I _i , A] = I _j entonces GOTO también asigna un estado i y un A no terminal al estado j.

Por ejemplo:
Considere la gramática S ->AA
A -> aA | b
Gramática aumentada S’ -> S
S -> AA
A -> aA | b

La tabla de análisis LR(0) para el gráfico GOTO anterior será:

La parte de acción de la tabla contiene todos los terminales de la gramática, mientras que la parte goto contiene todos los no terminales. Para cada estado del gráfico goto escribimos todas las operaciones goto en la tabla. Si se aplica goto a un terminal, se escribe en la parte de acción, si se aplica goto en un no terminal, se escribe en la parte goto. Si al aplicar goto se reduce una producción (es decir, si el punto llega al final de la producción y no se puede aplicar más cierre), entonces se denota como R _i y si la producción no se reduce (desplazada) se denota como S _i .
Si se reduce una producción, se escribe debajo de los terminales dados a continuación del lado izquierdo de la producción que se reduce, por ejemplo: en I ₅ S->AA se reduce, por lo que R ₁está escrito debajo de los terminales en follow(S)={$} (Para saber más sobre cómo calcular la función de seguimiento: Haga clic aquí ) en el analizador LR(0).
Si en un estado se reduce el símbolo de inicio de la gramática, se escribe bajo el símbolo $como aceptado.

NOTA: Si en cualquier estado están presentes producciones tanto reducidas como desplazadas o dos producciones reducidas, se denomina situación de conflicto y la gramática no es gramática LR.

NOTA:
1. Dos producciones reducidas en un estado – Conflicto RR.
2. Una producción reducida y otra desplazada en un estado: conflicto SR.

Si no hay conflicto SR o RR presente en la tabla de análisis, entonces la gramática es gramática LR(0).
En la gramática anterior no hay conflicto, por lo que es gramática LR (0).

NOTA –Al resolver la pregunta GATE, no necesitamos hacer la tabla de análisis, al mirar el gráfico GOTO solo podemos determinar si la gramática es LR (0) o no. Solo tenemos que buscar conflictos en el gráfico goto, es decir, si un estado contiene dos entradas reducidas o una reducida y una de cambio para una variable TERMINAL, entonces hay un conflicto y no es gramática LR(0). (En el caso de un turno con una VARIABLE y uno reducido, no habrá conflicto porque las entradas del turno irán a la parte GOTO de la tabla y las entradas reducidas irán a la parte ACTION y, por lo tanto, no habrá entradas múltiples).

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