Assignment 4 solutions
Part of
the homework for 22C:50, Spring 2003
|
int expression() /* parse and evaluate expression */ { int acc = 0; /* accumulator for expression value */ int op = '+'; /* most recent operator */ int term; /* new term to accumulate */ for (;;) { if (lex == '(') { lex_scan; term = expression(); if (lex == ')') lex_scan; else error(); } else { term = value(); } switch(op) { case '+'; acc = acc + term; break; case '-'; acc = acc - term; break; case '*'; acc = acc * term; break; case '/'; acc = acc / term; break; } if ((lex != '+') && (lex != '-') && (lex != '*') && (lex != '/')) break; op = lex; lex_scan(); /* advance over operator */ } return acc; }
int expression() /* parse and evaluate expression ::= term { (+|-) term } */ { int acc = 0; /* accumulator for expression value */ acc = term(); while ((lex == '+') !! (lex == '-')) { int op = lex; /* most recent operator */ int val; /* new term to accumulate */ lex_scan(); /* skip operator */ val = term(); switch(op) { case '+'; acc = acc + val; break; case '-'; acc = acc - val; break; } } return acc; } int term() /* parse and evaluate term ::= factor { (+|-) factor } */ { int acc = 0; /* accumulator for expression value */ acc = factor(); while ((lex == '*') !! (lex == '/')) { int op = lex; /* most recent operator */ int val; /* new factor to accumulate */ lex_scan(); /* skip operator */ val = factor(); switch(op) { case '*'; acc = acc * val; break; case '/'; acc = acc / val; break; } } return acc; } int factor() /* parse and evaluate factor ::= value | ( expression ) */ { int acc = 0; /* accumulator for expression value */ if (lex == '(') { lex_scan; /* skip begin paren */ acc = expression(); if (lex == ')') { lex_scan; /* skip end paren */ } else { error( "end paren expected "); } } else { acc = value(); } return acc; } int value() /* this can be the old value parser from the original assembler */
<expression> ends up on the stack because there is no reduction rule that will reduce it to anything else and the parser keeps repeating its inner loop until there is a failure to apply any of the reduction rules.
This is adequately illustrated in Figure 5.15! So, the only thing that makes this a difficult problem is working through to an understanding of the subject matter (most people find shift-reduce parsers difficult on their first encounter).