Compiladores

Universidad José Carlos MariáteguiAlumno: Calzada Meza José Antonio

http://es.wikipedia.org/wiki/Compilador

Un compilador es un programa que lee un programa escrito en un lenguaje (código fuente) y lo traduce a un programa equivalente en otro lenguaje (código objeto). En el proceso se informa al usuario sobre la presencia de errores en el código fuente.

Código FuenteCódigo FuenteCompilador o

Traductor

Código ObjetoCódigo ObjetoDatos entradaDatos entrada

ResultadosResultados

2Universiad José Carlos Mariategui

Compiladores de una pasada: Generan el código máquina a partir de una única lectura del código fuente. Compiladores de múltiples pasadas: Necesitan leer el

código fuente varias veces antes de poder producir el código de máquina.

Compiladores de carga y ejecución: Permiten enlazar varios módulos, cargarlos a la memoria y ejecutarlos directamente.

Compiladores de depuración o de optimación: Realizan cambios en el código para mejorar su eficiencia, pero manteniendo la funcionalidad del programa original.

Compiladores cruzados: Se ejecutan en una máquina pero el código objeto que producen es para otra máquina.

Compiladores JIT (Just-In-Time): Forman parte de un intérprete y compilan partes del código según se necesitan.


La transformación muestra:◦ Programa Fuente :

escrito en un LP de alto nivel◦ Compilador :

encargado de la traducción y comprobar las llamadas a las librerías para que se ejecuten correctamente.

◦ Programa Objeto : Programa traducido, puede o no estar en lenguaje máquina Aún no es directamente ejecutable


•Proceso de Transformación traducción :


La transformación muestra:◦ Programa Ejecutable :

Traducción completa a lenguaje máquina. Hecha por el Enlazador (Linker)o Montador. Es directamente ejecutable

◦ Enlazador (Linker) : Encargado de insertar al programa objeto el código máquina de

las funciones de las librerías (archivos de biblioteca) usadas en el programa y de realizar el proceso de montaje.


Las etapas en el proceso de Compilación son:◦ Análisis◦ Síntesis

Análisis :◦ Divide al programa en sus elementos componentes◦ Crea el código o programa intermedio.

Síntesis :◦ Construye el código objeto, a partir del código intermedio.


Tabla de Símbolos

Código Fuente

Código Intermedio

Código Objeto

Análisis Síntesis


Modelo de análisis y síntesis en la compilación

En la compilación hay 2 partes, análisis y síntesis.

El análisis divide el programa fuente en sus elementos componentes y crea una representación intermedia de este.

De las dos partes, la síntesis requiere las técnicas más especializadas.

La síntesis construye el programa objeto deseado a partir de la representación intermedia.

En el análisis se determinan las operaciones que implica el programa fuente y se registran en una estructura de árbol, llamado árbol sintáctico.

Por ejemplo, para la expresión vf:=vi+v*60 el árbol sintáctico podría ser:

Universiad José Carlos Mariategui

Además del compilador, se pueden necesitar otros programas para crear un programa objeto ejecutable.

El preprocesador: Programa encargado de reunir diferentes módulos que conforman el programa fuente. Este puede también expandir abreviaturas llamadas macros a proposiciones del lenguaje fuente.

En la figura, el compilador crea código en lenguaje ensamblador, el cual es traducido por un ensamblador a código de máquina.

Luego se enlaza a algunas rutinas de biblioteca para producir el código ejecutable.


En la compilación el análisis consta de tres fases

Análisis léxico: También llamado Análisis lineal. En este se lee la cadena de caracteres que constituye el programa de izquierda a derecha, y se agrupa en componentes léxicos, que son secuencias de caracteres con significado colectivo.

En esta etapa el compilador revisa que los tokens contengan los símbolos adecuados del lenguaje.

Requiere por parte del diseñador del lenguaje, una adecuada clasificación de componentes léxicos (tokens).

Dentro de las categorías léxicas se tienen: identificadores, números, separadores, operadores, comentarios, espacios en blanco.

