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>)
- Use the definitions on the handouts from class to compute each of the following sets for this grammar:
- First(α) for each right hand side α. Thus you will
compute First(<term><exptail>$), First λ, First (+ <exptail>), etc. -- a
total of 8 First sets.
- Follow(X) for each nonterminal X. Thus you will compute
Follow(<exp>), Follow(<exptail>), etc. -- a total of 5 Follow sets.
- 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.
- 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.