Í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
- 2. Casos especiales del ZX BASIC
- 3. IR estructurado, PRINT y polaco inverso
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 TOen lugar deGOTOGO SUBen lugar deGOSUB
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 tokenTK_GOTOuniendo ambos tokens. - Si es
TK_SUB, se generaTK_GOSUBuniendo 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 unPRINT - 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).