- In the this problem, follow the algorithms in the book
literally; don't "optimize" the results - that's more
error-prone (and makes it harder to grade).
- Text, 4.3(a)
- Eliminate left recursion from this grammar using the
method from section 4.3.
- Construct a parse tree for the same sentence as in
4.3(a) for the modified grammar.
- Compute the FIRST and FOLLOW sets (Section
4.4) for this grammar.
- Build the LL(1) parsing table for this grammar
(Algorithm 4.4).
- For the PL/0 original BNF,
- Compute the FIRST set for the right hand side of
each rule. Please list these sets in the same order as
given on the original BNF
page.
- Compute the FOLLOW set for each variable (left
hand side). Again, please list in order.
- Is the grammer LL(1)? Why or why not? If not, outline
one place in the base compiler where it deviates from
strict adherence to the base grammar in order to avoid
non-LL(1)-ness and sketch how it works.
Notes: (i) A rule like A -> B | C has two right hand
sides. (ii) The use of square brackets and curley braces in
rules is not strictly allowed in a context-free grammer, but in
the given PL/0 grammar it generally doesn't effect the
FIRST/FOLLOW sets. One exception is a rule like A
-> { B ; }, where FIRST(A) equals FIRST(B)
plus epsilon, perhaps plus ;, and similarly for
FOLLOW.
- Extend the BNF description of the PL/0 syntactic structure
to include the new language features, and hand in your revised
description (a sheet of paper). (You'll be given a solution set
grammar on the turn-in day, so don't start implementing the most
complex parts of the AST or parsing code until you get it.)
You will need to give some thought to which language features
(e.g., "variables must be declared", or "break may occur only in
a loop", or "every for loop must have an end token") are best
enforced by the grammar and which are best enforced during
semantic analysis (or later). Write a few sentences to document
these major design decisions, i.e., explain what you decided to
do and sketch why. Turn this in with your revised BNF.
In summary, the new language features are:
- if/then/else
- for loops
- break statements
- boolean types
- and/or operators
- constant expressions
- arrays & array indexing
- call by reference
- functions & function calls with results.
See the project description for
full details.
|
