View
15
Download
0
Category
Preview:
Citation preview
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
Recommended