Analizador Sintáctico

Analizador Sintáctico

Es una de las partes de un compilador que transforma su entrada en un árbol de derivación. Convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada.

Analizador Sintáctico Descendente (Top-Down-Parser)

Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia.
Pueden ser:

• Con retroceso.- parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda. Este método no funciona con gramáticas recursivas a la izquierda, ya que puede ocurrir que entre en un bucle infinito.
  
• Con recursión.- Diagramas de Conway.Un diagrama de Conway es un grafo dirigido donde los elementos no terminales aparecen como rectángulos, y los terminales como círculos
  
• LL.- es aquella en la que su tabla de chequeo de sintaxis no posee entradas múltiples, o sea, es suficiente con examinar sólo un símbolo a la entrada, para saber qué regla aplicar.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.

Analizador Sintáctico Ascendente (Bottom-Up-Parser)

Parten de la sentencia de entrada, y van aplicando reglas de producción hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial.
Pueden ser:

• Con retroceso.- no se permiten las reglas J, puesto que estas se podrán aplicar de forma indefinida.
  
• LR (k).- la “L” es por el examen de la entrada de izquierda a derecha (en inglés, left-to-right), la “R” por construir una derivación por la derecha (en inglés, rightmost derivation) en orden inverso, y la k por el número de símbolos de entrada de examen por anticipado utilizados para tomar las decisiones del análisis sintáctico. Cuando se omite, se asume que k, es 1. El análisis LR es atractivo por varias razones.
  
  • 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 eficiencia de tiempo de compilación frente a procedimientos menos adecuados como puedan ser los de retroceso.
    
  El principal inconveniente del método es que supone demasiado trabajo construir un analizador sintáctico LR a mano para una gramática de un lenguaje de programación típico.