Índice de entradas del conversor
Mejorando el transpilador: IR estructurado y parser avanzado
En el desarrollo de un compilador no solo importa que el código “funcione”, sino que
cada fase esté bien delimitada y tenga responsabilidades claras. En este artículo
repasamos una mejora importante en el proyecto actual del transpilador de ZX BASIC:
una revisión de la arquitectura general, la resolución de algunos retos léxicos
concretos del lenguaje y, sobre todo, un cambio estructural en el parser que impacta
directamente en el análisis semántico y en la generación de código.
Índice
1. Arquitectura del compilador: lexer, parser, semántico y generador
Los compiladores suelen dividirse en cuatro fases clásicas, cada una con un papel bien definido.
Esta separación es fundamental para mantener el código extensible, depurable y preparado
para futuros backends.
Lexer (analizador léxico)
El lexer es la primera fase del proceso. Su tarea es transformar el texto fuente en una
secuencia de tokens: identificadores, números, palabras clave, operadores y signos
de puntuación. En esta fase se ignoran detalles como espacios irrelevantes o comentarios y
se normaliza el formato.
Una decisión clave del diseño es que el lexer produzca tokens semánticamente completos.
Esto evita que el parser tenga que reinterpretar combinaciones de palabras o resolver
ambigüedades que no le corresponden.
El lexer solo conoce los elementos básicos del lenguaje: separadores, delimitadores y
palabras reservadas. Un tema importante que se resuelve aquí es el de los comentarios,
que pueden variar desde el simple REM del BASIC clásico hasta los de estilo C de una línea // o de várias líneas /* */.
Habitualmente los comentarios se eliminan en esta fase, pero en nuestro caso se conservan ya que el objetivo es un transpilador en el que puedan mantenerse o descartarse a elección.
Parser (analizador sintáctico)
El parser recibe la secuencia de tokens y la interpreta según la gramática del lenguaje. El parser trabaja por sentencias completas de una o varias líneas, lo que en nuestro caso se simplifica ya que el BASIC se estructura por líneas, por lo que nuestro parser trabaja línea por línea, detectando sentencias, expresiones y separadores
como : o el fin de línea.
El resultado del parser debería ser un árbol sintáctico, pero he optado por una forma
simplificada: una representación intermedia (IR) estructurada, que conserva la forma
del programa pero es más fácil de analizar y transformar.
Inicialmente el parser emitía sentencias “ajustadas” como texto, lo que obligaba al
semántico y al generador a volver a analizarlas. Esto se ha corregido parcialemnte emitiendo ya
tokens y estructuras explícitas desde el parser.
El parser detecta errores estructurales (por ejemplo, un LET sin un =),
pero no valida aún el significado profundo del programa.
Semántico
El análisis semántico valida el significado del programa: existencia de variables, tipos,
uso correcto de arrays, coherencia de expresiones y saltos válidos. Aquí ya no importa
cómo estaba escrito el código original, sino qué representa.
Esta fase se beneficia enormemente de que el parser proporcione estructuras claras y no
cadenas ambiguas.
Generador de código
Por último, el generador traduce la IR validada a un backend concreto, como SuperBASIC o
ensamblador 68000. Al trabajar sobre estructuras bien definidas, puede centrarse únicamente
en cómo emitir el código.
2. Resolviendo casos especiales: GO TO / GO SUB y variables con espacios
GO TO y GO SUB
El ZX BASIC tiene particularidades históricas heredadas del ZX80/81, máquinas con 1Kb de memoria, por lo que ahorrar espacio era fundamental.
En el Spectrum un tema llamativos es el uso de
sentencias formadas por dos palabras:
GO TO en lugar de GOTOGO SUB en lugar de GOSUB
Esto se produce porque heradado de los ZX80/81, internamente el Spectrum no almacena cadenas de texto para las palabras reservadas, sino
códigos dentro del propio juego de caracteres. Por ejemplo, al ejecutar
PRINT CHR$(236) aparece en pantalla GO TO, lo que hace que internamente sea un solo código, pero se presente en pantalla como 5 caracteres.
Aunque en los listados pueda verse separado, semánticamente siempre es una única
sentencia. Para tratarlo correctamente y aceptar las dos formas de escribir la sentencia, el lexer emite tokens separados para TK_GOTO, TK_GOSUB que ya se tratan sin problemas, y además para TK_GO, TK_TO, TK_SUB, y he optado por resolver este segundo caso en el parser por comodidad:
- Si aparecen
TK_GOTO o TK_GOSUB, se aceptan directamente - Si aparece
TK_GO, se mira el token siguiente
- Si es
TK_TO, se genera un único token TK_GOTO uniendo ambos tokens.
- Si es
TK_SUB, se genera TK_GOSUB uniendo ambos tokens.
- Cualquier otro caso es un error.
Así, el resto del parser y el semántico trabajan siempre con sentencias completas sin ambiguedades, y aunque parezca un poco inconsistente usar el mismo token para dos cosas, de esta manera tampoco hay conflictos con el TO usando en el bucle FOR.
Nombres de variables con espacios
Otra particularidad del ZX Spectrum es que los nombres de las variables pueden contener
espacios, los cuales son ignorados por el intérprete. Así, A B es equivalente a
AB. Este comportamiento proviene del modo en que el analizador de sentencias elimina
los espacios considerados no significativos durante el análisis. No obstante, en mi
opinión esto no responde a una decisión de diseño consciente, sino más bien a un
bug del intérprete que no contempla correctamente este caso.
No he encontrado documentación oficial que lo acredite explícitamente como un bug, aunque
no soy el único que lo interpreta así, como puede verse en este comentario técnico:
los nombres de variables pueden contener
espacios
.
Como curiosidad histórica, en el lenguaje FORTRAN los espacios tampoco son significativos
en ningún punto de la sentencia. Esto daba lugar a ambigüedades bien conocidas, como el
clásico ejemplo:
DO10I=1,10
donde el compilador no puede distinguir, hasta encontrar la coma, si se trata de una
asignación:
DO10I = 1
o de un bucle:
DO 10 I = 1,10
En ZX BASIC este comportamiento permite construcciones como esta que funcionan correctamente y muestran un 4 en pantalla:
LET A B=4 : PRINT AB
Para evitar estas ambigüedades en el transpilador, el lexer separa por espacios y produce varios identificadores en este caso, uno para A y otro para B, luego en el parser se detecta que existen varios identificadores consecutivos y se unen en uno solo, sustituyendo los espacios por un guion
bajo (_) y generando la variable A_B. Como este carácter no pertenece al juego de caracteres del Spectrum, no
puede entrar en conflicto con el código original. De este modo, el parser emite
internamente:
LET A_B=4 : PRINT AB
El semántico considera equivalentes A_B y AB, y finalmente el
generador emite el nombre correcto para el backend, produciendo:
LET AB=4 : PRINT AB
sin ambigüedades y totalmente compatible con SuperBASIC.
3. IR estructurado, PRINT dividido y polaco inverso
No me resultaba satisfactorio que el parser enviara información que luego el semántico
debía volver a analizar. Por ello he cambiado la representación de expresiones y PRINT,
acercándola más a un árbol real, pero usando una forma lineal conocida como montón
(heap), que corresponde al recorrido en postorden del árbol.
División estructurada del PRINT
En versiones anteriores del transpilador, el PRINT se generaba como texto
concatenado, lo que obligaba al semántico y al generador a reinterpretar de nuevo su
contenido. Esto resultaba frágil y poco extensible. Para evitarlo, ahora el parser
divide cada PRINT complejo en una secuencia de elementos estructurados.
Cada elemento del PRINT se representa como una unidad independiente que contiene:
- El tipo del elemento (cadena, variable, AT, TAB, INK, etc.)
- El separador asociado (
;, , o ninguno)
- El valor completo del elemento
Por ejemplo, la siguiente línea en ZX BASIC:
PRINT AT 3,4,"Nombre: ";N$;TAB(20);INK 3;"Edad: ";EDAD
Es descompuesta por el parser en una serie de instrucciones PRINT independientes,
cada una representando un único elemento lógico:
PRINT <AT> <3,4> <,>
PRINT <CADENA> <"Nombre: "> <;>
PRINT <VARIABLE> <N$> <;>
PRINT <TAB> <(20)> <;>
PRINT <INK> <3> <;>
PRINT <CADENA> <"Edad: "> <;>
PRINT <VARIABLE> <EDAD> <none>
Esta representación intermedia permite que cada fase posterior trate los elementos de
forma adecuada, sin necesidad de volver a analizar texto.Durante la generación de código para SuperBASIC, estas instrucciones se traducen en:
AT 3,4
PRINT ,
PRINT N$;
PRINT TO 20;
INK 3
PRINT "Edad: ";
PRINT EDAD
Hay varios cambios en SuperBASIC que obligan a hacerlo de esta manera:
- AT ya no forma parte del PRINT, se debe lanzar por separado
- Los modificadores gráficos (
INK, PAPER, etc.) tampoco se pueden usar ya dentro de un PRINT
- TAB cambia el nombre por TO, y no se deben usar paréntesis en su parámetro (en el Spectrum se puede usar con o sin paréntesis)
- Los separadores se tratan siempre correctamente. La segunda línea generada parece estraña, pero reemplaza a la coma tras el AT en la sentencia original, que ya no forma parte del
PRINT. Pero la coma es necesario incluirla para mantener lo que intenta presentar en pantalla el programa original. Como usar una coma tras un AT o tras un TAB no tiene
sentido, el parser emite un warning de aviso únicamente.
El resultado es un código más limpio, correcto y fácil de
generar, sin alterar para nada el código original, solo adaptado a la forma de trabajar del SuperBASIC.
Expresiones en polaco inverso (RPN), árbol y montón
Hasta ahora, el parser analizaba las expresiones, pero luego las enviaba prácticamente
en bruto al semántico, que debía volver a analizarlas. Esto implicaba repetir trabajo y
hacía el sistema más frágil. Para evitarlo, el parser genera ahora una representación
estructurada de las expresiones basada en el recorrido del árbol sintáctico.
Internamente, toda expresión puede representarse como un árbol, donde los nodos
son operadores y las hojas son operandos (variables, literales, constantes, etc.). Por
ejemplo, la expresión:
A + B * C
se puede representar mediante el siguiente árbol:
+
/ \
A *
/ \
B C
En lugar de almacenar explícitamente el árbol, el parser lo recorre en postorden
(primero los hijos, luego el nodo) y guarda el resultado en una estructura lineal
denominada montón (heap). Esta representación corresponde a lo que se conoce como
notación polaca inversa o RPN (Reverse Polish Notation):
A B C * +
El montón es, por tanto, un árbol almacenado de forma lineal: conserva toda la
información estructural, pero sin necesidad de punteros ni referencias explícitas,
lo que facilita enormemente su almacenamiento y recorrido.
La evaluación de una expresión en RPN se realiza mediante un autómata de pila,
siguiendo una regla muy simple: cuando se lee un operando se apila, y cuando se lee un
operador se desapilan los dos elementos superiores, se aplica la operación y se vuelve
a apilar el resultado.
Siguiendo el ejemplo anterior, la evaluación de A B C * + se realiza así:
Lee A -> se apila A (A)
Lee B -> se apila B (B, A)
Lee C -> se apila C (C, B, A)
Lee * -> C * B, se apila resultado (C*B, A)
Lee + -> (C*B) + A (resultado final)
La gran ventaja de este enfoque es que ya no son necesarios paréntesis ni reglas
implícitas de precedencia durante la evaluación: el orden de las operaciones está
completamente determinado por la posición de los elementos en el montón. La única
responsabilidad del parser es generar correctamente el árbol y recorrerlo respetando
la prioridad de los operadores.
Gracias a esta representación, el semántico puede validar fácilmente las
expresiones (tipos, operaciones permitidas, número de operandos), y el generador
puede emitir código eficiente sin necesidad de reinterpretar la expresión original.
Impacto en el semántico y el generador
- El semántico trabaja directamente con estructuras, sin reinterpretar texto.
- El generador emite código más limpio y eficiente.
Este enfoque hace que el transpilador sea más robusto, más extensible y más preparado
para múltiples backends.
Este tipo de decisiones estructurales, aunque no siempre visibles desde fuera, son las
que marcan la diferencia entre un traductor funcional y un compilador sólido y
mantenible (y sí, también sirven de consuelo cuando uno se da cuenta de que ha tenido
que volver a rehacer parte del camino por no preveerlo desde el inicio).