L8: Practica 3 - myTeachingURJC/2019-20-LAB-AO GitHub Wiki
Sesión Laboratorio 8: Práctica 3-2
- Tiempo: 2h
- Objetivos de la sesión:
- Instrucción de multiplicación: mul
- Practicar con la manipulación de cadenas
- Aplicar todos los conceptos aprendidos hasta el momento
Vídeos
- Fecha: 2019/Nov/26
Vídeo 1/4: Interpretación como caracteres ASCII
Haz click en la imagen para ver el vídeo en Youtube
Vídeo 2/4: Conversión de cadenas a números
Haz click en la imagen para ver el vídeo en Youtube
Vídeo 3/4: Manipulación de cadenas
Haz click en la imagen para ver el vídeo en Youtube
Vídeo 4/4: Detectando palíndromos
Haz click en la imagen para ver el vídeo en Youtube
Contenido
- Introducción
- Caracteres alfanuméricos: Tabla ASCII
- Conversiones entre cadenas y números
- Operaciones con cadenas
- Actividades NO guiadas
- Autores
- Licencia
- Enlaces
Introducción
Las cadenas de caracteres son muy importantes. Ahora que ya sabemos hacer bucles y tomar decisiones podemos implementar algoritmos sencillos para manipular cadenas. Haremos un repaso de los conceptos implicados, muchos de los cuales ya se han expuesto antes y se conocen, pero se incluyen aquí como referencia
Lo más importante es analizar los ejemplos y practicar intentando resolver los ejercicios
Caracteres alfanuméricos: Tabla ASCII
Los procesadores son sistemas digitales. Esto significa que funcionan con números. Son capaces de almacenar, transportar y transformar números. Estos números representan instrucciones o datos. Los números usados como datos pueden a su vez representar una imagen, un vídeo, un sonido, un carácter...
Los caracteres son letras (a,b,c...), dígitos (0,1,2...) o signos de puntuación (espacios, comas, paréntesis...). Para representar caracteres se usa una codificación: se asignan números para representar cada caracter. Una codificación muy extendida es el Código ASCII. Es el que usaremos
Así, por ejemplo, el código ASCII correspondiente a la letra 'G' es el 71 (0x47), y para la letra 'g' el 103 (0x67)
Cuando escribimos un caracter con sus comillas: 'g', en realidad nos estamos refiriendo a su código ASCII. En este caso sería el número 71
Ejemplo: Codificación en ASCII
Desde nuestros programas en ensamblador podemos referirnos al código ASCII de cualquier carácter colocando las comillas simples. Así por ejemplo, si cargamos en el registro t0 el valor 'g', el ensamblador sustituye 'g' por su valor ASCII (103 en decimal, 0x67 en hexa)
En este ejemplo lo comprobamos. Cargamos en el registro t0 el carácter 'g' y luego llamamos al servicio PRINT_CHAR para imprimir el carácter y a PRINT_INT para imprimir su código ASCII
##-- Imprimir el código ASCII de un carácter
##-- Cargamos en un registro un carácter constante
##-- Lo imprimimos en la consola interpretándolo de dos formas:
##-- * Si llamamos al servicio PRINT_CHAR: Lo interpretamos con un carácter
##-- * Si llamamos al servicio PRINT_INT: lo interpretamos como número entero
.include "servicios.asm"
.data
msg1: .string "Caracter: "
msg2: .string "\nCódigo ASCII: "
.text
#--- Cargamos en t0 el código ASCII de un carácter
li t0, 'g'
#-- En el registro t0 veremos su código ASCII (el ensamblador lo convierte)
#-- Llamamos al servicio PRINT_CHAR para imprimir el caracter
#-- Imprimir mensaje 1
la a0, msg1
li a7, PRINT_STRING
ecall
#--- Llamamos al servicio PRINT_CHAR para imprimir el caracter
mv a0, t0
li a7, PRINT_CHAR
ecall
#-- Imprimir mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
#-- Llamamos al servicio PRINT_INT para imprimir su código ASCII
mv a0, t0
li a7, PRINT_INT
ecall
#--- Terminar
li a7, EXIT
ecall
Ensamblamos y ejecutamos el programa:
En el programa fuente indicamos que queremos cargar en el registro t0 el carácter 'g'. El ensamblador lo convierte a ASCII, y lo que se almacena en t0 es 103. Según al servicio que se llame, este número se interpreta de una forma u otra. El servicio PRINT_CHAR lo interpreta como ASCII, e imprime su carácter equivalente: 'g'. El servicio PRINT_INT lo interpreta como un número entero, imprimiendo en la consola 103. Pero en todo momento, lo que está almacenado en t0 es el numero 103 en binario 01100111 (0x67)
Conversión carácter - código ASCII en python
El intérprete de python se pueden usar para obtener los códigos ASCII de un carácter, o lo contrario: el carácter que se corresponde con un código ASCII. Simplemente abrimos el intérprete de python desde un terminal y ejecutamos las siguientes órdenes:
- ord('g') : Obtener el código ASCII del carácter g
- chr(103) : Obtener el carácter cuyo código ASCII es 103
$ python3
Python 3.6.8 (default, Oct 7 2019, 12:59:55)
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> ord('g')
103
>>> chr(103)
'g'
>>>
En esta animación se muestra en funcionamiento, usando ipython3:
Códigos ASCII de los dígitos decimales
Los dígitos decimales 0, 1, 2 ... 9 también son caracteres. Y por tanto tienen un código ASCII asociado. Así, el número 2, es diferente del carácter '2'. El primero es un número (0x02) y el segundo es el código ASCII asociado al carácter 2: 0x32
Los códigos ASCII asociados los caracteres '0' al '9' se muestran en esta tabla:
| Carácter | Código ASCII | Código ASCII (hex) |
|---|---|---|
| '0' | 48 | 0x30 |
| '1' | 49 | 0x31 |
| '2' | 50 | 0x32 |
| '3' | 51 | 0x33 |
| '4' | 52 | 0x34 |
| '5' | 53 | 0x35 |
| '6' | 54 | 0x36 |
| '7' | 55 | 0x37 |
| '8' | 56 | 0x38 |
| '9' | 57 | 0x39 |
En este ejemplo cargamos en el registro t0 el carácter '2' y en el registro t1 el número 2, y luego llamamos al servicio PRINT_INT para sacar por consola sus valores, y comprobar que efectivamente '2' y 2 SON DIFERENTES
##-- Diferencia entre el número 2 y el carácter '2'
.include "servicios.asm"
.data
msg1: .string "Caracter '2': "
msg2: .string "\nNumero 2: "
.text
#--- Cargamos en t0 el código ASCII de un carácter
li t0, '2'
li t1, 2
#-- Imprimir mensaje 1
la a0, msg1
li a7, PRINT_STRING
ecall
#-- Imprimir t0 como numero, usando PRINT_INT
mv a0, t0
li a7, PRINT_INT
ecall
#-- Imprimir mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
#-- Imprimir t1 como número, usando PRINT_INT
mv a0, t1
li a7, PRINT_INT
ecall
#--- Terminar
li a7, EXIT
ecall
Lo ensamblamos y lo probamos:
Al imprimir '2' como número, obtenemos su código ASCII, que es 50 en decimal. Al imprimir el número 2, obtenemos el dígito 2, como era de esperar
Conversiones entre cadenas y números
Las cadenas pueden contener cualquier carácter. En muchas ocasiones contienen dígitos decimales. Así, por ejemplo, la cadena "255" está formada por 3 caracteres más el '\0' final. NO ES UN NÚMERO. En memoria está almacenada de esta forma:
En ese dibujo se han representado los caracteres entrecomillados, pero en realidad lo que está almacenado es su código ASCII:
En este programa de ejemplo vemos la diferencia. En el segmento de datos almacenamos la cadena "255" y a continuación el número 255, que ocupa un byte
#-- Ejemplo de almacenamiento en memoria
#-- de la cadena "255" y del número 255
.include "servicios.asm"
.data
cad: .string "255"
num: .byte 255
Ensamblamos el programa y miramos lo que hay en el segmento de datos:
Si lo miramos en ASCII, veremos los dígitos '2', '5' y '5'
Para practicar la programación del RISC-V, veremos cómo hacer conversiones entre cadenas con dígitos numéricos y su número correspondiente. ¿Cómo transformar la cadena "255" en el número 255?
Números de un dígito
Empezaremos primero con la conversión de dígitos aislados en sus números correspondientes
Para convertir un carácter ASCII numérico en el número que representa sólo hay que restar el valor 0x30, que se corresponde con el carácter ASCII '0'. Así, si queremos convertir el carácter '1' en el número 1, hay que hacer esta operación: '1' - '0', que representa la resta de sus códigos ascii: 49 - 48 = 1
En este programa en ensamblador se muestra un ejemplo de conversión del carácter '2' al número 2. El carácter '2' se introduce en el registro t1 y en el regitro t2 se deja el resultado de la conversión:
#-- Ejemplo de conversión de un digito decimal ASCII
#-- a su número
.include "servicios.asm"
.text
#-- En t1 ponemos el carácter '2'
#-- Es el que queremos convertir a numero
li t1, '2'
#-- En t0 metemos el caracter '0' que usaremos
#-- para hacer la conversion
li t0, '0'
#-- Realizar la conversion
#-- t2 = t1 - t0 ('2' - '0')
sub t2, t1, t0
#-- Terminar
li a7, EXIT
ecall
Lo ensamblamos y lo probamos. Nos fijamos en los registros: t1 contiene 0x32 (el ASCII del dígito 2), mientras que t2 contiene 0x02: que es el número 2. Hemos convertido el carácter '2' en su número correspondiente 2
Números de 2 dígitos
Para convertir a número una cadena con dos dígitos hay que multiplicar el dígito de mayor peso por 10 (decenas) y sumar el de menor peso (unidades)
Por ejemplo, si tenemos la cadena "23", en memoria se representaría así:
Como sabemos que tiene 2 dígitos, directamente podemos calcular la fórmula:
num = 10 * n1 + n0
Donde n1 es el dígito de las decenas convertido a número y n0 dígito de las unidades también convertido a número. Por el apartado anterior ya sabemos convertir un dígito a su número
La operación de multiplicación en el RISCV es mul, y tiene la misma sintaxis que la suma add
En este ejemplo se implementa la conversión de la cadena "23" a su número
#-- Conversion de una cadena de 2 dígitos a número
.include "servicios.asm"
.data
msg1: .string "\nCadena: "
msg2: .string "\nNumero: "
#-- Cadena a convertir a numero
cadnum: .string "23"
.text
#-- Imprimir mensaje 1
la a0, msg1
li a7, PRINT_STRING
ecall
#-- Imprimir cadena a convertir
la a0, cadnum
li a7, PRINT_STRING
ecall
#--- Calcular la expresion de conversion
#--- t3 = (d1 -'0') * 10 + (d0 - '0')
##-- Leer digito de mayor peso
##-- t1 = d1
lb t1, 0(a0)
#-- Convertir el dígito ASCII a número
li t6, '0'
sub t1, t1, t6 #-- t1 = t1 - '0'
##-- Leer digito de menor peso
##-- t0 = d0
lb t0, 1(a0)
#-- Covnertirlo a numero
sub t0, t0, t6 #-- t0 = t0 - '0'
#-- Calcular d1 * 10
li t5, 10
mul t2, t1, t5
#-- Calcular t3 = d1 * 10 + d0
add t3, t2, t0
#-- Imprimir mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
#-- Imprimir el numero calculado
mv a0, t3
li a7, PRINT_INT
ecall
fin:
#-- Terminar
li a7, EXIT
ecall
Lo ensamblamos y lo probamos
Conversión de cualquier cadena a número
Para convertir una cadena genérica, de cualquier longitud, a un número tenemos que recorrer la cadena empezando por su primer dígito hasta llegar al final ('\0'). El algoritmo es el siguiente:
- Inicializar el resultado parcial a cero: num = 0
- Repetir las siguientes acciones (bucle)
- Leer el carácter actual de la cadena (car)
- Si car es un salto de línea '\n', entonces hemos terminado. El resultado está en num
- Multiplicar num por 10: num = num * 10
- Convertir el dígito car a su número: n = car - '0'
- Calcular: num = num + n
- Apuntar al siguiente carácter
- Repetir el bucle
La implementación de este algoritmo se deja como ejercicio (Ejercicio 5)
Operaciones con cadenas
Con las cadenas se pueden realizar muchas operaciones como copiarlas de una parte de memoria a otra, realizar conversiones en ellas (paso a mayúsculas, encriptación...), búsquedas, comprobación de si cumplen alguna propiedad (por ejemplo, si son palíndromos), etc.
Para realizarlas se declaran uno o más punteros, que se van incrementando o decrementando para recorrer la cadena (hacia delante o hacia atrás)
Manipulación de caracteres
Los caracteres de una cadena se pueden modificar, para sustituirlos por otros, o encontrar su posición dentro de la cadena. En todos los casos necesitamos un puntero que contenga la dirección del primer carácter. Este puntero se va incrementando para leer los caracteres (bytes) uno a uno y realizar la operación requerida
Así, si estamos usando el registro t0 como puntero, las operaciones que típicamente se realizan son:
- Inicialización: Asignar a t0 la dirección del primer caracter de la cadena
la t0, etiqueta_cadena
- Recorrer la cadena: Para pasar al siguiente carácter hay que incrementar el puntero en 1 byte
addi t0, t0, 1
- Leer carácter: Para leer el carácter usamos load-byte (lb). Una vez leído en un registro, ya podemos tomar decisiones con las instrucciones de salto condicional (beq, bne, bgt...)
lb t1, 0(t0) #-- Leer el caracter en t1
- Modificación del carácter: Para cambiar el carácter actual hay que hacer un store-byte (sb). Si en el registro t1 tenemos el nuevo carácter a escribir, usamos la instrucciónn:
sb t1, 0(t0) #-- Escribir el carácter de t1 en la posición actual de la cadena
- Detección del final: El final de la cadena lo detectamos bien usando el carácter de terminación '\0' o bien el carácter '\n' que se introduce siempre al final de la cadena (antes del '\0') al invocar el servicio READ_STRING. Hay que leer el carácter actual, y si es alguno de esos, hemos terminado de recorrer la cadena
En este ejemplo se recorre una cadena definida en tiempo de compilación y se sustituyen todos los caracteres 'a' por 'i'
En este dibujo se muestra el funcionamiento gráficamente:
Y este es el código:
#-- Recorrer una cadena definida en tiempo de compilacion
#-- sustituyendo el carácter 'a' por 'i'
.include "servicios.asm"
.data
cad: .string "Holaaaa"
.text
#-- Usamos el registro t0 como puntero
#-- t0 apunta al comienzo de la cadena
la t0, cad
#-- Bucle principal para recorrer la cadena
bucle:
#-- Leer el caracter. Se almacena en t1
lb t1, 0(t0)
#-- Evaluar la condicion de terminacion
#-- Si t1 es 0 --> Terminar
beq t1, zero, fin
#-- Comprobar si t1 = 'a'
li t2, 'a'
beq t1,t2,encontrado
#-- El caracter NO es una 'a'
#-- Pasar al siguiente caracter
addi t0, t0, 1
#-- Repetir el bucle
b bucle
encontrado: #-- El caracter actual es una 'a'
#-- Escribir en esa posicion una 'i'
li t2, 'i'
sb t2, 0(t0)
#-- Repetir bucle
b bucle
fin:
#-- Imprimir la cadena modificada
la a0, cad
li a7, PRINT_STRING
ecall
#-- Terminar
li a7, EXIT
ecall
La cadena original es "Holaaaa". Tras su modificación se imprime en la consola y se obtiene "Holiiii"
En esta animación se muestra en acción. Inicialmente se ve que en la memoria está "Holaaaa". Tras la ejecución, la cadena se ha modificado en memoria
Copias
La copia o duplicado de cadenas es una operación muy frecuente. Para realizarla necesitamos dos punteros: uno para la cadena origen y otro para la cadena destino. Inicialmente apuntan a la posición del primer carácter
El proceso de copia se resume en este dibujo
Es muy importante copiar también el caracter de terminación '\0'
Su implementación se deja como ejercicio (Ejercicio 7)
Palíndromos
Un palíndromo es una palabra que se lee igual al derecho que al revés. Por ejemplo, rotor es un palíndromo
Para practicar los bucles y el manejo de cadenas de caracteres, vamos a hacer un programa que pida al usuario una cadena y que detecte si es un palíndromo o no
Antes de empezar a programar, hay que pensar cómo resolver el problema (el algoritmo) y luego se implementa. El algoritmo que usaremos se explica a continuación
- Una vez que el usuario ha introducido la cadena, quedará almacenada en memoria y tendremos un puntero que apunta al primer carácter
- Utilizaremos dos punteros, uno que apunte al carácter izquierdo y otro al derecho. Para obtener el puntero derecho, copiamos el puntero inicial y lo incrementamos hasta llegar al '\0' (detectar el final de la cadena) y luego retrocedemos 2 caracteres, para apuntar al carácter de la derecha
- Leemos los caracteres apuntados por ambos punteros. Si son diferentes, la palabra NO es un palíndromo, por lo que terminamos. Pero si son iguales, hay que actualizar los punteros para apuntar a los siguientes caracteres. El puntero izquierdo lo incrementamos, y el derecho lo decrementamos
- Repetimos la operación anterior. Cuando llegamos a la situación en la que los punteros "se cruzan" (el derecho es menor o igual que el izquierdo) entonces sabemos que la palabra SÍ es un palíndromo, y terminamos
Este es el código
#-- Ejemplo de manejo de cadenas
#-- Determinar si una cadena es un palindromo o no
#-- El usuario debe introducir la palabra por la consola
#-- Ejemplos de palindromos: rotor
.include "servicios.asm"
.eqv MAX 1024
.data
#-- Almacenamiento de la cadena introducida por el usuario
cadena: .space MAX
#-- Mensajes a imprimir en la consola
msg1: .string "Introduzca cadena: "
pal_si: .string "ES UN PALINDROMO"
pal_no: .string "NO es palindromo"
.text
#-- Imprimir mensaje 1
la a0, msg1
li a7, PRINT_STRING
ecall
#-- Esperar a que el usuario introduzca la cadena
la a0, cadena
li a1, MAX
li a7, READ_STRING
ecall
#-- Inicializar los punteros a la cadena
#-- t0: Puntero izquierdo
#-- t1: Puntero derecho
la t0, cadena
mv t1, t0
#----------- Actualizar t1 para que apunte al final de la cadena
#-- Comprobar si el caracter actual es 0
bucle1:
lb t2, 0(t1)
beq t2, zero, final_cadena
#-- Apuntar al siguiente caracter
addi t1, t1, 1
b bucle1
final_cadena:
#-- t1 apunta al final de la cadena
#-- Hay que retroceder 2 caracteres: uno es el 0, el otro \n
addi t1, t1, -2
#-- Ahora t1 apunta al último carácter ASCII legible
#-- Que comiencen los juegos del palindromo!
bucle:
#-- Condicion de salida: si el puntero derecho (t1)
# es menor o igual que el izquierdo (t0):Terminamos:
# es un palindromo
ble t1, t0, es_palindromo
#-- Leer caracteres izquierdo (t2) y derecho (t3)
lb t2, 0(t0)
lb t3, 0(t1)
#-- Si no son iguales: no es un palindromo
bne t2, t3, no_palindromo
#-- Actualizar los punteros
addi t0, t0, 1 #-- Puntero izquierdo
addi t1, t1, -1 #-- Puntero derecho
#-- repetir
b bucle
#------- La palabra NO es un palindromo
no_palindromo:
#-- Imprimir mensaje
la a0, pal_no
li a7, PRINT_STRING
ecall
b fin
#--------- La palabra SÍ es un palíndromo
es_palindromo:
#-- Imprimir mensaje
la a0, pal_si
li a7, PRINT_STRING
ecall
fin:
# -- Terminar
li a7, EXIT
ecall
En esta animación se muestra en funcionamiento. Al introducir la palabra "hola", nos indica que NO es un palíndromo. Pero si introducimos "rotor" la detecta correctamente
Actividades NO guiadas
Estudia los ejemplos presentados en esta sesión. Compréndelos muy bien. Modifícalos. Aplica lo aprendido a resolver los ejercicios. Algunos son muy sencillos, pero en otros tendrás que pensar más. Y tomar decisiones. Y resolver ambigüedades. Recuerda: hay infinitas soluciones. Los problemas se pueden resolver con programas diferentes
Ejercicio 1
Escribir un programa que pida al usuario un número entero y que imprima por pantalla su carácter ASCII correspondiente. NOTA: Para que sea un caraćter ASCII visible, el entero deberá estar comprendido entre 33 y 126
Su funcionamiento se muestra en esta animación
Ejercicio 2
Escribe un programa que pida al usuario que introduzca un carácter y que imprima su código ASCII. Su funcionamiento se muestra en esta animación
Ejercicio 3
Escribir un programa que pida un carácter al usuario y lo convierta a su número correspondiente. El carácter debe ser un dígito '0'-'9'. Si el usuario introduce un carácter diferente, se imprimirá un mensaje de error y se volverá a pedir otro carácter
Una vez que se ha introducido un carácter correcto, se convierte al número entero que representa y se imprime en la consola
Ejercicio 4
Escribir un programa para realizar la conversión de una cadena de 2 caracteres en un número. Esta cadena se pide al usuario. NO se realizará comprobación de errores. Daremos por supuesto que los caracteres introducidos por el usuario son correctos. El resultado de la conversión se imprime en la consola. Usar la fórmula num = (d1 - 48) * 10 + (d0 - 48), donde d1 es el primer carácter de la cadena y d0 el segundo
Ejercicio 5
Escribir un programa para pedir al usuario una cadena de como máximo 10 caracteres y convertirla a un número entero. NO se realizará una comprobación de errores. Debes implementar el algoritmo descrito en este apartado. En esta animación se muestra su funcionamiento
Ejercicio 6
Modificar el programa del ejercicio anterior para que el usuario pueda introducir también números negativos como cadenas, usando el carácter '-' al comienzo, y que se convierta la cadena correctamente al número positivo o negativo que le corresponda. NO se realizará una comprobación de errores. Se dará por sentado que el número introducido por el usuario es correcto (y que no tiene caracteres extraños)
Ejercicio 7
Escribe un programa que pida una cadena al usuario y que se almacene al comienzo del segmento de datos. Luego el programa la copiará a otra posición de memoria. Finalmente imprimirá la cadena copia en la consola
Ejercicio 8
Escribe un programa que pida una cadena al usuario, la cifre y la imprima. El cifrado consistirá en sumar una constante K a cada uno de los caracteres de la cadena
En esta animación se muestra en funcionamiento, para un cifrado con K=5
Ejercicio 9
Escribe un programa que pida una cadena al usuario y los caracteres que estén en minúsculas los pase a Mayúsculas. Sólo los caracteres 'a' - 'z' se pasan a mayúsculas, el resto se dejan igual
Este es un ejemplo de funcionamiento:
Ejercicio 10
Escribe un programa que pida al usuario una cadena y la modifique para ponerla del revés. Deberá imprimir la cadena invertida
En esta animación se muestra un ejemplo de funcionamiento
Notas para el profesor
- Título informal de la clase: "Programando Algoritmos!"
- Ahora nuestro RISCV tiene la Potencia de ejecutar cualquier algoritmo, gracias a las instrucciones de toma de deciciones (saltos condicionales)
- Vamos a empezar a programar algunos algoritmos para la manipulación de cadenas
Autores
- Katia Leal Algara
- Juan González-Gómez (Obijuan)
Licencia
