pabloaguilar3: Análisis Sintáctico Descendente

El analizador sintáctico LL es un analizador sintáctico descendente, por un conjunto de gramática libre de contexto. En éste analizador las entradas son de izquierda a derecha, y construcciones de derivaciones por la izquierda de una sentencia o enunciado. La clase de gramática que es analizable por éste método es conocido como gramática LL.

El resto de este artículo se describe en el cuadro de base del tipo de analizador sintáctico, la alternativa comienza con ser un intérprete de ascendencia recursiva que normalmente son codificados a mano (aunque no siempre; por ejemplo, ANTLR para un LL(*) - (generador de analizador ascendencia recursiva).

Un analizador LL es llamado un analizador LL (k) si usa k tokens cuando el analizador ve hacia delante de la sentencia. Si existe tal analizador para cierta gramática y puede analizar sentencias de ésta gramática sin marcha atrás, entonces es llamada una gramática LL (k). De ésta gramáticas, la gramática LL(1), aunque es bastante restrictiva, éstas son muy populares porque los analizadores LL correspondientes sólo necesita ver el siguiente token para hacer el análisis de sus decisiones. Lenguajes mal diseñados usualmente suelen tener gramáticas con un alto nivel de k, y requieren un esfuerzo considerable a analizar.

Es del tipo LL1 porque empezamos a derivando por la izquierda, y los caracteres son leídos de izquierda a derecha, el 1 por que se lee 1 solo elemento de entrada.

También se puede considerar como un intento de construir un árbol de análisis sintáctico para la entrada comenzando desde la raíz y creando los nodos del árbol en orden previa.

Bueno primeramente para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:

- Eliminar Ambigüedad

- Eliminar Recursividad por la Izquierda

- Factorizar

- Primeros y siguientes

Ambigüedad

Una gramática es ambigua cuando genera más de un árbol de derivación.

Para eliminar la ambigüedad se debe reescribir la gramática.

Ejemplo:

Recursividad por la Izquierda

Una gramática es recursiva por la izquierda si tiene un no Terminal A tal que existe una derivación A->Aα para alguna cadena. Es decir por simple observación podemos identificar.

Para eliminar la recursividad por la izquierda se utiliza la siguiente formula.

Ejemplo:

Gramática Recursiva

Factorización por la Izquierda

Una gramática tiene dos producciones alternativas de un símbolo A empiezan iguales, no se sabrá por cuál de ellas seguir. Se trata de reescribir las producciones de A para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta.

Ejemplo de una gramática que tiene Factorización por la izquierda

Para eliminar la Factorización se debe poner en práctica la siguiente fórmula:

Ejemplo:

Resultado de factorizar

Se realiza factorización ya que si no lo hacemos al momento de que el análisis sintáctico inicia el reconocimiento se va a encontrar con varias alternativas, lo que hace que esto sea semejante a un autómata finito no determinista, por lo tanto no se sabe que camino elegir.

Primeros y Siguientes

*Primeros._ Conjunto de elementos terminales que se encuentran al lado derecho de la producción. Para lo cual se tiene la tres siguientes formulas. Su palabra lo dice es el primer elemento terminal que encontramos en el lado derecho de la producción

*Siguientes._ Si A es un símbolo no Terminal de la gramática; S(A) es el conjunto de terminales ( y $) que pueden aparecer a continuación de A alguna forma sentencial derivada del símbolo inicial.