ZB2SB. Conversor de Basic de los ZX al Super Basic del QL (II): Analizadór léxico primera parte, lectura de líneas

Índice de entradas del conversor

---

Comenzamos con el analizador léxico, esta lo divido en dos partes para simplificar, por un lado la lectura de líneas y por otro su descomposición en Tokens.

Partimos de que el programa de origen será un fichero de texto guardado en el Microdriver (o equivalentes como las unidades con una SD, un disquete, un disco duro, o desde un emulador un directorio en el equipo). El resultado serán líneas completas que pasaremos a la rutina que la descompone en Tokens. En esta entrada presentaré las rutinas de lectura del fichero fuente y las de escritura del fichero de destino, que son bastante sencillas realmente.

Para las pruebas el programa simplemente copiar la línea leída en el fichero de origen y la guardará tal cual en el fichero de destino. En otras entradas iré desarrollando esta parte.

En esta primera versión del programa incluyo la base del sistema, compuesta de una serie de procedimientos y funciones que iré llamando, usando este procedimiento:

1170 DEFine PROCedure Main
1180   Init        : REMark Inicializar variables globales
1190   Pantalla    : REMark Pantalla de petición de datos
1200   :
1210   REMark Preparar una ventana para ver los resultados
1220   :
1230   OPEN#cCon,con
1240   WINDOW #cCon,400,140,50,70 : BORDER #cCon; 2,2
1250   :
1260   Proceso     : REMark procesar el fichero de entrada
1270   :
1280   INK #cCon;6 : PRINT #cCon;LF$;"Finalizado"
1290   CLOSE #cCon
1300 END DEFine 

• Init: Este procedimiento inicializa las variables globales que usaremos. Al no existir contantes en SuperBASIC, usaremos variables para simularlas, por haber programado en C tengo la costumbre de que las contantes se escriban con nombres en Mayúsculas siempre.
  
• Pantalla: Este procedimiento presenta la pantalla inicial, y solicita los nombres de los ficheros de origen y destino.
• El OPEN y WINDOW crea una ventana para ir presentando las líneas leidas y las generadas
• Proceso: Este es el procedimeinto que realizará todo el proceso de conversión, en este momento lo único que hace es copìar la entrada sobre la salida para las pruebas de lectura y escritura de ficheros.
• Luego se presenta el mensaje de fin.

Veamos los procesos principales, comenzando por el denominado Proceso que es el que hace todo el trabajo de dirección:

1850 DEFine PROCedure Proceso
1860   LOCal fin,salida$
1870   :
1880   OPEN_IN  #cIn, fIn$
1890   OPEN_NEW #cOut, fOut$
1900   CLS #0 : REMark Por si hay un mensaje de sobreescribir
1910   :
1920   REMark --- Lectura del fichero de entrada
1930   :
1940   REPeat BucleLectura
1950     :
1960     fin = LeerFichero
1970     linea$=Trim$(linea$)
1980     IF (linea$ <> "") THEN
1990       nrl = nrl + 1
2000       Mostrar_Entrada linea$
2010       salida$=Montar$(linea$)
2020       Mostrar_Salida salida$
2030       Guardar(salida$)
2040     END IF
2050     IF fin THEN EXIT BucleLectura
2060     :
2070   END REPeat BucleLectura
2080   :
2090   REMark Finalizar el proceso
2100   :
2110   CLOSE #cIn
2120   CLOSE #cOut
2130 END DEFine Proceso

Este proceso comienza abriendo los canales para lectura y escritura asociandolos a los ficheros que usaremos, al llegar a la línea 1890, si el sistema encuentra que el fichero de salida ya existe nos pregunta si deseamos sobre-escribirlo. si usamos Minerva o algún Toolkit existe la posibilidad de evitar esto indicando que deseamos sobre-escribir siempre, pero yo prefiero usar la ROM estándar únicamente en estas entradas.

Luego llamará al procedimiento que lee el fichero línea a línea, presentando la línea en la pantalla, llama al proceso que Montará la línea de salida (repito en este momento solo copia origen a destino), y nos presenta la línea generada.

Al final cierra los canales de entrada y salida.

