Lenguajes y Compiladores Introducción - FACULTAD...

Facultad de Ingeniería de SistemasFacultad de Ingeniería de Sistemas

Lenguajes y Compiladores

Introducción

Compiladores1

ObjetivosObjetivos

� Conocer los fundamentos de construcción deCompiladores en todas sus fases, presentando losconceptos básicos, definiciones formales, técnicasutilizadas, las clases de compiladores, el contexto enel que se desarrollan, así como el tratamiento yrecuperación de errores

Compiladores 2

el que se desarrollan, así como el tratamiento yrecuperación de errores

� Aplicar estos conceptos al desarrollo de:� Software de base

� Software de uso específico

� Interfaces de usuario

IntroducciónIntroducción

� ¿Por qué es importante el estudio de compiladares?

� Conocer el diseño de los compiladores y su efectosobre los lenguajes:� Permite desarrollar algoritmos eficientes: por ejemplocuando usar recursión.

Compiladores 3

cuando usar recursión.

� Mejora el uso del lenguaje disponible: si el uso deapuntadores es eficiente o no.

� Ayuda a la depuración de los errores tanto sintácticoscomo semánticos


� En 1940 surge el 1° lenguaje utilizado en la programación decomputadoras : “El lenguaje de máquina” (lenguaje de 1erageneración).

� ¿Cuál era ventaja de programar en lenguaje de máquina ?

El lenguaje de máquina, es el único lenguaje que la

Compiladores 4

� El lenguaje de máquina, es el único lenguaje que lacomputadora entiende directamente.

� ¿Cuáles eran los inconvenientes o desventajas?

� Dificultad y lentitud en la codificación. Gran dificultad paraverificar y poner a punto los programas.


� Las desventajas Las ventajas.

� Surge la necesidad de buscar otros lenguajes.

� ¿ Que sucedió a comienzos de la década de 1950 ?

� Criterio : Usar notación simbólica.

>

Compiladores 5

Criterio : Usar notación simbólica.

� ¿Cómo se llamó a esos lenguajes?

� Fue el primer intento.

� Esos lenguajes fueron de alto o bajo nivel?

� ¿Esos lenguajes presentaron la mayoría de inconvenientesque presentaba el lenguaje de máquina?.


� La interface (de programación) entre los humanos ylas máquinas son los Lenguajes de programación: Lasolución a un problema se especifica a través de unprograma fuente escrito en un Lenguaje deprogramación.

Es necesario un proceso de traducción para que los

Compiladores 6

� Es necesario un proceso de traducción para que losprogramas fuentes sean entendidos (ejecutados)

� Los compiladores son necesarios para el desarrollode cualquier sistema, caso contrario tendríamos queprogramar en lenguaje ensamblador o peor aún enlenguaje máquina

Lenguajes de programaciónLenguajes de programación

� Los lenguajes de programación han evolucionado� Lenguaje de máquina: combinación de 1’s y 0’s

� Lenguaje montador (ensamblador): uso de mnemónicosy direcciones de memoria

� Lenguajes basados en cálculos numéricos:

Compiladores 7

Lenguajes basados en cálculos numéricos:» ForTran, AlGol, PL/1, Pascal, Basic

� Lenguajes para los negocios: COBOL

� Lenguajes para inteligencia artificial: LISP

� Lenguajes para sistemas: C

� Lenguajes orientados a objetos: C++, Object Pascal

� Lenguajes visuales: Entornos de desarrollo*


� Lenguaje Objeto: Conjunto de instrucciones que uncomputador entiende y ejecuta, es una combinaciónde 1’s y 0’s.

� Lenguaje ensamblador: Conjunto de instruccionescuyas operaciones se especifican a través demnemónicos que representan códigos de operaciones.

Compiladores 8

mnemónicos que representan códigos de operaciones.Es como un lenguaje objeto codificado.

� Lenguaje de programación: Conjunto deinstrucciones más cercanas al lenguaje humano y quepermiten especificar algoritmos y estructuras dedatos.


Compiladores 9

Lenguaje Objeto

Lenguaje Natural

Lenguajes de programación


ProgramafuenteEscrito en Lenguaje de programación

Compiladores 10

