Tema 4: Análisis semántico
Horas de trabajo estimadas y calendario de clases
Posible planificación del trabajo al ritmo de las clases presenciales:
11/02 - 18/02 - 04/03 - 25/03 - Para saber más
Plan de trabajo y bibliografía recomendada
- 4.1 Esquemas de Traducción Dirigidos por la Sintaxis (ETDS). Integración con Analizadores Sintácticos RLL(1).
Semana del 11/02/2010
- Un objetivo importante de este tema es aprender a
escribir Esquemas de Traducción Dirigidos por la Sintaxis
compatibles con las técnicas de análisis descendente RLL(1) del
tema anterior. Ello incluye el empleo de atributos sintetizados
y de atributos heredados.
- Haz una primera lectura (sin preocuparte si de momento no
entiendes todo) de los apartados 4.2 "Traducción dirigida por
sintaxis" y 4.7 "Definiciones L-atribuidas" del libro
"Compiladores y procesadores de lenguaje" de Jiménez
Millán.
- Mira de momento solamente el ejercicio 7 de esta recopilación de
ejercicios sobre esquemas de traducción en exámenes de
Compiladores e Intérpretes. En clase veremos variaciones
del mismo para ilustrar esos apartados del libro.
Mira también esta posible solución del ejercicio 7 (es otra versión, ampliada artificialmente para probarla con Metacomp).
- Esta semana no hay más ejercicios propuestos, dedica el
tiempo a la práctica 3 y a
completar los ejercicios del tema
3 que te falten.
- En la práctica 3 se te da
hecho un ETDS que construye un AST, para un lenguaje de entrada
que irás enriqueciendo en la práctica 4. De momento debes
completar, sobre todo, lo que falta en los nodos del AST para
obtener el intérprete MINIINT. Ello te permitirá familiarizarte
con el lenguaje de entrada inicial, la implementación y las
herramientas de la práctica 4, y con ello abordar la misma con
más soltura.
El plan de trabajo que sigue consiste en dedicar el trabajo de la práctica 3 a la implementación del AST y, en paralelo, ir aprendiendo con los ejercicios y ejemplos del tema 4 cómo se escribe un ETDS. Posteriormente, en la práctica 4, haremos ejercicios que requerirán modificar ambas cosas.
Semana del 18/02/2010
- Resuelve primero este boletín con algunos ejercicios
básicos sobre esquemas de traducción de la asignatura IG29,
ordenados por dificultad creciente.
Después compara tus soluciones con las de este mismo boletín, incluyendo las soluciones (en él se utiliza pseudocódigo en las acciones semánticas).
- De esta
recopilación de
ejercicios sobre esquemas de traducción en exámenes de
Compiladores e Intérpretes, completa solamente los
ejercicios que aparecen resueltos a continuación. Tras intentar
cada uno, mira la
solución y complétala indicando para cada atributo si es
heredado o sintetizado, su tipo y qué representa. Aquí se
utiliza la notación para las acciones semánticas que se
describe en el manual
de Metacomp, si quieres probar alguna puedes hacerlo
añadiendo la especificación léxica y el código de usuario como
en la solución
del ejercicio 7 anterior.
Ten en cuenta que cuando el enunciado pide añadir acciones semánticas a una gramática dada hay que resolver el ejercicio usando la gramática que nos dan, no otra equivalente; y si se pide escribir la gramática de modo que sea incontextual, sin o con partes derechas regulares, LL(1) o RLL(1), hay que atenerse a eso.
- Abrir solución
del ejercicio 4.
- Abrir solución
del ejercicio 11.
- Abrir solución
del ejercicio 2 (partiendo de esta solución del
ejercicio 5 del tema
3.1).
- Abrir solución
del ejercicio 8 (observa que ésta es muy similar
a una posible solución de la segunda opción del
ejercicio 6 del boletín de
modelado sintáctico del tema 3.1, como
alternativa a esta solución de la
primera opción y en combinación con el ejercicio 4
del tema 3.2, en el que se demostraba que la
gramática es LL(1); todo ello es un ejemplo de un
problema que se puede resolver con el modelado
sintáctico o combinando el modelado sintáctico con el
semántico).
- Abrir solución del ejercicio 3.
- Abrir solución
del ejercicio 4.
Semana del 04/03/2010
- Lee la introducción a Metacomp y los ejemplos de las
secciones 6 y 7 de estos apuntes de análisis
semántico de J. M. Vilar
(que es uno de los coautores de Metacomp) como complemento
al manual
de Metacomp. Mira también bien la sección 5.1 del
manual, para conocer el convenio de numeración de los
terminales y no terminales que se usa con Metacomp.
Opcionalmente, mira también estos ejemplos más simples, que ilustran las ideas básicas e incluyen funciones main diferentes, y pruébalos o modifícalos como creas conveniente.
- Resuelve estos ejercicios de los exámenes de los dos
ultimos cursos; en ellos se parte de una gramática LL(1) o
RLL(1) dada, y el resultado debe ser un ETDS compatible
con las técnicas de análisis descendente predictivo.
La mayoría de las soluciones que siguen se han implementado en lenguaje Metacomp, de modo que puedas ejecutarlas, modificarlas si quieres probar alguna variación, y utilizarlas como ejemplos adicionales de uso de Metacomp.
En algunas falta la descripción de los atributos utilizados que se pedía en el examen: intenta completarla tú, tomando como ejemplo, si hace falta, las que lo incluyen.
- Control
de análisis semántico del grupo TE2 del curso
2007/2008 (examen de junio 2006 de la asignatura
F54).
- Pregunta 4 en el examen
de junio 2008.
- Pregunta 4 en el examen
de diciembre 2008.
- Pregunta 4 en el examen
de septiembre 2008.
- Pregunta 4 en el examen
de junio 2009.
- Pregunta 4 en el examen
de septiembre 2009.
- Control de análisis semántico del grupo TE2 del curso 2008/2009.
- Control
de análisis semántico del grupo TE2 del curso
2007/2008 (examen de junio 2006 de la asignatura
F54).
- Este es otro tipo de problema, en el que se pide el
modelado completo mediante una gramática o mediante un
esquema de traducción. Aunque el enunciado no pide una
solución compatible con las técnicas de análisis
descendente predictivo, lo interesante sería conseguir
eso, inténtalo:
- Pregunta 3 en el examen de diciembre 2006 (sesión de refuerzo del 24/06/2010).
- Evaluación del tema 4 en el itinerario A (grupo TE2): jueves 25/03/2010.
La materia que será objeto de evaluación puntuable ese día llega hasta aquí, aunque el tema sigue y el resto se incluirá en otras pruebas de evaluación del curso. Cada estudiante debe complementar el trabajo realizado en clase con el trabajo no presencial propuesto aquí, contando con la ayuda del profesor en tutorías para cualquier explicación adicional que haga falta.
- 4.2 El Arbol de Sintaxis Abstracta (AST, Abstract Syntax Tree). Comprobaciones semánticas. La tabla de símbolos (TDS). Comprobaciones de tipos. Interpretación.
Semana del 25/03/2010
- Este apartado del tema lo hemos ido introduciendo ya a lo
largo de las prácticas de la asignatura. Como complemento
de eso, lee ahora las secciones 3 a 5 de los apuntes de análisis
semántico de Vilar.
- Como trabajo opcional y recomendable, complementario del
que has hecho en las prácticas, implementa de nuevo tu intérprete MICROCALC,
reutilizando tus clases de nodos del AST de la práctica 1
y haciendo uso ahora de un ETDS para construir el AST al
analizar la entrada. Haz lo mismo para implementar de
nuevo tu intérprete
POLICALC.
- De estos documentos de la asignatura IG29 te puede interesar estudiar y/o realizar estos boletines de prácticas sobre MMPor, aunque no entran en la planificación de tiempo prevista en la asignatura II26.
- Otros ejercicios opcionales.
Resto del curso
Los siguientes ejercicios tampoco se incluyen en las horas previstas, pero son recomendables y se pueden discutir en tutorías o en las sesiones de refuerzo con quien quiera seguir practicando.
- Pregunta 4 en el examen
de diciembre 2009 (sesión de refuerzo del 14/06/2010).
- Control
de análisis semántico del grupo TE1 del curso
2007/2008 (sesión de refuerzo del 22/03/2010).
- Ejercicio 9 de esta recopilación de ejercicios sobre esquemas de traducción en exámenes de Compiladores e Intérpretes (sesión de refuerzo del 21/06/2010).
- Otras fuentes de información.
Si quieres ver otras explicaciones de este tema:
- Para ver una presentación más completa y muy formal,
consulta el capítulo 5 ("Traducción dirigida por la
sintaxis") del libro clásico
"Compiladores: principios, técnicas y herramientas" de
A.
Aho, R.
Sethi y J.
Ullman, en su edición de 1990 (sobre todo la sección
5.4).
- El capítulo 6 ("Análisis semántico") del libro "Construcción de compiladores" de K. Louden contiene una presentación alternativa, si prefieres un enfoque menos formal.
- Un objetivo importante de este tema es aprender a
escribir Esquemas de Traducción Dirigidos por la Sintaxis
compatibles con las técnicas de análisis descendente RLL(1) del
tema anterior. Ello incluye el empleo de atributos sintetizados
y de atributos heredados.