COMPILER DESIGN 

1 a) Define Boot strapping.    [3M]  b) What are the draw backs of predictive parsing?  [4M]

1. What are the actions performed by Shift reduce parser? [4M]
2. What are Abstract Syntax trees? [4M]
3. What are the advantages of heap storage allocation?             [4M]
4. What is machine independent code optimization?             [3M]

2          a)         Discuss in brief about left Recursion and Left Factoring with examples.            [8M]    b)         Define Regular Expression? Write about the identity rules for regular     [8M] expressions.

             3 a) Construct a Predictive parsing table for the Grammar  [8M]

                                    EàE+T/T, TàT*F/F, Fà(E)/id .

1. b)      Define Ambiguous grammar? Explain it with an Example.      [8M]

• a) Construct CLR Parsing table for the grammar SàL=R/R, Là*R/id, Rà [8M]   b)         What is Dangling ELSE ambiguity? How to reduce it.     [8M]

• a) Translate the expression –(a+b)*(c+d)+(a+b+c) in to quadruple, triple and [8M] indirect triple.
  1. Differentiate between Synthesized and Inherited attributes with suitable [8M] examples.

• a) Define Symbol table? Explain about the data structures used for Symbol table.     [8M]    b)         Explain in brief about Stack Storage allocation strategy.        [8M]
• a) What are loop invariant Computations? Explain how they affect the efficiency of [8M] a program.
  1. Explain in brief about different Principal sources of optimization techniques [8M] with suitable examples.

• a) What are the features of a Lexical analyzer? [3M]    b)      Explain in brief about left most and right most derivations.      [4M]
  1. List out the rules for FIRST and FOLLOW.                     [3M]
  2. Describe in brief about types of LR parsers.            [4M]
  3. What is common sub expression elimination?             [4M]
  4. Discuss about Instruction Selection and Register allocation. [4M]

• a) Define Compiler? Explain in brief about various language processing tools.             [4M]    b)         Construct a Finite Automaton for the Regular Expression (00+11)*?        [8M]
  1. Differentiate between NFA and DFA. [4M]

• a) Discuss in brief about LL(1) Grammars. [3M]    b)      Differentiate between Top down and bottom up parsing techniques.          [8M]
  1. Construct FIRST and FOLLOW for the Grammar: [5M]

                                    EàE+T/T,   TàT*F/F, Fà(E)/id.

• a) Construct LALR Parsing table for the grammar SàL=R/R, Là*R/id, Rà [8M]   b)         Define Ambiguous Grammar? Check whether the grammar SàaAB,               [8M]

                              AàbC/cd,    Càcd, Bàc/d,   is Ambiguous or not?

• a) Define Intermediate code generator. Explain in brief about different forms of [8M] Intermediate code generation.

1. b)         Explain in brief about Type checking and Type Conversion.        [8M]

• a) Differentiate between Static and Dynamic Storage allocation Strategies. [8M]    b)         What is dangling Reference in storage allocation? Explain with an Example.   [8M]

• a) Explain in brief about peephole optimization techniques. [8M] b) What is a Flow Graph? Explain how a given program can be converted in to a [8M] Flow graph?

• a) Define preprocessor. What are the functions of pre-processor? [4M]
  1. Discuss about the Syntax Error Handling. [4M]
  2. Differentiate between shift-reduce and Operator Precedence Parsers. [4M]
  3. What are the benefits of intermediate code generation? [3M]
  4. What are the various attributes of a Symbol Table? [3M]
  5. Mention the issues to be considered while applying the techniques for code [4M] optimization.

PART -B

• a) Write a regular expression for identifiers and reserved words. Design the [4M] transition diagrams for them.
  1. Explain the three general approaches for the implementation of a Lexical [8M] analyzer.
  2. Compare compiler and interpreter with suitable diagrams. [4M]
• a) Why lexical and syntax analyzer are separated out? [3M]    b) Construct the predictive parser for the following grammar      [8M]

S -> (L) | a

L ->L,S | S

1. c) Give the classification of parsing techniques and briefly explain each.                                                           [5M]

• a) Parse the input string int id,id; using shift-reduce parser for the grammar [8M] S -> TL;

T -> int | float

L -> L,id | id

1. Write the steps for the efficient construction of LALR parsing table. Explain [8M] with an example.

• a) Translate the assignment x := A[y,z] into three address statement. [8M]    b) Define Type Checker. Write down the specification of a simple Type Checker. [8M]
• a) How symbol table can be managed? Explain. [8M]    b) Discuss storage allocation for block structured languages.        [8M]
• a) Explain in detail about inter procedural optimization with an example. [8M]  b) Discuss in detail the role of dead code elimination and strength reduction [8M] during code optimization of a compiler.

• a) Briefly describe about the Lexical errors. [3M]
  1. What are the functions used to create the nodes of syntax trees? [4M]
  2. What are the three techniques for constructing LR parsing table? [4M]
  3. Discuss the evaluation of semantic rules. [4M]
  4. List the characteristics of peephole optimization. [4M]
  5. Give the criteria for achieving machine independent code optimization. [3M] PART -B
