5 de Enero, 2014

Mi propio lenguaje de programación

No sé que tienen los sistemas operativos y los lenguajes de programación que son tan interesantes de diseñar e implementar (al menos hasta cierto nivel de complejidad, que es más o menos cuando deja de ser divertido :P), pero a mi me pica el gusanillo de vez en cuando.

Hace años programé un intérprete para un lenguaje inventado (hasta cierto punto, era una especie de C) usando flex y bison, dos herramientas para generar compiladores e intérpretes, y fue muy entretenido y aprendí muchas cosas.

Lamentablemente eran tiempos de DOS (y pre-Internet, al menos para mi), con lo que todo aquello se perdió (no sé si es mejor así :D).

Estas vacaciones he vuelto a las andadas, aunque con un conjunto de herramientas ligeramente distinto: Python y PLY (que es una implementación en Python de Lex y Yacc; o lo que es lo mismo: flex y bison).

Además he cambiado el enfoque creando un compilador en lugar de un intérprete, generando código intermedio en C que puede ser compilado a código binario. Así que no es solo Python, también he tenido que escribir una buena cantidad de código C (especialmente el run-time del lenguaje).

Tomemos como ejemplo el siguiente programa:

# calculate the n-th Fibonacci number
def main() {
    def fib(n) {
        if(n <= 1) {
            return n;
        }
        return fib(n-1) + fib(n-2);
    }
    println(fib(10));
    return 0;
}

Los pasos para compilar el código son los habituales:

  1. Análisis léxico: usando lex se transforma el código en tokens con significado en nuestro lenguaje y que serán procesados por el parser.
  2. Análisis sintáctico: se analizan los tokens y se genera un árbol de sintaxis con yacc que permite evaluar qué es correcto o no en nuestro lenguaje.
  3. Generación de código: en mi caso genero código en C, comprobando algunas cosas como que no se acceda a variables que no existan o el número de argumentos de las funciones, que finalmente se compila con cualquer compilador de C estándar.

En nuestro ejemplo los token serían algo así como:

LexToken(DEF,'def',2,38)
LexToken(ID,'main',2,42)
LexToken(LPAR,'(',2,46)
LexToken(RPAR,')',2,47)
LexToken(LCB,'{',2,49)
LexToken(DEF,'def',4,53)
LexToken(ID,'fib',4,57)
LexToken(LPAR,'(',4,60)
LexToken(ID,'n',4,61)
LexToken(RPAR,')',4,62)
LexToken(LCB,'{',4,64)
...

Que al procesarlos con el parser se transforman en lo siguiente:

(15: func -> sub: [
  (2: params -> sub: [] value: None), (13: block -> sub: [
    (11: func -> sub: [(4: params -> sub: ['n'] value: None), ...

Con esa estructura de datos se genera el siguiente código C, que al compilarlo da un binario que cuando se ejecuta imprime el resultado esperado: 55.

El compilador está disponible en github: Juan's Toy Compiler; y como su propio nombre indica: es un juguete ;) (además ha sido un proceso de descubrimiento para mi y no estoy del todo seguro de hacer las cosas de la forma más adecuada).

En la página del proyecto hay una descripción del lenguaje, cuyas principales características son:

  • Soporta funciones con ámbito local, parámetros por referencia, recursividad y devolución de valores.
  • Tipado dinámico con tres tipos distintos: números enteros, números decimales (coma flotante) y cadenas de texto. No hay tipo booleano, se usan enteros como en C.
  • Operadores aritméticos y lógicos, con algunas conversiones automáticas (sin llegar a la pesadilla de Javascript :P).
  • Control de flujo con condicionales y bucles.
  • Algunas funciones internas como salida por pantalla o identificar el tipo de una variable.

Lo más interesante (e ineficiente, por cierto) es la implementación del tipado dinámico, que hace que el run-time se comporte en realidad como un intérprete (los operadores no saben qué tipo son los operandos hasta que están en tiempo de ejecución), y probablemente usar uthash para almacenar las variables.

Por lo demás es un juguete que no sirve para nada más que para tenerme entretenido un par de tardes, y por la satisfacción de haber creado mi propio lenguaje de programación ;).

Actualización: me acabo de acordar de mi intérprete de Forth, que me parece que es la última vez que me dio por hacer un intérprete :D.

Anotación por Juan J. Martínez, clasificada en: programming, jtc.

Los comentarios están cerrados: los comentarios se cierran automáticamente una vez pasados 30 días. Si quieres comentar algo acerca de la anotación, puedes hacerlo por e-mail.

Algunas anotaciones relacionadas: