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.
Para poder trabajar el análisis sintáctico
descendente se debe de realizar primeramente alguna de las operaciones para que
la gramática sea LL1 las cuales son:
·
-Eliminar ambigüedad.
·
-Eliminar recursividad por la izquierda.
·
-Factorizar.
· -Primeros y siguientes
Eliminar 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.
Eliminar ambigüedad: Para eliminar la ambigüedad se
debe reescribir la gramática.
Eliminar recursividad por la izquierda: Una
gramática es recursiva por la izquierda si tiene un nodo
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.
Factorizar: Se trata de rescribir las producciones
de la gramática con igual comienzo para retrasar la decisión hasta haber visto
lo suficiente de la entrada como para elegir la opción correcta.
Ejemplo:
Análisis
sintáctico descendente:
·
-Partir del axioma de la gramática.
·
-Escoger reglas gramaticales.
·
-Hacer derivaciones por la izquierda.
·
-Procesar la entrada de izquierda a derecha.
·
-Obtener el árbol de análisis sintáctico o error.
Primero y
siguiente:
Las funciones primero y siguiente permiten
rellenar, siempre que sea posible, las entradas de una tabla de análisis
sintáctico predictivo para una gramática.
También se usan los componentes devueltos por la
función siguiente para sincronizar la recuperación de errores en modo pánico.
