Ask a question from expert

Ask now

Compiler Construction: Context-Free Grammars and Top-Down Parsing

2 Pages750 Words282 Views
   

Added on  2019-09-18

About This Document

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.

Compiler Construction: Context-Free Grammars and Top-Down Parsing

   Added on 2019-09-18

BookmarkShareRelated Documents
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)
Compiler Construction: Context-Free Grammars and Top-Down Parsing_1

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Desklib - Online Library for Study Material with Solved Assignments, Essays, Dissertation
|4
|530
|469

Compiler Construction | Assignment
|3
|1049
|585

Concepts of Programming Language
|15
|1712
|339

Ambiguous Grammar and BNF Grammar in Programming
|6
|1081
|79