Compiler Construction Assignment: CFGs and Top-Down Parsing

The assignment is related to compiler construction and parsing techniques, specifically focusing on context-free grammars and top-down parsing. It consists of several questions that test the understanding of these concepts, including describing languages generated by grammars, giving derivations for strings using a grammar, generating grammars for given languages, applying left-recursion elimination and left factoring to grammars, and extending a grammar to express new language constructs.

Compiler Construction
Fall 2017
Second Assignment
Context-Free Grammars and Top-Down Parsing
Due Wednesday Oct 11, 2017 at 9 AM
Question 1 [25 points]
(a) For each of the following grammars, precisely describe the language generated by the grammar. The
set of terminals T is {a, b} unless another set is specified. (16 points)
(1) S → A | B
A → aaaA | є
B → Bbb | b
Ans. S = { є , aaa, aaaaaa, aaaaaaaaa, …. , ,b,bbb,bbbbb, bbbbbbb, …. }
Thus S contains all strings made from a and b such that strings made from a contain a’s in this
order: 3,6,9,… and strings made form b contain b in this order: 1, 3,5,7,9,….
2 S → RbR
R → aRb | bRa | RR | bR | є
Ans. R = { є, b, ab, ba, bb, abb, bba, bab, bbb, abbb, … }
(2) S → aSbSaS | aSaSbS | bSaSaS | є
S = { aba, aab, baa, aababa, aabaab, babaaa, aaabba, aaabab, …. }
S contains all the strings having 2 more a’s than b’s
(4) S → a S b | C Set of terminals here is T = {a, b, c}
C → cc C | є
Ans.
C = {cc, cccc, cccccc, … }
S = { ab, accb, accccb, aaccbb, … }
C contains all the strings having even number of c’s
S contains all strings beginning with a and ending b, in the middle it contains strings of set C or of set S
(b) Using the grammar in Part 2 above, give a derivation for the string abbabb. Give your derivation in
three different forms: a derivation tree, a left-most derivation and a right-most derivation. (9 points)
Ans.
S → RbR → aRbbR → abbR → abbRbR → abbaRbbR → abbabbR → abbabb
Question 2 [20 points]
Give a grammar that generates each of the following languages. The set of terminals T is given for each
grammar.
(1) L = {a3n b2m | m ≥ 0, n ≥ 0}. T = {a, b}
Ans L → aaaL | Lbbb | є
(2) L = {a2n cm bm | m ≥ 0, n ≥ 0}. T = {a, b, c}.
Ans R → cRb | є
L → aa| LR | є

(3) L = {an bm | n+m is even}. T = {a, b}.
Ans.
EvenA → aa EvenA| є
EvenB → bb EvenB| є
OddA → aEvenA| є
OddB → aEvenB| є
L → EvenA | EvenB | EvenAEvenB | OddAOddB
(4) The complement of the language L = {anbn | n ≥ 0}. T = {a, b}. Hint: analyze the language into
multiple languages.
Ans.
EvenA → aa EvenA| є
EvenB → bb EvenB| є
OddA → aEvenA| є
OddB → aEvenB| є
L → EvenA | EvenB | OddAEvenB | EvenAOddB | OddBOddA | EvenBEvenA | EvenBOddA
Question 3 [25 points]
Consider the following grammar:
S → AB
B → BaAC | c
A → Ca | є
C → b | є
(1) Apply left-recursion elimination to this grammar. Then do Parts 2, 3 and 4 below for the grammar
after left-recursion elimination. (5 points)
(2) Compute the First and Follow Sets for all non-terminals in the grammar. (10 points)
(3) Is the grammar LL(1)? Justify your answer by checking the condition given in class for all
productions. If the grammar is not LL(1), identify all the problems with it. (5 points)
(4) Show step by step the LL(1) parsing of the string bac. Show the steps using a parse tree, and if
LL(1) parsing fails, show where it fails and explain why. (5 points)
Question 4 [30 points]
Consider the following variant of the classic expression grammar studied in class:
Expr → Term | Expr + Term | Expr – Term
Term → Factor | Term * Factor | Term / Factor
Factor → (Expr) | num | ident | ident [Expr] | ident (ExprList)
ExprList → Expr | Expr, ExprList
1. Apply left factoring to the above grammar. Only rewrite the changed productions. Don’t worry
about left-recursion elimination in this question. (10 points)
2. Using the transformed grammar that you wrote in Part 1, give, in the form of a parse tree, the
derivation for the following input: x3 * foo(a5, b+6). (10 points)
3. Extend the above grammar to express the following language constructs:
The start variable is Statement. A Statement is either an Assignment or a Conditional.
An Assignment consists of an expression assigned to a variable using the = operator and ends
with a semi-colon.

A Conditional consists of the if keyword followed by a Condition between parentheses
followed by an arbitrary number of Statements between braces.
The Condition consists of exactly two expressions related by one of the operators:
== != > < <= >=
Follow the above description precisely and do not add any language constructs that are not
mentioned above. You may add auxiliary (intermediate) non-terminals if you need. Only write
the new productions that you have added. (10 points)