Crea tu propio compilador – Cap. 4 – Inventando un lenguaje

4.1 Introducción

El siguiente paso en la creación de nuestro compilador, será la parte más divertida, que es la creación de un lenguaje nuevo que será el lenguaje que va a entender nuestro compilador.

Aunque podríamos dejar volar la imaginación para crear lenguajes de cualquier tipo, para este proyecto en particular, vamos a cumplir las especificaciones ya establecidas con anterioridad, como que el lenguaje debe ser de alto nivel.

De todas formas queda a merced del lector el poder plantear su propio lenguaje (sin apegarse necesariamente a nuestros objetivos [1. En nuestro caso, el objetivo más limitante es que el compilador se pueda compilar a sí mismo. Si se obvia este requerimiento, se puede tener mayor libertad y capacidad de crear un lenguaje más completo que el que aquí definimos]), siempre teniendo en cuenta que mientras más complejo sea, mayor será la complejidad de la implementación.

Implementar completamente un lenguaje ya existente, con todas sus características, es una tarea descomunal para una sola persona, aún si elegimos un lenguaje sencillo como Basic o C. Ni que decir de lenguajes como C++ u Object Pascal o alguno de tipo funcional.

El lenguaje que aquí planteo puede servir como guía de implementación en caso de que el lector opte por crear su propio lenguaje.

4.2 Teoría de Compiladores

Lenguajes para crear lenguajes

Antes de entrar de lleno en la definición de nuestro lenguaje, revisaremos algo sobre la teoría en la definición de lenguajes, referido principalmente a los lenguajes que se usan para crear otros lenguajes.

No es necesario dominar esta teoría para crear nuestro lenguaje o compilador, pero resulta útil conocer algo del fundamento o marco teórico que soporta a las gramáticas.

En el siguiente diagrama muestro las tecnologías que soportan a las computadoras desde su nivel más bajo que es la Física y las Matemáticas, indicando al lado derecho los lenguajes que soportan esa tecnología [1. Por encima de estos niveles podemos decir que se encuentran los algoritmos que soportan a los programas y que se escriben en los lenguajes de programación que se definen en los niveles más bajos.]:

Figura 4.1 – Lenguajes que describen a las tecnologías de las computadoras.

La parte superior de la figura nos indica que los lenguajes de programación se definen usando lenguajes como Backus Naur, EBNF o los diagramas de sintaxis.

Puede resultar extraño que los lenguajes necesiten definirse otro lenguaje, pero lo cierto es que es algo completamente natural. La gramática española está definida en español y los diccionarios en español se escriben en español, al margen de que puedan definirse en inglés u otro idioma.

Usar el español para describir al español es, de alguna forma similar, a escribir un compilador en el mismo lenguaje que el compilador compilará.

Notación Backus Naur

El lenguaje Backus Naur o la Notación de Backus Naur (BNF) es probablemente la forma más usada para describir a los lenguajes de programación, es por ello que se le considera un «metalenguaje». Fue creada por John Backus y mejorada por Peter Naur en la definición del lenguaje ALGOL 60.

La Notación Backus–Naur define un conjunto de símbolos usando expresiones de la forma:

<símbolo> ::= <expresión>

Los símbolos se escriben entre los caracteres «<» y «>».

Las expresiones se construyen a partir de:

  • Caracteres o letras, como «A», «b» o «,». Llamados también símbolo terminal.
  • Otros símbolos como <número> o <sentencia>. Llamados también símbolo no-terminal.

Lo sorprendente de las expresiones en BNF es que solo necesitan un operador de opciones múltiples («|») para crear todas sus definiciones. ¿Dónde está el truco? La potencia de BNF reside en que los símbolos se pueden definir de forma recursiva, de otra forma todas las definiciones se quedarían en simples opciones de caracteres.

Como ejemplo consideremos la siguiente definición de identificadores en notación BNF:

<número> ::= <dígito> | <dígito> <número>
<dígito> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Esta forma de notación es la clásica en BNF. Se empieza con la definición de un símbolo de mayo nivel, seguido de las definiciones de símbolos de menor nivel o terminales.

La opción de tipo «<dígito> | <dígito> <número>» es una de las potentes y nos indica que el símbolo <número> puede ser un simple dígito como «0», «1» o «9», o que puede ser un dígito seguido de otro <número>. Algo como «01» o «12», pero como ahora número puede ser de dos dígitos, puede ser también de tres dígitos y así sucesivamente. Esta definición sería equivalente a la que podríamos definir usando la expresión regular «\d+» o «[0-9]+».

Podemos crear definiciones más elaboradas como las de un identificador:

<identificador> ::= <letra> | <identificador> <letra> | <identificador> <dígito>
<letra> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
<dígito> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Existen diversas variaciones a la notación BNF (sin contar los cambios en la sintaxis original que suelen hacer). Una de ellas es la notación EBNF que agrega operadores adicionales a la notación BNF, similares a los que se tienen en expresiones regulares. Otras notaciones adicionales son ANF, CDL

Un lenguaje gráfico, que también permite definir un sintaxis, es el llamado Railroad diagram (Diagrama de ferrocarril). En estos diagramas se dibuja la secuencia que debería seguir un hipotético autómata para implementar un analizador léxico.

Como ejemplo, el siguiente diagrama en Railroad define la sintaxis de un número entero:

Figura 4.2 – Sintaxis en diagrama de ferrocarril

4.3 Nuestro lenguaje

Recordando las especificaciones de nuestro proyecto, que se discutieron en la sección 1.2 (del artículo 1), podríamos definir las especificaciones de nuestro lenguaje de la siguiente forma:

  1. Debe ser un lenguaje de alto nivel.
  2. Debe ser Imperativo. Alejado de la complejidad de lenguajes declarativos o funcionales.
  3. Debe ser tipado. Así se facilita el análisis de expresiones y detección de errores.
  4. Debe contar con solo dos tipos de datos. Lo necesario para poder ser autocontenido.
  5. Reducida cantidad de instrucciones. Para no complicar la implementación.

Adicionalmente, aunque no está directamente en las especificaciones del lenguaje, de los objetivos del proyecto, se deduce que el lenguaje debe tener la suficiente potencia como para poder escribir un compilador. Esta especificación adicional se contrapone con la simplicidad que definen las especificaciones anteriores.

Como queremos que el lenguaje pueda compilar un código fuente, lo más lógico es que este este código se encuentre en un archivo, así que el lenguaje debe tener funciones para leer archivos, aunque sea de texto.

Otra de las funcionalidades que debería tener el lenguaje, dado que deberá poder implementar un analizador léxico, será que debe disponer de funciones y operadores para manipulación de cadenas, y por supuesto debe tener el tipo de dato cadena.

Ahora, es posible que el lenguaje no implemente el tipo cadena (lo cual sería un alivio), y manejara todo como arreglos de caracteres, al mismo estilo de C, pero esto implicaría hacer al compilador aún más complejo, porque seguramente debería implementar punteros y su aritmética respectiva.

El soporte del lenguaje para números es mínimo y solo nos basta con manejar 1 tipo de dato numérico entero, que nos puede servir a su vez como carácter (de forma similar al tipo «char» del C) o como valor booleano, si restringimos su valor a 0 o 1.

Otra de las características que debe tener el lenguaje, es poder soportar el uso de funciones o procedimientos, porque es lo mínimo que se puede pedir para hacer a un programa, algo modular. De momento no se tiene pensado implementar librerías externas o algún tipo de módulo, para no complicar el proyecto.

Como no estamos restringidos a una sintaxis en particular, podríamos usar en principio, cualquiera. Inclusive podríamos usar palabras reservadas en castellano o cualquier otro idioma.

El lenguaje que yo propongo aquí, y al que llamaré «Titan», tomará elementos de Pascal y Basic porque por un lado son lenguajes con una sintaxis simple y por otro lado, como vamos a usar Pascal para crear la primera versión del compilador, nos conviene que nuestro lenguaje se parezca a Pascal, de modo que al final, cuando tengamos que escribir nuestro compilador en este nuevo lenguaje, la migración no sea tan complicada.

El Código Fuente

