compiladores - profr. edgardo adrián franco martínez contenido

Contenido

• Análisis Descendente Predictivo

• Gramáticas LL(1)

• Método Descendente LL(1)

• Definiciones

• Pasos para el Método LL(1)

• Ejemplo

• Ejercicios

2 Compiladores (Análisis Sintáctico V - Edgardo A. Franco)

19, 20 y 21 Análisis sintáctico IV Compiladores - Profr. Edgardo Adrián Franco Martínez

2

Análisis Descendente Predictivo

•Es un tipo especial del análisis sintáctico

descendente recursivo

•Observa el siguiente token en la cadena de entrada

para determinar cual va a ser la regla de producción

a aplicar en la construcción del árbol de derivación.



3

Análisis Descendente Predictivo

•El símbolo de pre análisis determina sin

ambigüedad el procedimiento seleccionado para

cada entrada.

•Las gramáticas con análisis de una pasada son de

tipo LL(k) las mas frecuentemente usadas son las

de tipo LL1.



4

Gramáticas LL(1)

• Las gramáticas LL(1) permiten construir de forma

automática un analizador direccional determinista

descendente con tan sólo examinar en cada momento el

símbolo actual de la cadena de entrada (símbolo de pre

análisis) para saber que producción aplicar.

5 Compiladores (Análisis Sintáctico IV - Edgardo A. Franco)

Teorema 1: Una gramática LL(1) no puede ser recursiva

por la izquierda y debe estar factorizada.

Teorema 2: Una gramática LL(1) es no ambigua


5

Método Descendente LL(1) Análisis Descendente No Recursivo (Predictivo)

• La primera L representa el tipo de lectura de la cadena de

entrada Left (de izquierda a derecha) método direccional

(from left to rigth).

• La segunda L representa la derivación Left, por la

izquierda (left-most derivation).

• Y el 1, es el número de símbolos de entrada para analizar

por anticipado. Método determinista (Símbolo de pre

análisis).



6

1. Buffer de Entrada

• Cadena de entrada a analizar, finaliza con el carácter $

2. Pila

• Estructura de datos que almacena temporalmente

símbolos gramaticales que se van utilizando.

3. Tabla de Análisis Sintáctico

• Matriz bidimensional que sirve para el análisis

4. Cadena de Salida

• Cadena de Salida posterior al análisis

Método Descendente LL(1) Componentes para el análisis



7



8

Método Descendente LL(1) Componentes para el análisis

Pasos para el Método LL(1)

1. Escribir adecuadamente la gramática.

2. Calcular el conjunto de FIRST'S (PRIMEROS) y FOLLOW'S (SIGUIENTES).

3. Construir la tabla de Análisis Sintáctico.

4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis.

9

Compiladores (Análisis Sintáctico V - Edgardo A. Franco)


9

1. Escribir adecuadamente la

gramática • Para poder utilizar un analizador descendente no recursivo

la gramática debe cumplir con:

• No debe tener ambigüedad

• No debe ser recursiva por la izquierda

• Debe estar factorizada




10

Símbolo PRIMERO

Si X es terminal PRIMERO(x) = {x}

Si X → ε Producción

Añadir ε al PRIMERO (x)

Si X es No Terminal y X →YZW

1. Si Y → ε añadir el PRIMERO (Z) 2. Si Z → ε añadir el PRIMERO (W) 3. Si todos generan ε entonces añadir →ε,

de lo contrario no se agrega.

2. Calcular el conjunto de PRIMEROS




11



2 . Calcular el conjunto de PRIMEROS • Ejemplo 1

• E → T E’

• E’ → + T E’ | ε

• T → F T’

• T’ → * F T’ | ε

• F → ( E ) | ident

PRIMERO(E) = PRIMERO(TE’)

PRIMERO(E’) = { + , ε}

PRIMERO(T) = PRIMERO(FT’)

PRIMERO(T’) = { * , ε}

