PDA

Visualizza la versione completa : [ASM] Parsing di un'espressione aritmetica


Ilmalcom
17-05-2005, 16:10
Al momento per l'Università mi tocca lavorare con l'assembly MIPS :dottò: Ho risolto senza alcun problema le esercitazioni assegnate, trovandole anzi piuttosto facili, ora ho dato un'occhiata ai testi d'esami degli anni precedenti e... :dottò: mi sembrano veramente fuori parametro.

In pratica molto spesso viene chiesto di effettuare il parsing di un'espressione aritmetica in forma di stringa come la seguente: 3*(12*(5*6))*5 ---> 5400

Bisognerebbe quindi:
1. Controllare la validità dell'espressione
2. Valutare partendo dalla parentesi più interna
3. Procedere ricorsivamente

Ecco, già realizzare procedure ricorsive in ASM è una piaga, figurarsi poi l'utilizzo di un albero di parsing, che peraltro non ho ancora incontrato nel mio percorso di studi. Qualcuno ha mai avuto a che fare con problemi analoghi? Apprezzerei molto non dico una soluzione, perchè mi rendo conto che chiederei troppo, ma almeno un po' di link in cui trovare qualcosa di analogo o qualche suggerimento su come procedere, se no è veramente da panico :cry:

Ringrazio in anticipo :fagiano:

floyd
17-05-2005, 16:16
ho fatto una che calcola espressioni tipo
1+2-1
se vuoi te la mando

Ilmalcom
17-05-2005, 16:20
Originariamente inviato da floyd
ho fatto una che calcola espressioni tipo
1+2-1
se vuoi te la mando
Non so quanto complesso sia, ma ti ringrazio e ci darò un'occhiata volentieri, ti scrivo la mia email in pvt

Ilmalcom
17-05-2005, 21:52
Ringrazio floyd per l'aiuto, purtroppo però il sorgente è un po' troppo complicato per quello che abbiamo visto al corso :fagiano: Tuttavia, dopo quasi tre ore di sudore e sangue, sono riuscito ad elaborare questa soluzione, che posto qui visto che può servire a qualcun altro. Se qualcuno avesse voglia di leggerla ed avesse suggerimenti da darmi o trovasse qualche bug... gliene sarò grato :)

Questo programma valuta un'espressione aritmetica contenente solo numeri, parentesi e simboli di moltiplicazione, qualora la stringa sia malformata restituisce come risultato -1. Il codice dovrebbe spiegarsi abbastanza bene grazie ai commenti.



.data
richiesta: .asciiz "Inserisci l'espressione: "
expr: .space 40
output: .asciiz "Risultato: "

.text
main:
addi $v0,$zero,4
la $a0,richiesta
syscall
addi $v0,$zero,8
la $a0,expr
addi $a1,$zero,40
syscall
addi $sp,$sp,-44 # PUSH dei registri
sw $ra,40($sp)
sw $t0,36($sp)
sw $t1,32($sp)
sw $t2,28($sp)
sw $t3,24($sp)
sw $t4,20($sp)
sw $t5,16($sp)
sw $t6,12($sp)
sw $t7,8($sp)
sw $t8,4($sp)
sw $t9,0($sp)
mfhi $t8
mflo $t9 #
jal minicalc
lw $ra,40($sp) # POP dei registri
lw $t0,36($sp)
lw $t1,32($sp)
lw $t2,28($sp)
lw $t3,24($sp)
lw $t4,20($sp)
lw $t5,16($sp)
lw $t6,12($sp)
lw $t7,8($sp)
mthi $t8
mtlo $t9
lw $t8,4($sp)
lw $t9,0($sp)
addi $sp,$sp,44 #
addi $v0,$zero,4
la $a0,output
syscall
addi $v0,$zero,1
add $a0,$a1,$zero
syscall
jr $ra

