Transcript
Lenguajes de Programaci´on Compilaci´ on vs Interpretaci´ on
Juan Zamora O.
Semestre II - 2013
Anteriormente...
I
Inicios de los LP.
I
Ppio de los tiempos → Secuencias de bits.
I
Aumento progresivo del nivel de abstracci´ on.
I
Traductor → Interprete.
I
Modelo de computaci´ on y categor´ıas.
[email protected]
1/1
Compiladores I
Compilacion y ejecucion de un programa en un lenguaje de alto nivel: P.Fuente Compilador Entrada
Ejecutable
Salida
I
Traducci´on del programa fuente en programa objeto (tipicamente en lenguaje de maquina).
I
”tiempo de compilacion” vs ”tiempo de ejecuci´on”.
[email protected]
2/1
Compiladores I
Compilacion y ejecucion de un programa en un lenguaje de alto nivel: P.Fuente Compilador Entrada
Ejecutable
Salida
I
Traducci´on del programa fuente en programa objeto (tipicamente en lenguaje de maquina).
I
”tiempo de compilacion” vs ”tiempo de ejecuci´on”.
[email protected]
2/1
Interpretes
I
Esquema general de interpretaci´ on de un programa fuente: P.Fuente Interprete
Salida
Entrada I
Interprete ∼ maquina virtual.
I
Se procesa y se ejecuta.
I
Manejo ”c´omodo” de asignaciones din´amicas (dep. entrada).
[email protected]
3/1
Interpretes
I
Esquema general de interpretaci´ on de un programa fuente: P.Fuente Interprete
Salida
Entrada I
Interprete ∼ maquina virtual.
I
Se procesa y se ejecuta.
I
Manejo ”c´omodo” de asignaciones din´amicas (dep. entrada).
[email protected]
3/1
Interpretes
I
Esquema general de interpretaci´ on de un programa fuente: P.Fuente Interprete
Salida
Entrada I
Interprete ∼ maquina virtual.
I
Se procesa y se ejecuta.
I
Manejo ”c´omodo” de asignaciones din´amicas (dep. entrada).
[email protected]
3/1
Compilador vs Interprete I I
Lenguajes compilados generalmente tienen un mejor desempe˜ no. I
Ahorran realizacion de tareas en tiempo de ejecucion al ejecutarlas una unica vez en el tiempo de compilacion.
I
Criterio: Complejidad en el analisis e intervencion del codigo
I
Interprete ∼ traducci´ on mec´anica.
I
Compilador: I
An´alisis sint´actico.
I
odigo. Modifica c´
I
Genera programa intermedio entre c.orig. y lenguaje de maq.
[email protected]
4/1
Compilador vs Interprete I I
Lenguajes compilados generalmente tienen un mejor desempe˜ no. I
Ahorran realizacion de tareas en tiempo de ejecucion al ejecutarlas una unica vez en el tiempo de compilacion.
I
Criterio: Complejidad en el analisis e intervencion del codigo
I
Interprete ∼ traducci´ on mec´anica.
I
Compilador: I
An´alisis sint´actico.
I
Modifica c´ odigo.
I
Genera programa intermedio entre c.orig. y lenguaje de maq.
[email protected]
4/1
Compilador vs Interprete I I
Lenguajes compilados generalmente tienen un mejor desempe˜ no. I
Ahorran realizacion de tareas en tiempo de ejecucion al ejecutarlas una unica vez en el tiempo de compilacion.
I
Criterio: Complejidad en el analisis e intervencion del codigo
I
Interprete ∼ traducci´ on mec´anica.
I
Compilador: I
An´alisis sint´actico.
I
Modifica c´ odigo.
I
Genera programa intermedio entre c.orig. y lenguaje de maq.
[email protected]
4/1
Compilador vs Interprete I I
Lenguajes compilados generalmente tienen un mejor desempe˜ no. I
Ahorran realizacion de tareas en tiempo de ejecucion al ejecutarlas una unica vez en el tiempo de compilacion.
I
Criterio: Complejidad en el analisis e intervencion del codigo
I
Interprete ∼ traducci´ on mec´anica.
I
Compilador: I
An´alisis sint´actico.
I
Modifica c´ odigo.
I
Genera programa intermedio entre c.orig. y lenguaje de maq.
[email protected]
4/1
Compilador vs Interprete II
I
En L.Compilados, el ”traductor” se denomina preprocesador. I
Operaciones basadas en calce de patrones.
I
Existe posibilidad de errores posteriores. P.Fuente Preprocesador P.Fuente Mod. Compilador
Prog. Assembly
Ejemplo gcc...
[email protected]
5/1
Compilador vs Interprete II
I
En L.Compilados, el ”traductor” se denomina preprocesador. I
Operaciones basadas en calce de patrones.
I
Existe posibilidad de errores posteriores. P.Fuente Preprocesador P.Fuente Mod. Compilador
Prog. Assembly
Ejemplo gcc...
[email protected]
5/1
Compilador vs Interprete III
Esquema gral. de impl. para la mayor´ıa de los LLP. P.Fuente Traductor P.Interm. Maq. Virtual
Salida
Entrada
[email protected]
6/1
Compilador vs Interprete III
Esquema gral. de impl. para la mayor´ıa de los LLP. P.Fuente Traductor
depende de complej.
P.Interm. Maq. Virtual
Salida
Entrada
[email protected]
7/1
Como se construye un compilador?
I
Bootstrapping I
Compilador C → C
I
Compilador ADA → ADA
I
Compilador no necesariamente traduce de L. de alto nivel a L. de maquina.
I
∃ ssi ∃ traducci´on automat. Y ∃ an´alisis sem´antico de entrada (C.Fuente).
[email protected]
8/1
Como se construye un compilador?
I
Bootstrapping I
Compilador C → C
I
Compilador ADA → ADA
I
Compilador no necesariamente traduce de L. de alto nivel a L. de maquina.
I
∃ ssi ∃ traducci´on automat. Y ∃ an´alisis sem´antico de entrada (C.Fuente).
[email protected]
8/1
Fases de compilaci´on I I
Compilaci´on consiste en una serie de pasos secuenciales.
(Img. extra´ıda del libro de Scott.)
[email protected]
9/1
Fases de compilaci´on II
I
Frontend: Buscan significado del programa.
I
Backend: Construyen programa objeto equivalente.
I
Ambos pueden ser compartidos por compiladores: I
Frontend: para m´as de una maq.
I
Backend: para m´as de un lenguaje de fuente.
[email protected]
10/1
An´alisis l´exico y sint´actico I Consideremos el siguiente c´ odigo: int main (){ int i = getint () , j = getint (); while ( i != j ) { if (i > j ) i = i - j ; else j = j - i ; } putint ( i ); } I
An´alisis l´exico:
[email protected]
11/1
An´alisis l´exico y sint´actico II I
I
I
An´alisis l´exico I
Reconoce s´ olo estructura & agrupa atomos (tokens).
I
Reduce tama˜ no de la entrada.
An´alisis sint´actico organiza tokens jer´arquicamente. I
Representa conceptos de alto nivel (uno por nodo en ´arbol).
I
Componentes de c/concepto → hijos.
I
Hojas (D → I) son los Tokens recibidos por el A.Lex.
Estructura del ´arbol se basa en cjto. de reglas recursivas (”CFG”). I
Una regla: Concepto → { expansi´ on posible}
[email protected]
12/1
An´alisis l´exico y sint´actico III
´ Arbol sint´ actico Concreto del c´ odigo anterior(1).
[email protected]
13/1
An´alisis l´exico y sint´actico IV
´ Arbol sint´ actico Concreto del c´ odigo anterior(2).
[email protected]
14/1
An´alisis l´exico y sint´actico V
´ Arbol sint´ actico Abstracto del c´ odigo anterior.
[email protected]
15/1
An´alisis l´exico y sint´actico VI
Importante I
Cada punto de ramificcaci´ on → aplicaci´ on de una regla gram´atica.
I
Complejidad resultante es reflejo de gram´atica, no del programa de entrada.
I
Durante an´alisis l´exico y sint´actico compilador verifica: I
Correctitud de tokens (bien formados). (e.g. $mi var en C)
I
Coherencia de secuencia de tokens con la gram´atica. (e.g. i = j.i 2)
[email protected]
16/1
An´alisis sem´antico y gen. de c´od. intermedio I
I
I
An´alisis sem´antico → Identificaci´ on del sentido/intenci´on en un programa. I
Reconoce si mult. ocurrencias de un ID hacen ref. a la misma entidad.
I
Verifica su uso consistente.
I
Rastrea tipos de ID y exprs. para verificar uso consistente.
Construcci´on de tabla de s´ımbolos (T.S.). I
Asocia cada ID con su informaci´ on (tipo, ambito, estr. interna, etc.)
[email protected]
17/1
An´alisis sem´antico y gen. de c´od. intermedio II
I
I
(usando T.S.) Otras reglas pueden ser verificadas (e.g.): I
Declaraci´ on previa de cada ID y aplicaciones coherentes (e.g. String + INT).
I
Par´ametros correctos en subrutinas.
Revisi´on exhaustiva de reglas sem´anticas en T.Compilaci´on I
Imposible.
I
”Aquellas que s´ı” → Sem´anticas Est´aticas.
I
Resto → Sem´anticas Din´amicas.
[email protected]
18/1
An´alisis sem´antico y gen. de c´od. intermedio III
I
¿Balance en t´erminos de desempe˜ no? (verif. semant. estaticas vs din´amicas)
I
¿Balance en t´erminos de seguridad? (verif. semant. estaticas vs din´amicas)
I
Algunos LP. verifican en tiempo de ejecuci´ on: I
Inicializaci´ on de vars. previo a su uso en expr.
I
Expr. con indices de arreglos queden dentro del rango.
[email protected]
19/1
An´alisis sem´antico y gen. de c´od. intermedio IV
I
Compilador produce c´ odigo para verificar algunas reglas (Lanzamiento de Excepciones). I
Aquello que no puede ser verif. genera programas indefinidos.
void main (){ int arr [4] = {0 , 1 , 2 , 3}; int * p = arr ; printf ( " % d \ n " , *( p +5)); }
[email protected]
20/1
Arbol de sint´axis concreto vs abstracto I
I
I
´ Arbol sint´actico pasa por 2 etapas: I
Concreta: muestra derivaci´ on de reglas a partir de CFG.
I
Abstracta: Refinaci´ on de la v.Concreta. → Arbol de sintaxis (a secas).
En etapa abstracta: I
Nodos artificiales son removidos.
I
Incorporaci´ on de anotaciones por el A. Sem´antico.(atributos) I
E.g. ptrs de ID hacia entradas de T.S.
[email protected]
21/1
Arbol de sint´axis concreto vs abstracto II
I
En algunos compiladores: I I
´ Arbol de sint´axis [Forma intermedia] → Backend. Recorrido sobre ´arbol de sintaxis [Forma Intermedia] → Backend. I
E.g. grafo de flujo de control: potenciales caminos durante ejec.
[email protected]
22/1
Generaci´on de c´odigo objeto I
I
Forma intermedia es llevada al lenguaje objetivo.
I
Dada la info. del ´arbol de sint´axis se genera el c´odigo.
I
Revisi´on de T.S. para asignar ubic. de vars.
I
Recorrido de repres. intermedia (resto de ops. y ramificaciones)
I
T.S. almacenada en programa objeto para depuraci´on.
[email protected]
23/1
Generaci´on de c´odigo objeto II
C´ odigo ensamblado del programa GCD en C.
[email protected]
24/1
Mejora del c´odigo I I
”Optimizaci´on” (no siempre es realizada)
I
Transforma programa que:
I
I
Hace lo mismo.
I
M´as rapido o
I
usando menos memoria.
Mejoras pueden ser I
Dependientes de la maq. I
I
I
I
sobre forma intermedia.
Indep. de la maq. sobre programa objeto.
2 fases adicionales al proceso de compilaci´ on (eventualmente).
[email protected]
25/1
Mejora del c´odigo II
C´ odigo ensamblado del programa GCD en C.(version mejorada)
[email protected]
26/1