Ask a question to Desklib · AI bot
Compiler Construction | Assignment
Added on -2019-09-18
| 3 pages
| 1049 words
| 585 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 | bAns. S = { є , aaa, aaaaaa, aaaaaaaaa, .... , ,b,bbb,bbbbb, bbbbbbb, .... }Thus S contains all strings made froma and b such that strings made from a contain a’s in thisorder: 3,6,9,... and strings made form b contain b in this order: 1, 3,5,7,9,....2 S → RbR R → aRb | bRa | RR | bR | єAns. R = { є, b, ab, ba, bb, abb, bba, bab, bbb, abbb, ... }(2)S → aSbSaS | aSaSbS | bSaSaS | єS = { aba, aab, baa, aababa, aabaab, babaaa, aaabba, aaabab, .... }S contains all the strings having 2 more a’s than b’s (4)S → a S b | C Set of terminals here is T = {a, b, c} C → cc C | є Ans.C = {cc, cccc, cccccc, ... }S = { ab, accb, accccb, aaccbb, ... }C contains all the strings having even number of c’sS contains all strings beginning with a and ending b, in the middle it contains strings of set C or of set S(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)Ans.S → RbR → aRbbR → abbR → abbRbR → abbaRbbR → abbabbR → abbabbQuestion 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}Ans L → aaaL | Lbbb | є(2)L = {a2n cm bm | m ≥ 0, n ≥ 0}. T = {a, b, c}.Ans R → cRb | є
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