Diseño de Compiladores

Humberto Ortiz-Zuazaga
humberto.ortiz@upr.edu

Introducción

¿Que es un compilador? Muchas veces pensamos en el compilador como una caja negra que traduce un programa a un ejecutable:

graph LR;
 id1[/hello.c/]-->cc[cc -o hello hello.c];
 cc-->id2[/hello/];

En este curso vamos a descomponer el trabajo del compilador en multiples fases. Vamos a ver que hace cada fase, y vamos a implementar las fases en un lenguage de programmación.

Vamos a aprender Diseño de Compiladores construyendo varios compiladores para pequeños lenguajes. Esto nos ayudara a entender que es un compilador, y aprender como funciona una computadora de una forma bien concreta. Para hacer esto, vamos a utilizar una variedad de herramientas teoricas y practicas. En cierto sentido, compiladores amarra mucho del material que han estudiado en el bachillerato, desde programacion, estructuras de datos, algoritmos, teoria, y hasta matematicas discretas.

En particular, en este curso, vamos a utilizar el lenguage rust para implementar nuestros compiladores. Rust es un lenguaje relativamente nuevo, pero tiene mucho auge. Tiene razgos de lenguages funcionales, y nos va a permitir trabajar de forma natural con las estructuras que tenemos que utilizar para crear el compilador.

Como no enseñamos rust en el bachillerato, voy a dar una brevisima introduccion al lenguage, y luego vamos a comenzar a implementar compiladores para idiomas sencillos. Poco a poco vamos a añadair mas capacidades a nuestro lenguaje, y a nuestro compilador. Este concepto de comenzar con un idioma sencillo e ir implemmentando mas capacidades es el descrito en [1] y utilizado en el libro Essentials of Compilation An Incremental Approach de Jeremy G. Siek. Ese libro implementa scheme en un scheme, y he visto estudiantes confundir el lenguage de implementacion y el que estan compilando. Prefiero compilar un lenguage con otro. En otros años he utilizado un ML para el lenguage de implementacion. En 2019 use Modern Compiler Implementation in ML by Andrew Appel, que utiliza SML/NJ. En el 2020 utilize Ben Lerner's Spring 2020 Compiler lecture notes que utiliza OCaml. Este año vamos a seguir ese material, pero cambiando el lenguage de implementacion de ML a rust. Me gusta este acercamiento porque al final de cada seccion tenemos un compilador que funciona. SML/NJ y OCaml son lenguajes funcionales. Rust es parecido a los ML, asi que puede ser un buen fundamento para un curso de compiladores. Asi espero que los estudiantes se confundan menos, y terminen aprendiendo un lenguaje que los pueda ayudar en su carrera profesional.

[1] Ghuloum, Abdulaziz. "An incremental approach to compiler construction." Proceedings of the 2006 Scheme and Functional Programming Workshop, Portland, OR. Citeseer. 2006. http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

Tutorial breve de rust

OK, mentí. No voy a darles un breve tutorial de rust. Los voy a mandar a leer un breve tutorial de rust. O busquen los tutoriales en la pagina de rust.

Vayan y aprendan, yo los espero aqui.

Números

Vamos a construir un pequeño compilador que puede entender enteros.

No es un lenguaje muy interesante, pero el compilador tiene todos los razgos principales de un compilador de verdad, y podemos ir construyendo sobre el.

Lo primero es construir un proyecto de rust para nuestro compilador. Yo lo voy a llamar just-numbers, para recordarme que solo puede compilar numeros.

Ve a un directorio donde quieras almacenar el proyecto y corre:

cargo new just-numbers

esto crea un nuevo directorio just-numbers con varios archivos, incluyendo Cargo.toml y src/main.rs. Cambiense a este nuevo directorio en la consola.

La funcion main solo tiene un hello world. Vamos a modificarlo para leer un numero de un archivo, e imprimir ensamblador de x86_64 para almacenar el numero en el registro rax.

use std::fs;
use std::env;
use std::str::FromStr;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];

    let program_text = fs::read_to_string(filename)?;
    // println!("Input = {}", program_text);

    let program = i64::from_str(&program_text.trim())?;
    println!("section .text\n\
global our_code_starts_here\n\
our_code_starts_here:\n\
\tmov RAX, {}\n\
\tret\n", program);
    Ok(())
}

Si tuvieramos un archivo como 123.jn que tiene adentro solo el numero 123 podrimamos compilarlo con las siguientes instrucciones:

cargo build
cargo run 123.jn > 123.s

Y el archivo 123.s contendria las instrucciones en assembly para devolver 123.

section .text
global our_code_starts_here
our_code_starts_here:
	mov RAX, 123
	ret

La etiqueta our_code_starts_here dejaria 123 en el registro rax.

Ahora necesitamos un programa que reciba este resultado y haga algo util. En nuestro caso, vamos a hacer un programa en C que imprima el resultado.

#include <stdio.h>
#include <stdint.h>

extern int64_t our_code_starts_here() asm("our_code_starts_here");

int main(int argc, char** argv) {
  int64_t result = our_code_starts_here();
  printf("%ld\n", result);
  return 0;
}