Por cuestiones de simplicidad, nuestro lenguaje será sensible a la caja, es decir, que diferenciará mayúsculas de minúsculas. Hacer al lenguaje insensible a mayúscula/minúscula, es algo sencillo, pero implica un trabajo adicional (como implementar las funciones de transformación), y considerando que nuestro objetivo inicial es simplificar el lenguaje, lo más que se pueda, prescindiremos de esta característica.

Otro detalle adicional, para simplificar nuestro compilador, es que solo manejaremos un tipo de datos cadena, y para simplificar su implementación, las definiremos de un tamaño fijo, de 255 caracteres, al mismo estilo de Pascal, en sus primeras versiones.

Debido a esta limitación, tampoco se podrán tener, en el código fuente, líneas de más de 255 caracteres, porque no habría forma de guardarlas de forma sencilla.

En aras de la simplicidad se estará usando el punto y coma como delimitador de instrucciones. Otra opción sería usar el fin de línea como delimitador, al igual que se hace en Basic o Python, pero esta forma de delimitar instrucciones puede ser problemática de implementar y complicaría la futura migración del código fuente del compilador.

Un detalle adicional, es que no incluiremos rutinas de verificación de errores en algunas instrucciones. De esta forma simplificaremos el código, pero hay que dejar en claro que un buen diseño, implica siempre, manejar rutinas de protección de errores.

El lenguaje que defino aquí, usa palabras del alfabeto inglés, por comodidad, pero bien se puede usarse español o cualquier otro idioma.

Estructura de un programa

Para facilitar le implementación del compilador vamos a definir una estructura con el siguiente orden:

Figura 4.3 – Estructura de un programa en Titan

Un ejemplo de programa en nuestro lenguaje Titan podría ser:

//Declaración de variables
var cad: string;

//Declaración de procedimientos
procedure hola();
  cad = "hola";
  print cad;
end;

//Programa principal
hola();

Notar el punto y coma, al final de cada instrucción.

Aunque hay similitud con el lenguaje Pascal (lo cual es premeditado), notar que no es necesario crear bloques BEGIN … END para los bloques de código.

El programa «Hola mundo», será en nuestro caso.

print "Hola mundo";

Palabras Reservadas

Se definen aquí las palabras que no pueden usarse como identificadores  o algún otro elemento del lenguaje.

Solo manejaremos un número reducido de palabras reservadas:

"var"
"integer"
"string"
"if"
"then"
"end"
"while"
"do"
"procedure"
"func"
"break"
"exit"

Como se puede deducir, se tratará de mantener esta lista lo más pequeña posible (por simplicidad del compilador), pero es posible que vayamos ampliando esta lista conforme vayamos desarrollando el lenguaje, sin embargo, este es un buen punto de partida.

Un detalle adicional que hay que considerar es que, como nuestro compilador generará código ensamblador directamente de nuestro lenguaje, las palabras reservadas del ensamblador MASM también serán palabras reservadas de nuestro lenguaje. Entre estas palabras están:

  • Instrucciones o nemónicos: AAA, AAD, AAM, AAS, ADC, ADD, AND, CALL, CBW, CLC, CLD, CLI, CMC, CMP, CMPSB, CMPSW, CWD, DAA, DAS, DEC, DIV, …
  • Directivas: IF, ELSEIF, ELSE, ENDIF, IF1, IF2, IFE, IFDEF, IFNDEF, IFB, IFNB, PROC, INVOKE, PUBLIC, EXTERN, OPTION, PROTO, …
  • Operadores: LENGTH, SIZE, WIDTH, MASK, LENGTHOF, SIZEOF, LROFFSET, OFFSET, SEG, THIS, TYPE, HIGH, HIGHWORD, LOW, LOWWORD, …

Una lista detallada de todas las palabras reservadas del ensamblador sería extensa (Se puede encontrar en las guías de programador del MASM). Es por eso que solo se listan algunas, más que nada, para tener una idea de algunas de los identificadores (que no son pocos) que no podremos usar en nuestro lenguaje.

Es totalmente posible, hacer que el compilador haga una especie de traducción a sus identificadores para evitar conflictos con las palabras reservadas del ensamblador, pero dicha tarea agregaría un nivel más de complejidad al compilador, que no incluiremos, en este proyecto.

Comentarios

