resources:
ch 4.1 - 4.3 lecture notes
01. For this CFG
S -> SS+ | SS* | a
a) give a leftmost derivation and the parse tree on string aa+a*
b) give a rightmost derivation and the parse tree on string aa+a*
c) is the grammar ambiguous? justify your answer.
d) describe the language generated by this grammar
02. Consider the language that is the set of all strings of 0s and 1s such that
every 0 is immediately followed by at least one 1. Is this a context-free
language? If not, explain why.
03. Design a CFG for the set of strings that are palindromes over the alphabet
A = {0,1}. A string s is a palindrome if print(s) is the same forward and
reverse. Think inductively.
04. Consider the grammar below, where '-' is the minus operator.
S -> S - S | a | b
Parse a - b - c. Show the parse tree for a leftmost derivation and
a rightmost derivation to show that the grammar is ambiguous.
a) left factor the grammar to remove ambiguity.
b) does left factoring make the grammar suitable for top-down parsing?
c) apply algorithm 4.19 to eliminate left recursion from the grammar
d) is the resulting grammar now suitable for top-down parsing?
05. The following grammar is proposed to remove the "dangling else ambiguity"
in if-else statements without the use of curly braces. Is it successful?
To answer this question, try to construct 2 different parse trees for this
statement below. This statement includes a dangling else.
if (C1) then if (C2) then S2 else if (C3) then S3 else S4
PROPOSED GRAMMAR.
<if-stmt> : if <cond> then <stmt> | <if-else>
<if-else> : if <cond> then <stmt> else <stmt> | <stmt>
<cond> : (C1 | C2 | C3)
<stmt> : S1 | S2 | S3 | S4 | <if-stmt>