CPSC 425 Spring 2006
HW 6: Making a Grammar LL(1)

  1. Consider the grammar below (from HW 2, problem 1):
    <exp> -> <exp> + <mulexp> | <exp> - <mulexp> | <mulexp>
    <mulexp> -> <mulexp> * <rootexp> | <mulexp> / <rootexp> | <rootexp>
    <rootexp> -> (<exp>) | a | b | c
    Use the strategies discussed in class and on the handout on top down parsing to make this grammar LL(1). Show your work.

  2. Besides the inclusion of the / operator, how is the language described by the grammar in (1) different from that described by the grammar used by the recursive descent parser handed out in class?

  3. Trace the calls required by the recursive descent parser in parsing the string a+b*(c-d). Show each method call with the remaining input and the value of c at each call.