PRIMERO(F) = { ( , ident }

*como PRIMERO(T) no incluye ε

PRIMERO(E)=PRIMERO(T)

*como PRIMERO(F) no incluye ε

PRIMERO(T)=PRIMERO(F)

PRIMERO(E) = { ( , ident }

PRIMERO(E’) = { + , ε }

PRIMERO(T) = { ( , ident }

PRIMERO(T’) = { * , ε }



12



2 . Calcular el conjunto de PRIMEROS • Ejemplo 2

• A → Aa | BCD

• B → b | ε

• C → c | ε

• D → d | Ce

PRIMERO(A) = {b, c, d, e }

PRIMERO(B) = { b, ε }

PRIMERO(C) = { c , ε }

PRIMERO(D) = { d, c , e}

PRIMERO(A) = PRIMERO(A) U PRIMERO(BCD)

PRIMERO(B) = { b , ε}

PRIMERO(C) = { c , ε}

PRIMERO(D) = {d} U PRIMERO(Ce)

*como PRIMERO(B) incluye ε y como PRIMERO(C) incluye

ε PRIMERO(A)=PRIMERO(BCD) *

*como PRIMERO(C) incluye ε PRIMERO(D)=PRIMERO(Ce)


13

Símbolo SIGUIENTE

Si B es símbolo inicial SIGUIENTE ( B) = { $}

Si A → α B M Producción

1. SIGUIENTE (B) = PRIMERO(M) excepto ε. 2. Si el PRIMERO(M) contiene ε entonces añadir el SIGUIENTE (A) a SIGUIENTE (B)

Si A → B Producción

Añadir el SIGUIENTE (A) a SIGUIENTE (B)



2. Calcular el conjunto de SIGUIENTES


14



2 . Calcular el conjunto de SIGUIENTES • Ejemplo 1

• E → T E’

• E’ → + T E’ | ε

• T → F T’

• T’ → * F T’ | ε

• F → ( E ) | ident

SIGUIENTE(E) = $ U PRIMERO())

SIGUIENTE(E’) = SIGUIENTE(E) U SIGUIENTE(E’)

SIGUIENTE(T) = PRIMERO(E’) y ε esta en PRIMERO(E’)

se añade SIGUIENTE(E) y SIGUIENTE(E’)

SIGUIENTE(T’) = SIGUIENTE(T) U SIGUIENTE(T’)

SIGUIENTE(F) = PRIMERO(T’) y como incluye la ε se añade

SIGUIENTE(T’) y SIGUIENTE(T)

PRIMERO(E) = { ( , ident }

PRIMERO(E’) = { + , ε }

PRIMERO(T) = { ( , ident }

PRIMERO(T’) = { * , ε }


SIGUIENTE(E) = { $ , )}

SIGUIENTE(E’) = {$, )}

SIGUIENTE(T) = { +, $, )}

SIGUIENTE(T’) = { +, $, )}

SIGUIENTE(F) = { *, +, $, )}


15



2 . Calcular el conjunto de SIGUIENTES • Ejemplo 2

• A → Aa | BCD

• B → b | ε

• C → c | ε

• D → d | Ce

SIGUIENTE(A) = {$, a }

SIGUIENTE(B) = { c, d, e }

SIGUIENTE(C) = { e, d, c}

SIGUIENTE(D) = { $, a}

SIGUIENTE(A) = {$} U PRIMERO (a)

SIGUIENTE(B) = PRIMERO(C) y como PRIMERO(C)

incluye ε =PRIMERO (CD)

SIGUIENTE(C) = PRIMERO(e) U PRIMERO (D)

SIGUIENTE(D) = SIGUIENTE(A)

PRIMERO(A) = {b, c, d, e }

PRIMERO(B) = { b, ε }

PRIMERO(C) = { c , ε }

PRIMERO(D) = { d, c , e}


16

3. Construir la tabla de Análisis Sintáctico

Símbolos

No Terminales

Símbolo Terminal




17


