CPSC425 Spring 2008 HW 7: Top Down Parsing

1. In class we started a top-down parse of the string A+B*C using the grammar below. Here I have writting it with each production numbered, and just one production per line (except for the 26 that are combined in production 7). Recall that $ signifies end of input and λ signifies the empty string.

   1) <exp> := <term> <exptail> $
   2) <exptail> := λ
   3) <exptail> := + <exp>
   4) <term> := <factor>  <termtail>
   5) <termtail> := λ
   6) <termtail> := * <term>
   7) <factor> := A|B|C...|Z
   8) <factor> := (<exp>)
   

   1. Use the definitions on the handouts from class to compute each of the following sets for this grammar:
      1. First(α) for each right hand side α. Thus you will compute First(<term><exptail>$), First λ, First (+ <exptail>), etc. -- a total of 8 First sets.
      2. Follow(X) for each nonterminal X. Thus you will compute Follow(<exp>), Follow(<exptail>), etc. -- a total of 5 Follow sets.
      3. Use the First and Follow sets to compute Predict(P) for each production P above. It is convenient to use the production numbers here, that is, Predict(1) instead of Predice(<exp> := <term> <exptail> $). You will compute 8 Predict sets.

   2. Now use your Predict sets to complete the parse that we started in class. Start from the beginning, including the part we did in class. Note that your parse should take the form of a leftmost derivation that starts with <exp> and ends with A+B*C.

2. Draw a parse tree for your derivation above. Does it do the right thing with precedence of + and *?

3. Now use this grammar to parse A+B+C. Show the derivation and then draw the parse tree. What do you notice that is different from how expressions are usually handled, e.g. in C and Java?