Los comentarios se definirán con los caracteres «//» de la misma forma a como se hace en el lenguaje C.

Los comentarios serán de una sola línea. Por ahora no implementaremos comentarios de varias líneas.

Los comentarios pueden ir al inicio de una línea o al lado de una instrucción.

//Este es un comentario.
print "Hola mundo";  //Este también es un comentario

Literales numéricos

Solo se reconocerán números enteros de hasta 32 bits, como:

123, -10000, o 001.

Todos los literales numéricos deben escribirse en base decimal. No se implementarán formatos en otras bases.

No habrá soporte para números en coma flotante.

Identificadores

Los identificadores son los nombres que se usarán para las variables. Para nuestro caso, se usarán las siguientes reglas:

  • El primer carácter, debe ser siempre una letra, sea mayúscula o minúscula o el carácter guion bajo “_”.
  • Los caracteres siguientes, si es que los hay, pueden ser cualquier letra, número o el carácter guion bajo “_”.

Para las letras solo se reconocerán las letras del alfabeto inglés.

Considerar que los identificadores diferencian mayúsculas de minúsculas y que no se pueden usar identificadores iguales a las palabras reservadas.

Otro detalle a tener en cuenta es que la longitud de los identificadores no puede ser mayor a 255 caracteres, ni contener caracteres fuera del alfabeto ASCII.

Operadores

Nuestro lenguaje tendrá un número reducido de operadores:

  • «=» : Operador de asignación de variables y de comparación de números.
  • «<>»: Operador de comparación de números.
  • «>», «>=»: Operadores de comparación de números.
  • «<«, «<=»: Operadores de comparación de números.
  • «+»: Operador para suma de números o concatenación de cadenas.
  • «-«: Operador para resta de números.
  • «|» Operador OR lógico de dos números.

La concatenación de cadenas se hará con el mismo operador «+» que se usa para la suma aritmética. La concatenación es importante para poder realizar la manipulación de cadenas.

Expresiones

Las expresiones serán simples. De dos operandos como máximo, aparte de la asignación, si es que existe.

Así, las siguientes expresiones serán válidas:

x;    //Válido en el lado derecho de las asignaciones.
x+1;  //Válido en el lado derecho de las asignaciones.
x>0;  //Válido solo dentro de condicionales,

Pero las siguientes expresiones, son inválidas:

x = x + y + 1;  //Más de 2 operandos después de la asignación
x>y+1;          //Más de 2 operandos (dentro de condicionales)

Como las expresiones son simples, no hay problemas en definir la precedencia de operadores y solo asumiremos que la asignación tiene la mayor precedencia.

Tipos de datos

Solo manejaremos dos tipos de datos.

  • Tipo numérico (integer) -> Números con signo, de hasta 32 bits de longitud. Ejemplos: 1000, -50 Solo se permiten valores enteros.
  • Tipo cadena (string) -> Cadenas de cualquier longitud, terminadas en caracter NULL. Ejemplo: «Hola». Las cadenas tendrán una longitud máxima de 255 caracteres.

Dentro del código, las cadenas solo pueden ocupar una línea.

Los tipos numéricos se usarán también como valores booleanos haciendo la comparación para ver si son diferente de cero, en cuyo caso, se asumirá como el valor TRUE.

Variables

Las variables se declaran con la palabra reservada «var»:

var x: number;
var cad: string;

Solo se permite una declaración por cada palabra reservada «var».

Las declaraciones de variables deben hacerse antes del código o instrucciones.

No se manejará constantes, por el momento.

Arreglos

Se pueden crear arreglos de datos de los tipos número y cadena:

var x[10]: integer;
var cad[5]: string;

Esta definición indica que se está creando un arreglo, de 10 elementos: Desde x[0] hasta x[9].

Las cadenas, se podrán tratar también como arreglos:

var cad: string;
var x: integer;
cad = "ABC";
x = cad[0];    //Lee primer carácter como número: 65.

Estructuras

Solo se reconocerá una sentencia condicional y un bucle.

La sentencia condicional tendrá la forma:

if <expresion> then 
  <cuerpo> 
end;

Opcionalmente, se puede incluir la opción «ELSE»:

if <expresion> then 
  <cuerpo> 