Lenguaje ObjetoLenguaje Natural

�Ensambladores.

�Compiladores.

�Interpretes.

Traductor

TraducciónTraducción

� La idea básica es tener un traductor que permita alcomputador “entender” (ejecutar) un programaescrito en un lenguaje de programación.

� Los softwares que realizan estas “traducciones” sonconocidos como Compiladores

Compiladores 11

conocidos como Compiladores

� En una visión simplista el compilador recibe unaprograma fuente y genera un programa objeto.

Fuente ObjetoCompilador

TiposTipos

� Ensamblador: recibe un programa en lenguajeensamblador y genera programa objeto.

� Compilador: recibe un programa escrito en unlenguaje de programación y genera un programaobjeto.

Compiladores 12

objeto.

� Intérprete: Analiza una instrucción fuente y laejecuta directamente sin generar código objeto.

� Preprocesador. Permite sustituir macros, incluirarchivos, entre otras funciones. Generalmente es unpaso anterior a la traducción.


Programa fuente assembly language

Ensamblador

Compiladores 13

Lenguaje Objeto

language

Traductor


Programa fuente Escrito en Lenguaje de

Compilador

Compiladores 14

Lenguaje Objeto

Lenguaje deProgramaciónde A.N.

Traductor

Ambiente de compilaciónAmbiente de compilación

� Luego de la generación del código objeto a veces esnecesario importar algunas funciones estándares loque significa combinar el código obtenido con otrospreviamente almacenados, de manera que se formeun código ejecutable y se pueda ubicar en la memoria

Compiladores 15

un código ejecutable y se pueda ubicar en la memoriapara su ejecución.

� Los encargados de realizar estas funciones sonconocidos como Cargadores y Editores de enlaces.

Ambiente de compilaciónAmbiente de compilación

Fuente

Compilador

Objeto

Compiladores 16

Ejecutable

CargadorEd. Enlace

Objeto

Cargadores y Editores de enlaceCargadores y Editores de enlace

� Editor de enlace: permite formar un solo programa apartir de varios archivos de código de máquinareubicables, ya obtenidos de compilaciones oalmacenados en bibliotecas de rutinas.

� Cargadores: Resuelve el problema de direccionesabsolutas y/o programas reentrantes. Tiene como

Compiladores 17

absolutas y/o programas reentrantes. Tiene comoobjetivo ubicar el programa en memoria para suejecución.

*

Modelo Modelo

� En el proceso de traducción existen dos tareas básicas:

� Análisis (front-end): El texto de entrada esexaminado, verificado y comprendido.

� Generación de Código (back-end): Se genera códigoobjeto equivalente a la cadena de entrada.

Esto permite que:

Compiladores 18

� Esto permite que:

� Front-end y back-end se comuniquen solo a través dela representación intermedia.

� Front-end depende sólo del lenguaje fuente(independe del lenguaje objeto)

� Back-end depende exclusivamente del lenguaje objeto(independe del lenguaje fuente).

*

AnálisisAnálisis

� Normalmente asociamos la Sintaxis a la idea deforma, mientras que la Semántica se asocia asignificado o contenido. Así la sintaxis de un lenguajedebe describir todos los aspectos relativos a laforma de construcción de programas correctos,mientras que la semántica debe describir lo que

Compiladores 19

mientras que la semántica debe describir lo quesucede cuando el programa es ejecutado.

� Teóricamente sólo los programas correctospertenecen al lenguaje y los programas incorrectosno tienen interés. Un programa o es del lenguaje(está correcto) o no es del lenguaje (no estácorrecto).

AnálisisAnálisis

� Pero en la práctica cuando un programa no estácorrecto un buen compilador debe indicar este hechoy tratar de ayudar al usuario a transformalo en unprograma correcto. El tratamiento de erroresincluye mensajes informativos y una recuperación delerror para que el análisis continúe y otros errores

Compiladores 20

incluye mensajes informativos y una recuperación delerror para que el análisis continúe y otros erroressean detectados.

� Normalmente el análisis se divide en léxico,sintáctico y semántico.

Fases de un compiladorFases de un compilador

� Las fases de un compilador son:� Análisis léxico

