In-Class Exercise 1
Due: Thursday, 28 February, end of class.
Objectives:
- Understand how to cure left recursion and pairwise disjointness problems.
Reference: Programming Languages, Sebesta, chapter 4. and
class slides, chapter 4, part 2.
Instructions:
- Write solutions to the following problems in a text.
Name the file with the last name of the two members doing the exercise.
Drag the file into
the user/faculty/barrj/CS 321/TurnIn/In-Class-1 folder.
- You may work in pairs. Put the name of both members as the
first line of the file that you turn in.
- This is open book/open notes.
Problems:
- Consider the following grammer. Eliminate left-recursion using the
techniques described in class. Capital letters are nonterminals, lowercase terminals. The only
BNF symbol is the "or" symbol: |
Hint: first eliminate the immediate left
recursion for each nonterminal, then apply the algorithm given in class, if
necessary.
E -> E + T | T
T -> T * F | F
F -> id | E id
- Consider the following grammer. Calculate the FIRST sets for each
nonterminal in the grammar. Ensure that there is no pairwise
disjointness problem by changing the grammar using the technique described in
class. The language described by the grammar will not make sense, but that's ok.
Capital letters are nonterminals, lowercase terminals. The only
BNF symbol is the "or" symbol: |
B -> ! id | BE ; BE
BE -> = id id | > id id | < id id | L
L -> ! BE and BE
