Page 84 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

84

Analizador sintáctico descendente (top-down-parser): un analizador puede empezar con el
símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la
entrada progresivamente en partes cada vez más pequeñas, de esta forma funcionan los
analizadores LL, un ejemplo es el JAVACC.

Analizador sintáctico ascendente (bottom-up-parser): un analizador 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, los
analizadores LR funcionan así y un ejemplo es el YACC.

Proceso de análisis sintáctico LL:

Gramáticas independientes del contexto a autómatas de pila que analiza su cadena de entrada
marcando antes el fondo de la pila e insertando en la pila el fondo inicial de la gramática. Luego
repite los 3 pasos siguientes según sea aplicable:

1- Si la cima de la pila contiene un no terminal de la gramática, reemplace ese no terminal
de acuerdo con una de las reglas de reescritura de la gramática.
2- Si la cima de la pila contiene un terminal, elimínelo de la pila a la vez que lee de la entrada
el mismo terminal. Si el símbolo de la entrada no equivale al de la cima, se declara la
cadena ilegal.
3- Si en la cima de la pila aparece la marca de fondo de pila, elimínela y declare aceptada la
porción de la cadena procesada hasta el momento.

Este proceso analiza la sintaxis de la cadena de entrada produciendo una derivación por la
izquierda conforme lee la cadena de izquierda a derecha. Estos analizadores que trabajan
así se conocen como analizadores ll. Primera l denota de left-to-rigth y la segunda leftmost
derivation, o sea denota que el objetivo del analizador es producir una derivación por la
izquierda.
La forma en que se genera el programa es transcribir las transiciones del autómata en sentencias
de programa.

El problema común en los autómatas de pila, es cuando la gramática que sigue propone más de
una forma de reescribir un no terminal. Por esto la actividad básica de un analizador ll es predecir
cuál de las distintas reglas de reescritura es que debe usarse, para poder procesar los símbolos de
entrada que restan. Este realmente es el problema de estas gramáticas, que deben tener varias
opciones o reglas de reescrituras para poder generar más de una cadena, que es el caso de los
lenguajes de programación, que contiene más de una cadena. Obviamente las gramáticas libres
de contexto que solo ofrece una manera de reescribir cada no terminal, solo puede generar una
cadena.

A este tipo de analizador se le conoce como: analizador sintáctico predictivo. Este tipo de
analizador también se ve limitado, en el punto de que no necesariamente podrá determinar que
regla de derivación deberá usar, conociendo el siguiente símbolo de entrada, es posible que
requiere conocer los restantes, para lograr hacer una derivación exitosa. Así las cosas, para lograr
una rutina determinista de análisis sintáctico, se debe contar con memoria temporal como para 2
símbolos de entrada; conociendo lo que leerá y el estado de la cima puede decidir qué derivación
conviene realizar.