Trusted by 2+ million users,

1000+ happy students everyday

1000+ happy students everyday

Showing pages 1 to 1 of 2 pages

Compiler ConstructionFall 2017Second AssignmentContext-Free Grammars and Top-Down ParsingDue Wednesday Oct 11, 2017 at 9 AMQuestion 1 [25 points](a) For each of the following grammars, precisely describe the language generated by the grammar. Theset of terminals T is {a, b} unless another set is specified. (16 points)(1)S → A | BA → aaaA | єB → Bbb | b(2)S → RbRR → 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 stringabbabb. Give your derivation inthree 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 eachgrammar.(1)L = {a3nb2m| m ≥ 0, n ≥ 0}. T = {a, b}(2)L = {a2ncmbm| m ≥ 0, n ≥ 0}. T = {a, b, c}.(3)L = {anbm| n+m is even}. T = {a, b}.(4)The complement of the language L = {anbn| n ≥ 0}. T = {a, b}. Hint: analyze the language intomultiple 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 grammarafterleft-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 forallproductions. If the grammar is not LL(1), identifyallthe problems with it. (5 points)

**You’re reading a preview**

To View Complete Document

Click the button to download

Subscribe to our plans