else 
  <cuerpo> 
end;

El bucle a implementar será el «while», y tendrá la forma:

while <expresión> do
  <cuerpo> 
end;

Las expresiones a usar, tanto para la condicional IF como para el bucle WHILE, deben tener una estructura fija de dos operandos y un operador de comparación:

a < 0
contador >= 0
cadena = "hola"

Esta restricción simplificará la implementación de las estructuras IF y WHILE en el compilador.

Funciones del sistema

Se implementarán algunas funciones internas, es decir, que no necesitan ser declaradas. Estas son:

print <expresion>

Permite imprimir un valor por consola.

println <expresion>

Permite imprimir un valor por consola, agregando un salto de línea al final.

exit <expresion>

Sale de una función, devolviendo un valor.

length(<expresión>)

Devuelve la longitud de una cadena, como número.

StrToInt(<expresión>)

Devuelve una cadena convertida a número.

IntToStr(<expresión>)

Convierte un número a una cadena.

Procedimientos y Funciones

Adicionalmente a las funciones predefinidas, el lenguaje debe permitir al programador la creación de sus propias funciones y procedimientos:

Por simplicidad las funciones y procedimientos se crearán de la misma forma, usando la palabra reservada «procedure».

La estructura de un procedimiento es:

procedure <nombre>([lista de parámetros]);
  <declaración de variables>
  <cuerpo>
end

Un ejemplo de procedimiento podría ser:

procedure mostrar_mensaje();
  var txt: string;
  txt = "Mensaje";
  print txt; 
end

La única diferencia de un procedimiento con una función, es que las funciones devuelven valores. Las funciones pueden devolver valores usando la instrucción «exit».

procedure doble(x:integer);
  exit x+x;
end

Los procedimientos pueden también usar parámetros o variables locales. Todos los parámetros se pasarán por valor, excepto las cadenas que se pasan por referencia.

La estructura general de un procedimiento es:

Figura 4.4 – Estructura de un procedimiento

La forma de llamar a los procedimientos es simplemente invocando a su nombre:

mostrar_mensaje();

La llamada a los procedimientos debe incluir los paréntesis obligatoriamente, inclusive si el procedimiento no incluye parámetros.

4.4 Conclusiones

Se puede notar que el lenguaje ofrece lo mínimo necesario para cumplir los objetivos propuestos. La razón es lógica: Cualquier característica adicional implicará un trabajo adicional de implementación.

Conviene recordar además, que previendo una fácil migración del código fuente del compilador a este mismo lenguaje minimalista, es que escribiremos nuestro compilador usando Pascal, pero con las mismas limitaciones que tiene el lenguaje que hemos definido. Es decir que, a pesar de que podemos usar características avanzadas del Pascal como conjuntos o Registros (lo que nos simplificaría la implementación), nos abstendremos de usarlas. Tampoco usaremos expresiones complejas o tipos que no sean enteros o cadenas, ni más funciones del sistema que las que estamos definiendo en nuestro lenguaje Titan.

Esta limitación constituirá un desafío adicional, pero resultará también una forma entretenida de codificar algoritmos a la vieja usanza, como retrocediendo a la forma estructurada de programar de los años 80, cuando Turbo Pascal estaba naciendo y el BASIC era el rey.

Y así, finalmente, terminamos de definir un lenguaje. Puede que alguien se pregunte ¿Y cómo hiciste para saber lo que le debes ponerle a tu lenguaje? ¿Cómo sabes qué especificaciones debió tener? La respuesta es: Estudio y mucha práctica. Yo puedo estimar bien qué tan complicado puede resultar implementar una característica nueva en el lenguaje, porque ya alguna vez lo he hecho (o al menos intentado) en los muchos proyectos que he realizado. Aún así, sigo aprendiendo acerca de cómo se hacen los compiladores y sobre las nuevas técnicas y tecnologías que aparecen a diario sobre el tema. Y aunque hoy yo me decidí a escribir y compartir este conocimiento, mañana puede ser usted quien lo haga porque el conocimiento es un bien de toda la humanidad.


Sé el primero en comentar

Dejar una contestacion

Tu dirección de correo electrónico no será publicada.


*