Se colocan las

producciones

que corresponden

a los datos

obtenidos del

cálculo del PRIMERO




18

4. Hacer el análisis de sintáctico por medio

de la pila y la tabla de análisis

Pila Entrada

. . .




19

Ejemplo LL(1)

Partiendo de la Gramática:

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’

1. Es una gramática adecuada para el análisis LL(1)



20

Ejemplo LL(1)

2. Cálculo del conjunto de PRIMEROS

E → T E′

E′ → ‘+’ T E′

| ε

T → F T′

T′ → ‘x’ F T′

| ε

F → num

| ‘(‘ E ‘)’

Símbolo

No Terminal PRIMERO

E num, (

E’ +, ε

T num, (

T’ x, ε

F num, (



21

Ejemplo LL(1)

2. Cálculo del conjunto de SIGUIENTES

E → T E′

E′ → ‘+’ T E′

| ε

T → F T′

T′ → ‘x’ F T′

| ε

F → num

| ‘(‘ E ‘)’

Símbolo

No Terminal SIGUIENTE

E $ , )

E’ $ , )

T +, $, )

T’ + ,$, )

F x, +, $, )



22


num + x ( ) $

E E→T E’ E→T E’

Símbolo

No Terminal PRIMERO

E num, (

PRIMERO PRIMERO

E → T E′


Ejemplo LL(1)

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’


23

Colocar la producción que genera

al símbolo terminal primero,

excepto las producciones vacías


Símbolo

No Terminal PRIMERO

E’ +, ε

PRIMERO

E′ → ‘+’ T E′

num + x ( ) $


E’ E′→ ‘+’ T E′ E’→ε E’→ε


Ejemplo LL(1)

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’


24

Para el caso de los No terminales con

el símbolo ε en su conjunto de

primeros (Las producciones vacías se

colocan según el conjunto de

siguientes)

Símbolo


E’ $ , )


num + x ( ) $


E’ E′→ ‘+’ T E′

T T→F T’ T→F T’

T’ T'→‘x’F T’

F F → num F→‘(‘ E ‘)’


Ejemplo LL(1)

Símbolo

No Terminal PRIMERO

