ANÁLISIS DESCENDENTE
El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.
- Partir del axioma de la gramática
- Escoger reglas gramaticales
- Hacer derivaciones por la izquierda
- Procesar la entrada de izquierda a derecha
ANÁLISIS ASCENDENTE
Parte de la cadena de entrada para construir la inversa de una derivación por la derecha. Genera el árbol de análisis sintáctico partiendo de las hojas hasta alcanzar el axioma.
Análisis ascendente se construye el árbol de análisis sintáctico de la cadena de entrada desde las hojas hasta la raíz. En las hojas tenemos la cadena a analizar (los símbolos terminales) que se intentan reducir al axioma, que se encontrara en la raíz, si la cadena es correcta sintácticamente.
¿Cómo construir el árbol?
Se trata de desplazarse en la entrada hasta encontrar una subcadena de símbolos que represente la parte derecha de una producción, en ese momento sustituimos esa subcadena por el no-terminal de la parte izquierda correspondiente de la producción, la reducimos.
Ejemplo: Supongamos la siguiente gramática que permite generar expresiones aritméticas donde aparece el operador suma y potencia y combinar números e identificadores.
Nos restringimos al caso de métodos deterministas (no hay vuelta atrás) analizando un solo símbolo de pre análisis sabemos exactamente en todo momento que acción realizar: bien desplazarnos en la entrada o bien aplicar una reducción. En el caso de una reducción debemos saber de forma única que producción aplicar.
Los métodos ascendentes se caracterizan porque analizan la cadena de componentes léxicos de izquierda a derecha, obtienen la derivación más a la derecha y el árbol de derivación se construye desde la raíz hasta las hojas.
Diferencia entre Análisis Sintáctico Descendente, Análisis Sintáctico Ascendente:
Descendente: En este tipo de análisis, 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.
Ascendente: Se parte de las hojas y se intenta construir el árbol hacia arriba hasta llegar al símbolo inicial de la gramática
Por ejemplo, si quisiéramos reconocer “id + id + id”, partiendo de la gramática del cuadro se comenzaría a construir el árbol sintáctico a partir del árbol vacío (α = ε) y con toda la cadena de entrada por consumir (β = id + id + id):
Fuente Bibliográfica
Análisis Sintáctico Descendente [en línea]
Análisis Sintáctico Ascendente [en línea]
http://www.lsi.uned.es/procleng/apuntes/2006-2007/AnalisisSintacticoAscendente.pdf
No hay comentarios:
Publicar un comentario