Compiladores

Analizador Sintáctico

ANÁLISIS SINTÁCTICO DESCENDENTE

El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.

Se centra en los siguientes pasos:

  • Partir del axioma de la gramática
  • Escoger reglas gramaticales
  • Hacer derivaciones por la izquierda
  • Procesar la entrada de izquierda a derecha
  • Obtener el árbol de análisis sintáctico o error

Pueden ser:

  1. Con retroceso.- El método parte del axioma inicial y aplica todas las posibles reglas alno terminal más a la izquierda
  2. Con recursión.- Una gramática de contexto libre puede expresar un lenguaje al igual que puede hacerlola notación BNF, y los diagramas de Conway. Un diagrama de Conway es un grafo dirigido donde los elementos noterminales aparecen como rectángulos, y los terminales como círculos.
  3. LL(1) .- Una gramática LL(1) es aquella en la que su tabla de chequeo de sintaxis no poseeentradas múltiples, o sea, es suficiente con examinar sólo un símbolo a la entrada, parasaber qué regla aplicar. Toda gramática reconocible mediante el método de los diagramasde Conway es LL(1)El método consiste en seguir un algoritmo partiendo de:
  • La cadena a reconocer, junto con un apuntador, que nos indica cual es el token actual
  • Una pila de símbolos ( terminales y no terminales)
  • Una tabla asociada de forma unívoca a una gramática.

ANÁLISIS SINTÁCTICO ASCENDENTE

Un análisis ascendente (ASA) puede empezar con la entrada e intentar llegar hasta el símbolo inicial, intuitivamente el analizador intenta encontrar los símbolos más pequeños y progresivamente construir la jerarquía de símbolos hasta el inicial.

Aquí se construye el árbol sintáctico de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente (si hablamos del caso con retroceso).

Pueden ser:

  1. Con retroceso.- Cuando se da cuenta que llega a una situación en la que no puede continuar, entonces vuelve atrás deshaciendo todos los cambios.
  2. LR(1).-Pueden reconocer la inmensa mayoría de los lenguajes de programación que puedan ser generados mediante gramáticas de contexto-libre. El método de funcionamiento de estos analizadores posee la ventaja de localizar un error sintáctico en el mismo instante que se produce con lo que se adquiere una gran eficienciade tiempo de compilación frente a procedimientos menos adecuados como puedan ser losde retroceso.

DIFERENCIAS ENTRE ANÁLISIS SINTÁCTICO DESCENDENTE Y ANÁLISIS SINTÁCTICO ASCENDENTE

ANÁLISIS DESCENDENTE(Top-Down).- En este tipo de análisis se construye el árbol desde la raíz (S) hasta llegar a las hojas

ANÁLISIS ASCENDENTE(Bottom-Up).- En este tipo de análisis se construye el árbol desde las hojas hacia la raíz (S)

 

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s