Post on 11-Jan-2016
description
ARBOL DE ANALISIS
GRAMATICAL
GENERA UNA CADENA
UTILIZANDO UNA GRAMATICA
ARBOL SINTACTICO
ARBOL DE DERIVACION
ÁRBOL DE ANÁLISIS
GRAMATICAL <expresión>
<termino>
<termino> * <factor>
<factor>
<nombre>
A
<nombre>
B
A * B
DERIVACIONESNOS DICE EN QUE ORDEN FUERON APLICADAS LAS REGLAS
1. E E+T2. E T3. T T*F4. T F5. F (E)6. F a
GRAMÁTICA
E E+T E+T*F T+T*F F+T*F F+T*a a+T*a
a+F*a a+a*a
1 2 3 4 6
4
6
6
DERIVACION DE a+a*a
NUMERO DE PRODUCCION APLICADA
DERIVACIONES
DERECHA
IZQUIERDA
E E + T E + T * FE + T * a
E + F + a E + a *aT + a * a F + a * aa * a * a
DERIVACIÓN DE DERECHA DE a+a*a
1 3 6
4 6
2
6
4
Las reglas aplicadas son:1 3 6 4 6 2 4 6
Si aplicamos las reglas en el orden enumerado, podemos esquematizar el árbol de análisis sintáctico
TERMINALES•Son los tokens •Son las nodos hojas
NO TERMINALES•Encerrados entre <> •Son los nodos no hojas
PODUCCIONES •Conjunto de reglas de reemplazo
SIMBOLO DE INICIO•Es un no terminal
FORMA SENTENCIAL•Conjunto de terminales y no terminales
SENTENCIA•Consiste en terminales
BNF EXTENDIDA
Los procedimientos recursivos en programación pueden reescribirse haciendo uso de la iteración
Las iteraciones que empleamos son:
Las llaves tipográficas, para representar 0 a mas ocurrencias
Los corchetes para representar elementos opcionales
PRODUCCIONES EPSILON
•Representan a las cadenas vacías
RELACIÓN DE LAS
GRAMÁTICAS Y EL ANÁLISIS SINTÁCTICO
•El análisis sintáctico revierte el proceso de derivación en el sentido que hay una cadena de entrada y un árbol de salida.
AMBIGUEDAD
E E + E
E E * E
E (E)
E a
GRAMATICA
E
E E+
E + EE
E E
E
EE +
E + EE
E E
DERIVACION 1 DERIVACION 2
ANALISI SINTACTICO
DESCENDENTE ASCENDENTE
PROBLEMAS DEL ANALISIS SINTACTICO
ASCENDENTE
MAS DE UNA ELECION
DESCENDENTE
MAS DE UNA ELECCION
RECURSIVIDAD DE IZQUIERDA
FACTORIZACION IZQUIERDA