Compiler Construction.

Added on - 18 Sep 2019

Trusted by +2 million users,
assist thousands of 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)
desklib-logo
You’re reading a preview
Preview Documents

To View Complete Document

Become a Desklib Library Member.
Subscribe to our plans

Download This Document