� Análisis Sintáctico

� Análisis Semántico

� Generación de código

Compiladores 21

� Generación de código

Fases de un compiladorFases de un compilador

Analizador Léxico

Analizador Sintáctico

Analizador SemánticoAdministrador de la tabla de símbolos

Manejador de errores

Compiladores 22

Generador de Código

Optimizador de Código

tabla de símbolos errores

Analizador LéxicoAnalizador Léxico

� Tiene como finalidad la separación e identificaciónde los elementos que componen un programa,igualmente elimina los elementos “decorativos “ comoblancos, comentarios, etc.

� Como resultado de este análisis los items como

Compiladores 23

� Como resultado de este análisis los items comoidentificadores, palabras reservadas, operadores,etc. son reconocidos (comúnmente a través de uncódigo y una cadena de caracteres).

*


� Ejemplo:

if x > 0 then

modx := x {x es positivo}

else modx := (-x) {x es negativo}

Compiladores 24

else modx := (-x) {x es negativo}


� Luego del análisis léxico tendríamos la secuencia deelementos (tokens):Tipo de token Valor del token

palabra reservada if if

identificador x

Compiladores 25

identificador x

operador mayor >

literal numérico 0

palabra reservada then then

identificador modx

operador de atribución :=


� Normalmente los tipos de tokens se representan convalores de un tipo enumerado o con valoresnuméricos

� Generalmente la implantación de un analizador léxico(scanner) se basa en un autómata finito que reconocelas diferentes construcciones.

Compiladores 26

las diferentes construcciones.� El análisis léxico puede ser complicado dependiendodel lenguaje fuente, por ejemplo Fortran no tienepalabras reservadas, permite el uso de blancos en losidentificadores entre otras características quehacen que el scanner sea bastante complejo.


� Ejemplo: DO 10 I = 5� Puede ser el inicio de un comando de asignación

DO 10 I = 5.

� Puede ser el inicio de un comando repetitivo

DO 10 I = 5, 10

Compiladores 27

DO 10 I = 5, 10

� Note que sólo cuando aparece el . o la ; se sabe conseguridad que comando estamos analizando.

� La mayoría de los lenguajes modernos trata desimplificar la implantación de los scanners

Analizador SintácticoAnalizador Sintáctico

� También conocido como Parser.

� Tiene como finalidad reconocer la estructura globaldel programa, verificando que los comandos,declaraciones, expresiones cumplan con las reglasde composición (está bien escrito).

Compiladores 28

de composición (está bien escrito).

� Para el programa presentado antes se deberíareconocer que se trata de un <comando>, masespecíficamente de un <comando-if> compuesto dela palabra reservada if, seguido de una <expresión>,seguida de la palabra reservada then, etc.

*


� Normalmente las reglas de formación de loslenguajes se expresan mediante reglas gramaticales(que se conoce como gramática de un lenguaje)

� Existen tipos de gramáticas y a cada unocorresponde una forma de realizar el análisis

Compiladores 29

corresponde una forma de realizar el análisissintáctico, lo que da origen a los diferentesmétodos de parsers.

� Un aspecto importante de los analizadoressintácticos es la recuperación de errores es deciruna vez detectado el error ¿cómo continuar con elanálisis sintáctico?


� Ejemplo: forb I := 1 to 10 do …..;� Si se detecta el error en el identificador forbseguido de otro identificador I (no es inicio deningún comando válido), podemos considerar forbcomo error y asumir que I es el inicio de unaasignación; cuando se encuentra la palabra

Compiladores 30

asignación; cuando se encuentra la palabrareservada to nuevamente dará error puesto queuna asignación no contiene esa palabra reservada.Es claro que seguiremos generando errores (que noexisten) como consecuencia de una palabrareservada mal escrita y principalmente de unarecuperación no muy correcta.

Analizador SemánticoAnalizador Semántico

� Básicamente el análisis Semántico trata losaspectos sensibles al contexto de la sintaxis de loslenguajes de programación. Por ejemplo no se puederepresentar en una gramática libre de contexto unaregla como: “todo identificador debe ser declaradoantes de ser usado”, es responsabilidad del análisis

Compiladores 31

