Analisis semantico

Introducción

Análisis Semántico
José M. Castaño
Teoría de Lenguajes 2011
Departamento de Computación
FCEyN, UBA

Compiladores
Introducción

Análisis Léxico
Análisis Sintáctico
Análisis Semántico
Generación
Código Intermedio
Optimización
Generación Código

Introducción
Introducción

• Reconocer/Generar un lenguaje independiente de

contexto (CFL).
• Poder expresivo CFL• Análisis léxico (tokenización, lexers, scanners)
• Análisis sintáctico

• Mientras se reconoce se construye árbol (AST), para

hacer algo más ...

Introducción
Introducción

• Análisis léxico: condiciones de buena formación a nivel

palabra
• Análisis sintáctico: condiciones de buena formación a

nivel estructural.
• Análisis semántico: condiciones de buena formación a

nivelinterpretación.

ASTs: Abstract Syntax Trees
Introducción

• árbol para codificar la estructura lógica (Abstracción de

la sintaxis particular)
• Elimina símbolos inútiles
• Elimina nodos internos
• Traducción última.

Cómo se construye el AST?
Introducción

• Acciones semánticas
• Asociar el código con cada producción
• Mientras se hace el análisis sintáctico se ejecuta elcódigo para construir el AST
• El orden exacto del código depende del parsing
• Traducción dirigida por la sintaxis

Análisis Semántico
Introducción

• Verificar que el input tenga un significado o

interpretación.
• Verificar propiedades que no se pueden verificar al

nivel sintáctico.
• Desafío:
• Rechazar el mayor númeor de programas sin

interpretación
• Aceptar el mayor número deprogramas correctos.
• Hacerlo lo más rápido posible.

• También guardar información que puede ser usada

posteriormente (alcance de variables, herencia, etc.)

Análisis Semántico: Más allá de
CFL

Introducción

Algunas preguntas...
• Se declaró x antes de usarlo?
• Se declaró x pero no se usa?
• Es el tipo de una expresión el que corresponde?
• La referencia a una posición en unarray está dentro de

sus límites?
• ...

Más allá de CFL
Introducción

• Usamos una gramática de mayor poder expresivo que

una CFG?
• Usamos una estructura de datos adicional? Una pila

semántica?
• Necesitamos guardar la información semantica.
• Gramáticas de Atributos

• Usamos métodos ad-hoc?

Más allá de CFL
Introducción

• Importancia del formalismo de las gramáticasde

atributos
• Claridad formal
• Base para la práctica ad-hoc

• Limitaciondes de las GA motivan la práctica
• Computación no-local
• Necesidad de información centralizada

Análisis Semántico
Introducción

Dos enfoques:
• Gramática de Atributos
• Aumentar CFG
• Traducción dirigida por la sintaxis
• Recorrer recursivamente el AST
• Construir el AST
• Usar funciones y recursiónpara explorar el árbol.

Propagación de la información
Introducción

• El análisis semántico requiere comparar información

que se tiene en distintas partes del árbol de derivación.
• Comparar declaración de una variable con asignación

de la misma variable.
• La información se propaga hacia un nodo común para

llegar hasta el punto donde se la necesita.

Atributos
Introducción• Para poder realizar un movimiento de información es

necesario extender la gramática
• Permitir que los símbolos (tanto terminales como no

terminales) tengan información asociada: atributo.
• Cada símbolo puede tener asociado uno o más

atributos.
• Notación similar a Java: atributos de un objeto o en C:

componente de una estructura :
• nombreSímbolo.nombreAtributo
• Ej: noterminal E, con atributo val: E.val

Gramática de Atributos
Introducción

• Una CFG aumentada con atributos
• Cada símbolo gramatical tiene un conjunto de atributos

asociados.
• Cada producción tiene una regla semántica asociada
• Traducción Dirigida por la Sintaxis (SDD)
• Usar los atributos para el análisis/traducción

semántica.
• Chequeo de tipos.
• Generación del código...