Compilador Diseño - Analizador Ascendente


Advertisements

Análisis bottom-up se inicia a partir de los nudos de las hojas de un árbol y trabaja en dirección hacia arriba hasta que llega al nodo raíz. En este sentido, partimos de una frase y, a continuación, aplicar normas de producción en forma contraria a fin de alcanzar el símbolo de arranque. La imagen siguiente muestra la parte inferior de los analizadores.

De abajo hacia arriba de análisis

Análisis Shift-Reduce

Shift-reducir el análisis utiliza dos únicos pasos para la parte inferior de análisis. Estos pasos son conocidos como cambio de paso y reducir de paso.

  • Paso de cambio: el paso de cambio se refiere a la promoción del puntero de entrada con el siguiente símbolo de entrada, el cual se denomina el símbolo cambia. Este símbolo se empuja en la pila. Cambia el símbolo es tratado como un único nodo del árbol analizar.

  • Reducir paso: Cuando el analizador encuentra una regla gramatical (RHS) y reemplaza a (LHS), se conoce como reducir paso. Esto ocurre cuando la parte superior de la pila contiene un identificador. A fin de reducir, un POP función se realiza en la pila que los contaminantes orgánicos persistentes de la palanca y se reemplaza con LHS símbolo no terminal.

Analizador LR

El analizador LR es un non-recursive, shift-reducir, analizador bottom-up. Utiliza una amplia clase de gramática libre de contexto lo que lo convierte en el más eficiente técnica de análisis sintaxis. LR los analizadores son también conocidos como LR(k) analizadores, donde L es de izquierda a derecha la exploración del flujo de entrada; R significa para la construcción de más a la derecha en derivación hacia atrás, y k indica el número de símbolos anticipada a la hora de tomar decisiones.

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

  • SLR(1) - Simple Analizador LR:
    • Trabaja en clase de gramática más pequeña
    • Algunos de los estados, por lo tanto, muy pequeña mesa
    • Construcción sencilla y rápida
  • LR(1) - LR Analizador:
    • Trabaja en conjunto completo de LR(1) Gramática
    • Genera una gran mesa y gran número de estados
    • Construcción Lenta
  • LALR(1) - Vista adelantada LR Analizador:
    • Obras de tamaño intermedio de gramática
    • Número de estados son los mismos del SLR(1)

Análisis LR algoritmo

Aquí se describe un esqueleto de un algoritmo LR analizador:

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, tpken] = “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 y LR

LL LR
La izquierda tiene una derivación. Una derivación derecha en marcha atrás.
Comienza con el nonterminal de raíz en la pila. Termina con el nonterminal de raíz en la pila
Termina cuando la pila está vacía. Comienza con una pila vacía.
Usa la pila para designar lo que aún queda por esperar. Usa la pila para designar lo que ya está visto.
Construye el árbol análisis top-down. Construye el árbol análisis bottom-up.
Continuamente aparece un nonterminal de la pila y empuja el lado derecho correspondiente. Intenta reconocer un lado derecho de la pila, lo viejo y empuja la correspondiente nonterminal.
Amplía el no-terminales. Reduce la no-terminales.
Lee los terminales cuando aparece uno fuera de la pila. Lee los terminales mientras que les empuja en la pila.
Pre-orden el análisis transversal del árbol. Después de analizar el recorrido de árbol.
Advertisements