analizador ascente y descente

ANALIZADOR SINTÁCTICO DESCENDENTE Y ANALIZADOR SINTÁCTICOASCENDENTE


La tarea esencial de un analizador es determinar si una determinada entrada puede ser derivada desde el símbolo inicial, usando las reglas de una gramática formal, y como hacer esto, existen esencialmente dos formas:

Analizador sintáctico descendente

(Top-Down-Parser ): parten del axioma inicial, y van efectuandoderivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia.

Pueden ser:
 
Con retroceso Pretende buscar en el árbol universal a la sentencia a reconocer; cuando lo encuentre, el camino que lo separa de la raíz nos da el árbol sintáctico. Ahora bien, es posible que la sentencia sea errónea y que no se encuentre como hoja del árbol lo que, unido a que es muyprobable que el árbol sea infinito, nos lleva a la necesidad de proponer un enunciado que nos indique cuándo se debe cancelar la búsqueda porque se da por infructuosa.
 
Con funciones recursivas No todo diagrama de sintaxis es susceptible de ser convertido tan fácilmente en función recursiva; concretamente, en aquellos nudos del diagrama en los que el flujo puede seguir por varios caminos, ladecisión sobre cuál seguir se ha hecho en base al siguiente token de la entrada, de manera que dicho token actúa como discriminante.
 
De gramáticas LL(1).Se basa en un autómata de reconocimiento en forma de tabla, denominada tabla de chequeo de sintaxis. Dicha tabla posee como eje de ordenadas a los no terminales de la gramática, y como abscisas a los terminales (incluido en pseudotoken EOF).El contenido de cada casilla interior (que se corresponde con la columna de un terminal y la fila de un no terminal) contiene, o bien una regla de producción, o bien está vacía, lo que se interpreta como un rechazo de la cadena a reconocer. En general, podemos decir que una gramática LL(1) es aquélla en la que es suficiente con examinar sólo un símbolo a la entrada, para saber qué regla aplicar,partiendo del axioma inicial y realizando derivaciones a izquierda. Toda gramática reconocible mediante el método de los diagramas de sintaxis siguiendo el procedimiento visto en el punto anterior es LL(1).El método consiste en seguir un algoritmo partiendo de:
 
La cadena a reconocer, junto con un apuntador, que nos indica cuales el token de pre-búsqueda actual; denotaremos por a dicho token. 
Una pila de símbolos (terminales y no terminales); denotaremos por X la cima de esta pila.
 
Una tabla de chequeo de sintaxis asociada de forma unívoca a una gramática.







Ejemplo: Utilizaremos la gramática simple, G1 (T1, N1, P1, S1) que define los enteros no negativos (ENN)T


T1= {0,1,2,3,4,5,6,7,8,9}N

N1= {DIGITO, ENN} P

P1= {ENN à DIGITO | ENN DIGITO}

DIGITO à0|1|2|3|4|5|6|7|8|9|S

S1= {ENN} Queremos analizar la frase 123. en un principio solo conocemos la raíz del árbol y la frase que debe analizarse.

 Árbol semántico frase
 
ENN 1 2 3
 En el primer paso encontramos la producción ENN à ENN DIGITO y obtenemos el inicio del árbol de análisis sintáctico.


  
















 

 En el siguiente paso hallamos de nuevo la mismaproducción. Después encontramos la producción ENN à DIGITO, que expande el árbol sintáctico a lo siguiente:





































Encontramos ahora la producción DIGITO à 1, que establece la conexión con el primer elemento de la frase dada. La producción DIGITO à 2 establece la conexión con el segundo elemento de la frase: Por último el árbolde análisis sintáctico queda completo con la producción DIGITO à 3.Podemos ver que el árbol crece de arriba abajo a medida que se lee la frase de entrada de izquierda a derecha.




Analizador sintáctico ascendente

( Bottom-Up-Parser ): Parten de la sentencia de entrada, y van aplicando derivaciones inversas (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial....