# Compiler Construction Assignment

2 Pages750 Words282 Views
|
|
|
Compiler ConstructionFall 2017Second AssignmentContext-Free Grammars and Top-Down ParsingDue 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 → ABB → BaAC | cA → 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 allproductions. If the grammar is not LL(1), identify all the problems with it. (5 points)

## End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
|3
|1049
|585

|4
|530
|469

|6
|1081
|79

|15
|1712
|339

### Support

#### +1 306 205-2269

Chat with our experts. we are online and ready to help.