Compiler Construction | Assignment

Added on - 18 Sep 2019

  • 3

    pages

  • 1049

    words

  • 125

    views

  • 0

    downloads

Showing pages 1 to 1 of 3 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 | 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,....2S → RbRR → 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 stringabbabb. Give your derivation inthree 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 eachgrammar.(1)L = {a3nb2m| m ≥ 0, n ≥ 0}. T = {a, b}Ans LaaaL | Lbbb | є(2)L = {a2ncmbm| m ≥ 0, n ≥ 0}. T = {a, b, c}.Ans R→ cRb |є
desklib-logo
You’re reading a preview
card-image

To View Complete Document

Become a Desklib Library Member.
Subscribe to our plans

Unlock This Document