Proceso de Compilación: Análisis Léxico, Sintáctico y Generación de Código
Análisis Léxico
El analizador léxico lee el flujo de caracteres que componen el programa fuente y los agrupa en secuencias significativas, conocidas como lexemas. Para cada lexema, el analizador léxico produce como salida un token.
Análisis Sintáctico (Parsing)
El análisis sintáctico o parsing utiliza los primeros componentes de los tokens producidos por el analizador léxico para crear una representación intermedia en forma de árbol que describa la estructura gramatical del flujo.
Gramática Libre de Contexto (GLC)
Una gramática libre de contexto consiste de:
- Un conjunto de no terminales N
- Un conjunto de terminales T
- Un símbolo inicial S (no terminal)
- Un conjunto de producciones
La idea de una GLC es verificar la membresía en el lenguaje («sí» o «no») y obtener el árbol sintáctico de la entrada. También se necesita para manejar errores y para una implementación de la GLC.
Árbol Sintáctico
Un árbol sintáctico tiene terminales en las hojas y no terminales en los nodos interiores.
Análisis Gramatical
El análisis gramatical es la tarea de determinar la sintaxis o estructura de un programa.
Una gramática libre de contexto utiliza convenciones para nombrar y operaciones muy similares a las correspondientes en las expresiones regulares.
La estructura del árbol sintáctico depende en gran medida de la estructura sintáctica particular del lenguaje.
Una gramática libre de contexto es una especificación para la estructura sintáctica de un lenguaje de programación.
Ambigüedad
Una gramática es ambigua si puede generar una secuencia de símbolos con dos árboles sintácticos diferentes.
Representaciones Intermedias
Existen dos representaciones intermedias principales: notación sufija (polaca inversa) y cuádruplas.
Notación Polaca Inversa (Sufija)
Los operadores diádicos (o binarios) pueden especificarse mediante tres notaciones principales:
- Prefija: el operador diádico es analizado antes que sus operandos.
- Infija: el operador diádico es analizado entre sus operandos.
- Sufija: el operador diádico es analizado después que sus operandos.
Existen dos problemas principales en la polaca inversa:
- Construir la notación sufija a partir de la infija.
- Analizar la notación sufija en el segundo paso de la compilación.
Generador de Código
El generador de código realiza tres tareas: selección de las instrucciones, localización de registros y asignación, y ordenar las instrucciones. Depende de la representación intermedia, el lenguaje destino y el run-time system.
Conjuntos de Instrucciones y Arquitecturas
- RISC (Reduced Instruction Set): muchos registros, instrucciones de tres direcciones, modos de direccionamiento simples, conjunto de instrucciones simple.
- CISC (Complex Instruction Set): pocos registros, instrucciones de dos direcciones, muchos modos de direccionamiento, instrucciones de longitud variable.
- Basada en Pila (Stack Based): las operaciones se realizan sobre operandos que están en el tope de la pila, requiere muchas operaciones de intercambio y copia (swap, copy). Ejemplo: JVM (Java Virtual Machine).
Localización y Asignación
Localización: qué variables se asignan a registros.
Asignación: establecer la relación variable-registro.
Orden de las Instrucciones
El orden puede afectar la eficiencia del código. En algún orden se puede requerir menos registros que en otro. Encontrar un orden óptimo es un problema NP-Completo.
Costo de las Instrucciones
El costo de cada instrucción es uno más el costo de los modos de direccionamiento que usa.
El uso de registros no genera costo (costo 0).
Cada acceso a memoria, o el uso de constantes, agrega 1 al costo.
Grafos de Flujo
Representación en grafos del código intermedio. Permite: mejor localización de registros, mejor selección de instrucciones. Se construye partiendo el código intermedio en bloques básicos.
Los bloques básicos se convierten en nodos de un grafo de flujos, cuyos arcos indican qué bloques pueden seguir a otros bloques.
Bloques Básicos
Método de construcción:
Encontrar instrucciones líderes:
- La primera instrucción del código intermedio.
- Cualquier instrucción que es destino de un salto condicional o incondicional.
- Cualquier instrucción que sigue inmediatamente a un salto condicional o incondicional.
Para cada líder, su bloque básico se forma consigo misma y las instrucciones que le siguen, sin incluir otro líder ni el final del programa.
Gramática
Una gramática G es una tupla (T, N, I, P) donde:
- T: conjunto de símbolos terminales.
- N: conjunto de símbolos no terminales.
- I ∈ N: símbolo inicial.
- P: conjunto de producciones.
Letras mayúsculas representan símbolos no terminales.
Letras minúsculas representan símbolos terminales.
Clasificación de las Gramáticas
- Regulares
- Libres del Contexto
- Dependientes del Contexto
- Generales