Posts
ASSIGNMENT No. 1
Note: All questions are compulsory & carry equal marks.
Q. 1 (a) What is meant by compiler? How it is different from other translators?
(b) Explain the different phases of compiler.
Q. 2 (a) Explain the following:
a. Symbol Table
b. Reserved Word Table.
Also explain their roles in each phase of compiler.
(b) Pass the given statement from all the phases of compiler and mention output of each phase.
Result = (a – b) + (c / d) + 5
Q. 3 (a) Explain the following terms
a. Abstract Stack Machine
b. Annotated Parse Tree
(b) Construct minimum-state DFA’s for the following regular expressions
a. (a | b) * a (a | b)
b. (a | b) * a (a | b) (a | b)
c. (a | b) * a (a | b) (a | b) (a | b)
(c) Let
S→ xyS
S→ yzS
S→ yyS
S→ x
S→ zy
Construct a parse tree for the following string “xyxyxyyzyyzy”.
Q. 4 (a) What is meant by parsing. Explain top down and bottom up parsing with examples.
(b) Difference between an LL and Recursive Descent parser?
(c) Construct recursive descent parsers for the following grammars:
a. 0 S 1 | 0 1
b. + SS | - SS | a
Q. 5 (a) Differentiate ambiguous and unambiguous grammar. When does a context-free grammar is ambiguous?
(b) Construct unambiguous contex-free grammar for each of the following. In each case show that your grammar is correct.
a. Arithmetic expressions in postfix notation
b. Left associative lists of identifiers separated by commas
c. Left associative lists of identifiers separated by commas
d. Arithmetic expressions of integers and identifiers with the four binary operators +, –, *, /
e. Add unary plus and minus to the arithmetic operators (+, –, *, /)
ASSIGNMENT No. 2
(Total Marks: 100)
Note: All questions are compulsory & carry equal marks.
Q. 1 (a) Give Regular Expression for each of the following languae defined over alphabet ∑ = {a, b}
a. Language having all strings STARTING with a or b
b. Language having all strings NOT having ab
c. Language having all strings NOT having bb
d. Language having all strings HAVING aa
e. Language having all strings HAVING bba
f. Language having all strings NOT having two consecutive a’s
g. Language having all strings NOT having even no of a’s and b’s
(b) Construct a DFA for the regular expressions of the languages given in part (a).
Q. 2 (a) Construct a syntax-directed translation scheme that translates arithmetic expressions from infix notation into prefix notation.
(b) Give annotated parse trees for the inputs 9-5+2 and 9-5*2.
Q. 3 (a) Eliminate left recursion from the following given grammars:
S → S a b
| S a S
| X
X → X c
| a
| b
(b) Give detail for how a non-recursive predictive parser will parse the sentence “dace” using the table you constructed above?
(c) What are attribute grammars? Why we need attribute grammars?
Q. 4 (a) Explain the FIRST Sets and FOLLOW sets? Write down the rules for computing FIRST AND FOLLOW.
(b) Find the First and Follow sets for the grammar
S → ABC
A → a | Cb | ε
B → c | dA | ε
C → e | f
(c) Construct LL(1) parsing table from grammar
Q. 5 Explain the concept of Intermediate Code Generation. State your answer with the help of suitable example.
3468 Compiler Construction Credit Hours: 3(3, 0)
Recommended Book:
Compliers; Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, Jerrey D. Ullman
Course Outlines:
Unit No. 1 Introduction to Compiling
Compliers, analysis of the source program, The phases of a Complier, Cousins of the compiler, The grouping of phases, Complier-construction tools
Unit No. 2 A Simple One-pass Compiler
Overview, Syntax definition, Syntax-directed translation, parsing, A translator for simple expressions, Lexical analysis, Incorporating a symbol table, Abstract stack machines, Putting the techniques together
Unit No. 3 Lexical and Syntax Analysis
Lexical analysis (The role of the Lexical Analyzer, Input buffering, Specification of tokens, Recognition of tokens, a language for specifying Lexical analyzers, finite automata, From a regular expression to an NFA, Design of a Lexical analyzer Generator, Optimization of DFA-based pattern matchers), Syntax Analysis (The role of the parser, context-free grammars, Writing a grammar, Top-down parsing, Bottom-up parsing, Operator-precedence parsing, LR parsers, Using ambiguous grammars, parser Generators)
Unit No. 4 Syntax-Directed Translation
Syntax-directed definitions, construction of syntax trees, Bottom-up evaluation of S-attributed definitions, L-attributed definitions, Top-down translation, Bottom-up evaluation of inherited attributes, Recursive evaluators, Space for attribute values at compile time, Assigning space at complier-construction time, Analysis of syntax-directed definitions
Unit No. 5 Type Checking
Type systems, Specification of a simple type checker, Equivalence of type expressions, Type conversions, Overloading of functions and operators, Polymorphic functions, an algorithm for unification
Unit No. 6 Intermediate Code Generation
Intermediate Languages, Declarations, Assignment statements, Boolean expressions, Case statements, Back Patching, Procedure calls
Unit No. 7 Code Generations
Issues in the design of a code generator, The target machine, Run-time storage management, Basic blocks and flow graphs, Next-use information, A simple code generator, Register allocation and assignment, The dag representation of basic blocks, Peephole optimization, Generating code from dags, Dynamic programming code-generation algorithm, Code-generator generators
Unit No. 8 Code Optimization
Introduction, The principal sources of optimization, Optimization of basic blocks, Loops in flow graphs, Introduction to global data-flow analysis, Iterative solution of data-flow equations, Code-improving transformations, Dealing with aliases, Data-flow analysis of structured flow graphs, Efficient data-flow algorithms, A tool for data-flow analysis, Estimation of types, Symbolic debugging of optimized code
Unit No. 9 Writing a Complier
Planning a compiler, Approaches to compiler development, The compiler-development environment, Testing and maintenance, A Look at Some Compilers, EQN, a preprocessor for typesetting mathematics, Compilers for Pascal, The C compilers, The Fortran H compilers, The Bliss/11 compiler, Modula-2 optimizing compiler