Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 2 Compiladores e intérpretes image, image, image, image, image…
Capítulo 2
Compiladores e intérpretes
2.1 Enfoques del lenguaje de programación Implementación
2.1.1 ¿Compilar o interpretar?
Cuando un programa pasa por un compilador que genera código para alguna máquina de destino, el código puede ejecutarse en la arquitectura mymachine y tiene el efecto de ejecutar el programa original.
El hardware del procesador interpreta las instrucciones de máquina generadas por el compilador y el estado de la cpu se altera.
El intérprete lee el código de la máquina virtual y emula la ejecución de ésta, instrucción por instrucción.
Ventajas
● El diseño del código generado por el compilador no está condicionado por la arquitectura de la máquina de destino.
● Se mejora la portabilidad.
● El código de la máquina virtual puede diseñarse para que sea especialmente compacto.
● La depuración y supervisión en tiempo de ejecución pueden incorporarse al intérprete de la máquina virtual, permite mejorar la seguridad en la ejecución del programa.
Desventaja
Es la cuestión de la eficiencia, es probable que el código interpretado sea más lento que la ejecución nativa.
Si el diseño de la máquina virtual es idéntico al del lenguaje que se implementa, el compilador se simplifica mucho, pero el intérprete se ocupa de decodificar y analizar este código.
Enfoque tradicional para la implementación de un lenguaje de programación
Consiste en escribir un programa que traduzca los programas escritos en ese lenguaje a programas equivalentes en el código máquina del procesador de destino.
Tener una definición precisa de las reglas y la estructura de los programas escritos,
La naturaleza del lenguaje afectará al diseño del software traductor.
Ejemplo
Si mylanguage es un lenguaje de programación de alto nivel y mymachine es un procesador implementado en hardware, el programa traductor se llama compilador.
Si mylanguage es un lenguaje ensamblador, el traductor se llama ensamblador y es más fácil de implementar que un compilador.
Un enfoque para la implementación del lenguaje asume que mymachine es una máquina virtual.
Se trata de una máquina para la que no existe el hardware correspondiente y sólo existe como consecuencia de una pieza de software que emula las instrucciones de la máquina virtual.
El traductor se utiliza para traducir de mylanguage a un lenguaje de alto nivel.
Cual sea la forma de mymachine y el código generado, se requiere una especificación al igual que para mylanguage.
El traductor preserva la semántica del programa en mylanguage al ejecutar el código generado en mymachine .
La semántica de mylanguage puede especificarse formal o informal y el usuario de mylanguage debe tener una idea de lo que cada programa válido debe significar.
El traductor va a ser una pieza de software compleja.
Un compilador puede construirse en dos fases:
Fase de análisis
Lee el programa fuente en mylanguage, creando estructuras de datos internas que reflejan su estructura sintáctica y semántica.
Fase de síntesis
Genera código para mymachine a partir de las estructuras de datos creadas por la fase de análisis.
2.2 Definición de un lenguaje de programación
2.2.1 BNF y variantes
2.2.1.1 Limitaciones
La sintaxis formal de los lenguajes, expresada en forma de BNF, carecerá de una especificación para algunas de las reglas de construcción de programas bien formados.
Se debe al hecho de que una especificación BNF no puede expresar restricciones contextuales.
Un ejemplo es la gramática de dos niveles.
Utiliza dos conjuntos de reglas en dos metalenguajes diferentes.
Una de las ventajas de conservar esta forma de especificación sintáctica es que la generación de la fase de análisis del compilador puede hacerse muy sencilla.
Forma Backus-Naur o forma normal Backus
Se uso en la definición de la sintaxis de ALGOL 60.
Es un metalenguaje sencillo pero potente, se ha utilizado para apoyar las definiciones formales.
Una especificación BNF
Es un conjunto de reglas, cada una define un símbolo del lenguaje.
BNF está lejos de ser lo potente como para definir la sintaxis del inglés o de otro lenguaje natural.
Algunas reglas definen la sintaxis de las expresiones aritméticas simples que utilizan valores enteros y operadores +, -, * y /, junto con paréntesis para la agrupación.
No existe límite máximo para la longitud de expresiones que pueden ser generadas por estas reglas.
Las reglas BNF pueden utilizarse para apoyar la idea de la precedencia de los operadores, aquí el operador * es mayor que la del operador +: la multiplicación se "hace antes" que la suma.
Las reglas BNF pueden utilizarse para expresar la asociatividad de los operadores.
Una variante se llamó Forma Backus-Naur Extendida (EBNF)
Conserva los principios básicos de BNF, pero el detalle sintáctico es un poco diferente.
Los símbolos terminales están entre comillas dobles, cada regla de producción termina con un punto y aparte y el token separa el token no terminal de su definición.
● Se pueden utilizar paréntesis para indicar la agrupación en la regla.
● Característica específica para indicar la opcionalidad en una regla: X] especifica que X es opcional.
● Se admite la repetición: {X} implica cero o más instancias de X.
El uso de diagramas de sintaxis en la definición de los lenguajes de programación, utiliza una notación pictórica para representar la sintaxis de cada uno de los tokens no terminales del lenguaje.
2.2.2 Semántica
La semántica formal abre la posibilidad de demostrar la corrección del programa y elimina la posibilidad de ambigüedad semántica.
Enfoques para la especificación de la semántica de los lenguajes de programación:
La semántica operativa, denotativa y axiomática, basando una descripción formal de la semántica en la sintaxis del lenguaje.
Las gramáticas de atributos se utilizan para ayudar a definir aspectos de la semántica de un lenguaje de programación.
Los símbolos de la gramática se asocian a los atributos.
Permiten la especificación formal de la semántica operativa del lenguaje, apoyando comprobaciones semánticas.
Un enfoque alternativo
Especifica la semántica de forma más indirecta mediante la producción de una implementación de referencia.
Se selecciona una implementación concreta para definir cómo deben comportarse las demás implementaciones.
La simplicidad de este enfoque es atractiva.
Tercer enfoque
Consiste en especificar la semántica utilizando un lenguaje natural.
Se utiliza un texto en un lenguaje natural como el inglés para describir las reglas semánticas.
Hay que tener cuidado para evitar omisiones o ambigüedades y evitar que la especificación sea demasiado larga.
Es importante para los usuarios del lenguaje de programación y para el escritor del compilador.
La definición proporciona información sobre cómo escribir programas en el lenguaje.
Especificar el conjunto infinito de programas válidos y lo que significa cada programa válido.
La definición debe ser clara, precisa, completa, sin ambigüedades y comprensible para los usuarios.
La especificación de la sintaxis es fundamental.
La sintaxis define las secuencias de caracteres que pueden formar un programa válido.
El significado de los programas se especifica por la semántica del lenguaje.
La definición de la sintaxis del lenguaje se hace con un enfoque formal y se ha desarrollado una serie de metalenguajes.
El uso de un metalenguaje sencillo para definir la sintaxis da como resultado una especificación sintáctica compacta y completa.
2.3 Análisis de los programas
2.3.1 Gramáticas
La gramática (G) de un lenguaje se define como una 4-tupla G = (N, T, S, P) donde:
● N es el conjunto finito de símbolos no terminales.
● T es el conjunto finito de símbolos terminales (N y T son disjuntos).
● S es el símbolo inicial, S ∈ N.
● P es el conjunto finito de reglas de producción.
Si se utilizan diagramas BNF, EBNF o de sintaxis para especificar las reglas de producción, todas las reglas tienen la particularidad de que los lados izquierdos son siempre símbolos no terminales simples.
Una gramática proporciona las reglas para derivar cadenas de caracteres que se ajustan a las reglas sintácticas de la gramática.
Una forma sentencial es cualquier cadena que pueda derivarse de S, el símbolo inicial.
Una frase es una forma sentencial que no contiene ningún símbolo no terminal.
Una sentencia es un programa completo, que sólo contiene símbolos terminales.
2.3.2 Jerarquía de Chomsky
Una regla de producción tiene la forma α → β
Se traduce como cualquier cosa puede transformarse en cualquier cosa.
Noam Chomsky elaboró una clasificación jerárquica de las gramáticas formales, se compone de cuatro niveles:
● Una gramática de tipo 0, una gramática libre o sin restricciones contiene producciones de la forma α → β.
● Una gramática de tipo 1 o sensible al contexto tiene producciones de la forma αAβ → αγβ.
● Una gramática de tipo 2 o libre de contexto tiene producciones de la forma A → γ donde A es un único símbolo no terminal.
● Una gramática de tipo 3, una gramática regular o una gramática de estado finito pone más restricciones a la forma de las producciones. Las producciones son de la forma A → a o A → aB.
2.3.3 Análisis sintáctico
2.3.3.1 La salida del analizador sintáctico
El analizador sintáctico obtiene un flujo de tokens
A partir del analizador léxico de un compilador convencional y los hace coincidir con los tokens de las reglas de producción
Indica si la entrada del analizador sintáctico forma una frase sintácticamente correcta.
Esta estructura de datos es un árbol
El árbol se construye a medida que realiza su secuencia de reducciones y la forma del árbol refleja refleja la especificación sintáctica del lenguaje.
El nodo raíz del árbol corresponde al símbolo inicial de la gramática.
Refleja la definición sintáctica formal del lenguaje y puede resultar redundante.
2.3.3.2 Estrategias de análisis sintáctico
La mayoría de los analizadores sintácticos pueden clasificarse como descendentes o ascendentes.
Analizador sintáctico descendente
Comienza con el símbolo inicial de la gramática y con la raíz del árbol de análisis sintáctico.
Su objetivo es hacer coincidir la entrada con la definición del símbolo inicial.
Cuando el lado derecho de una producción que se está emparejando con la entrada contiene símbolos terminales, estos pueden ser con la cadena de entrada
Si está haciendo reducciones repetidas, el orden y la elección están controlados por la estructura del conjunto de producciones.
Analizador sintáctico ascendente
Empezamos con la cadena de entrada, elegimos una subcadena que coincida con el lado derecho, esta reemplaza la subcadena con el lado izquierdo y repetir hasta que quede el símbolo inicial.
El árbol de análisis sintáctico se construye hacia arriba desde las hojas, llegando finalmente al símbolo inicial en la raíz.
El problema clave aquí es determinar qué reducciones aplicar y en qué orden.
Hace coincidir las subcadenas con los lados derechos de las producciones, sustituyendo las subcadenas por el lado izquierdo de la producción.
Es posible que podamos alcanzar el símbolo inicial a través de varios conjuntos de operaciones de reducción.
Se tiene que considerar la idea de las gramáticas formales y las notaciones asociadas.
2.4 Estructura del compilador y del intérprete
2.4.1 Análisis léxico
Lee los caracteres del programa fuente y los agrupa en un flujo de tokens léxicos.
Cada token léxico es un componente sintáctico básico del lenguaje de programación.
Son tokens como números, identificadores, signos de puntuación, operadores, cadenas, palabras reservadas, etc.
Los comentarios pueden ignorarse a menos que el lenguaje defina componentes sintácticos especiales codificados en comentarios.
Los espacios en blanco pueden ser ignorados excepto, cuando tengan algún significado sintáctico.
La sintaxis de tokens léxicos básicos es sencilla, y puede especificarse en términos de la gramática de Chomsky de tipo 3.
La salida del analizador léxico es un flujo de tokens que se pasa al analizador sintáctico.
2.4.2 Análisis sintáctico
Agrupa y estructura los tokens léxicos según las reglas sintácticas del lenguaje.
Si la secuencia no es sintácticamente correcta, el analizador sintáctico debería informar de un error y realizar alguna acción de recuperación.
Construye una estructura de datos que representa la estructura sintáctica de la entrada.
Se basa en un tipo de árbol en el que los nodos representan componentes sintácticos definidos por la gramática.
Esta estructura de datos debe contener o enlazar con toda la información necesaria para las fases de compilación
Tratar los tokens léxicos utilizando un enfoque de análisis gramatical de tipo 2.
Al dejar que el analizador léxico se ocupe de estos tokens mejora la eficiencia del compilador.
2.4.3 Análisis semántico
Los lenguajes tipificados pueden requerir que los nodos del árbol estén etiquetados con un tipo de datos.
La complejidad aumenta cuando el lenguaje que se compila permite tipos definidos por el usuario.
Segunda tarea de esta fase
Aplanar el árbol de análisis sintáctico para producir alguna forma de código intermedio.
Debe ser sencillo generar este código intermedio recorriendo el árbol.
La información de tipo se preserva para que el código intermedio sea funcionalmente equivalente al programa fuente original.
Esta representación puede considerarse como el código máquina de una máquina virtual.
2.4.4 Optimización independiente de la máquina
La generación de código intermedio por medio de un simple recorrido en forma de árbol dará lugar a un código con oportunidades de mejora.
El análisis postsemántico es una buena etapa de la compilación para la optimización del código.
La representación intermedia se habrá diseñado teniendo en cuenta la optimización.
La eliminación de código redundante, el alineamiento de funciones de bucle, análisis de dependencia y flujo, etc., pueden realizarse aquí.
La salida de esta fase es una representación del programa que se compila en una forma intermedia.
2.4.5 Generacion de codigo
Esta fase lee el código intermedio y produce instrucciones de la máquina de destino.
La implementación requiere la manipulación de detalles complejos.
El generador de código tiene que
Seleccionar las instrucciones de máquina adecuadas.
Tratar con un esquema de asignación de almacenamiento para todas las variables y estructuras.
Generar código para interactuar con las bibliotecas y el SO.
2.4.6 Optimización en función de la máquina
La gestión de algunas compensaciones puede ser difícil y los objetivos deben ser claros.
El resultado final del compilador es un programa que se ejecute en la máquina de destino.
La salida puede ser un tipo de archivo de objetos o un archivo de lenguaje ensamblador.
2.4.7 Tablas de símbolos
Es una estructura de datos compleja
Soporta una búsqueda de nombres eficiente y accesible.
El analizador léxico puede insertar símbolos en esta tabla.
La fase de análisis semántico hace un uso intensivo de la tabla de símbolos, y puede generar código intermedio.
2.4.8 Problemas de aplicación
Hay muchas cuestiones prácticas que hay que tener en cuenta a la hora de diseñar el plan de implementación de un compilador.
Es posible que haya que escribir más software que el compilador o el intérprete.
La tarea puede descontrolarse fácilmente, pero hay muchas rutas de implementación estándar.
El compilador realiza 2 tareas. La fase de análisis y la fase de síntesis, se denomina front-end y back-end.
