Download compilador - Biblioteca de la UNS
Document related concepts
Transcript
Teoría de lenguajes y compiladores Unidad I Analizadores lexicográficos Semana 1 Introducción Objetivo General El alumno al finalizar el curso desarrollará aplicaciones que le permitan determinar si una sentencia corresponde a la estructura gramatical de un lenguaje de programación. Así mismo estará capacitado para proponer nuevas formas estructurales en la definición de lenguajes de programación. Objetivo Específico Desarrollar un analizador lexicográfico Objetivo Instruccional Analizar la evolución de los lenguajes de programación; estableciendo las diferencias entre ellos, así como los elementos que los conforman. Reflexión: Si eres programador y desarrollas algo, pero no logras hacer que sirva … … llámalo versión Contenidos Introducción Evolución de los lenguajes de programación Categorías de los lenguajes Organización de un programa Notación gramatical de los lenguajes Compiladores e interpretes Introducción Programación “La programación, es el arte de organizar la complejidad”. “Organizar los cálculos de manera que nuestros sentidos sean suficientes para garantizar que el cómputo arrojado, sean los resultados esperados”. Introducción Requisitos mínimos para desarrollar un lenguaje •Ayudar a escribir buenos programas. •Fácil de leer. •Fácil de entender. •Fácil de modificar. Introducción Programación vs Mantenimiento Creación inicial y verificación de un programa. Se refiere a las correcciones y los cambios que se realizan en un programa después de su desarrollo. Introducción Estructura y Organización de los Programas “Son claves para manejar programas muy grandes” La legibilidad de un programa puede mejorarse organizándolo de tal manera que cada parte pueda entenderse en forma relativamente independiente del resto. Introducción Von Neumann Introduce el concepto de programa almacenado. Propuso que los programas se almacenaran de forma digital en la memoria de la computadora junto con los datos Por otro lado, se dio cuenta que la aritmética decimal usada por la ENIAC podía ser reemplazada usando aritmética binaria. Este diseño conocido como ARQUITECTURA de VON NEUMANN, ha sido la base para casi todas las computadoras digitales. Introducción Organización de la Máquina de Von Neumann Unidad de control Unidad Aritmética Acumulador A Unidad de entrada y salida Registro R Memoria para instrucciones y datos Introducción Elementos de la máquina de Von Neumann Determina el orden de ejecución de las instrucciones. Flujo de control A una localidad de memoria podía asignársele el valor contenido en el acumulador Datos Comprende… Asignaciones a localidades de memoria Los enteros eran la única forma de datos Operaciones aritméticas Podía sumar, restar, multiplicar, dividir y tomar el valor absoluto de un numero. Introducción Codificación Lenguaje de máquina: 00000010101111001010 00000010101111101010 00000011001100100110 Lenguaje Ensamblador: Load I Add J Store K Lenguaje alto nivel: K=I+J Introducción Primera experiencia En los años 50, se creía que los programas eficientes solo podían escribirse manualmente, usando algunas variantes de lenguajes de máquina. (Fortran) ¡ Surge preocupación por la eficiencia de ejecución ! •El alto costo de creación de código ensamblador o de máquina fue la principal motivación para el desarrollo de Fortran (FORmula TRANslation). •Ninguna notación diferente del lenguaje de máquina puede ejecutarse directamente en un computador. …Primera experiencia Programa fuente Tiempo de traducción Introducción Compilador Tiempo de ejecución Entrada Código destino Salida …Primera experiencia Introducción Beneficios de los lenguajes de alto nivel •Surgimiento de usuarios y programas nuevos. •Proporciona notaciones fáciles de leer. •Proporciona portabilidad (Usuarios pueden intercambiar programas) …Primera experiencia Introducción Estructura y legibilidad vs Eficiencia •La legibilidad y la capacidad de modificar los programas pueden contribuir también a la eficiencia. •La eficiencia de un programa depende de las decisiones tomados en los niveles de diseño, desde la concepción hasta la elección de estructuras de datos y algoritmos para el código final. •El refinamiento de código se realiza con la mejora de puntos críticos, que son las pequeñas partes muy utilizadas en donde el programa la mayor parte de su tiempo de ejecución. Evolución de los lenguajes Generaciones de los lenguajes de programación Generación Nombre Particularidad Primera De maquina Especifico para cada microprocesador, uso de código binario Segunda Ensamblador Uso de nemotécnicas que abstraen al lenguaje de maquina Tercera De alto nivel Lenguajes estructurados con comandos cercanos al lenguaje natural Cuarta Propósito especial Programas orientados a programas específicos Quinta Naturales Incluye inteligencia artificial y sistemas expertos Categoría de los lenguajes Clasificación de los lenguajes de programación Lenguaje de máquina • Orientado al microprocesador (Sistema binario) Lenguaje de bajo nivel • Ensamblador (Usa código nemónico y también esta orientado a un microprocesador) Lenguajes de alto nivel • Orientado a que las personas entiendan y escriban los programas Organización de un programa Formas de organización Existe más de una forma para solucionar un problema, así que hay mas de una forma para estructurar un programa. La estructura tiene que establecerse para cada programa. Formas: • Descendente • Modular •Objetos Notación gramatical de un lenguaje Estructura sintáctica •La sintaxis de un lenguaje especifica como están construidos los programas en dicho lenguaje. •La estructura sintáctica, es decir la estructura impuesta por la sintaxis del lenguaje, constituye la herramienta para trabajar con el lenguaje. •Se utiliza para organizar descripciones de lenguajes y traductores, así como reglas para entender los programas escritos en un lenguaje. Notación gramatical de un lenguaje Notación sintáctica La sintaxis de un lenguaje programación casi siempre se especifica usando alguna variante de una notación conocida como GRAMATICA INDEPENDIENTE DEL CONTEXTO o simplemente GRAMATICA. Las variantes de notación son: • BNF (Forma de Backus-Naurs) • BNFE (BNF extendida) • ESQUEMAS DE SINTAXIS Notación gramatical de un lenguaje BNF (Forma de Backus-Naurs) La siguiente notación describe la sintaxis de los números reales. <numero-real> ::= <secuencia-digitos> . <secuencia-digitos> <secuencia-digitos> ::= <digito> | <digito><secuencia-digitos> <digito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Otro ejemplo: <expresion> ::= <expresion> + <termino> | <expresion> - <termino> | <termino> <termino> ::= <termino> * < factor> | <termino> div <factor> | <factor> <factor> ::= <expresion> |<termino> | <constante> Notación gramatical de un lenguaje BNFE (BNF Extendida) Los símbolos no terminales comienzan con letras mayúsculas, los terminales que consisten en símbolos como + , - se colocan entre comillas sencillas y los símbolos terminales en negrita. Además: • Una barra vertical |, representa una opción • Los paréntesis, ( y ), se usan para agrupar • Las llaves, { y }, representan cero o mas repeticiones • Los corchetes, [ y ], representan una construcción opcional Ejemplo: Expresion ::= Termino { ( ´+´ | ´-´ ) Termino } Termino ::= Factor { ( ´*´ | div ) Factor } Factor ::= ´(´ Expresion ´)´ | Variable | Constante Notación gramatical de un lenguaje ESQUEMA DE SINTAXIS Se construye un sub-esquema para cada símbolo no terminal. Expresión Termino + Termino - Termino Factor * Factor div Factor ( Termino Variable Constante ) Notación grafica de un lenguaje Diagrama de Conway Un diagrama de conway es un grafo dirigido que tiene dos componentes esenciales, además de las líneas de flechas que sirven de conectivas. • El “rectángulo” para indicar que en ese punto hay una metanoción del vocabulario no terminal N ( y por tanto tendrá otro diagrama de conway para definirle). • El “circulo” para indicar que en ese punto hay un símbolo terminal, que por lo tanto será un elemento del vocabulario terminal T. En estos diagramas se acostumbrará a comenzar el recorrido por la izquierda, por la rama que suele llevar muy cercano a ella el nombre de la metanoción a definir, se sigue el recorrido en el sentido de las flechas y cada elemento que se va encontrando se toma y se concatena a lo que ya se tuviera. Notación grafica de un lenguaje Diagrama de Conway Entero Digito Identificador Letra Letra Digito Notación grafica de un lenguaje Diagrama de Conway Parametros ( Lista_id Lista_id Identificador , ) Compiladores e interpretes Conceptos relacionados Arquitectura de Computadoras Teoría de Lenguajes Lenguajes de Programación Compiladores Ingeniería de Software Teoría de Algoritmos Con algunas técnicas básicas de escritura de compiladores se pueden construir traductores para una gran variedad de lenguajes y máquinas Compiladores e interpretes Compiladores Un compilador es un programa que lee un programa en un lenguaje y lo traduce a un programa equivalente en otro lenguaje, y además informa al usuario sobre la presencia de errores en el programa de entrada programa fuente compilador mensajes de error programa objeto Compiladores e interpretes HISTORIA Computadora Persona Código Máquina Ensamblador Código Máquina Ensamblador Código Máquina Lenguaje Ensamblador Lenguaje Ensamblador Compilador Lenguaje de Alto Nivel Compiladores e interpretes Tipos de sistemas de compilación • ENSAMBLADOR Traducen programas escritos en lenguaje ensamblador a código máquina • COMPILADOR Traducen programas escritos en lenguaje de alto nivel a código intermedio o a código máquina • INTERPRETE No genera código objeto, analiza y ejecuta directamente cada proposición del Programa Fuente (PF) • PREPROCESADOR Sustituyen macros, incluyen archivos o extensión del lenguaje. Compiladores e interpretes Sistema de procesamiento de un lenguaje estructura del programa fuente preprocesador programa fuente compilador programa objeto en lenguaje ensamblador ensamblador código de máquina relocalizable biblioteca editor de carga y enlace código de máquina absoluto archivos obj.relocal. Compiladores e interpretes PARTES DE LA COMPILACIÓN • Análisis (Etapa Inicial): Divide al Programa Fuente en sus elementos componentes y crea una representación intermedia. Se determinan las operaciones y se registran en una estructura de árbol (ej. árbol sintáctico) • Síntesis (Etapa Final): Construye el Programa Objeto deseado a partir de la representación Intermedia (requiere técnicas más especializadas) Compiladores e interpretes UN AMBIENTE GENERAL DE COMPILACIÓN Fuente Análisis léxico Análisis sintáctico Análisis semántico Intermedio Generador de código Código relocalizable Enlazador Objeto Más: Sistemas de edición y depuración Compiladores e interpretes FASES DE UN COMPILADOR PROGRAMA FUENTE analizador léxico administrador de la tabla de símbolos analizador sintáctico analizador semántico generador de código intermedio optimizador de código generador de código manejador de errores PROGRAMA OBJETO Cada fase transforma al PF de una representación a otra Compiladores e interpretes ESQUEMA DE BLOQUES DE UN COMPILADOR FUENTE Compilador ANALISIS Scanner Parser SINTESIS Prep. para la Gen. del código OBJETO Gener. del código Tabla de símbolos Compiladores e interpretes ESTRUCTURA FUNCIONAL DE UN COMPILADOR (de una pasada) SENTENCIA Fuente Explorador Reconocedor Generador de código Tabla de símbolos Objeto Compiladores e interpretes HERRAMIENTAS PARA CONSTRUCCIÓN DE COMPILADORES Lex y YACC • Herramientas que nos permiten desarrollar componentes o la mayor parte de un compilador • Son un recurso invaluable para el profesional y el investigador • Existen paquetes freeware Teoría de lenguajes y compiladores Unidad I Analizadores lexicográficos Semana 1 Introducción