21 marzo 2008

Un compilador sencillo paso a paso (1)

Voy a hacer un pequeño proyecto para estas vacaciones: un compilador sencillo.

No soy ningún experto en creación de compiladores, y por eso será un compilador sencillo y lo haré paso a paso. Quizá estos pasos ayuden a alguien más a entender un poco cómo funcionan estas herramientas, así que los dejaré disponibles aquí.

Más detalles:
  • Quiero crear el compilador en un lenguaje "razonablemente fácil de leer" (y por tanto de depurar) y que esté disponible para muchas plataformas. Por eso usaré el lenguaje Pascal como lenguaje "anfitrión". En concreto, yo desarrollaré desde Free Pascal para Windows.
  • Se tratará también de un compilador de lenguaje Pascal (realmente, de un lenguaje "parecido a Pascal"). Nuevamente por facilidad de lectura y de depuración, pero eso además da la posibilidad de que quizá algún día el compilador se pueda "compilar a sí mismo" y se puedan crear programas directamente desde la "máquina de destino".
  • En cuanto a esa máquina de destino, tiene que ser un sistema "razonablemente sencillo", pero considero más motivador usar un sistema real que un sistema "inventado". Por eso, usaré una arquitectura que a la vez es sencilla y fácil de programar: un ordenador "clásico" de los años 80, el Amstrad CPC, que usa un Z80 de 8 bits como procesador y que permite hacer muchas tareas de "alto nivel" mediante simples llamadas al firmware.
La mayoría de libros de compiladores comienzan por crear un analizador léxico, luego uno sintáctico, y van ampliando sucesivamente hasta llegar a crear un compilador completo. Mi aproximación va a ser radicalmente diferente. Con la esperanza de obtener algo "totalmente funcional" (aunque muy limitado) desde un primer momento, yo haré lo siguiente:
  • Crear un primer compilador que sólo reconozca una orden muy simple, avise en caso de error y genere el código de destino correspondiente.
  • Ampliar para que reconozca tres órdenes distintas, con parámetros sencillos, y las acepte en cualquier orden.
  • Ampliar nuevamente para que fuerce a una estructura de programa concreta (el programa deberá comenzar por "program", el cuerpo deberá estar entre "begin" y "end", las órdenes deberán terminar en "punto y coma").
  • Añadir la posibilidad de declarar y usar variables.
  • Poder hacer comparaciones simples ("if").
  • Añadir variables de más de un tipo (numéricas, carácter) y hacer las comprobaciones de tipo correspondientes.
  • Permitir la creación de procedimientos ("procedure"), que permitan crear programas modulares para la máquina objetivo.
  • ...
Este primer acercamiento reconocerá sólo la orden CLS, encargada de borrar la pantalla. La orden en lenguaje ensamblador de un Amstrad CPC equivalente es CALL &BB6C, que en código máquina sería la secuencia de bytes CD, 6C, BB (expresados en hexadecimal).

Para simplificar la prueba de los programas destino creados, el compilador no generará ensamblador. Ni siquiera creará un fichero ".BIN" de código máquina, sino un fuente en Basic capaz de "generar ese código máquina". Así, para una única orden CLS, se obtendría el siguiente programa, que lee los bytes en hexadecimal, los coloca a partir de la dirección 40.000 de la memoria y finalmente llama a esa dirección para poner el programa en marcha:


10 DATA CD,6C,BB: ' CALL &BB6C
20 DATA C9: ' RET
30 longitud = 3
40 MEMORY 39999
50 FOR n=40000 TO 40000+longitud
60 READ a$:POKE n,VAL("&"+a$)
70 NEXT
80 CALL 40000


Con todas estas consideraciones, el primer acercamiento al compilador es muy sencillo:
  • Un procedimiento que obtiene una orden (sólo una) del usuario, desde el teclado.
  • Un procedimiento que analiza la orden, y da un mensaje de error si no es CLS.
  • Un procedimiento que genera el código de destino (que por ahora es fijo).

El fuente sería así:




program cpcPaChi;

(* Un compilador de Pascal chiquitito para CPC
Por Nacho Cabanes - Version 0.01, preliminar

Versiones hasta la fecha:

Num. Fecha Cambios
---------------------------------------------------
0.01 21-Mar-2008 Preliminar: solo acepta CLS por teclado
y genera el codigo correspondiente
*)


var
ficheroDestino: text;
orden: string;


(* Obtiene una orden del programa fuente. En esta version, solo
es una unica orden, y solo se admite "CLS" *)
procedure obtenerOrden;
begin
write('Introduzca la orden a traducir: ');
readln(orden);
end;

(* Analiza la orden que el usuario ha dado, y sale con un mensaje
de error si es incorrecta *)
procedure analizarOrden;
begin
if upcase(orden) <> 'CLS' then
begin
writeln('Error: orden no reconocida. Se esperaba: CLS');
halt;
end;
end;

(* Genera el codigo de destino: codigo maquina de Amstrad CPC
dentro de un cargador en Basic *)
procedure generarCodigo;
begin
assign( ficheroDestino, 'salida.bas' );
rewrite( ficheroDestino );
writeln( ficheroDestino, '10 DATA CD,6C,BB: '' CALL &BB6C' );
writeln( ficheroDestino, '20 DATA C9: '' RET' );
writeln( ficheroDestino, '30 longitud = 3' );
writeln( ficheroDestino, '40 MEMORY 39999' );
writeln( ficheroDestino, '50 FOR n=40000 TO 40000+longitud' );
writeln( ficheroDestino, '60 READ a$:POKE n,VAL("&"+a$)' );
writeln( ficheroDestino, '70 NEXT' );
writeln( ficheroDestino, '80 CALL 40000' );
close(ficheroDestino);
end;

(* Cuerpo del programa *)
begin
obtenerOrden;
analizarOrden;
generarCodigo;
end.

4 comentarios:

Anónimo dijo...

Llevo varios años desarrollando y queria poder realizar un pequeño compilador para trabajar con documentos xml. No sabía por donde comenzar. Pero tu articulo me dio nuevas ideas para hacerlo. Asi que gracias por tu información. Sabré apreciarla.

Marcelo Rojas Rojas
Abaddon.1974@hotmail.com

CaStarCo dijo...
Este comentario ha sido eliminado por el autor.
CaStarCo dijo...

Para el que quiera el código ensamblador sobre x86 (sintaxis AT&T) aquí lo tiene :) . (Lo hago para ir probando el código que produce el compilador a medida que voy avanzando, se puede compilar directamente con gcc o gas)

.data
command:[tabulador].string "clear"

.text
[tabulador].global main
main:
[tabulador]pushl $command
[tabulador]call system
[tabulador]addl $4, %esp

[tabulador]ret

Anónimo dijo...

En mi caso me gustaria saber si hay algun libro para aprender a crear compiladores, seguro lo comprare, saludos.

Desde Mexico.