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 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

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 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

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

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

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 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

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 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

7

8 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

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)

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

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 Compiladores (Análisis Sintáctico V - Edgardo A. Franco)

Pasos para el Método LL(1)

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

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 Compiladores (Análisis Sintáctico V - Edgardo A. Franco)

Pasos para el Método LL(1)

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

11

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

Pasos para el Método LL(1)

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’) = { * , ε }

PRIMERO(F) = { ( , ident }

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

12

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

Pasos para el Método LL(1)

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)

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

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)

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

Pasos para el Método LL(1)

2. Calcular el conjunto de SIGUIENTES

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

14

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

Pasos para el Método LL(1)

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’) = { * , ε }

PRIMERO(F) = { ( , ident }

SIGUIENTE(E) = { $ , )}

SIGUIENTE(E’) = {$, )}

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

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

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

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

15

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

Pasos para el Método LL(1)

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}

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

16

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

Símbolos

No Terminales

Símbolo Terminal

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

Pasos para el Método LL(1)

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

17

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

Se colocan las

producciones

que corresponden

a los datos

obtenidos del

cálculo del PRIMERO

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

Pasos para el Método LL(1)

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

18

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

de la pila y la tabla de análisis

Pila Entrada

. . .

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

Pasos para el Método LL(1)

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

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 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

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 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

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 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

22

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

num + x ( ) $

E E→T E’ E→T E’

Símbolo

No Terminal PRIMERO

E num, (

PRIMERO PRIMERO

E → T E′

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

Ejemplo LL(1)

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’

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

23

Colocar la producción que genera

al símbolo terminal primero,

excepto las producciones vacías

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

Símbolo

No Terminal PRIMERO

E’ +, ε

PRIMERO

E′ → ‘+’ T E′

num + x ( ) $

E E→T E’ E→T E’

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

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

Ejemplo LL(1)

E → T E′

E′ → ‘+’ T E′ | ε

T → F T′

T′ → ‘x’ F T′ | ε

F → num | ‘(‘ E ‘)’

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

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

No Terminal SIGUIENTE

E’ $ , )

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

num + x ( ) $

E E→T E’ E→T E’

E’ E′→ ‘+’ T E′

T T→F T’ T→F T’

T’ T'→‘x’F T’

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

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

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

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

25

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

num + x ( ) $

E E→T E’ E→T E’

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

T T→F T’ T→F T’

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

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

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

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

No Terminal SIGUIENTE

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)

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

26

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

num + x ( ) $

E E→T E’ E→T E’

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

T T→F T’ T→F T’

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

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

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

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 ‘)’

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

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 $

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

Ejemplo LL(1)

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

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

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

Ejemplo LL(1) num + x ( ) $

E E→T E’ E→T E’

E’ E′→ ‘+’ T

E′ E’→ε E’→ε

T T→F T’ T→F T’

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

T’ T’→ε T’→ε

F F → num F→‘(‘ E

‘)’

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

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

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

Ejemplo LL(1) num + x ( ) $

E E→T E’ E→T E’

E’ E′→ ‘+’ T

E′ E’→ε E’→ε

T T→F T’ T→F T’

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

T’ T’→ε T’→ε

F F → num F→‘(‘ E

‘)’

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

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

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

Ejemplo LL(1) num + x ( ) $

E E→T E’ E→T E’

E’ E′→ ‘+’ T

E′ E’→ε E’→ε

T T→F T’ T→F T’

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

F F → num F→‘(‘ E

‘)’

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

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.

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

Ejemplo LL(1)

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

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)

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

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 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

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 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

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.

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

Ejercicio 2

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

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$

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

Ejercicio 3

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

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.

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

Ejercicio 4

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

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.

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

Ejercicios 3 y 4

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

39