minicalc:
addi $t0,$zero,40 # Parentesi aperta
addi $t1,$zero,41 # Parentesi chiusa
addi $t2,$zero,42 # Asterisco
addi $t3,$zero,10 # Fine linea, utile anche per costruire i numeri dalle cifre
la $t4,expr # Puntatore
prima: # Carico il primo carattere
lbu $t5,0($t4)
beq $t5,$t3,esci # E' gia' fine linea?
slti $t6,$t5,48
bne $t6,$zero,errore # Semplificazione: se il primo carattere non e' un numero da' errore
addi $t5,$t5,-48 # Trasformo in numero
add $a1,$t5,$zero # Inizio a calcolare il risultato
poi: # Carico il primo numero
addi $t4,$t4,1
lbu $t5,0($t4) # Leggo il secondo carattere
beq $t5,$t3,esci # E' fine linea?
slti $t6,$t5,40
bne $t6,$zero,errore # E' un simbolo strano?
beq $t5,$t0,errore # E' una parentesi aperta dopo il primo numero?
beq $t5,$t1,errore # E' una parentesi chiusa dopo il primo numero?
beq $t5,$t2,aster # E' un asterisco?
slti $t6,$t5,57
beq $t6,$zero,errore # E' un simbolo strano?
mult $a1,$t3
mflo $a1
addi $t5,$t5,-48 # Trasformo in numero
add $a1,$a1,$t5 # In risultato ho il primo numero
j poi
aster:
addi $t4,$t4,1
lbu $t5,0($t4)
beq $t5,$t3,errore # E' fine linea dopo l'asterisco?
slti $t6,$t5,40
bne $t6,$zero,errore # E' un simbolo strano?
beq $t5,$t0,par_ap # E' una parentesi aperta dopo l'asterisco?
beq $t5,$t1,errore # E' una parentesi chiusa dopo l'asterisco?
beq $t5,$t2,errore # E' un altro asterisco?
slti $t6,$t5,57
beq $t6,$zero,errore # E' un simbolo strano?
j number
par_ap:
addi $t4,$t4,1
lbu $t5,0($t4)
beq $t5,$t3,errore # E' fine linea dopo la parentesi aperta?
slti $t6,$t5,40
bne $t6,$zero,errore # E' un simbolo strano?
beq $t5,$t0,par_ap # E' una parentesi aperta dopo la parentesi aperta?
beq $t5,$t1,errore # E' una parentesi chiusa dopo la parentesi aperta?
beq $t5,$t2,errore # E' un asterisco dopo la parentesi aperta?
slti $t6,$t5,57
beq $t6,$zero,errore # E' un simbolo strano?
j number
par_ch:
addi $t4,$t4,1
lbu $t5,0($t4)
beq $t5,$t3,esci # E' fine linea dopo la parentesi chiusa?
slti $t6,$t5,40
bne $t6,$zero,errore # E' un simbolo strano?
beq $t6,$t0,errore # E' una parentesi aperta dopo la parentesi chiusa?
beq $t6,$t1,par_ch # E' una parentesi chiusa dopo la parentesi chiusa?
beq $t6,$t2,aster # E' un asterisco dopo la parentesi chiusa?
j errore # E' un numero o un simbolo strano dopo la parentesi chiusa?
number:
lbu $t5,0($t4)
addi $t5,$t5,-48
next_term: # Continua a formare i numeri dalle cifre se non ha finito
addi $t4,$t4,1
lbu $t7,0($t4) # Se ho letto un numero, leggo il carattere successivo
beq $t7,$t3,completa # Se sono a fine linea, manca solo una mult
slti $t6,$t7,40
bne $t6,$zero,errore # E' un simbolo strano?
beq $t7,$t0,errore # E' una parentesi aperta dopo il numero?
beq $t7,$t1,completa # Se trovo una parentesi chiusa, manca solo una mult
beq $t7,$t2,completa # Se trovo un asterisco, manca solo una mult
addi $t7,$t7,-48
crea_numero:
mult $t5,$t3
mflo $t5
add $t5,$t5,$t7
j next_term
completa: # Completa le moltiplicazioni quando necessario
mult $a1,$t5
mflo $a1
beq $t7,$t3,esci
beq $t7,$t0,errore
beq $t7,$t1,par_ch
beq $t7,$t2,aster
errore:
addi $a1,$zero,-1 # Ritorno -1
jr $ra
esci:
jr $ra

Fabiuz
18-05-2005, 11:51
ciao!

scusa ma dove lo hai trovato sto testo?
è un programmone....non ho mai visto una cosa cosi in un compito di assembly MIPS...di Mr Marchiori...!
di quanti anni fa è?

Ilmalcom
18-05-2005, 13:29
Originariamente inviato da Fabiuz
ciao!

scusa ma dove lo hai trovato sto testo?
è un programmone....non ho mai visto una cosa cosi in un compito di assembly MIPS...di Mr Marchiori...!
di quanti anni fa è?
E` un esame del 2002, in segreteria ci sono solo quelli del 2002 e del 2003 :fagiano: Credo che ora siano diventati piu` semplici, essendo stato ridotto il tempo a disposizione per l`esame :stordita: Spero almeno che sia cosi`!

Fabiuz
18-05-2005, 15:50
speriamo...ma quelli del 2004 non ci sono?

Loading