arbol de analisis gramatical

12
ARBOL DE ANALISIS GRAMATICAL GENERA UNA CADENA UTILIZANDO UNA GRAMATICA ARBOL SINTACTICO ARBOL DE DERIVACION

Upload: nikita

Post on 11-Jan-2016

22 views

Category:

Documents


0 download

DESCRIPTION

ARBOL DE ANALISIS GRAMATICAL

TRANSCRIPT

Page 1: ARBOL DE ANALISIS GRAMATICAL

ARBOL DE ANALISIS

GRAMATICAL

GENERA UNA CADENA

UTILIZANDO UNA GRAMATICA

ARBOL SINTACTICO

ARBOL DE DERIVACION

Page 2: ARBOL DE ANALISIS GRAMATICAL

ÁRBOL DE ANÁLISIS

GRAMATICAL <expresión>

<termino>

<termino> * <factor>

<factor>

<nombre>

A

<nombre>

B

A * B

Page 3: ARBOL DE ANALISIS GRAMATICAL

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

Page 4: ARBOL DE ANALISIS GRAMATICAL

DERIVACIONES

DERECHA

IZQUIERDA

Page 5: ARBOL DE ANALISIS GRAMATICAL

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

Page 6: ARBOL DE ANALISIS GRAMATICAL

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

Page 7: ARBOL DE ANALISIS GRAMATICAL

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

Page 8: ARBOL DE ANALISIS GRAMATICAL

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.

Page 9: ARBOL DE ANALISIS GRAMATICAL

AMBIGUEDAD

Page 10: ARBOL DE ANALISIS GRAMATICAL

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

Page 11: ARBOL DE ANALISIS GRAMATICAL

ANALISI SINTACTICO

DESCENDENTE ASCENDENTE

Page 12: ARBOL DE ANALISIS GRAMATICAL

PROBLEMAS DEL ANALISIS SINTACTICO

ASCENDENTE

MAS DE UNA ELECION

DESCENDENTE

MAS DE UNA ELECCION

RECURSIVIDAD DE IZQUIERDA

FACTORIZACION IZQUIERDA