regla como: “todo identificador debe ser declaradoantes de ser usado”, es responsabilidad del análisissemántico verificar si esa regla se cumplió o no.

� En muchos casos un gran apoyo para esta fase es ladenominada Tabla de símbolos

*

Analizador SemánticoAnalizador Semántico

� Se dice que el análisis semántico es dirigido por lasintaxis: se asocia a cada regla de la gramática unaacción (acción semántica) que será ejecutada cadavez que se “señala” la regla. Estas acciones sonimplantadas frecuentemente como llamadas a rutinassemánticas y pueden ser responsables por realizar el

Compiladores 32

semánticas y pueden ser responsables por realizar elanálisis semántico y la generación de código.

� No existe una frontera definida entre lo que debeser tratado por el análisis sintáctico o lo que debeser tratado por el análisis semántico, quedando estadecisión a criterio del diseñador del compilador.

Tabla de SímbolosTabla de Símbolos

� También conocida como tabla de identificadores

� Es una estructura de datos que contiene un registropor cada identificador del programa (con susatributos). Esta estructura permite encontrarrápidamente el registro para cada identificador y

Compiladores 33

rápidamente el registro para cada identificador yalmacenar o consultar de manera eficiente loscampos dentro de ese registro.

� Por tanto guarda información sobre losidentificadores (nombre, tipo, ámbito, dirección dememoria, número de parámetros y tipo si fuera unnombre de procedimiento, etc.)

*

Tabla de SímbolosTabla de Símbolos

� Es una tabla muy importante por cuanto apoya a lasdiferentes etapas de la traducción.

� Su estructura y organización en general depende delas características del lenguaje fuente.

Compiladores 34

Generación de códigoGeneración de código

� A veces se construye una representación intermediadel programa fuente para ser usada como base parala generación del código objeto. Suponiendo que laforma de ese código intermedio es buena entoncesel proceso de generación de código depende sólo dela arquitectura de la máquina para la cual el código

Compiladores 35

el proceso de generación de código depende sólo dela arquitectura de la máquina para la cual el códigoserá generado.

� Las máquinas sencillas ofrecen pocas opciones y esoimplica en un proceso de generación de código másdirecto.

*


� Ejemplo: para la expresiónx := a + b * c

� Usando variables temporales para guardaroperaciones intermedias, podemos generar elsiguiente código, que aunque correcto puede ser

Compiladores 36

siguiente código, que aunque correcto puede seroptimizado:


Load b

Mult c

Store t1

Load a

Add t1

Compiladores 37

Add t1

Store t2

Load t2

Store x

Podemos notar que hay instrucciones no necesarias.

Un código optimizado sería:


Load b

Mult c

Add a

Store x

� Este tipo de optimización de código se denomina

Compiladores 38

� Este tipo de optimización de código se denominadependiente de la máquina porque usa lascaracterísticas de la máquina para optimizar elcódigo.

� Hay optimizaciones que son independientes de lamáquina y cuya preocupación principal es analizar elprograma más que las características de la máquina.

Tratamiento de erroresTratamiento de errores

� Un problema muy importante que hay resolver encualquier fase de un traductor es la recuperación deerrores. Es es: como continuar con el proceso unavez que se detectó un error de manera tal a noemitir mensajes de errores no existentes.

Compiladores 39

emitir mensajes de errores no existentes.

� Errores léxicos: abre “ y no se cierran

� Errores sintácticos: comandos mal escritos

� Errores semánticos: variable no declarada.

Tratamiento de erroresTratamiento de errores

� Se han realizado intentos para tener compiladoresque no sólo se recuperen de un error sino mas bientraten de corregir los errores para continuar con unprograma sin error que se pueda ejecutar.

� No se trata de un problema trivial y se tendrían que

Compiladores 40

� No se trata de un problema trivial y se tendrían queaplicar técnicas de inteligencia artificial

� Por ejemplo si tenemos: forb I := 10

� ¿Cuál fue el error? ¿Variable mal escrita (forbI) opalabra reservada mal escrita (for)?

Lenguajes y Compiladores Introducción - FACULTAD...

Documents

Transcript of Lenguajes y Compiladores Introducción - FACULTAD...