Grade statistics:
56 students handed in assignment 5.
assignment 5 as a whole: mean 49.2196
stdev 27.4466
w/o late adjustment: mean 51.3929
stdev 27.9334
Excluding all-zero scores:
assignment 5 as a whole: mean 49.2196
stdev 27.4466
w/o late adjustment: mean 51.3929
stdev 27.9334
Per-problem statistics:
Num 1: mean 31.875000
stdev 9.662266
Num 2: mean 3.660714
stdev 2.214214
Num 3: mean 14.107143
stdev 19.344322
Num 4: mean 1.750000
stdev 3.641281
Per-problem statistics, omitting zero grades:
Num 1: mean 31.875000
stdev 9.662266
Num 2: mean 5.000000
stdev 0.000000
Num 3: mean 30.384615
stdev 17.646261
Num 4: mean 8.909091
stdev 1.928473
Due Nov 30.
Download this code and translate to MIPS assembly code following the instructions therein.
#define DEBUG 0
/*
* "compatibility" layer to simulate SPIM syscalls. you can safely ignore
* this code to "Start of assignment code".
*/
#include <stdio.h>
void print_int(int a0)
{
printf("%d",a0);
}
void print_float(float f12)
{
printf("%f",f12);
}
void print_double(double f12)
{
printf("%f",f12);
}
void print_string(char *a0)
{
printf("%s",a0);
}
int read_int(void)
{
int v0;
scanf("%d",&v0);
return v0;
}
float read_float(void)
{
float f0;
scanf("%f",&f0);
return f0;
}
double read_double(void)
{
double f0;
scanf("%lf",&f0);
return f0;
}
void read_string(char *a0,
int a1)
{
fgets(a0,a1,stdin);
}
/* sbrk/exit implemented in libc */
/*
* Start of assignment code
*/
/*
* Assignment 5.
*
* In-fix calculator.
*
* Your job is to hand translate this to MIPS assembly and run this using
* the SPIM simulator. Your code should include the usual comments /
* documentation.
*
* We do operator precedence parsing. The expression grammar is
*
* START -> expr
*
* expr -> expr '+' term | term
*
* term -> term '*' factor | factor
*
* factor -> number | '(' expr ')'
*
* number -> [0-9]+
*
* Your MIPS assembly code should be a direct translation of this
* "2-banger" calculator. The conditional compilation symbol DEBUG
* should have the value 0, so you should not generate any DEBUG code.
* You may, however, wish to include that in a test version to aid you
* in debugging your assembly language translation.
*/
struct expr {
struct expr *a,*b;
int op, val;
};
#define OP_NUM 0 /* only val used */
#define OP_PAREN 1 /* only a used */
#define OP_ADD 2 /* both a and b used */
#define OP_MULT 3 /* both a and b used */
#define LINE_LENGTH 256
#define MAX_ELTS 32
struct expr e_space[MAX_ELTS];
struct expr *e_unused[MAX_ELTS]; int e_ix;
void out_of_memory(void)
{
print_string("Out of memory!\n");
exit(0);
}
void corrupt_data_structure(void)
{
print_string("Internal error: data structure corrupt!\n");
exit(0);
}
void allocator_init(void)
{
int i;
for (i = 0; i < MAX_ELTS; i++) {
e_unused[i] = &e_space[i];
}
e_ix = MAX_ELTS;
}
struct expr *e_alloc(void)
{
if (e_ix == 0) {
out_of_memory();
}
--e_ix;
e_unused[e_ix]->a = 0;
e_unused[e_ix]->b = 0;
return e_unused[e_ix];
}
void e_free(struct expr *ep)
{
e_unused[e_ix++] = ep;
}
void free_expr(struct expr *ep)
{
if (ep) {
free_expr(ep->a);
free_expr(ep->b);
e_free(ep);
}
}
#if DEBUG
void print_expr(struct expr *ep)
{
if (!ep) {
print_string("NULL\n");
} else {
switch (ep->op) {
case OP_NUM:
print_int(ep->val);
break;
case OP_PAREN:
print_string("(");
print_expr(ep->a);
print_string(")");
break;
case OP_MULT:
print_string("(");
print_expr(ep->a);
print_string("*");
print_expr(ep->b);
print_string(")");
break;
case OP_ADD:
print_string("(");
print_expr(ep->a);
print_string("+");
print_expr(ep->b);
print_string(")");
break;
default:
corrupt_data_structure();
}
}
}
#endif
char expr_buf[LINE_LENGTH];
int expr_ix;
struct expr *read_num(void)
{
int val = 0, ch, got_num = 0;
struct expr *exprp = 0;
while ((ch = expr_buf[expr_ix]) && ch != '\n') {
switch (ch) {
case '0': case '1': case '2': case '3':
case '4': case '5': case '6': case '7':
case '8': case '9':
val = 10 * val + ch - '0';
got_num = 1;
expr_ix++; /* consume the digit */
break; /* break from switch; continue while */
default:
goto done;
}
}
done:
if (got_num) {
exprp = e_alloc();
exprp->op = OP_NUM;
exprp->val = val;
}
#if DEBUG
else {
print_string("read_num: no number found\n");
}
#endif
return exprp;
}
struct expr *read_expr(void); /* forward declaration */
struct expr *read_factor(void)
{
int ch;
struct expr *exprp = 0, *paren;
ch = expr_buf[expr_ix];
switch (ch) {
case '0': case '1': case '2': case '3':
case '4': case '5': case '6': case '7':
case '8': case '9':
return read_num();
case '(':
expr_ix++; /* consume open parenthesis */
paren = read_expr();
ch = expr_buf[expr_ix];
if (ch == ')') {
expr_ix++; /* consume close parenthesis */
exprp = e_alloc();
exprp->op = OP_PAREN;
exprp->a = paren;
return exprp;
}
#if DEBUG
print_string("No matching close parenthesis\n");
print_expr(paren);
print_string("\n");
#endif
free_expr(paren);
return 0;
}
return 0;
}
struct expr *read_term(void)
{
struct expr *a, *b, *exprp;
int ch;
exprp = 0;
a = read_factor();
if (!a) return 0;
while (expr_buf[expr_ix] == '*') {
expr_ix++; /* consume the times */
b = read_factor();
if (!b) {
#if DEBUG
print_string("read_term: Times nothing!\n");
print_expr(a);
print_string("\n");
#endif
free_expr(a);
return 0;
}
exprp = e_alloc();
exprp->op = OP_MULT;
exprp->a = a;
exprp->b = b;
a = exprp; exprp = 0;
}
return a;
}
struct expr *read_expr(void)
{
struct expr *a, *b, *exprp;
int ch;
exprp = 0;
a = read_term();
if (!a) return 0;
while (expr_buf[expr_ix] == '+') {
expr_ix++; /* consume the plus */
b = read_term();
if (!b) {
#if DEBUG
print_string("read_expr: Plus nothing!\n");
print_expr(a);
print_string("\n");
#endif
free_expr(a);
return 0;
}
exprp = e_alloc();
exprp->op = OP_ADD;
exprp->a = a;
exprp->b = b;
a = exprp; exprp = 0;
}
return a;
}
struct expr *read_expression(void)
{
int i;
struct expr *exprp;
expr_ix = 0;
read_string(expr_buf,LINE_LENGTH);
exprp = read_expr();
if (expr_buf[expr_ix] != '\n') {
print_string("Warning: excess characters ignored:\n");
print_string(expr_buf);
for (i = 0; i < expr_ix; i++) {
print_string(" ");
}
print_string("^\n");
}
return exprp;
}
int eval_expr(struct expr *e)
{
if (!e) corrupt_data_structure();
switch (e->op) {
case OP_NUM:
return e->val;
case OP_PAREN:
return eval_expr(e->a);
case OP_ADD:
return eval_expr(e->a) + eval_expr(e->b);
case OP_MULT:
return eval_expr(e->a) * eval_expr(e->b);
default:
corrupt_data_structure();
}
}
void main(void)
{
struct expr *e;
int i;
allocator_init();
while ((e = read_expression()) != NULL) {
#if DEBUG
print_string("Entered: "); print_string(expr_buf);
print_string("Parsed: "); print_expr(e);
print_string("\n");
#endif
print_int(eval_expr(e));
print_string("\n");
free_expr(e);
}
print_string("syntax error:\n");
print_string(expr_buf);
for (i = 0; i < expr_ix; i++) {
print_string(" ");
}
print_string("^\n");
}
bsy+cse30.f99@cs.ucsd.edu, last updated
email bsy.