2530 DEFine FuNction LeerFichero
2540     LOCal car$
2550     :
2560     linea$=""
2570     REPeat Bucle_Lectura
2580         IF (EOF(#cIn)) THEN RETurn TRUE
2590         :
2600         car$=INKEY$(#cIn)
2610         :
2620         IF (car$ <> CR$) AND (car$ <> LF$) THEN
2630           linea$ = linea$ & car$
2640         ELSE
2650           IF (linea$<>"") THEN
2660             EXIT Bucle_Lectura
2670           END IF
2680         END IF
2690     END REPeat Bucle_Lectura
2700     RETurn FALSE
2710     :
2720 END DEFine LeerFichero

Esta es la función de lectura del fichero de origen, como el final de las líneas puede ser LF, CR+LF o solo CR dependiendo del origen del fichero, no puedo leer por líneas sino que leo carácter a carácter, y si no es un CR o un LF lo incluyo en la línea que estoy leyendo, pero si es uno de estos entiendo que es el fin de línea y retorno lo que he leído hasta el momento. Si el siguiente carácter es CR o LF, es de la línea anterior o es una línea en blanco, lo que no está realmente permitido, y en este caso no retorno nada y sigo leyendo.

Ahora el procedimiento para guardar las línea convertidas en el fichero de salida, como vemos es muy  sencillo ya que guarda la línea completa sin complicaciones, en formato del QL que es el que lo ejecutará:

2760 DEFine PROCedure Guardar(s$)
2770   PRINT #cOut, s$
2780 END DEFine  

Como de momento el proceso solo copia tal cual, si se ejecuta con un fichero de prueba la pantalla que aparece será como esta:

 

Vemos que se solicita los nombres de los ficheros de origen y destino, y el proceso va presentando las líneas, el primer número en color blanco es el contador de líneas leídas. Luego en verde está la línea que ha leído, marcada como "L:", debajo y en color rojo la línea que ha convertido (repito que nuevamente en esta fase solo es copia de la leída) marcada como "C:".

El módulo completo lo podéis descargar desde este enlace

ZB2SB. Conversor de Basic de los ZX al Super Basic del QL (I): Introducción

Índice de entradas del conversor

Cambios en rojo el 23/11/2024

---

Como sabemos, los programas se escriben en un lenguaje de alto nivel, y usando otro programa se convierten en programas escritos en otro lenguaje. Cuando ese lenguaje es directamente código máquina (a veces es ensamblador que se ensambla y linka de forma transparente) tenemos los que habitualmente se llama un COMPILADOR.

Por definición, un COMPILADOR es un programa que convierte un programa escrito en un lenguaje, en un programa escrito en otro lenguaje. Cuando ese otro lenguaje no es código máquina (o ensamblador, que se considera lo mismo en este tema), sino que lo convierten en otro lenguaje diferente, se le denomina TRANSPILADOR.

Los viejos quizá recuerden el compilador Turbo Pascal y luego el compilador Turbo C (posteriormente Borland C), que eran ampliamente usados por generar no solo de forma mas rápida que otros compiladores del momento (recuerdo en un 386 esperar 20 minutos para que terminara de compilar un programa en ABAL), sino porque generaba un código bastante rápido al estar bien optimizado. Luego se pasó al Turbo C++, pero las primeras versiones usaban dos pasos, primero un pre-procesador convertía el código C++ en C estándar, y luego el compilador compilaba el programa en C. Esto hacía que depurar fuera un infierno, depurabas el programa en C que no era el que habías escrito tu en C++, lo que era un desastre. Por fortuna, fueron rápidos en sacar un compilador completo, que generaba ya directamente desde C++ código máquina y podías debugear sin problemas.

Partes de un compilador

Un compilador se divide en varias partes, cada una centrada en un aspecto de la conversión del fuente en el objeto:

• El analizador Léxico toma el programa y lo descompone en sus unidades básicas, sentencias, variables, operadores, separadores, etc. Para hacerlo necesita unas tablas auxiliares con los elementos que debe reconocer, separadores, sentencias, formato de variables, formato de comentarios, formato de cadenas, etc. Cada uno de estos componentes se denomina un TOKEN, y tiene dos atributos, el token y su tipo.
  Por ejemplo si tenemos la instrucción 100 IF a>=b THEN GOTO 500 lo descomponemos en estos tokens: 
• 100, número de línea
• IF, sentencia de comparación
• a, variable
• >=, operador de comparación
• b, variable
• THEN, sentencia de ejecución
• GOTO, sentencia de salto
• 500, operador del salto
• vacío, fin de instrucción (en lenguajes como C sería ";" en lugar de vacío)
  
• El analizador sintáctico toma los Tokens que va recibiendo del léxico y monta lo que se denomina el árbol de sintaxis, que representa la estructura lógica de las sentencias, y unas tablas auxiliares con las variables, funciones, procedimientos y en los lenguajes que los usan los saltos que se han ido encontrando.
• El Analizador semántico es el resultado de validar que el árbol de sintaxis es correcto.
  
• El generador de código crea a partir de lo anterior el código de destino. En general se divide en tres partes, aunque puede usar una, dos o las tres partes dependiendo del lenguaje de destino principalmente si es o no lenguaje máquina, o de la complejidad del lenguaje destino, no es lo mismo un I7 que un pequeño microcontrolador PIC:
  
• El generador de código intermedio crea a partir de la estructura lógica el código en el lenguaje de destino, o a veces en un lenguaje similar simplificado, en general genera lo que se denomina "código de tres direcciones", no mira mas que las sentencias que está recibiendo.
  
• El optimizador mejora el código intermedio generando uno lo más rápido posible, usará las tablas auxiliares y puede tener en cuenta código precedente y posterior para eso.
• El generador final convierte el código intermedio optimizado en el definitivo en lenguaje de destino.

El compilador actúa simultáneamente en las tres fases, no las hace una tras otra (salvo en algunos compiladores antiguos o cuando se desea ver lo que se genera de forma didáctica), en general el Sintáctico es el director, ya pidiendo tokens al léxico y va montando las estructuras, cuando tiene una sentencia completa llama al generador de código.

El diseño de compiladores actual utiliza programas que se han desarrollado, probado y optimizado para ayudarnos a generar el código necesario, estos programas los encontrareis escritos en C y en Java principalmente, como son Flex y JFlex para el léxico y para el sintáctico yacc, GNU bison y javaCC. El generador de código es lo que se programa realmente.

Notación BNF

No quiero ser muy académico (aunque para eso estamos los ingenieros informáticos), prefiero ser lo mas didáctico posible, pero solo por completar la definición, para poder compilar un lenguaje es primero necesario definirlo correctamente, para eso se utiliza la notación BNF.

Para definir el lenguaje a compilar, el señor John Backus, uno de los grandes pioneros, de los que antes de que existieran lenguajes de programación ya trabajaba con ordenadores en código máquina, para desarrollar el FORTRAN ideó una notación para describir la sintaxis del lenguaje, de forma que no hubiera problemas ni existieran ambigüedades. Este sistema fue ampliada por Peter Naur fijando lo que se conoce como Notación BNF. Para poder hacer algo con lenguajes de programación, lo primero que se debe hacer es definir el lenguaje de la forma más precisa y exhaustiva posible, para eso lo mejor es la BNF, o su equivalente en formato gráfico.

Objetivo

Mi idea en esta serie de entradas es intentar desarrollar algo mas sencillo de que un transpilador, ya que los lenguajes de origen y destino son muy similares y bastante compatibles, en su lugar mi idea es desarrollar en Super Basic un conversor que transforme programas escritos en ZX BASIC o Sinclair BASIC (se conoce por ambos nombres), que así se denomina el BASIC que fue inicialmente para el ZX80/ZX81, luego ampliado con nuevas sentencias en el Spectrum (el mismo en todos sus modelos, salvo comandos específicos para el +2 para cambiar el modo 48/ampliado o los de manejo del disco en los +3), en programas en Super Basic del QL. Digo intento porque espero acabarlo, ahora mismo lo tengo iniciado y genera código sin problemas para programas sencillos, pero le faltan todavía algunas cosas para considerarlo operativo.

Del compilador solo voy a usar el analizador léxico, que me retornará las sentencias separadas en Tokens, que convertirá a la sintaxis del SuperBasic.

En esta serie de entradas mi idea es reescribirlo mejorado, siempre que se reescribe un programa no partes de cero, sino de lo aprendido anteriormente, por lo que siempre se genera mejor código, y el que tengo no me convence actualmente, por lo que tengo excusa para empezar esta serie. Pero hay que empezar desde el principio.

Características del Basic de Sinclair

Me basaré es estas características que tienen todos los programas en Sinclair Basic, que en principio son comunes al SuperBasic:

1. El programa lo leeremos desde un fichero de texto.
2. Un programa se compone de líneas individuales, separadas por un terminador de línea ^{* ver nota al final}. Este terminador depende del origen del fichero que las contiene (si el origen es Windows será CR+LF, si el origen es Linux o el propio QL será LF, si estamos en Apple será CR). Por tanto lo primero que haremos es un proceso que lea un fichero de texto con el programa y lo descomponga en líneas, pasando el proceso para cada una de forma independiente.
3. Cada línea del programa se compone de un número de línea, un espacio en blanco, y una o varias sentencias separadas por el carácter ":"
   
4. Cada sentencia comienza por un identificador de sentencia, seguido por un espacio y una serie de modificadores. Por ejemplo la sentencia LET a=r-3 se compone del identificador "LET", seguido por el modificadores"a=r-3". 
5. Existen sentencias simples como REM, LET o GOTO, y sentencias compuestas como pueden ser las decisiones IF/THEN o los bucles FOR/TO.
6. Un comentario se define por el identificador de sentencia REM y su modificador abarca siempre hasta el final de la línea en que se encuentra. No hay comentarios multi-línea y por tanto tampoco anidados.
7. Se aceptan nombres de variables con cualquier longitud.
   

Hay algunas sentencias que no se pueden usar en SuperBasic, por ejemplo PLOT, hay que analizar todas las sentencias y buscar su equivalencia, pero en general las principales diferencias entre ambos BASIC las podemos resumir en:

1. El ZXBasic del Spectrum amplia el de los ZX80/81, por lo que incluye algunos comandos adicionales, como PAPER o INK. Por tanto todo lo aplicable a los programas para el Spectrum se debe poder aplicar a los programas para los ZX80/81.
2. El ZXBasic utiliza variables numéricas sin atributo adicional, o de cadena con el atributo $. Super Basic se comporta igual, pero añade la posibilidad de usar variables enteras con el atributo %
3. ZXBasic utiliza obligatoriamente la sentencia LET en las asignaciones, en SuperBasic es opcional.
   
4. ZXBasic usa NEXT como final del bucle FOR, mientras que SuperBasic utilizar END FOR en su lugar, reservando NEXT dentro del bucle para otro comportamiento.
5. No existe un cierre de los condicionales en el ZXBasic, por tanto estas instrucciones solo ocupan una línea. En este caso la sentencia "IF operador1 THEN sentencias", en la parte de las sentencias puede abarcar varias. Se admite lo mismo en SuperBasic, pero existe un fin de comparación por lo que es posible separar en varias líneas un IF.
6. Las sentencias GO TO y GO SUB se escriben como una o como dos palabras separadas por un espacio, aunque sean una sola sentencia. En ZXBasic irán juntas y también en SuperBasic van en dos palabras separadas. En ZXBasic por un solo espacio, en SuperBASIC pueden usarse uno o varios espacios indiferentemente.
   
7. La sentencia "PRINT expresion" admite varios operadores separados por coma o por punto y coma, algunos operadores NO los admite super Basic. Dentro de una sentencia PRINT la expresión puede ser uno de estos términos (algunos no se pueden usar en ZX80/81):
   
   • Quedar vacío
     
   • Una expresión numérica
   • Una expresión de cadena
   • AT m,n  >> Desplaza el curso a la línea-columnas. Esto no lo admite SuperBasic,
     
   • TAB n >> Desplaza el cursor al tabulador n. No admitido por SuperBasic
     
   • PAPER, INK, FLASH, BRIGHT,  INVERSE, OVER >> Atributos de color, que no admite SuperBasic
     

    
   Por esto, si tenemos por ejemplo:

   PRINT AT 4,12;INK 4;PAPER 5;"Hola ";INK 2;"que tal"
   

   Lo debemos convertir en:

   AT 4,12 : INK 4 : PAPER 5 : PRINT "Hola" : INK 2 : PRINT "que tal"
   
   

Limitaciones

El principal problema proviene de las diferencias entre los sistemas, no por los procesadores que sean diferentes, sino por las características propias de cada máquina, esencialmente en la pantalla y las llamadas a la ROM o a las variables del sistema desde el Basic.

Los ZX usan una pantalla con un tamaño y unos colores, mientras que el QL tiene varias resoluciones con varios modos de color. Aunque no es directo pero esto se puede ajustar creando una ventana en el QL.

Los ZX usan un juego de caracteres de 8x8, mientras que el QL usa varios juegos de resoluciones variables, y los comandos para redefinir el juego de caracteres del Spectrum no funcionan en el QL, que usa otras resoluciones y puede disponer de varios juegos, esto es complejo pero se puede llegar a solucionar.

Casi todos (por no decir todos) los comandos que se refieren al hardware del aparato no se pueden convertir, si en el ZX se hace un POKE para obtener una variable del sistema, lo más seguro es que esa variable no exista en el QL. Hay veces que se llama a una rutina en la ROM para acelerar el programa, esto no es posible replicarlo en el QL (no es el objetivo de estas entradas, pero siempre existe la posibilidad de escribir rutinas en código máquina que hagan algo equivalente), por tanto no se van a convertir comandos dependientes del Hard como PEEK o POKE.

(*) Nota sobre CR y LF. En las máquinas de escribir, el papel se insertaba en un rodillo que estaba ubicado sobre lo que se denominada Carro. Las teclas eran fijas, pero el carro se movía a izquierda o derecha, y el rodillo se movía hacia arriba o hacia abajo, de esta forma al pulsar una tecla esta presionaba una cinta entintada sobre el papel marcando un carácter, y luego movía el carro una posición a la izquierda para escribir el siguiente carácter. Si pulsábamos el espacio el carro se movía una posición a la izquierda sin imprimir nada. Al llegar al final de la hoja, había que hacer dos cosas, mover el carro completamente hacia la derecha y mover el rodillo una línea hacia arriba, esto se hacía con una palanca ubicada a la derecha, al apretarla primero movía el rodillo hacia arriba una línea (esto se podía usar siempre de manera independiente), si seguías apretando soltaba un freno y movías todo el carro hacia la derecha. Cuando se crearon los teletipos, esto se hacía de forma eléctrica, pero necesitaban dos comandos para hacerlo:

• CR: significa Carriage Return (Retorno de carro). Al recibir este comando el sistema movía el carro completamente a la derecha.
• LF: significa Line Feed (Avance de línea). Al recibir este comando el sistema movía el rodillo una línea hacia arriba.

Realmente se solía enviar primero el LF y luego el CR, aunque el orden es indiferente. En los sistemas operativos se adoptó una codificación u otra, según lo decidieron sus creadores, así:

• En Unix (y todos sus derivados como Linux o BSD) se decidió que los ficheros de texto usaran solo LF para marcar el fin de línea. A la hora de imprimir se hacía con un programa que la controlaba y cambiaba en los teletipos LF por CR+LF. 
• En CP/M se decidió usar CR+LF, que es lo que se remitía realmente a los teletipos al usar un controlador de impresión muy básico, del CP/M pasó al MS.DOS (a través del QDOS que era un clon del CP/M), y de este al Windows actual. 
• Apple decidió lo de siempre, llevar la contraria a todos y usar CR únicamente. 
• Los Mainframes de IBM usaban otro carácter diferente, denominado NEL, de NExt Line (línea siguiente). Otros sistemas como VMS no requerían usar fin de línea ya que guardaban los textos como registros.
  

Monto el taller en Retroplay Las Américas

Me vuelto a caer en los viejos vicios, monto el taller en el evento Retroplay, que será el 5 y 6 de octubre de 2024, de 10 a 21 horas, que se realiza en el Centro Comercial "Las Américas" de Torrente.

Solo puedo ir el sábado 5 de Octubre de 2024 de 10 a 21 horas. Si alguno no puede ir el sábado lo puede dejar el domingo en el stand de RetroJapan, que luego pasaré por la tienda a revisarlo.

El que desee traer cosas para Reparar-Ajustar-Revisar-Modificar debe tener en cuenta esto:

• Lo hago por afición, no es un negocio y no hay garantías.
• Solo cosas retro, no me traigas una Wii, XBox 360 o PS3/4 (salvo que quieras hacerme un regalo), para esas cosas hay muchos sitios que las reparan.
• No dispongo en un evento de todo el material necesario, por tanto si puede dime lo que vas a traer y lo que quieres hacerle a este e-mail y voy preparado.
  
• No es sencillo reparar durante el evento, si es una avería al menos intento darte un diagnóstico para que decidas que hacer.
• Si no da tiempo durante el evento y tu quieres, me lo llevaría y te aviso cuando esté, luego lo recoges en la tienda RetroJapan en Paterna o te lo envío a casa, lo que prefieras.
  
• En el evento voy con una tele con cable de antena, herramientas y algún componente, pero no puedo llevar todo lo necesario para cada máquina, por tanto debes traer todo lo necesario para que la pueda poner en marcha, incluyendo:
• La máquina
• Su alimentador (hay muchos tipos de conectores diferentes y no puedo tener de todos)
• Cable de video si es necesario (no el de TV que si llevo uno a los eventos, pero cada máquina usa sus cables de AV o RGB)
• Si es una consola, un juego y un mando (en casa tengo de muchos sistemas, pero en el evento no puedo llevar todo).
• Si es un ordenador no es imprescindible pues se puede probar directamente, pero si quieres algo relacionado con la carga debes traer una cinta, y si es con los mandos uno de los que uses.
• IMPORTANTE: Lo debes traer todo en una caja o una bolsa, en los eventos hay mucha gente, no suele pasar nada, pero así es mas difícil que se pierda algo o que me equivoque de máquina.
• ES FUNDAMENTAL asegurarte de que me has dato un contacto tuyo, mail o teléfono, si no es muy difícil localizarte, en los eventos hay mucho follón, una vez se fueron sin darme el contacto y no regresaron a recoger el material, por tanto no puede devolvérselo.
• Cuando me dejes el material rellenaremos una hoja con tus datos y lo que me dejas, pero si puedes trae una hoja con estos datos y ahorramos tiempo de rellenar:
• Nombre o nik.
• Mail o teléfono
  
• Todo el material que me dejas (por ejemplo Snes, alimentador, mando, juego SuperMario, cable RGB).
• Lo que debo hacer (si es reparar que le pasa, si es revisar algo que es lo que deseas que revise, si es hacer un MOD cual).
• Debes intentar traerlo temprano para que me de tiempo, y pasar antes del cierre para ver el estado, si se ha podido hacer te lo llevas, si no se ha podido decides si me lo llevo para seguir en casa o te lo prefieres llevar.
• Si lo traes el domingo y lo dejas en RetroJapan , acuerdate de que debe ir en una caja o una bolsa, y poner la hoja con tus datos, lo que deseas que haga y el material que dejas.
  

Sobre el coste es difícil darlo sin saber lo que hay que hacer, y depende mucho de los componentes necesarios, pero suele estar entre 10 y 20 euros. Yo no me dedico a esto, es un hobby, no cobro por dar el presupuesto, cuando vea la máquina te digo lo que cuesta y tu decides, si no te gusta el precio te lo llevas y arreglado.

Si lo necesitas, este es el MAIL DE CONTACTO

Programación del Sinclair QL (XXVI): Arboles. Manejo de la memoria y sus pruebas

 

Índice de entradas sobre programación del Sinclair QL

---

El módulo que simula la memoria es reducido, crea unas variables de control, luego una variable de cadena en la que simularé el manejo de la memoria, la inicializa rellenándola con asteriscos, tiene una función para retornar un puntero a un espacio en la "memoria" del tamaño que le pasemos, otra para copiar una cadena a la "memoria" a partir de una posición, y una para presentar la "Memoria" en pantalla.

He rediseñado el sistema ocupando ahora cinco módulos:

• Arbol_Base: Se ocupa de cargar los módulos del programa y presentar un menú de las pruebas. 
• Arbol_Utilidades: Funciones comunes a todos los módulos
• Arbol_Nodos: Funciones de manejo de nodos
• Arbol_Nodos_Test: Para efectuar pruebas del manejo de nodos
• Arbol_Memoria: Funciones de manejo de la memoria
• Arbol_Memoria_Test: Pruebas de manejo de la memoria
  

Veamos las funciones para el manejo de la memoria:

• init_mem: inicializa la memoria con su tamaño mínimo
• init_mem_max(max): inicializa la memoria con un tamaño max, si este es menos del mínimo será el mínimo, definido en 300 bytes. Luego podemos usar las variables globales para ver en minMem el tamaño mínimo, y en maxMem el tamaño definido para la memoria.
• ver_mem: presenta la memoria en pantalla
• MemPos$(i): función auxiliar, la memoria comienza en posición cero, pero las cadenas en la posición 1, lo que hace es retornar el byte en la posición i+1
  
• GetBytes(bytes): Solicita un hueco de bytes tamaño, y retorna el puntero a donde comienza.
• SaveMem(base, ValorCadena$): Guarda una cadena en la memoria, a partir de una posición
• GetMem$(base,lon): Retorna el contenido de la memoria a partir de la posición indicada, en una cadena de longitud indicada.

7000 REMark *************************************************************
7010 REMark * Librería.: Arbol Binario                                  *
7020 REMark * Modulo...: Memoria                                        *
7030 REMark * Contenido: Rutinas de manejo de memoria                   *
7040 REMark * Autor....: javu61, septiembre 2024                        *
7050 REMark *************************************************************
7060 :
7070 REMark --- Inicializa la memoria con su tamaño mínimo por defecto
7080 :
7090 DEFine PROCedure init_mem
7100   init_mem_max(0)
7110 END DEFine
7120 :
7130 REMark --- Inicializa la memoria con el tamaño que le indicamos
7140 :
7150 DEFine PROCedure init_mem_max(max)
7160    LOCal i
7170   :
7180   minMem = 300
7190   maxMem=max
7200   IF (max < minMem) THEN maxMem=minMem
7210   NULL = -1 : REMark Puntero nulo
7220   ptrBase = 0 : REMark Puntero a la base de la memoria
7230   :
7240   REMark --- Crear la memoria e inicializarla
7250   :
7260   DIM Memoria$(maxMem)
7270   PRINT "Inicializando la memoria (";maxMem;" bytes) ";
7280   Memoria$=FILL$("*",maxMem)
7290   :
7300 END DEFine
7310 :
7320 REMark --- Presentar el contenido de la memoria en pantalla
7330 :
7340 DEFine PROCedure ver_mem
7350   LOCal i
7360   :
7370   PRINT " "; : FOR i=0 TO 4 : PRINT i;"/";i+5;" "; : END FOR i
7380   PRINT
7390   PRINT " "; : FOR i=0 TO 4 : PRINT "| "; : END FOR i
7400   PRINT
7410   PRINT " "; : FOR i=0 TO 4 : PRINT "0123456789"; : END FOR i
7420   :
7430   FOR i=0 TO maxMem-1
7440     IF (i=0) OR ((i MOD 50) = 0) THEN
7450       INK 7 : PRINT : PRINT n2c$(i,3);":"; : INK 4
7460     END IF
7470     PRINT MemPos$(i);
7480   END FOR i
7490   INK 7 : PRINT
7500 END DEFine
7510 :
7520 DEFine FuNction MemPos$(i)
7530   RETurn (Memoria$(i+1))
7540 END DEFine
7550 :
7560 REMark --- Solicita un hueco en memoria de x bytes
7570 :
7580 DEFine FuNction GetBytes(bytes)
7590   LOCal base
7600   :
7610   IF (ptrBase + bytes > maxMem) THEN
7620     PRINT "No hay sitio en la memoria"
7630     base = NULL
7640   ELSE
7650     base = ptrBase
7660     ptrBase = ptrBase + bytes
7670   END IF
7680   RETurn base
7690 END DEFine GetBytes
7700 :
7710 REMark --- Guarda una cadena en la memoria
7720 :
7730 DEFine PROCedure Save_Mem(base, ValorCadena$)
7740   LOCal i,p
7750   :
7760   FOR i=1 TO LEN(ValorCadena$)
7770     p=base+i
7780     IF (p < 1) OR (p > maxMem) THEN
7790       PRINT " *** Sobrepasa la memoria "
7800       EXIT i
7810     ELSE
7820       Memoria$(base+i)=ValorCadena$(i)
7830     END IF
7840   END FOR i
7850 END DEFine Save_Mem
7860 :
7870 : REMark --- Recupera una cadena desde la memoria
7880 :
7890 DEFine FuNction GetMem$(base,lon)
7900   LOCal c$,i,p
7910   :
7920   c$=""
7930   FOR i=1 TO lon
7940     p = base + i
7950     IF (p<0 or="" p="">maxMem) THEN
7960       PRINT " +++ Sobrepasa la memoria ";
7970       EXIT i
7980     ELSE
7990       c$=c$ & Memoria$(p)
8000     END IF
8010   END FOR i
8020   RETurn c$
8030 END DEFine GetMem
8040 :

Para ejecutar solo debéis cargar el módulo Arbol_Base y ejecutarlo, se encargará de cargar el resto de módulos y presentar el menú. Los módulos los podéis descargar de este enlace.

En este momento el sistema pasa los test, pero al final del segundo da un error que no tiene nada que ver, y no consigo localizar, a ver si alguno ve donde puede estar el problema.  

Programación del Sinclair QL (XXV): Arboles. Pruebas de los nodos

Índice de entradas sobre programación del Sinclair QL

---

Vamos con el programa para poder probar lo escrito en la entrada anterior. Es muy sencillo, genero en un bucle una cantidad aleatoria de nodos, cada uno con un valor que será una cadena de caracteres aleatorios entre "A" y "Z". Luego pruebo las rutinas de modificar los punteros a los hijos de los nodos, y la de cambiar el contenido del nodo.

Como las rutinas para montar los nodos están en otro fichero, tengo que cargarlo con un MERGE. En las entradas anteriores usaba un módulo base con los MERGE, y si se ejecutaba el módulo más de una vez volvía a ejecutarlos, con la pérdida de tiempo que eso genera.

La solución ha sido añadir un controlador de errores, si detecta que no se ha cargado el módulo hace el MERGE, si ve que se ha cargado no hace nada. De esta forma podemos ejecutarlo varias veces sin pérdidas de tiempo.

• WHEN ERRor: Es la rutina que se encarga de errores, para activarla se mira en la línea 260 el valor de una variable NODOS, si no existe dará un error -17
• Prepara el sistema: Prepara la pantalla y llama a la rutina del módulo de nodos para inicializarlo
• Crea módulos: Crea los nodos con información aleatoria
• Modifica módulo: Modifica un nodo para añadir puntero a los hijos y cambia el contenido.
• RndChr: Retorna un caracter aleatorio entre "A" y "Z"


100 REMark *************************************************************
110 REMark * Pruebas para el Manejo de nodos del arbol binario
120 REMark *************************************************************
130 :
140 REMark --- Control de si se ha incluido o no el módulo de nodos
150 :
160 WHEN ERRor
170   IF ERNUM=-17 THEN
180     PRINT "Cargando rutinas de nodos..."
190     MERGE mdv1_nodos
200     NODOS=1
201     RETRY
210   ELSE
220     PRINT "Se ha producido un error ";ERNUM;" en l“nea ";ERLIN
230     STOP
240   END IF
250 END WHEN
260 IF NODOS=0 THEN REMark --- Si da un error es que no ha cargado ---
270 :
280 REMark --- Preparar el sistema
290 :
300 MODE 0 : PAPER 0 : CLS
310 inicializa
320 :
330 REMark --- Generar nodos aleatorios para probar las rutinas
340 :
350 generar = RND(1 TO 10) : PRINT "Generando "& generar & " nodos"
360 FOR n=1 TO generar
370   c$=""
380   IF RND(1 TO 9) > 2 THEN
390     FOR i=0 TO RND(20)
400       c$ = c$ & RndChr$
410     NEXT i
420   END IF
430   n$ = NuevoNodo$(n,c$)
440   PRINT n$
450 NEXT n
460 :
470 PRINT "Finalizados los ";n;" nodos"
480 PRINT
490 PRINT "Cambiando datos de un nodo"
500 PRINT NuevoHijo$(n$,pIzq,56)
510 PRINT NuevoHijo$(n$,pDer,67)
520 PRINT NuevoValor$(n$,"Pruebas de valores")
530 :
540 REMark --- Retorna un caracter aleatório entre A y Z
550 :
560 DEFine FuNction RndChr$
570   RETurn CHR$(RND(CODE("A") TO CODE("Z")))
580 END DEFine aleatorio
590 :

 

El programa fuente lo podéis bajar de aquí.

En la siguiente entrada se añadirá el módulo memoria, añadiendo y eliminando nodos en la misma, por lo que luego mejoraré este programa para poder hacer pruebas de ambas partes, añadiendo un menú para definir cual se desea probar.

Para completar habría que hacer un proceso para compactar la memoria, pero eso requiere cambiar los punteros de los nodos, para lo que es necesario conocer su estructura interna, cosa que el sistema operativo no puede hacer, es responsabilidad de nuestro programa. En los lenguajes modernos con recolectores de basura, como Java o C# intentan hacer esto, con la ventaja de que no usan punteros a memoria, sino que las referencias son a la tabla de variables, con lo cual al cambiar la tabla ya ha cambiado todos los punteros, lo que es mucho mas sencillo que ir buscando en cada objeto a donde apunta y cambiarlo, pero a cambio usan mas memoria para la tabla de variables.

Programación del Sinclair QL (XXIV): Arboles. Estructura de los nodos en Super Basic

 

Índice de entradas sobre programación del Sinclair QL

---

Hemos visto el tema de las variables y el de los punteros, ahora vamos a hacer algo en Super Basic, pero ya que no es un lenguaje que soporte punteros ni se pueden usar variables compuestas de tipo registro, es un poco más complicado su manejo. Para manejar memoria hay que usar llamadas al Sistema Operativo para reservar memoria y código máquina para manejar los registros y punteros, o en el Toolkit II hay algunas funciones que nos lo facilitan. Como esto se sale de estas entradas que son de programación en SuperBasic, con la idea de que se pueda portar a otros Basic, voy a hacer otra cosas diferente para manejar árboles binarios, aunque no descarto luego hacer algo usando código máquina y llamadas al sistema.

Simularé la memoria usando una cadena de caracteres, usando el hecho de que una cadena tiene n caracteres, y podemos acceder a cualquiera de ellos individualmente, y cada carácter tiene un valor de 8 bits, lo que es muy similar a como se maneja una memoria. Desarrollaré funciones para reservar "memoria" dentro de la cadena, guardar datos en ella, leer cualquier dato usando un puntero a su dirección base, etc.

Nodos

Para crear los nodos del árbol, en entradas anteriores usé varios vectores de enteros, ya que los valores que manejamos lo eran. Ahora usaremos valores de tipo cadena de longitud variable, por lo que ya no nos sirve usar un vector, desperdiciamos demasiada memoria definiendo cadenas de longitud fija que pueden estar casi vacías. En su lugar en C se usaría un registro, que es una variable que se subdivide en varias, comportándose como un todo o como cada variable individual. Veamos como lo definiríamos en C:

struct nombre_registro    //El nombre que deseamos darle
{
     tipodato campo_1;    //Se define como cualquier variable, tipo y nombre
     tipodato campo_2;
     ....
     tipodato campo_N;    //Podemos usar todas las variables necesarias       
};


En el programa usaremos el nombre como el tipo de variable:

nombre_registro Variable_Registro;     //El nombre que deseamos darle a la variable

Y luego llamamos a los valores añadiendo un punto al nombre:

Variable_Registro.campo_n = ....
if (Variable_Registro.campo_n == true) {....


En los árboles binarios, necesitamos estos datos dentro para montar el registro:

• Nodo_Izquierdo: Puntero al sub-nodo izquierdo de este nodo.
• Nodo_Derecho: Puntero al sub-nodo derecho de este nodo.
• Nodo_Padre: Puntero al nodo padre de este nodo.Este dato no es estrictamente necesario, pero simplifica el montaje del árbol.
  
• Contenido del nodo: En nuestro caso es una cadena de caracteres, pero puede ser cualquier tipo, como un entero o un vector, o incluso otra estructura de tipo registro.
• Longitud del contenido: Al ser una cadena de longitud variable, necesitamos sabes su longitud para reservar solo la memoria necesaria.
  

Funciones para montar registros

Para montar un registro usaré una cadena de caracteres dividida en partes, los punteros serán valores numéricos entre 0 y 99, mientras que el contenido lo limitaremos a entre 0 y 99 caracteres. 

Para almacenar los números usaré cadenas de longitud fija, ajustadas a la izquierda con ceros por la derecha, así será sencillo ver su valor, realmente lo que se debe usar son bytes, con 1 byte podemos almacenar un número entero sin signo entre 0 y 255, con 2 bytes alcanzamos entre 0 y 65.535, esto pueden ser fácilmente dos caracteres, pero muchos no sería visibles ni nos informarían de los valores del puntero, por eso prefiero usar números almacenados en la cadena, aunque solo puedo almacenar entre 0 y 99 tengo la ventaja de que los puedo ver de forma sencilla, y este desarrollo intenta ser instructivo más que efectivo.

Nuestro nodos serán una cadena de caracteres con este formato <NN:NN:NN:NN:cadena> en donde:

• Inicio del nodo: Un carácter "<"
  
• Puntero al nodo padre: Dos caracteres numéricos. No es necesario pero simplifica la navegación por el árbol.
• Separador: Un carácter ":"
  
• Puntero al nodo hijo izquierdo: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Puntero al nodo hijo derecho: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Longitud del contenido: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Contenido: Una cadena de entre 0 y 99 caracteres
• Fin del registro: Un carácter ">"

Los caracteres de inicio y fin no son necesarios, así como los separadores tampoco lo son, pero los usaré para poder ver los nodos de manera sencilla, y rellenaré la "memoria" con asteriscos, de forma que se vean los huecos libres, y cuando queramos ver la "memoria" lo podemos hacer simplemente imprimiendo la cadena, y veremos un texto de la forma:

<00:01:23:04:HOLA>******************<19:40:00:05;ADIOS><04:25_09:00:>********....

Así creo que es mas sencillo presentar los valores de forma que se vean correctamente, sin necesidad de grandes procesos.

Empecemos por las funciones que montan los nodos, para lo que defino funciones y procedimientos para manejarlas:

• inicializa: Este procedimiento inicializa las variables que usaremos, en donde:
• mLon: Longitud de las cadenas para guardar los punteros
• mNodos: Máximo número de nodos que manejamos
• nIni, nSep, nFin: inicio, separador y final para montar el nodo
• pPadre, pIzq, pDer, pLon, pVal: Orden de los campos para el nodo
  
• n2c$(n,l): Esta función retorna una cadena cuyo contenido es un valor numérico (n), ajustada a una longitud máxima (l) y rellena con ceros por la izquierda. Si le pasamos por ejemplo (17,3) nos retorna "017"

• MontarNodo$(p,i,d,c$): Función que retorna un nodo montado con los valores para el padre (p), hijo izquierdao (i), hijo derecho (d) y una cadena de caracteres (c$), si le pasamos por ejemplo (2,12,3,"Hola") nos retorna "<02:12:03:04:Hola>"

• NuevoNodo$(p,c$): Función que retorna un nuevo nodo sin hijos, con los valores para el padre (p) y una cadena de caracteres (c$), si le pasamos por ejemplo (2,"Hola") nos retorna "<02:00:00:04:Hola>"
• Posicion(pos): Retorna un número que indica donde comienza en la cadena que representa el nodo uno de los valores del nodo (pos con valores para 0=padre, 1=izquierdo, 2=derecho, 3=longitud del contenido, 4=valor del contenido), si le pasamos por ejemplo (pIzq) nos retorna 5
• NuevoHijo$(nodo$, pos, valor): Retorna una cadena que representa un nodo (nodo$), en la que cambia el puntero para uno de los hijos (pos donde 1=izquierdo o 2=derecho), con su nuevo valor de puntero (valor), si le pasamos por ejemplo ("<02:00:00:04:Hola>", pIzq,2) nos retorna "<02:02:00:04:Hola>"
• NuevoValor$(nodo$, NuevoValor$): Retorna una cadena que representa un nodo (nodo$), en la que cambia el valor del contenido (NuevoValor$), si le pasamos por ejemplo ("<02:02:00:04:Hola>", "Adios") nos retorna "<02:02:00:05:Adios>"

5000 REMark *************************************************************
5010 REMark * Librería.: Arbol Binario                                  *
5020 REMark * Programa.: Nodos                                          *
5030 REMark * Contenido: Rutinas de manejo de los nodos                 *
5040 REMark * Autor....: javu61, octubre 2024                           *
5050 REMark *************************************************************
5060 :
5070 REMark --- Inicializar el sistema
5080 :
5090 DEFine PROCedure inicializa
5100   mLon=2
5110   mNodos = 10^mLon - 1
5120   nIni$="<" : nSep$=":" : nFin$=">"
5130   pPadre=0 : pIzq=1 : pDer = 2 : pLon=3 : pVal=4
5140 END DEFine inicializa
5150 :
5160 REMark --- Numero en cadena ajustado a longitud
5170 :
5180 DEFine FuNction n2c$(n,l)
5190   LOCal c$
5200   c$=n
5210   REPeat bucle_n2c
5220     IF LEN(c$)>=l THEN EXIT bucle_n2c
5230     c$ = "0" & c$
5240   END REPeat bucle_n2c
5250   c$= c$(1 TO l)
5260   RETurn c$
5270 END DEFine n2c$
5280 :
5290 REMark --- Montar un nodo
5300 :
5310 DEFine FuNction MontarNodo$(p,i,d,c$)
5320   LOCal n$
5330   n$ = nIni$
5340   n$ = n$ & n2c$(p,mLon) & nSep$
5350   n$ = n$ & n2c$(i,mLon) & nSep$
5360   n$ = n$ & n2c$(d,mLon) & nSep$
5370   n$ = n$ & n2c$(LEN(c$),mLon) & nSep$ & c$
5380   n$ = n$ & nFin$
5390   RETurn n$
5400 END DEFine MontarNodo
5410 :
5420 REMark --- Montar un nodo nuevo sin hijos
5430 :
5440 DEFine FuNction NuevoNodo$(p,c$)
5450   RETurn MontarNodo$(p, 0, 0, c$)
5460 END DEFine NuevoNodo
5470 :
5480 REMark --- Retorna la posición de un elemento en el nodo
5490 :
5500 DEFine FuNction Posicion(pos)
5510   RETurn LEN(nIni$) + (pos * mLon) + (pos * LEN(nSep$)) + 1
5520 END DEFine Posicion
5530 :
5540 REMark --- Añadir un hijo a un nodo
5550 :
5560 DEFine FuNction NuevoHijo$(nodo$, pos, valor)
5570   LOCal p
5580   p = Posicion(pos)
5590   nodo$(p TO p+mLon-1)= n2c$(valor, mLon)
5600   RETurn nodo$
5610 END DEFine NuevoHijo$
5620 :
5630 REMark --- Cambiar el valor de un nodo
5640 :
5650 DEFine FuNction NuevoValor$(nodo$, NuevoValor$)
5660   LOCal p1,p2
5670   p1 = Posicion(pLon)
5680   p2 = Posicion(pVal)
5690   nodo$ = nodo$(1 TO p1-1)
5700   nodo$ = nodo$& n2c$(LEN(NuevoValor$), mLon) & nSep$
5710   nodo$ = nodo$ & NuevoValor$ & nFin$
5720   RETurn nodo$
5730 END DEFine NuevoValor$

 

En la siguiente entrada añadiré un programa para probar que estas funciones trabajen correctamente, y si queréis descargar este fichero lo tenéis aquí.