resources:
chapter 4 lecture notes
**************
* Grammar 1 *
**************
01. Assume you want to devise an LL(1) parser for Grammar G below.
G: S -> 0S1 | 01
L(G): { 01, 0011, 000111, ... }
LL(1) parsing is top-down and predictive. This means the lookahead symbol
must unambiguously decide the flow from LHS (head) to RHS (body) of the
productions. Since Grammar G is ambiguous, the first step is to left factor
G to remove ambiguity. Call your new grammar G'.
02. To confirm that Grammar G' is correct, parse '0011' and '01'. Give a
leftmost derivation and a parse tree for each string.
03. To construct the LL(1) parsing table for Grammar G' you start by defining
the FIRST and FOLLOW sets. FIRST(X) is the set of terminals that begin
strings derived from X. FOLLOW(A), for nonterminal A is the set of terminals
that can appear immediately to the right of A in some sentential form.
Construct those sets now.
04. Lastly, use the FIRST and FOLLOW sets to construct the parse table for
Grammar G'.
05. Using the parse table for Grammar G', perform an LL(1) parse of string:
0011
**************
* Grammar 2 *
**************
06. For the following Grammar G, devise a predictive parser. Provide the parsing
tables. Is this language LL(1)?
S -> +SS | *SS | a // 'a' '+' and '*' are terminals
07. Use your parsing table from #6 to perform an LL(1) parse of this string:
+a*aa
08. Is Grammar G below LL(1)? What is L(G) for this grammar? Can you construct
FIRST and FOLLOW sets?
S -> SSO | a
O -> + | -
01. What is a handle? Give the handles for this grammar.
S -> 0S1 | 01
02. For the grammar below
S -> 0S1 | 01
indicate the handle in each of the these right-sentential forms.
a) 000111 b) 00S11
03. Give the shift-reduce parse of 000111 for this grammar
S -> 0S1 | 01
04. List the possible handles for this Grammar G:
S -> SS+ | SS* | a
Each right-sentential form below has multiple handles for Grammar G.
a) SSS+a*+ b) SS+a*a+ c) aaa*a++
How do you know which handle to pick? Give the handle.
05. For sentential form T*a on input a*a, the handle is 'a' and not T for the
grammar below. Why?
G: E -> E + T | T
T -> T * F | F
F -> a
09. Do a shift-reduce parse of
SSS+a*+
to show that it is a valid sentential form in Grammar G:
S -> SS+ | SS* | a
10. Do a rightmost derivation of aaa*a++ to show that the leftmost handle in
[a]aa*a++
for grammar
S -> SS+ | SS* | a
is the leftmost 'a'. Hint: show that the leftmost handle is the last
terminal to be reduced.
11. For the grammar G from Problem 05,
S -> SS+ | SS* | a
on input
aaa*a++
give a bottom-up parse using the technique of shift-reduce parsing. Show
the stack, input, action and handle at each step.