COMP1521 2022T3 Q8 · MIPS函数/递归

COMP1521 2022T3 Q8 · 10 marks · MIPS
知识点: MIPS函数/递归（MASM-F） · 次: 递归/全局指针/解析 · 难度: 进阶
Topic: MIPS functions & recursion · Source: https://cgi.cse.unsw.edu.au/~cs1521/26T1/resources/practice_exams.html

一句话 / Summary: 布尔表达式求值递归下降

You have been given 22t3final_q8.s ,
a MIPS assembler program that reads a line of input and then prints 'T' on a new line.

Add code to 22t3final_q8.s to make it equivalent to this C program:

// // // // // // // // DO NOT CHANGE THIS FILE! // // // // // // // //
// COMP1521 22T3 ... final exam, question 8
// Modify 22t3final_q8.s so that its behaviour
// matches the following C code.

#include <stdio.h>

char * s ;

int expression ( void );
int term ( void );
int value ( void );

int main ( void ) {
char buffer [ 10000 ];
fgets ( buffer , 10000 , stdin );
s = buffer ;

if ( expression ()) {
printf ( "T \n " );
} else {
printf ( "F \n " );
}

return 0 ;
}

int expression ( void ) {
int lhs = term ();
if ( * s != '|' ) {
return lhs ;
}
s ++ ;
int rhs = expression ();
return lhs || rhs ;
}

int term ( void ) {
int lhs = value ();
if ( * s != '&' ) {
return lhs ;
}
s ++ ;
int rhs = term ();
return lhs && rhs ;
}

int value ( void ) {
int retval = * s == 'T' ;
s ++ ;
return retval ;
}

The above C program reads a line of input
containing a boolean expression, and evaluates it.

The boolean expression only contains the characters 'T', 'F',
representing true and false respectively, and the operators
'&' and '|', representing the logical AND and OR operators.

For example:

1521 mipsy 22t3final_q8.s
T&F
F
1521 mipsy 22t3final_q8.s
T|F
T
1521 mipsy 22t3final_q8.s
F|T&F
F

No error checking is required.

Your program can assume it is given exactly one line of input.

Your program can assume this line contains only these 4 characters: TF&|

You can assume the line contains less than 10,000 characters.

Your program can assume that these characters form a valid boolean expression.

Your solution must be in MIPS assembler only.

🤖 Write MIPS (mipsy). Read one line — a boolean expression over T F & | (&=AND, |=OR; | binds looser; both right-associative, exactly per the exam's recursive-descent C). Print T or F.

Verified on the sandbox AND cross-checked against an independent oracle.