Este programa declara our_code_starts_here como una funcion externa en assembly, y la llama, guardando el resultado en result. Luego imprime el resultado.

Ahora estamos listos para combinar el programa en C (nuestro "runtime") con el programa en assembly para hacer un programa completo.

nasm -f elf64 -o 123.o 123.s
gcc -g -o 123 main.c 123.o

*En la Mac, pueden ensamblar sustituyendo -f elf64 por -f macho64.

Si todo salio bien, si corren ./123 debe salir 123 en pantalla.

Conclusión

graph TB;
    jn[/123.jn/]-->rs[cargo run];
    rs-->s[/123.s/];
    s-->nasm[nasm];
    nasm-->obj[/123.o/];
    obj-->cc[gcc];
    main[/main.c/]-->cc;
    cc-->exe[/123/];

¡Hicimos un compilador! No parece mucho, y es algo frágil, pero tiene todos los componentes principales: lee un programa en ASCII, lo convierte a una representacion binaria, y lo traduce a lenguage de máquina. Hicimos varias trampas y usamos algunos trucos, pero funciona, y no es complicado (cabe en 19 lineas de rust).

En los siguientes capitulos haremos mas compiladores, y utilizaremos herramientas mas sofisticadas.

Incrementar

Aunque tenemos un compilador, hasta yo tengo que admitir que no es muy interesante. Solo podemos compilar programas que generen un entero de 64 bits. Para poder tenqer programas mas interesantes vamos a tener que añadir instrucciones a nuestro compilador.

Para lograr esto vamos a utilizar unas herramientas del curso de teoría: expressiones regulares y gramaticas libre de contexto (context-free grammar, o CFG). Además dividiremos el compilador en fases, donde cada fase consume lo que la anterior produce. Por ahora nos vamos a concentrar en las primeras dos fases: "lexing" y "parsing". Lexing utiliza expresiones regulares para dividir el input en lexemas o "tokens". Parsing lee una lista de tokens y utiliza CFG para dividir el input.

graph LR;
      jn[/123.jn/]-->lexer;
      lexer-->parser;
      parser-->dots[...];

Rust, igual que muchos otros lenguages, tiene herramientas que pueden generar lexers y parsers de una descripcion del lenguage. Collectivamente estas herramientas se llaman YACC, por una de las primeras, o "parser-generators", por su función. Vamos a utilizar la herramienta lalrpop para generar lexers y parsers en esta clase.

lexer y parser

Proyecto

Para utilizar lalrpop, vamos a crear un nuevo proyecto en rust.

cargo new incr

Hay que hacer unos cambios al Cargo.toml

[package]
name = "inc"
version = "0.1.0"
authors = ["Humberto Ortiz-Zuazaga <humberto.ortiz@upr.edu>"]
edition = "2018"
build = "build.rs" # LALRPOP preprocessing

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[build-dependencies] # <-- We added this and everything after!
lalrpop = { version = "0.19.0", features = ["lexer"] }

[dependencies]
lalrpop-util = "0.19.0"
regex = "1"

La linea de build indica que queremos que cargo corra codigo adicional cuando hagamos cargo build. El archivo build.rs contiene el codigo a correr (ver abajo). El archivo debe estar ubicado junto con el Cargo.toml. Luego en build-depencencies, indicamos que queremos lalrpop, y que lalrpop genere el lexer. Por ultimo, en dependencies traemos unas utilidades.

El archivo build.rs deben crearlo con el siguente contenido:

extern crate lalrpop;

fn main() {
    lalrpop::process_root().unwrap();
}

lexer y parser

El lexer y parser lo especificaremos en el archivo src/nums.lalrpop:

#![allow(unused)]
fn main() {
use std::str::FromStr;

grammar;

pub Num: i64 = <s:r"[0-9]+"> => i64::from_str(s).unwrap();
}

Este archivo importa la funciones de FromStr que utilizamos para convertir String a enteros. Luego declara una gramatica, que tiene un elemento publico Num. Si encontramos un String que consiste de solo digitos r"[0-9]+" entonces convertimos esa secuencia de digitos a un i64. La expression regular r"[0-9]+" es utilizada para crear el lexer, y lo que va a la derecha de => es código de rust que corre el parser cuando reconoce el lexema de la izquierda.

main

Para terminar el compilador, vamos a crear un src/main.rs que llame el parser y genere el ensamblador.

#[macro_use] extern crate lalrpop_util;

lalrpop_mod!(pub nums); // synthesized by LALRPOP

use std::fs;
use std::env;

fn compile(prog : i64) -> String {
    format!("section .text\n\
            global our_code_starts_here\n\
            our_code_starts_here:\n\
            \tmov RAX, {}\n\
            \tret\n", prog)
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let args: Vec<String> = env::args().collect();

    let filename = &args[1];

    let prog_text = fs::read_to_string(filename)?;
    let prog = nums::NumParser::new().parse(&prog_text);
    let instr = compile(prog.unwrap());
    println!("{}", instr);
    Ok(())
}

Probando el compilador

Podemos probar el compilador corriendolo con cargo:

cargo run 123.jn