View
61
Download
1
Category
Preview:
Citation preview
Procesadores de lenguajeEjercicios Análisis semántico
Salvador Sánchez, Daniel RodríguezDepartamento de Ciencias de la ComputaciónUniversidad de Alcalá
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 1 (propuesto)
• A partir de gramática de abajo se pide: – Mostrar el árbol sintáctico decorado para la cadena de entrada “aaaa”– Elaborar el grafo de dependencias para la evaluación en el orden
correcto de todos los atributos.– Indique la salida que produce el análisis de la entrada “aaaa”
A.v = A.x + 1A → a
A.x = 0 S.v = A.v
S → A
S0.v = A.vA.x = S1.v
S → AS
printf(“%d”,S.v);S’→S
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 2: Binario a decimal
• Considerar la siguiente gramática que genera números binarios:
A → AB | B
B → 0 | 1
• Obtener la gramática con atributos que al analizar un número binario calcule su equivalente en decimal.
• Mostrar el árbol para la cadena de entrada 101
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 2: Binario a decimal
• Gramática con atributos:
A → AB { A0.val = 2*A1.val + B.val }
A → B { A.val = B.val}
B → 0 { B.val = 0 }
B → 1 { B.val = 1 }
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 2: Binario a decimal
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 3 (propuesto)
• Considerar la siguiente gramática:
num → dig num | digdig → 0 | 1 | … | 9
• Añadirle atributos y acciones semánticas para que calculesu valor en decimal
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 4: octal-decimal
• Dada la gramática de la página siguiente:
– Dibujar las gráficas de dependencias para cada regla– Dibujar el árbol sintáctico para la expresión 345o– Dibujar la gráfica de dependencia para el árbol sintáctico anterior y
establecer una clasificación topológica para el mismo– Generar el código correspondiente a las reglas semánticas asociadas al
análisis de la expresión anterior
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio octal-decimal (semántica)
dígito.val = if dígito.base == 8 then error else9
dígito → 9
dígito.val = if dígito.base == 8 then error else8
dígito → 8
dígito.val = 7dígito →7
…...
dígito.val = 0dígito → 0
num.val = dígito.valdígito.base = num.base
num → dígito
num1.val =if dígito.val = error or num2.val = errorthen errorelse num2.val * num1.base + dígito.val
num2.base= num1.basedígito.base = num1.base
num → num dígito
carbase.base = 10carbase → d
carbase.base = 8carbase → o
num-base.val = num.val; num.base = carbase.base
num-base → num carbase
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Octal-decimal. (Graf. de dependencias)
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Octal-decimal. (Árbol sintáctico 345o)num_base
num carbase
num digito
num digito
digito
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Octal-decimal. (Gráf. de dependencia)
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Octal-decimal. (Código intermedio)
a1=8; //carbase.base=8a2=a1; //m.base=8a3=a2; //m.base=8a4=a3; //m.basea5=a4; //digito.base=8a6=3;a7=a6; a8= a3;a8=4;if (a9=error||a7==error) then a10=error else a10=a7*a3+a9;// a10=3*8+4=28
a11=a2; //a11=8a12=5;if (a12=error||a10==error) then a13=error else a13=a10*a2+a12;// a13=28*8+5a13=a13;
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 5 (propuesto)
• A partir de la gramática siguiente, amplíala con atributos sintetizados de manera que, cuando se reduzca por S, se muestre el número de a y b que contiene una frase cualquiera del lenguaje generado por la gramática:
S → (A)A → A , DA → DD → aD → bD → (A)
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 6 (propuesto)
• Amplie la gramática siguiente con atributos sintetizados para que obtenga el número decimal correspondiente al número binario de entrada:
S → CC → 0 C C → 1 CC → 0 C → 1
• Construya el árbol sintáctico para la entrada 110101 incluyendo infomación topológica para nodos y hojas.
• Evalúe el árbol aplicando las reglas semánticas.
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 6.
• Amplíe la gramática siguiente con atributos sintetizadospara que calcule el valor mínimo y máximo de una lista de enteros.
S → LL → num , LL → num
• Presente las diferentes acciones semánticas para la entrada siguiente:
7, 8, 5, 3 $
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 6. (Solución)
L.maximo = num.valor
L.minimo = num.valor
L → num
L0.minimo = MIN (num.valor, L1.minimo) L0.maximo = MAX (num.valor, L1.maximo)
L0 → num , L1
S.maximo = L.maximo
S.minimo = L.minimo
S → L
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 7a
• Complete la gramática del ejercicio 7a con acciones semánticas que permitan calcular el número de listas de una expresión de entrada.
L → (A)A → A (A) | €
• Tenga en cuenta que una lista está formada por una pareja de paréntesis balanceados, por lo que:
()(()) 3 listas
(()) 2 listas
()() 2 listas
(()(())) 4 listas
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 7a. (Solución)
A.listas_despues = A.listas_antesA → €
A1.listas_antes = A0.listas_antes
A2.listas_antes = A1.listas_despues + 1
A0.listas_despues = A2.listas_despues
A → A(A)
A.listas_antes = 1
L.total_listas = A.listas_despuesL → (A)
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 7b
• Complete la gramática siguiente con acciones semánticas que permitan calcular la profundidad de una expresión de entrada, entendida como el máximo número de anidamiento de todas las listas de la expresión.
• Ejemplos:
()(()) Profundidad 2
(()) Profundidad 2
()() Profundidad 1
(()(())) Profundidad 3
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 7b . (Solución)
A0.p = 0A → €
si A1.p > A2.p entonces A0.p = A1.p
si_no A0.p = A2.p + 1A → A(A)
L.p = A.p + 1L → (A)
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 7b (Árbol sintáctico).
Procesadores de lenguaje – Tema 4: Análisis semánticoSalvador Sánchez, Daniel Rodríguez
Ejercicio 7b. Profundidad
p=0 p=0
p=0p=1
p=1
p=2
Recommended