Para la expresión de pascal vf := vi + v * 60se agruparían los componentes léxicos así:•el identificador vf •el símbolo de asignación := •el identificador vi •el signo de suma +•el identificador v •el signo de multiplicación *•el número 60 Los espacios en blanco se eliminan durante el análisis léxico.


Análisis Sintáctico: Conocido igualmente como Análisis jerárquico, se encarga de agrupar los componentes léxicos jerárquicamente en colecciones anidadas con un significado colectivo.

Se usan árboles sintácticos para representar esas agrupaciones.

La estructura jerárquica de un programa normalmente se expresa utilizando reglas recursivas.

De igual forma, muchos lenguajes definen recursivamente las proposiciones mediante reglas como:Si identificador1 es un

identificador y expresión2 es una expresión, entonces:

Identificador1 := expresión2 es una proposición.


1. Cualquier identificador es una expresión. 2. Cualquier número es una expresión. 3. Si expresión1 y expresión2 son

expresiones, entonces también lo son:

expresión1 + expresión2expresión1 * expresión2 (expresión1)

Análisis semántico: Se realizan revisiones que aseguran que los componentes de un programa se ajustan de un modo significativo.

La fase de análisis semántico revisa el programa fuente para tratar de encontrar errores semánticos

Reúne la información sobre los tipos para la fase posterior de generación de código.

Utiliza la estructura jerárquica determinada por la fase de análisis sintáctico para identificar los operadores y operandos de expresiones y proposiciones.

Se encarga además de la verificación de tipos.

El compilador verifica si cada operador tiene operandos permitidos por la especificación del lenguaje fuente.


Un compilador opera en fases. Cada una transforma el programa fuente

de una representación en otra. En la práctica se pueden agrupar algunas

fases. Administración de la tabla de

símbolos: Registra los identificadores utilizados en el programa fuente y reúne información sobre los distintos atributos de cada identificador.

Una tabla de símbolos es una estructura de datos que contiene un registro por cada identificador, con los campos para los atributos del identificador.

Detección e información de errores: Cada fase puede encontrar errores, después de detectar un error, cada fase debe tratar de alguna manera ese error, para poder continuar con la compilación, permitiendo la detección de más errores en el programa fuente.

Las fases de análisis sintáctico y semántico generalmente manejan la mayor cantidad de los errores detectables por el compilador.


Las fases de análisis: Conforme avanza la traducción, la representación interna del programa fuente que tiene el compilador se modifica. Estas fases se refieren a las de análisis léxico, sintáctico y semántico ya definidas.

Generación de código interno: Algunos compiladores generan una representación intermedia explicita del programa fuente.

Se puede considerar esta como un programa para una máquina abstracta.

Debe ser fácil de producir y fácil de traducir al programa objeto.

Por ejemplo el “código de tres direcciones”, que traduce el código en una secuencia de instrucciones, cada una de las cuales tiene como máximo tres operandos.


Las actividades de compilación se agrupan normalmente en dos o mas fases.

Etapa inicial: Recoge aquellas que dependen principalmente del lenguaje fuente.

análisis léxico y sintáctico, creación de tabla de símbolos, análisis semántico y la generación de código intermedio, con su respectivo manejo de errores.

Etapa final: Incluye las partes que dependen de la máquina objeto y del lenguaje intermedio.

Fase de optimación de código, la generación de código, el manejo de errores y las operaciones que involucran la tabla de símbolos.

Pasadas: Se acostumbra aplicar varias fases de un compilador en una sola pasada.

Una pasada es la lectura de un archivo de entrada y en la escritura de un archivo de salida.

Es mejor agrupar los proceso de compilación por pasadas y no por fases.

El análisis léxico, el análisis sintáctico, el análisis semántico y la generación de código intermedio pueden agruparse en una pasada

Reducción del número de pasadas: Es recomendable tener pocas pasadas.

La lectura y escritura de archivos toma tiempo e implica la carga de todo el programa en memoria.


La sintaxis de un lenguaje de programación es una definición de lo que constituye un programa gramaticalmente válido en dicho lenguaje.

La sintaxis queda especificada por un conjunto de reglas.

Una definición de la sintaxis clara, concisa y formal es especialmente importante en los lenguajes de programación.


Un Metalenguaje es un lenguaje usado para definir otros lenguajes.

Backus-Naur Form o BNF es uno de ellos. BNF desarrollado por Noam Chomsky, es

altamente usada en la definición de lenguajes de programación.

Es útil para describir de forma precisa las cadenas que son programas legítimos y aislar todas las demás (las que tienen errores sintácticos de varios tipos)

Las expresiones regulares también es un Metalenguaje


una sintaxis BNF sencilla es mostrada en la figura.


Las etapas de análisis semántico y de optimización analizan la consistencia semántica (comprobando, por ejemplo, la utilización consistente de operadores y tipos de datos) y transforman el texto de forma que pueda utilizar de forma eficiente la arquitectura en la que se ejecutará el programa.

Para terminar, la etapa de generación de código utiliza la representación abstracta resultante como base para la generación de código máquina ejecutable.

• Todos los programas deben ser analizados para comprobar su corrección sintáctica antes de ser interpretados o traducidos a código máquina.

• Al nivel más elemental, el proceso de análisis léxico separa los caracteres individuales del programa en una cadena de tokens que se analiza sintácticamente, de uno en uno, hasta un nivel de análisis superior.


Las Expresiones regulares son una herramienta muy utilizada en el diseño de lenguajes para especificar formalmente cada clase de token.

Estas permiten conceptos como «una o más apariciones de un dígito». Es más, se puede crear de forma similar una expresión regular para definir el significado de un ldentificador: [a-zA-Z] [a-zA-Z0-9]*

lo que significa «una letra seguida por una o más apariciones de una letra o un dígito».

Las expresiones regulares se han convertido en una herramienta muy popular del diseño de lenguajes, porque admiten la generación automática de analizadores léxicos sin problemas.

Dos generadores bastante utilizados son el «Lex» (que genera código de C) y el «JLex» (que genera código de Java).


La sintaxis completa de un lenguaje de programación utiliza el resultado del análisis léxico como base para la definición de la estructura de todas las partes diferentes de programa que aparecen por encima del nivel léxico

La sintaxis de un lenguaje utiliza BNF como herramienta principal para proporcionar una definición precisa y una guía estricta para que la fase de análisis sintáctico detecte errores sintácticos y desarrolle una interpretación abstracta a partir de un flujo de tokens.

Consideremos las categorías sintácticas Asignación y Expresión, que definen todas las secuencias de Pasos de testigo que describen los cálculos aritméticos y asignaciones de resultados a una variable.

la Figura 2.8 muestra una derivación de la Expresión x+2*y.


Una gramática es ambigua si permite que una cadena se convierta en uno o más árboles sintácticos diferentes.

Por ejemplo, la gramática ambigua, AmbExp, para expresiones con enteros y sustracciones.AmbEx Integer | AmbExp –

AmbExp Esta gramática permite que

una expresión tenga dos interpretaciones distintas en tiempo de ejecución.

Por ejemplo, consideremos el fragmento de programa 2 - 3 - 4.


El BNF extendido (EBNF) fue introducido para simplificar la especificación de la recursividad en las reglas de gramática y para introducir la idea de una parte opcional en la parte derecha de una regla. Expression Term | Expression +

Term | Expression -TermTerm Factor | Term * Factor | Term /

Factor Se puede representar como

◦ Expression Term{[+| –] Term}*

◦ Term Factor{ ['*' | /] Factor} *

(*) significa «cero o más apariciones de los símbolos que están entre llaves { } inmediatamente antes de él».

Los corchetes [ y ] encierran una serie de alternativas, de las que debemos elegir una.

Para terminar, el asterisco (*) indica que la multiplicación está entre comillas ('), para distinguirla de la utilización metalingüística del asterisco como un operador EBNF.

Los diagramas sintácticos se usan para clarificar el significado de varias construcciones de lenguajes cuando se enseñan a los programadores noveles.


Los sistemas de tipos se usan en el diseño de lenguajes para formalizar la definición de los tipos de datos de un lenguaje y su utilización correcta en los programas.

La definición de un lenguaje de programación está completa sólo cuando están completamente definidos su semántica, su sintaxis y su sistema de tipos.

La semántica de un lenguaje de programación es una definición del significado de cualquier programa que sea sintácticamente válido desde los puntos de vista de la sintaxis concreta y de la revisión de tipos estática.

Una idea intuitiva sencilla del significado de un programa es: «lo que sucede en un computador cuando se ejecuta el programa». semántica operacional.

Otro modo de ver el significado de un programa es: empezar con una especificación formal de lo que tiene que hacer el programa y después demostrar que lo hace, utilizando una serie sistemática de pasos lógicos. semántica axiomática.

Un tercer modo de ver la semántica de un lenguaje de programación es: definir el significado de cada tipo de instrucción que se produce en la sintaxis (abstracta) como una función matemática de transformación de estado. semántica denotativa.


Los tres métodos de definición semántica tienen ventajas e inconvenientes.

La semántica operacional Tiene la ventaja de representar

el significado del programa directamente en el código de una máquina real (o simulada).

Esto es también una debilidad, debido a que la definición de la semántica de un lenguaje de programación con base a una arquitectura en particular, restringe la utilidad de esa definición a los escritores-compiladores y programadores que trabajen con arquitecturas diferentes.

Además, el equipo virtual en el que se ejecutan las instrucciones también necesita una descripción semántica, lo que añade complejidad y puede lleva a definiciones viciadas.

La semántica axiomática Es particularmente útil en la

exploración de las propiedades formales de los programas.

A los programadores que deben escribir programas correctos a partir de un conjunto de especificaciones preciso, les resulta particularmente útil este estilo semántico.

La semántica denotativa Es valiosa porque su estilo

funcional lleva la definición semántica de un lenguaje a un nivel alto de precisión matemática.

A través de ella, los diseñadores de lenguajes obtienen una definición funcional del significado de la elaboración de cada lenguaje que es independiente de cualquier arquitectura de equipo en particular.


Un tipo es un conjunto bien definido de valores y de operaciones en esos valores.

Un sistema de tipos es un sistema bien definido para asociar tipos con variables y otros objetos definidos en un programa.

Los lenguajes que permiten asociar sólo un tipo a una variable se llaman lenguajes de tipos estáticos, los que permiten asociar una variable a varios tipos se llaman de tipos dinámicos.

Un lenguaje de tipos estáticos permite que las reglas de su tipo se definan completamente con base a su sintaxis abstracta. Se llama a esta definición semántica estática.

Un error de tipo es un error en tiempo de ejecución que se produce cuando se intenta una operación en un valor para el que no está bien definida.

Un lenguaje de programación es de tipos estrictos si su sistema de tipos permite la detección de todos los errores de tipo de los programas, ya sea en tiempo de compilación como en tiempo de ejecución, antes de que la instrucción en la que se pueden producir se ejecute. (El hecho de que un lenguaje tenga tipos estáticos o dinámicos no evita que tenga tipos estrictos.). Java es un lenguaje con tipos estrictos, mientras que C no lo es.

Generalmente, los tipos estrictos fomentan programas más fiables y se consideran como una virtud en el diseño de lenguajes de programación.

Un programa es de tipo seguro si sabemos que no tiene errores de tipo.

Por definición, todos los programas de un lenguaje con tipos estrictos son de tipo seguro.

Un lenguaje es de tipo seguro si todos sus programas lo son.


Un tipo es un conjunto bien definido de valores y de operaciones en esos valores.

Un sistema de tipos es un sistema bien definido para asociar tipos con variables y otros objetos definidos en un programa.

Los lenguajes que permiten asociar sólo un tipo a una variable se llaman lenguajes de tipos estáticos, los que permiten asociar una variable a varios tipos se llaman de tipos dinámicos.

Un lenguaje de tipos estáticos permite que las reglas de su tipo se definan completamente con base a su sintaxis abstracta. Se llama a esta definición semántica estática.

Un error de tipo es un error en tiempo de ejecución que se produce cuando se intenta una operación en un valor para el que no está bien definida.

Un lenguaje de programación es de tipos estrictos si su sistema de tipos permite la detección de todos los errores de tipo de los programas, ya sea en tiempo de compilación como en tiempo de ejecución, antes de que la instrucción en la que se pueden producir se ejecute. (El hecho de que un lenguaje tenga tipos estáticos o dinámicos no evita que tenga tipos estrictos.). Java es un lenguaje con tipos estrictos, mientras que C no lo es.

Generalmente, los tipos estrictos fomentan programas más fiables y se consideran como una virtud en el diseño de lenguajes de programación.

Un programa es de tipo seguro si sabemos que no tiene errores de tipo.

Por definición, todos los programas de un lenguaje con tipos estrictos son de tipo seguro.

Un lenguaje es de tipo seguro si todos sus programas lo son.


Una manera de definir el sistema de tipos de un lenguaje es escribir un conjunto de especificaciones de funciones que defina lo que significa para un programa ser de tipo seguro.

Se pueden escribir estas reglas como funciones de valor booleano y se pueden expresar ideas como «todas las variables declaradas tienen nombres únicos» o «todas las variables utilizadas en el programa deben declararse».

La base de esta definición funcional es un mapa de tipos, que es un conjunto de parejas que representa las variables declaradas y sus tipos.

tm = {⟨v1, t1⟩, ⟨v2, t2⟩, ... , ⟨vn, tn⟩} Donde cada vi indica una Variable y

cada ti indica su Tipo declarado. Un ejemplo de mapa de tipos para

un programa que tiene tres variables declaradas; i y j con tipo int y p con tipo boolean:

tm = {⟨i, int⟩, ⟨j, int⟩, ... , ⟨p, boolean⟩}

Un trato formal de comprobación de tipos estáticos de un programa se basa en la existencia de un mapa de tipos que se haya extraído de las Declaraciones que aparecen en la parte superior del programa.

Se puede expresar la comprobación de tipos estáticos de un lenguaje en notación funcional, en la que cada regla que ayuda a definir el sistema de tipos es una función con valor booleano V.

V devuelve true o false dependiendo de si un miembro en particular de una clase sintáctica abstracta es válido o no, en relación a estas reglas. Es decir,

V: Class → B Por ejemplo, supongamos que queremos

definir la idea de que «una lista de declaraciones es válida si todas sus variables tienen identificadores únicos entre sí». Podemos expresar esta idea de manera precisa del siguiente modo:


Los números naturales, enteros, números reales y los booleanos y sus propiedades matemáticas proporcionan un contexto fundamental para el diseño de lenguajes de programación.

Estos conjuntos son ejemplos de dominios semánticos de lenguajes de programación.

Un dominio semántico es cualquier conjunto cuyas propiedades y operaciones son bien entendidas independientemente y sobre el que se basan, en última instancia, las funciones que definen la semántica de un lenguaje.

Tres dominios semánticos útiles de los lenguajes de programación son el entorno, la memoria y las ubicaciones.

El entorno es un conjunto de pares que une variables específicas con ubicaciones de memoria.

La memoria, es un conjunto de pares que une ubicaciones específicas con valores.

Las ubicaciones, en cada caso, son los números naturales N.

Por ejemplo, supongamos que tenemos variables i y j con valores 13 y -1.

Supongamos que las ubicaciones de memoria están numeradas en serie comenzando por el 0 y que, las variables i y j están asociadas con las ubicaciones de memoria 154 y 155.


El estado de un programa es el producto de su entorno y su memoria.

Define sencillamente el estado de un programa como un conjunto de pares (v, val) que representa todas las variables activas y sus valores asignados actualmente en alguna etapa durante la ejecución del programa.

• Aquí, cada vi indica una variable y cada vali indica su valor asignado actualmente.

• Antes de que el programa comience su ejecución, σ = { v1, ⟨ undef , v2, ⟩ ⟨ undef , ..., vm, ⟩ ⟨ undef }.⟩

• También utilizamos la expresión σ (v) para indicar la función que recupera el valor de la variable v del estado actual.


La semántica operacional de un programa proporciona una definición del significado del programa simulando el comportamiento del mismo en un modelo de equipo que tenga una organización de memoria y un conjunto de instrucciones muy sencillos (aunque no necesariamente realistas).

Uno de los primeros modelos de semántica operacional fue el «equipo SECD», que ofrecía una base para definir formalmente la semántica de Lisp.

Los modelos de semántica operacional estructurados utilizan un método basado en reglas y unas cuantas suposiciones sencillas sobre la capacidad lógica y aritmética del equipo subyacente.

Un modelo de semántica operacional puede utilizar la notación σ (e) => v para representar la computación de un valor v de la expresión e en estado σ.

Si e es una constante, σ (e) es sencillamente el valor de esa constante en el dominio semántico subyacente.

Si e es una variable, σ (e) es el valor de esa variable en el estado actual σ.

La segunda convención de notación de la semántica operacional es una regla de ejecución.

Una regla de ejecución tiene la forma

Se lee: “si la premisa es verdadera, entonces la conclusión es verdadera”.


Aunque es importante que los programadores y los escritores de compiladores comprendan lo que hace un programa en todas las circunstancias, también es importante que los programadores puedan confirmar, o probar, que hace lo que se supone que tiene que hacer bajo todas las circunstancias.

Es decir, que el programa es «correcto» de una manera convincente.

La semántica axiomática nos ofrece un medio para desarrollar dichas pruebas.

La semántica axiomática nos ofrece un medio para razonar sobre los programas y sus cálculos.

Esto permite a los programadores predecir el comportamiento de un programa de un modo más convincente y circunspecto que ejecutando el programa varias veces.

La semántica axiomática se basa en la noción de asertos, que es un predicado que describe el estado de un programa en cualquier momento de su ejecución.

El aserto Q≡m ≡max(a,b) define el significado de la función max(a,b).

Para demostrar que la el programa calcula realmente la función max, hay que demostrar que la expresión lógica Q es equivalente al significado de ese programa. Q es la poscondición del programa max.

La semántica axiomática permite derivar lógicamente una serie de predicados razonando sobre el comportamiento de cada instrucción individual en el programa. Comenzando por la postcondición Q y trabajando hacia atrás.

Universiad José Carlos Mariategui 33

La semántica denotativa de un lenguaje define los significados de los elementos abstractos de dicho lenguaje como un grupo de funciones de transformación del entorno y del estado.

El entorno de un programa es el conjunto de objetos y tipos que están activos en cada paso de su ejecución.

El estado de un programa es el conjunto de todos los objetos activos y sus valores actuales.

Estas funciones de transformación de estado dependen de la suposición de algunos tipos y transformaciones primitivas.

Mientras que la semántica axiomática es valiosa para la claridad del significado de un programa como un texto abstracto, la semántica operacional (o denotativa) se centra en el significado de un programa como un objeto activo dentro de un entorno computacional (o funcional).

La utilización de la semántica denotativa para la definición del significado tiene ventajas y desventajas.

Una ventaja es que podemos utilizar las denotaciones funcionales del significado de un programa como base para especificar un intérprete para el lenguaje.

la semántica denotativa es muy utilizada y permite definir el significado de un programa abstracto como una serie de transformaciones de estado resultante de la aplicación de una serie de funciones M.

Estas funciones definen individualmente el significado de cada clase de elementos que nos podemos encontrar en el árbol de sintaxis abstracta de un programa (Program, Block, Conditional, Loop, Assignment, etc.).


Education

Compiladores