E num, (

E’ +, ε

T num, (

T’ x, ε

F num, (

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’

Colocar la producción que genera

al símbolo terminal primero,

excepto las producciones vacías


25


num + x ( ) $


E’ E′→ ‘+’ T E′ E’→ε E’→ε


T’ T’→ε T→‘x’F T’ T’→ε T’→ε

F F → num F→‘(‘ E ‘)’


Ejemplo LL(1)

Símbolo

No Terminal PRIMERO

E num, (

E’ +, ε

T num, (

T’ x, ε

F num, (

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’

Símbolo


E $ , )

E’ $ , )

T +, $, )

T’ + ,$, )

F x, +, $, )

Para el caso de los No terminales con

el símbolo ε en su conjunto de

primeros (Las producciones vacías se

colocan según el grupo de siguientes)


26


num + x ( ) $


E’ E′→ ‘+’ T E′ E’→ε E’→ε



F F → num F→‘(‘ E ‘)’


Ejemplo LL(1)

Símbolo

No Terminal PRIMERO

E num, (

E’ +, ε

T num, (

T’ x, ε

F num, (

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’


27

4. Hacer el análisis de sintáctico por medio de la pila y la tabla de

análisis

Pila Entrada

$ E num + num x num $

num ‘+’ num ‘x’ num

Colocar $ y

el símbolo inicial

Colocar la cadena

de entrada y $


Ejemplo LL(1)


28

Pila Entrada

$ E

$ E’ T

num + num x num $

num + num x num $

num

E E→T E’

Se busca el símbolo terminal y el no

terminal, remplazándolo por la

producción que le corresponda.

Colocándola de izquierda a derecha 29


Ejemplo LL(1) num + x ( ) $


E’ E′→ ‘+’ T

E′ E’→ε E’→ε


T’ T’→ε T→‘x’F

T’ T’→ε T’→ε

F F → num F→‘(‘ E

‘)’


29

Pila Entrada

$ E

$ E’ T

$ E’ T’ F

$ E’ T’ num

num + num x num $

num + num x num $

num + num x num $

num + num x num $

Cuando se llega a una coincidencia, se eliminan ambos,

y se continua con el análisis




E’ E′→ ‘+’ T



T’ T’→ε T→‘x’F

T’ T’→ε T’→ε


‘)’


30

Pila Entrada

$ E

$ E’ T

$ E’ T’ F

$ E’ T’ num

$ E’

$ E’ T +

$ E’ T’ F

. . .

num + num x num $

num + num x num $

num + num x num $

num + num x num $

+ num x num $

+ num x num $

num x num $

. . . 31




E’ E′→ ‘+’ T





‘)’


31

4. Proceso de análisis LL(1)

Pila Entrada

. . .

$ E’ T’ F

$ E’ T’ num

$ E’ T’ F x

$ E’ T’ F

$ E’ T’ num

$ E’ T’

$ E’

$ E’

$

$

. . .

num x num $

num x num $

x num $

num $

num $

$

$

$

$

$

Se acepta la

cadena si se

logra eliminar

de la pila y la

entrada, todos

los símbolos.

De lo contrario

no se acepta

la cadena.


Ejemplo LL(1)


32

• Si no es posible realizar el cruce de símbolos durante la

tabla, la gramática es ambigua o no es apta para el

análisis LL(1).

• Si nunca es posible llegar a una cadena valida, entonces

la cadena es recursiva por la izquierda

• Si al realizar el cruce en la tabla no existe producción a

aplicar entonces la cadena no pertenece a la gramática.

Observaciones del análisis LL(1)


33

Ejercicio 1

•Partiendo de la siguiente gramática, evalúe las

siguientes cadena aaab, a, ab, abbbb

•X → a | Y

•Y → Y b | a

•Hacerlo por el análisis LL(1). Escriba adecuadamente la

gramática. Calcule el PRIMERO, construya la tabla de

análisis sintáctico, evalúe con la pila.



34

Ejercicio 1

• X → a | Y

• Y → Y b | a

• Gramática ambigua al hacer el análisis LL(1)

este no opera con cadenas validas.

•Quitando ambigüedad

•X →aY

•Y →bY| ε



35

• Partiendo de la siguiente gramática, evalúe la siguientes cadenas aaaabb, aaaab.

•X →Y T

•Y → Z Z

•Z → a a

•T → Tb | b

•Hacer el análisis LL(1).

•Escriba adecuadamente la gramática. Calcule el PRIMERO, construya la tabla análisis sintáctico, evalúe con la pila.


Ejercicio 2


36

•Obtenga la tabla de análisis sintáctico LL(1) para la gramática que se da a continuación.

•Aplique análisis sintáctico LL(1) a las cadenas:

aab$, abbcab$ y abbbab$


Ejercicio 3


37

|

|

|

|

cD

bC

aB

bbDaA

aABCS

•Obtenga la tabla de análisis sintáctico LL(1) para la gramática que se da a continuación.

E → TE'

E' → +TE'|-TE'|ε

T → PT'

T' → *PT'|/PT'|ε

P → FP'

P' → ^FP'|ε

F → (E)|num|var|sin(E)|cos(E)|tan(E)|log(E)|ln(E)|exp(E)

• Aplique análisis sintáctico LL(1) a la cadena: ((num+var)*sin(var)/log(num))-var.


Ejercicio 4


38

•Entregar vía página web con el titulo

"Ejercicios LL(1)", a más tardar el día

Lunes 23 de mayo de 2011 a las

23:59:59 hrs.

•Deberán estar resueltos a detalle y deben ser

en formato digital.


Ejercicios 3 y 4


39

compiladores - profr. edgardo adrián franco martínez contenido

Documents