5.7 - Tipos de analizadores sintácticos

Ascendente:

·          

     En el Análisis Sintáctico Ascendente se parte de las hojas y se intenta construir el árbol hacia arriba hasta llegar al símbolo inicial de la gramática.

·        

        En un análisis top-down un parser hacer corresponder cadenas de entrada con sus correspondientes derivaciones izquierdas.

·         

       En un análisis bottom-up un parser hace corresponder cadenas de entrada con las inversas de las correspondientes derivaciones derechas.

EJEMPLO

Análisis sintáctico ascendente

Parten de las hojas (conjunto de tokens) para llegar a la raíz (axioma de la gramática):

·                    Analizadores de procedencia de operador.

·                    Analizador LR(1)

Se denominan analizadores sintácticos ascendentes (botton-up) porque pretenden construir un árbol sintáctico para una determinada cadena de entrada, empezando por las hojas y constituyendo el árbol hasta llegar a la raíz.

Un analizador sintáctico ascendente utiliza una pila explicita para realizar un análisis sintáctico, de manera semejante como lo hace un analizador sintáctico descendente no recursivo. La pila de análisis sintáctico contiene los tokens como símbolos no terminales y también alguna información de estado adicional.

Los analizadores LR reconocen el lenguajes realizando dos operaciones cargar (shift) y reducir (reduce). Lo que hace es leer los tokens de la entrada e ir cargándolos en una pila, de forma que se puedan explorar lo n tokens que contiene esta y ver si se corresponden con la parte derecha de alguna de las reglas de la gramática.

Si es así se realiza un reducción, consistente en sacar de la pila esos n tokens y en su lugar colocar el símbolo que aparezca en la parte izquierda de esa regla. En caso contrario, se carga en la pila el siguiente token y una vez hecho esto se vuelve a intentar una reducción.

Descendente 

En el Análisis Sintáctico Descendente se va recorriendo el árbol sintáctico desde la raíz hasta las hojas, llegando a generar la sentencia que se está analizando. La raíz representa el símbolo inicial de la gramática.

Análisis sintáctico descendente LL(1) 

Parten del axioma y aplican las reglas de la gramática hasta llegar a la secuencia de símbolos terminales (tokens):

·                    -Analizadores LL(1).

·                    -Analizadores recursivos.

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