Ask a question to Desklib · AI bot
Compiler Construction: Context-Free Grammars and Top-Down Parsing
Added on -2019-09-18
This page covers the topic of context-free grammars and top-down parsing in Compiler Construction. It includes solved assignments and questions related to CFGs, LL(1) parsing, left-recursion elimination, and more. The page covers Fall 2017 semester's second assignment. The assignment includes questions on describing languages generated by grammars, giving derivations, and extending grammars to express new language constructs.
| 2 pages
| 750 words
| 282 views
Trusted by 2+ million users,
1000+ happy students everyday
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)
Found this document preview useful?
You are reading a preview
Upload your documents to download
or
Become a Desklib member to get accesss
Paid Plans
Free Plan
Single Unlock
Monthly Plan
Yearly Plan