Compiler Construction Fall 2017 Assignment 2: CFG and Parsing

This document provides a comprehensive solution to a compiler construction assignment, focusing on context-free grammars (CFGs) and top-down parsing. The solution begins by describing the languages generated by several given grammars. It then proceeds to grammar construction, providing grammars for specific languages, including those with constraints on the number of 'a's, 'b's, and 'c's, and languages where the sum of exponents is even. The solution continues with left-recursion elimination, computation of First and Follow sets, and LL(1) grammar analysis, including parsing a string with a parse tree. The assignment also includes left factoring and the derivation of an expression using a parse tree. Finally, the solution extends a grammar to incorporate assignment and conditional statements, demonstrating a practical application of CFG concepts. This assignment is a valuable resource for students studying compiler design and programming language theory.

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
(2) S → RbR
R → aRb | bRa | RR | bR | є
(3) S → aSbSaS | aSaSbS | bSaSaS | є
(4) S → a S b | C Set of terminals here is T = {a, b, c}
C → cc C | є
(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)
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}
(2) L = {a2n cm bm | m ≥ 0, n ≥ 0}. T = {a, b, c}.
(3) L = {an bm | n+m is even}. T = {a, b}.
(4) The complement of the language L = {anbn | n ≥ 0}. T = {a, b}. Hint: analyze the language into
multiple languages.
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)