Diseño del compilador: analizador ascendente

El análisis de abajo hacia arriba comienza desde los nodos de hojas de un árbol y trabaja en dirección ascendente hasta que alcanza el nodo raíz. Aquí, partimos de una oración y luego aplicamos las reglas de producción de manera inversa para llegar al símbolo de inicio. La imagen que se muestra a continuación muestra los analizadores de abajo hacia arriba disponibles.

Análisis Shift-Reducir

El análisis sintáctico con reducción de cambios utiliza dos pasos únicos para el análisis sintáctico ascendente. Estos pasos se conocen como paso de cambio y paso de reducción.

• Shift step: El paso de cambio se refiere al avance del puntero de entrada al siguiente símbolo de entrada, que se denomina símbolo desplazado. Este símbolo se coloca en la pila. El símbolo desplazado se trata como un solo nodo del árbol de análisis.

• Reduce step: Cuando el analizador encuentra una regla gramatical completa (RHS) y la reemplaza por (LHS), se conoce como reducir paso. Esto ocurre cuando la parte superior de la pila contiene un asa. Para reducir, se realiza una función POP en la pila que salta del asa y la reemplaza con el símbolo LHS no terminal.

Analizador LR

El analizador LR es un analizador de abajo hacia arriba no recursivo, con reducción de cambios. Utiliza una amplia clase de gramática libre de contexto que la convierte en la técnica de análisis de sintaxis más eficiente. Los analizadores sintácticos LR también se conocen como analizadores sintácticos LR (k), donde L significa escaneo de izquierda a derecha del flujo de entrada; R representa la construcción de la derivación más a la derecha en reversa y k denota el número de símbolos de anticipación para tomar decisiones.

Hay tres algoritmos ampliamente utilizados disponibles para construir un analizador LR:

• SLR (1) - Analizador LR simple:
  • Funciona en la clase de gramática más pequeña
  • Pocos estados, por lo tanto, una tabla muy pequeña
  • Construcción simple y rápida
• LR (1) - Analizador LR:
  • Funciona en el juego completo de gramática LR (1)
  • Genera una gran tabla y una gran cantidad de estados.
  • Construcción lenta
• LALR (1) - Analizador LR anticipado:
  • Funciona en tamaño intermedio de gramática
  • El número de estados es el mismo que en SLR (1)

Algoritmo de análisis LR

Aquí describimos un algoritmo de esqueleto de un analizador LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL vs. LR

LL	LR
Hace una derivación más a la izquierda.	Hace una derivación más a la derecha a la inversa.
Comienza con la raíz no terminal en la pila.	Termina con la raíz no terminal en la pila.
Termina cuando la pila está vacía.	Comienza con una pila vacía.
Utiliza la pila para designar lo que aún se espera.	Utiliza la pila para designar lo que ya se ve.
Construye el árbol de análisis de arriba hacia abajo.	Construye el árbol de análisis de abajo hacia arriba.
Saca continuamente un no terminal de la pila y empuja el lado derecho correspondiente.	Intenta reconocer un lado derecho en la pila, lo saca y empuja el no terminal correspondiente.
Expande los no terminales.	Reduce los no terminales.
Lee los terminales cuando saca uno de la pila.	Lee los terminales mientras los empuja en la pila.
Preordenar el recorrido del árbol de análisis.	Recorrido posterior al pedido del árbol de análisis.