Compiladores e Intérpretes Análisis Semántico IIlc/cei/downloads/Clases/Clase 7... ·...
Transcript of Compiladores e Intérpretes Análisis Semántico IIlc/cei/downloads/Clases/Clase 7... ·...
Compiladores e Intérpretes
Análisis Semántico IISebastian Gottifredi
Universidad Nacional del Sur
Departamento de Ciencias e Ingeniería de la Computación
2019
1
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Repaso
2
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Repaso
• El análisis léxico y sintácticos son los encargados de validar y entender la forma estructural del programa fuente
• El análisis semántico es el encargado validar y entender el significado del programa
• Para esto el analizador semántico debe:
• Recolectar, entender y controlar todas las entidades declaradas
Chequeo de Declaraciones
• Recolectar, entender y controlar todas las sentencias asociadas a las entidades recolectadas
Chequeo de Sentencias
3
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Repaso
• Hay dos alternativas para implementar el analizador
semántico:
• Intercalado con el analizador sintáctico (una pasada)
• Separado del analizador sintáctico (mas de una pasada)
• En cualquier caso, es necesario realizar acciones especiales
dentro del analizador sintáctico
• Las Gramáticas de Atributos son las herramientas formales
utilizadas para diseñar estas acciones en el analizador sintáctico
4
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Repaso
• Las gramáticas de atributos asocian acciones a las
producciones de la gramática
• Las acciones se representan con porciones de código que utilizan
atributos asociados a los símbolos de la producción.
• Hay atributos Sintetizados, Heredados e Intrínsecos
• Las acciones se ejecutan durante la derivación cuando tengamos
todos los valores de los atributos utilizados para el computo
• En el Árbol de Derivación al etiquetar los nodos con el valor que toman sus
atributos podemos ver como fluye la información.
5
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Repaso
6
D
T
pInt
L
Id R
Id R
Id R
int a1 v1 x
tipo=tInttipo=tInt
tipo=tInt
guardar(a1,tint)
tipo=tInt
guardar(v1,tint)
tipo=tInt
guardar(x,tint)
Lex=a1
Lex=v1
Lex=x
Producción Reglas Semanánticas
S → D$
D → T L {L.tipo = T.tipo}
T → idC {T.tipo = idC.nombre}
T → pString {T.tipo = tStr}
T → pInt {T.tipo = tInt}
L → id R {Guardar(id.lex,L.tipo)}{R.tipo = L.tipo}
R1 → id R2 {Guardar(id.lex, R1.tipo)}{R2.tipo = R1.tipo}
R → e
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Esquemas de Traducción
7
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Esquemas de Traducción
• Para decorar los arboles seguimos un orden al aplicar las
acciones vinculadas a las producciones
• Los esquemas de traducción (EDT) nos permiten embeber las
acciones en la gramática para indicar explícitamente el orden
• Siguiendo una estrategia de primero en profundidad de izquierda a
derecha para recorrer el arbol.
• En un EDT vamos a tener producciones, por ejemplo, de la forma:
8
A → B {C.y = B.x} C {A.z = C.w}
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Esquemas de Traducción
9
Producción Reglas Semanánticas
S → D$
D → T L {L.tipo = T.tipo}
T → idC {T.tipo = idC.nombre}
T → pString {T.tipo = tStr}
T → pInt {T.tipo = tInt}
L → id R {Guardar(id.lex,L.tipo)}{R.tipo = L.tipo}
R1 → id R2 {Guardar(id.lex, R1.tipo)}{R2.tipo = R1.tipo}
R → e
Esquema de Traducción (EDT)
S → D$
D → T L
T → idC {T.tipo = idC.nombre}
T → pString {T.tipo = tStr}
T → pInt {T.tipo = tInt}
L → id R
R1 → id R2
R → e
Esquema de Traducción (EDT)
S → D$
D → T {L.tipo = T.tipo} L
T → idC {T.tipo = idC.nombre}
T → pString {T.tipo = tStr}
T → pInt {T.tipo = tInt}
L → id R
R1 → id R2
R → e
Esquema de Traducción (EDT)
S → D$
D → T {L.tipo = T.tipo} L
T → idC {T.tipo = idC.nombre}
T → pString {T.tipo = tStr}
T → pInt {T.tipo = tInt}
L → id {R.tipo = L.tipo}R {Guardar(id.lex,L.tipo)}
R1 → id {R2.tipo = R1.tipo}R2 {Guardar(id.lex, R1.tipo)}
R → e
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Esquemas de Traducción
• No cualquier gramática de atributos tiene un esquema de
traducción asociado
10
¿Por qué?
En una EDT un atributo heredado asociado a un símbolo
en la parte derecha de una producción solo puede
depender de atributos heredados del símbolo de la parte
izquierda o de atributos (sintetizados o heredados) de
símbolos mas a la izquierda en la parte derecha
¿Por qué?
En la EDT la evaluación
se hace de izquierda a
derecha y en profunidad
A → B C {B.x = C.y}
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Evaluando EDTs en Analizadores Sintáctico
11
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
EDTs en Analizadores Sintácticos
• El analizador construye implícitamente el árbol
• Tenemos que combinar orden de aplicación de las acciones
de la gramática con tal construcción
• En particular, en los analizadores descendentes predictivos
el árbol se construye siguiendo una política de primero en
profundidad de izquierda a derecha.
• Es el orden de evaluación que asume la EDT!
13
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
EDTs en Analizadores Sintácticos
• En los analizadores descendentes predictivos recursivos, la implementación de una EDT es directa
• ¿Cómo codificamos las acciones?
• Cuando codificamos la parte derecha, también codificamos las acciones siguiendo el orden en el que aparecen en la producción
• ¿Cómo modelamos los atributos sintetizados?
• Son retornados por el subprograma correspondiente al NT asociado al atributo
• ¿Cómo modelamos los atributos heredados?
• Son los parámetros de entrada correspondiente al NT asociado al atributo
14
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
EDTs en Analizadores Sintácticos
• Por ejemplo:
15
A → r B {C.y = B.x} C {A.z = C.w}
A(){match(“r”)x = B()w = C(x)return w}
void A(){match(“r”)B()C()
}
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
EDTs en Analizadores Sintácticos
16
Esquema de Traducción (EDT)
S → D$
D → T {L.tipo = T.tipo} L
T → idC {T.tipo = idC.nombre}
T → pString {T.tipo = tStr}
T → pInt {T.tipo = tInt}
L → id {R.tipo = L.tipo}R {Guardar(id.lex,L.tipo)}
R1 → id {R2.tipo = R1.tipo}R2 {Guardar(id.lex, R1.tipo)}
R → e
void D()Type t = T()L(t)
Type T()if(tkAct es idC)
String nom = tkAct.lexmatch(“idC”)return new TipoClase(nom)
else if(tkAct es pInt)match(“pInt”)return new TipoInt()
else if(tkAct es pString)match(“pString”)return new TipoInt()
else ERROR SINTACTICO!void L(Type tipo)
String nom = tkAct.lexmatch(“id”)R(tipo)Guardar(nom, tipo)
void R(Type tipo)if(tkAct es id)
String nom = tkAct.lexmatch(“id”)R(tipo)Guardar(nom, tipo)
else if(tkActual es $)else ERROR SINTACTICO
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Tabla de Símbolos
19
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Recopilando Información de las Entidades
• En general en los lenguajes es posible declarar varios tipos de
entidades: variables, constantes, procedimientos, funciones,
parámetros, estructuras, tipos, clases, etc.
• Cada tipo de entidad tiene sus características propias y su
comportamiento, los cuales indican como:
• Usarlas de forma correcta
• Traducirlas de forma correcta
20
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Recopilando Información de las Entidades
• A cada entidad declarada la identificamos con un nombre
(usando un identificador)
• Por ejemplo: la clase A, el método m1, la variable v1
• Luego en el programa podemos hacer uso de los nombres
de las entidades declaradas para:
• Declarar nuevas entidades
• Realizar computaciones (asignaciones, cálculos, llamadas, etc.)
21
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Recopilando Información de las Entidades
• Una de las principales actividades de un compilador es
recolectar la información declarada de las entidades
declaradas para, posteriormente cuando estas sean usadas:
• Resolver con que entidad se corresponde un identificador
• Controlar que la entidad identificada sea correctamente usada
• Realizar una traducción adecuada según la entidad que se esta
identificando
22
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Recopilando Información de las Entidades
• Usar solo los atributos de la EDT para almacenar esta información no es una buena opción
• Tenemos que pasar esta información por toda la gramática!
• Nos obliga a realizar los controles en la EDT (en una pasada)
• La idea es tener un repositorio global a la EDT donde se vaya almacenando la información de las entidades a medida que se va reconociendo sintácticamente el programa
• Que, además, en caso de ser necesario pueda recibirla el modulo encargado de los controles semánticos (segunda pasada)
Tabla de Símbolos
23
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Tabla de Símbolos
• La tabla de símbolos (TS) es una (o mas) estructura(s) central(es) para el análisis semántico
• Mantiene información de todas las entidades declaradas (clases, métodos, variables, etc.)
• Cada entidad estará asociada a una entrada
• Una entrada tendrá toda la información del tipo de entidad que representa, tanto para el análisis semántico como para la generación de código
24
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Tabla de Símbolos
• La función principal de TS es buscar y/o obtener la entrada de
una entidad en base a un nombre
• La tabla de símbolos,
• Debe ser simple de crear y administrar
• Debe ser funcional/útil al análisis semántico y la traducción
• Debe funcionar de forma eficiente ya que casi todos los aspectos
del análisis semántico y la traducción refieren a la TS
25
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
• ¿Cómo es la estructura de la Tabla de Símbolos?
• Una tabla plana con todos los nombres no es adecuada…
26
Ciertos nombres sólo son visibles/accesibles en ciertos contextos
class A{
public int x;
dynamic public void m1(){ … }
}
class B{
dynamic public void m1(){ … }
}
Es posible referenciar directamente a la
variable de instancia x
No es posible referenciar directamente a la
variable de instancia x
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
• ¿Cómo es la estructura de la Tabla de Símbolos?
• Una tabla plana con todos los nombres no es adecuada…
27
Ciertos nombres sólo son visibles/accesibles en ciertos contextos
class A{
public int x;
dynamic public void m1(){ … }
}
class B{
dynamic public void m1(){ … }
}
Es posible referenciar directamente a la
variable de instancia x
No es posible referenciar directamente a la
variable de instancia x
Un nombre puede representar entidades diferentes en diferentes
contextos.
class A{
public boolean x;
dynamic public void m1(){ … }
dynamic public void m2(int x){ … }
}
En este método el nombre x corresponde
a la variable de instancia
En este método el nombre x corresponde
al parámetro
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
• ¿Cómo resolvemos este problema?
• Anidando/Jerarquizando adecuadamente tablas con las entidades correspondientes a cada nivel!
• En general, debemos estructurar la tabla de símbolos de manera tal que en un contexto, como el cuerpo de un método, sea claro a qué nombres se puede referenciar.
• Buscaremos que la estructura de la tabla respete lo mejor posible los ambientes de declaración determinados por la sintaxis del lenguaje
29
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
• En un lenguaje con alcance estático con anidamiento de suprogramas:
• Un subprograma tiene tablas para almacenar todos las entidades declaradas dentro de el (incluidos otros subprogramas)
• En un lenguaje orientado a objetos, como java donde no podemos anidar subprogramas, la estructura de la tabla de símbolos va respetar el los ambientes de declaración:
• Una tabla con todas las clases posibles
• Un Clase tiene tablas para almacenar todos las entidades declaradas dentro de el (métodos, variables de instancia, variables de clase, constructores)
• Un Métodos/Constructor va a tener tablas para almacenar todos las entidades declaradas dentro de el (parámetros)
30
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
Tabla de
Símbolos
Clases
…
…
A
…
Tabla
…
x
…
Tabla
Tipo
Entrda
Var Inst: x
…
TipoRetorno
…
Entrada de
Metodo m1
Params
…
…
…
Tabla
p
…
Tipo
Entrda
Parametro: p
…Lugar
…
m1
…
Tabla
Params
Entrada de
Constructor A
…
…
Tabla
VarsInst
Metodos
Herencia
Entrada de
Clase: A
Ctor
…
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
32
class A extends B{int x;B y;int m1(){…}void m2(String z){…}
}
class B{int v;B(int w) {…}int m1(){…}
}
Pizarrón!
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
• La TS se va creando a medida que se realiza el análisis
sintáctico (cuando procesamos la declaración de una entidad)
• Se diseña con acciones semánticas en la EDT y se trabaja a
la TS como un elemento global
• La estructura debe provee funciones para poder insertar
una entrada con un nombre en la tabla del contexto donde
esta declarada esa entidad.
33
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
• Una característica central que debe proveer la tabla es la
capacidad de indicar cual es contexto de declaración
actual
• Cuando la estamos creando, para insertar las entradas en las
tablas adecuadas
• Cuando la estamos usando, para controlar donde empezar a
buscar cuando tenemos que buscar una entidad por su nombre
34
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura de la Tabla de Símbolos
• En algunos lenguajes hay partes de la tabla que se terminan de consolidar en el chequeo de declaraciones
• Vinculado a entidades que dependen de otras entidades que se declaran mas adelante (referencias adelante).
• Por ejemplo, en los lenguajes orientados a objetos cuando tenemos herencia no conocemos todos los métodos que tiene una clase hasta que no procesamos a sus ancestros.
• En estos lenguajes una vez finalizado el análisis sintáctico se consolidan las tablas de métodos de las clases
35
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura y Creación de la Tabla de Símbolos: MiniJava
36
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura Tabla de Símbolos en MiniJava
• Cada tipo de entrada (clase, método, variable, etc.) se puede
representar mediante una clase
• Las variables de instancia de la clase representan los
diferentes atributos que caracterizan a la entidad asociada a
la entrada.
37
Tipo tipoRetornoHash<EntradaParam> params…
EntradaMetodo
TipoRetorno
Entrada de
Metodo
Params
…
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura Tabla de Símbolos en MiniJava
• ¿Cómo estructuramos las entradas de la TS de un programa MiniJava?
• La estructura principal es una tabla de clases
• Cada entrada de clase tiene una tablade vars de instancia y una de métodos
• Cada entrada de método/constructortiene una tabla de parámetros
38
Tipo TipoRetornoHash<EntradaParam> params…
EntradaMetodo
Hash<EntradaVar> atributosHash<EntradaMetodo> params…
EntradaClase
Hash<EntradaClase> …
TS
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura Tabla de Símbolos en MiniJava
• Además las clases que representan las entradas, deben proveer funciones para consultar/administrar la tabla de símbolos y las distintas entradas.
• Por ejemplo:
• La tabla de símbolos debería tener una función para ver si cierto nombre es una clase declarada y devolver su entrada
• Una entrada de clase debería tener una función para ver si determinado nombre es un método suyo, y devolver la correspondiente entrada de método.
39
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Estructura Tabla de Símbolos en MiniJava
• La TS debe proveer una forma de identificar cual es el ambiente actual
• ¿Por qué es importante?
• Para saber en que entrada tenemos que insertar la entrada de la declaración actual
40
EntradaMetodo metodoActualEntradaClase claseActualHash<EntradaClase> …
TS
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Creando la Tabla de Símbolos en MiniJava
• La tabla de símbolos se creará a medida que se va
realizando el Análisis Sintáctico.
• Haremos una EDT sobre la gramática utilizada en el
Analizador Sintáctico, donde las acciones semánticas
construirán la TS
• Luego, modificaremos los métodos del Analizador Sintáctico
para reflejar las acciones semánticas de la EDT y así crear la
TS que será utilizada en el análisis semántico
41
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Creando la Tabla de Símbolos en MiniJava
• Consideremos la reglas
<Clase> class idC <Herencia> { <Miembros> }
<Herencia> extends idC | e
42
Declaración de clase:
¿Qué debemos hacer?
Crear la entrada para la clase
con el nombre asociado al
lexema de idCIndicar el nombre de la clase
que hereda según <Herencia>
Antes de procesar los Miembros
tenemos que indicar que la entrada
creada es la clase actual: la clase
donde debemos insertar los atributos,
métodos y ctores declarados
Insertar la entrada en la
Tabla de Símbolos!
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Creando la Tabla de Símbolos en MiniJava
• Consideremos la reglas
<Clase> class idC <Herencia> { <Miembros> }
<Herencia> extends idC | e
43
<Clase> class idC {entradaClase c = new entradaClase(idC.lex)TS.claseActual = c
} <Herencia> {TS.claseActual.heredaDe(<Herencia>.clase)} { <Miembros> } {TS.insertarClase(TS.claseActual)
}
<Herencia> extends idC {<Herencia>.clase = idC.lex} | e {<Herencia>.clase = “Object”}
EDT
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Creando la Tabla de Símbolos en MiniJava
• Consideremos la reglas
<Clase> class idC <Herencia> { <Miembros> }
<Herencia> extends idC | e
44
<Clase> class idC {entradaClase c = new entradaClase(idC.lex)TS.claseActual = c
} <Herencia> {TS.claseActual.heredaDe(<Herencia>.clase)} { <Miembros> } {TS.insertarClase(TS.claseActual)
}
<Herencia> extends idC {<Herencia>.clase = idC.lex} | e {<Herencia>.clase = “Object”}
EDT
void Clase()match(“class”)String nom = tkAct.lexmatch(“idC”)entradaClase c = new entradaClase(nom)TS.claseActual = cString nomAncestro = Herencia()TS.claseActual.heredaDe(nomAncestro)match(“{”)Miembros()match(“}”)
TS.insertarClase(TS.claseActual)
String Herencia()if(tkAct es extends)
match(“extends”)String nom = tkAct.lexmatch(“idC”)return new nom
else if(tkAct es {)return new “Object”
else ERROR SINTACTICO!
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Creando la Tabla de Símbolos en MiniJava
• Consideremos la regla:
<Atributo> <Tipo> idMV <ListaDecs>
<ListaDecs> , idMV <ListaDecs> | e
Declaración de
atributos:
¿Qué debemos hacer?
Crear la entrada para el atributo con
el nombre asociado al lexema de iMV
y el tipo determinado por <Tipo>Pasar el tipo a <ListaDecs>
Insertar la entrada de atributo en la tabla
de atributos de la clase actual
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Creando la Tabla de Símbolos en MiniJava
• Consideremos la regla:
<Atributo> <Tipo> idMV <ListaDecs>
<ListaDecs> , idMV <ListaDecs> | e
<Atributo> <Tipo> idMV { entradaVar v = new entradaVar(idMV.lex, <Tipo>.tipo)TS.claseActual.insertarAtributo(idMV.lex, v)<ListaDecs>.tipo = <Tipo>.tipo
} <ListaDecs>
<ListaDecs>1 , idMV {entradaVar v = new entradaVar(idMV.lex, <ListaDecs>1.tipoE)TS.claseActual.insertarAtributo(idMV.lex, v)<ListaDecs>2.tipoE = <ListaDecs>1.tipoE
} <ListaDecs>2
| e
EDT
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Creando la Tabla de Símbolos en MiniJava
47
Tipo tipoVarString nombre…
EntradaVar
Una consideración
importante con
respecto al diseño de
la TS es cómo se
representarán los tiposPor otra parte es importante modelarlos de manera
uniforme para diseñar adecuadamente las
entidades que los utilizan (métodos y variables)
Son diferentes semánticamente y por lo tanto
deben modelarse por separado
(los tipos primitivos NO son clases)
Tipo Primitivo VS Tipo Referencia
Tipo*
TipoReferencia* TipoPrimitivo*
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones en MiniJava
48
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones
• El chequeo de declaraciones tiene dos actividades principales:
• Chequear que toda entidad fue correctamente declarada
• Consolidar la tabla de símbolos
• Estas actividades dependen de las restricciones de declaración del lenguaje
• Caso de estudio: MiniJava
49
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones
• Dependiendo del lenguaje el chequeo de declaraciones se
puede realizar mientras se realiza el análisis sintáctico, a
medida que se construye la tabla de símbolos (en una pasada)
• En los lenguajes con referencias hacia adelante (como
MiniJava) es necesario realizarlo una vez finalizado el
análisis sintáctico cuando se recopilo toda la información de
las entidades del programa (en dos pasadas)
• En MiniJava se realiza en la segunda pasada
50
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones
• En general, la semántica de declaraciones de MiniJava es como la de Java, aun así hay algunas diferencias, por ejemplo:
• Una clase no puede tener dos métodos con el mismo nombre
• No se puede definir más de un constructor por clase
• Si un método es sobre-escrito toda su signatura debe coincidir con la de su ancestro
• Una atributo no puede tener el mismo nombre que un atributo de un ancestro (sin importar su visibilidad)
Para más detalles ver el apunte de Semántica del lenguaje en la página web de la materia
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones en MiniJava
• Chequear que toda declaración fue
Correctamente Declarada
• En general implica chequear que:
• No haya nombres repetidos en el mismo contexto (ej: dos clases con el mismo nombre)
• Todo nombre usado en una declaración haya sido declarado en el contexto adecuado (ej: el tipo un atributo o retorno de un método)
• No haya herencia circular
• Todo método redefinido tenga exactamente la misma signatura que el ancestro
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones en MiniJava
• Chequear que toda declaración fue
Correctamente Declarada
• En general implica chequear que:
• No haya nombres repetidos en el mismo contexto (ej: dos clases con el mismo nombre)
• Todo nombre usado en una declaración haya sido declarado en el contexto adecuado (ej: el tipo de un método)
• No haya herencia circular
• Todo método redefinido tenga exactamente la misma signatura que el ancestro
puede realizarse
DIRECTAMENTE,
mientras se construye la
TS en el Análisis
Sintáctico!
En particular, cuando
tratamos de insertar una
entrada con un nombre en
una tabla y en esa tabla ya
hay una entrada con ese
nombre
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones en MiniJava
• Los controles y tareas se realizarán directamente sobre la
Tabla de Símbolos
• Para esto se analizarán las entradas de
• Clases
• Métodos
• Constructores
• Variables de Instancia y Parámetros
Los controles de
Variables locales
deben realizarse en
el Chequeo de
Sentencias!!!
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones en MiniJava
• Por ejemplo, para la entrada de una clase en la TS se controla que:
• Si tiene herencia explícita herede de una clase declarada
• No tenga herencia circular (i.e. que en su línea de ancestros no aparezca ella misma)
• No tenga dos métodos o variables de instancia con el mismo nombre
• Que todos sus métodos, sus variables de instancia y su constructor se encuentren correctamente declarados
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Chequeo de Declaraciones en MiniJava
• La implementación de todos estos controles puede
diseñarse de varias maneras
• Por ejemplo, se pueden agregar métodos para realizar los
controles directamente en las entradas de la TS
String HerenciaHash<EntradaVar> atributosHash<EntradaMetodo> metodos…
EntradaClase
void ChequeoDeclaraciones()
Si no(TS.ExisteClase(Herencia))entonces ERROR!
Para cada var en atributosvar.ChequeoDeclaraciones()
Para cada met en metodosmet.ChequeoDeclaraciones()
…
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Consolidación de la TS
• Otra tarea importante que debe realizarse en el chequeo de declaraciones es la
Consolidación de la Tabla Símbolos
• Consiste en actualizar las tablas con las entidades que son heredadas de otras clases
• Esto implica agregar (adecuadamente)
• todos los métodos heredados (consolidación de tablas de métodos)
• todos atributos heredados (consolidación de tablas de atributos)
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Consolidación de la TS
• Consolidación de tablas de métodos
• Consideraciones:
• Métodos sobre-escritos: una clase sólo tiene acceso a la última
versión de los métodos que tiene y hereda
• Además, podemos aprovechar y mientras actualizamos
controlamos si un método es correctamente redefinido
58
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Consolidación de la TS
…
Metodo m1
MétodosHereda: -
Clase A
MétodosHereda: A
Clase B
A B
C
Tabla m1 Tabla
m2 …
Metodo m2
m2 Tabla
m3 …
Metodo m2
…
Metodo m3
MétodosHereda: B
Clase C
m3 Tabla
m4 …
Metodo m3
…
Metodo m4
class A {
dynamic void m1(){…}
dynamic void m2(int p){…}
}
class B extends A{
dynamic void m2(int x){…}
dynamic void m3(){…}
}
class C extends B{
dynamic void m3(){…}
dynamic void m4(){…}
}
Tablas de Métodos antes de la consolidación
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Consolidación de la TS
…
Metodo m1
MétodosHereda: -
Clase A
MétodosHereda: A
Clase B
A B
C
Tabla m1 Tabla
m2 …
Metodo m2
m2 Tabla
m3 …
Metodo m2
…
Metodo m3
MétodosHereda: B
Clase C
m3 Tabla
m4 …
Metodo m3
…
Metodo m4
Tablas de Métodos luego de la Consolidación
m1 Tabla
m1 Tabla
m2
class A {
dynamic void m1(){…}
dynamic void m2(int p){…}
}
class B extends A{
dynamic void m2(int x){…}
dynamic void m3(){…}
}
class C extends B{
dynamic void m3(){…}
dynamic void m4(){…}
}
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Consolidación de la TS
• Consolidación de tablas de Atributos
• Consideraciones:
• Los atributos privados a pesar de no ser visibles son heredados
• Podemos aprovechar la actualización de la tabla para controlar que
no se haya declarado un atributo con el mismo nombre que el de
un ancestro
61
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Consolidación de la TS
…
Var v1
atributosHereda: -
Clase A
atributosHereda: A
Clase B
A B
C
Tabla v1 Tabla
v2 …
Var v2
v3 Tabla
v4…
Var v3
…
Var v4
atributosHereda: B
Clase C
v5Tabla
v6 …
Var v5
…
Var v6
Tablas de Atributos antes de la Consolidación
class A {
public int v1, v2;
}
class B extends A{
public String v3
private boolean v4
}
class C extends B{
public int v5
public int v6
}
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Consolidación de la TS
…
Var v1
atributosHereda: -
Clase A
atributosHereda: A
Clase B
A B
C
Tabla v1Tabla
v2 …
Var v2
v3v4
…
Var v3
…
Var v4
atributosHereda: B
Clase C
v5 v6
…
Var v5
…
Var v6
Tablas de Atributos luego de la Consolidación
v1Tabla
v1Tabla
v2
class A {
public int v1, v2;
}
class B extends A{
public String v3
private boolean v4
}
class C extends B{
public int v5
public int v6
}
v2
v3v4
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Errores – Chequeo de Declaraciones
• Los errores semánticos en el chequeo de declaraciones se
producen cuando se detecta una entidad mal declarada
• En MiniJava, en general, los errores se producen cuando al
declarar una entidad utilizamos una clase no declarada
• Pero también, se pueden producir por métodos mal
redefinidos, nombres repetidos, herencia circular, entre
otros…
64
Compiladores e Intérpretes 2019
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Errores – Chequeo de Declaraciones
• Para reportar los errores es necesario indicar en que
numero de línea se produce el error
• En la segunda pasada ya no tenemos los tokens
• Por lo tanto la entidades (y sus respectivas entradas) deben
llevar cuenta del numero de línea donde fueron declaradas
• Usualmente se determina con el token del identificador utilizado
para nombrarlas
65