• a) Write regular expressions for the set of words having a,e,i,o,u appearing in that [4M] order, although not necessarily consecutively.
  1. Construct NFA equivalent to regular expression r= (a + b)^* [8M]
  2. Give general format for LEX program. [4M]
• a) Show that the grammar S -> 0S1| SS |ϵ is ambiguous.        [3M]    b) Explain the Non-Recursive predictive parsing with an example.          [8M]

1. c) What are the limitations of recursive descent parser?                   [5M]

• a) Write the steps for the construction of CLR parsing table. [8M]    b) Explain the compaction of LR parsing tables with an example.           [8M]

• a) Write the quadruple, triple, indirect triple for the expression          [8M]

               -(a*b) + (c+d)-(a+b+c+d)

1. Write an algorithm for constructing the dependency graph for a given parse [8M] tree.

• a) Construct basic blocks, data flow graph and identify loop invariant statements [8M] for the following:

for (i=1 to n)

{     j=1;     while (j<=n)

    {

        A=B*C/D;

         j=j+1;

     }

}

1. Explain how an activation record is related with runtime storage organization. [8M]

a) Explain in detail about the instruction scheduling with an example. [8M]    b) What are the principle sources of optimization? Give the classification of code

• a) Write a LEX program to identify comments in the program. [4M]    b) Consider the CFG S ->  SS+|SS*|a  . Derive the string aa+a* from the given       [5M] CFG and construct a parse tree for this string.
  1. Differentiate between LR and LL Parsers. [3M]
  2. What are the different types of three address statements? [3M]
  3. 1. Compare deep access and shallow access. [3M]
     2. List the properties of optimizing compilers. [4M]

• PART -B

  • a) State the reasons for separating Lexical analysis and Syntax analysis [4M] b) Describe the lexical errors and various error recovery strategies with suitable [8M] examples.
    1. Write a regular expression for relation operators. Design a transition diagram [4M] for them.
  • a) What is left recursion and left factoring? [3M]    b)  Verify whether the following grammar is LL(1) or not? [8M]
    • ^→ E + T | T T ^→ T* F / F
    • ^→ (F) |a|b.
  1. Discuss about error recovery strategies in predictive parsing. [5M]
  • a) Construct the collection of LR(0) item sets and draw the goto graph for the [8M] grammar S -> S S | a | ϵ. Indicate the conflicts (if any) in the various states of the SLR parser.
  1. b) Explain the process of handling “Dangling-ELSE” ambiguity.    [8M]
  • a) Construct the syntax tree and postfix notation for the expression        [8M]

  (a+ (b*c)) ↑d-e / (f+g).

  1. b) Explain in detail how an L-attributed grammar can be converted into a [8M] translation scheme.
  • a) Discuss in detail about the Reference counting garbage collectors. [8M]    b) Explain reducible and non-reducible flow graphs with an example.           [8M]
  • a) Explain the role of semantic preserving transformations and dominators in code [8M] optimization.
  1. b) Explain with suitable example various sources of loop optimization.                                                          [8M]

• a) Write the regular expression for the language accepting the strings which are [4M] starting with 1 and ending with 0, over the set ∑ = {0,1}.
  1. What are the goals of error handler in a parser? [4M]
  2. List the properties of LR parser. [4M]
  3. Write the need the Semantic analysis. [3M]
  4. Describe the structure of entries in symbol table. [4M]
  5. Compare local optimization with global optimization. [3M] PART -B
• a) Draw a block diagram of phases of a compiler and indicate the main functions [8M] of each phase.
  1. Define lexeme, token and pattern. Identify the lexemes that make up the tokens [8M] in the following program segment. Indicate corresponding token and pattern.

void swap(int i, int j)

{ int t; t=i; i=j; j=t; }

• a) What is an LL(1) grammar? When the grammar is said to be LL(1) grammar? [3M]   b) Design a non-recursive predictive parser for the following grammar.          [8M]

S ->  AaAb | BbBb

• -> e
• -> e

1. c) Discuss how Brute-Force approach operates in top down parsing.                                                        [5M]

• a) Draw the structure of LR parser. [3M]    b) Compute closure(I) and goto(I) for the grammar     [8M]

S -> Aa| bAc| Bc| bBa

• -> d
• -> d

1. c) Compare bottom up approaches of parsing with all top down approaches.                                           [5M]

• a) Construct the syntax tree and draw the DAG for the expression              [8M]

(a*b) + (c-d) * (a*b) + b.

1. Write Syntax directed definition for constructing syntax tree of an expression [8M] derived from the grammar

E -> E + T | E – T | T

T -> (E) | id | num

• a) What is Peephole optimization? Explain its characteristics. [8M] b) Explain with an example optimization of Basic blocks. [8M]

• a) Discuss how copy propagation can be done using data flow equation. [8M] b) Explain in detail the procedure that eliminates global common sub-expression. [8M]