Assignment 4 solutions

From chapter 5

7. Modify the parser from 5.9 to evaluate exprressions using the grammar from 5.8:

   	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;
   	}
   

8. Write a parser for the grammar from 5.11 (and make it evaluate):

   	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 */
   

11. What's on the stack top when the loop in Figure 5.14 terminates, assuming legal input and the reduction rules in Figure 5.12:

    <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).