Compiladores

15º Concurso de Trabajos Estudiantiles, EST 2012

41 Jornadas Argentinas de Inform´tica a Concurso de Trabajos Estudiantiles 2012

Categor´ ıa: Teor´ de la Computaci´n, Modelos Formales y Compiıa o ladores. T´ ıtulo: Implementaci´n de un compilador de C- -. o Autor: Riberi, Franco Gaspar. Docente: Francisco Bavera. C´tedra: a Taller de Dise˜o de Software. n Instituci´n: o Universidad Nacionalde R´ Cuarto. ıo

1

41 JAIIO - EST 2012 - ISSN: 1850-2946 - Página 536

15º Concurso de Trabajos Estudiantiles, EST 2012

Implementaci´n de un compilador de C- -. o
16 de mayo de 2012
Resumen Se presentar´ un compilador para un subconjunto de estructuras del a conocido lenguaje de programaci´n C, llamado C - -. Se describir´n las o a distintas etapas de implementaci´n, partiendo porel an´lisis l´xico de un o a e secuencia de caracteres y finalizando en la generaci´n de c´digo assembly, o o pasando por el an´lisis sint´ctico y sem´ntico, adem´s de las represena a a a taciones internas y las distintas optimizaciones. Este proyecto contempla diversos conceptos de asignaturas previas, tales como gram´ticas libres de a contexto, expresiones regulares, aut´matas, entre otros. o Ellenguaje de implementaci´n utilizado para el mencionado compilao dor fue C, bajo el sistema operativo GNU/Linux. Se utilizaron adem´s a diversas herramientas auxiliares, tales como Lex y Yacc para el an´lisis a l´xico y sint´ctico (LR) respectivamente. Adem´s se utiliz´ c´digo de tres e a a o o direcciones como lenguaje intermedio y se gener´ un assembly x86. o Palabras clave: C- -, an´lisisl´xico, an´lisis sint´ctico, an´lisis sem´ntia e a a a a co, c´digo 3 direcciones, assembly, generaci´n de c´digo. o o o

1

41 JAIIO - EST 2012 - ISSN: 1850-2946 - Página 537

15º Concurso de Trabajos Estudiantiles, EST 2012

1.

Introducci´n o

Los lenguajes de programaci´n son notaciones que describen los c´lculos a o a las personas y las m´quinas. La percepci´n del mundo en que vivimosdepende a o de los lenguajes de programaci´n, ya que todo software que se ejecuta en una o computadora se escribi´ en alg´n lenguaje de programaci´n. Pero antes de poder o u o ejecutar un programa, primero debe traducirse a un formato en el que una computadora pueda ejecutarlo. Los sistemas de software que se encargan de esta traducci´n se denominan Compiladores. A grandes rasgos un compilador o esun programa que puede leer otro programa escrito en un lenguaje (fuente) y traducirlo en un programa equivalente. Dada la importancia de tal herramienta en la ciencia de la computaci´n y o como condici´n necesaria de la c´tedra Taller de Dise˜o de Software (c´digo o a n o 3306) de la Universidad Nacional de R´ Cuarto surgi´ la implementaci´n de un ıo o o compilador para un subconjunto delconocido lenguaje de programaci´n C, al o cual se denomina C- -. El producto de este proyecto deber´ aceptar programas a escritos en C - -, y efectuar su compilaci´n produciendo un archivo ejecutable. o A continuaci´n se detallar´n algunos conceptos importantes y necesarios o a para tal implementaci´n. o

2.

Compiladores

Un compilador [1] puede considerarse como una simple caja que mapea unprograma fuente a un programa destino con equivalencia sem´ntica, como se a observa en la Figura 1.

Figura 1: Visi´n Abstracta de un compilador. o

Si se inspecciona esta simple caja podemos observar que existen dos procesos importantes: an´lisis y s´ a ıntesis. La parte de an´lisis (front-end) divide el programa fuente en componentes a e impone una estructura gramatical sobre ellas. Luego utilizaesta estructura para crear una representaci´n intermedia del programa fuente. Adem´s esta o a etapa recolecta informaci´n sobre el programa fuente y la almacena en una o estructura de datos conocida como tabla de s´ ımbolos, la cual pasa a la siguiente etapa junto a una representaci´n intermedia. o La parte de s´ ıntesis (back-end) construye el programa destino deseado a partir de la entrada...