COMPILER DESIGN MATERIAL

        

Unit -I 

1. 1 Define a compiler. Explain the compilation process with example
   2.      Explain about the LEX tool.
   3.      Explain about the boot strapping.
   4.      Write the compilation process for the following statement.  a:=b+c*100;
   5. Write the difference between compiler and interpreter?
   6.      Explain the pass and phases of compiler
   7.      What is meant by input buffering? Explain the use of sentinels in recognizing tokens.
   8.      Draw the transition diagrams for the identifier and number.
   
   
   
   
   Unit – II
   
   
   1.      Define a context free grammar. Explain with example
   2.      Consider the following grammar         S->aS|aSbS|€.  Find the left most and right most derivation and corresponding derivation tree for string “aaabaab”
   3.      Consider the following grammar
   EàTE’
    E’à+TE’|€
   TàFT’
   Tà*FT’|€
   Fà (E)|id
   Find the FIRST and FOLLOW functions for the above grammar.
   4.      Construct the predictive parsing table for above grammar.
   5.      Check whether the string “id+id*id” is accepted by above grammar or not with the help of above parsing table?
   6. Compute the FIRST and FOLLOW for the following grammar    S->aAB|bA|€,    A->aAb|€,      B->bB|€
   7. Eliminate left recursion from the following grammar    E->E+T|T,     T->T*F|F,     F->(E)|a.
   8.      Consider the following grammar    S->(L)|a,    L->L,S|S. Find the left most and right most derivation and corresponding derivation tree for string (a,((a,a),(a,a))).
   9. Construct the recursive descent parser for the following grammar       E->TE’, E’->+TE’|€,      T->FT’, T->*FT’|€,   F->(E)|id.
   10.  construct the predictive parsing  table for following grammar
       S->(L)|a,     L->L,S|S
   11.  Check whether the following grammar is a LL(1) grammar
   S->iEtS|iEtSeS|a     E->b
   
   

                                                         UNIT-III

1. a) Consider the following grammar. S-> (L)|a        L->L,S|S

        Parse the input string: (a,(a,a)) using  Shift Reduce Parser.

    b) What is shift – reduce conflict?

2. Construct the SLR(1) parsing table for      E->E+T|T        T->T*F|F         F->(E)|id

3.  Consider the following grammar.  S → AS | b,  A → SA | a.  Construct the SLR parse table for the grammar. Show the actions of the parser for the input string “abab”

4. Find the closure (I) and goto(I) for the following grammar                                    

     E->E+T|T       T->T*F|F         F->(E)|a

    Construct SLR parsing table and parse the input string for a*a+a using above grammar.

5 .  Construct LALR(1) parser for the following grammar.

         S → L = R         S → R                         L → * R          L → id        R → L

6 Construct SLR parsing table for the grammar and parse the string: ( )( )$   

         S → S ( S )               S → ε

7.  a) Describe briefly about YACC parser generator.

     b) Write the comparisons of LR Parsers?

8   Construct CLR parser for the following grammar.  S->CC          C->aC|d

    

9  a) Build the SLR(1) parsing table for the following grammar:                      

E->E+T|T        T->T*F|F         F->F*|a|b

UNIT-IV

1 .a) For the following given grammar construct the Syntax directed definition and generate code fragment using S –attributed definition                                                       

 S->EN      E->E+T           E->E-T            E->T    T->T*F            T->T/F                T->F F->(E)       F->digit           N->;

Also calculate the input string 2*3+4; with parser stack using LR parser method.

     b) What are the benefits of intermediate code generation?

2 a) What are the various types of intermediate code representation?                 

   b) Give a syntax-directed definition to translate infix expressions into infix expressions

       Without redundant parenthesis.

3 a) What are the various methods of implementing three address statements?  

   b) Describe briefly about the construction of syntax trees?

4 a) Construct the 3- address code for the following expression.

         x=-a*b+-a*b                                                                                                 

   b) What are the different implementation methods for three-address code?

5 a) Explain in detail about the run time storage management.                            

   b) Discuss in detail about the storage allocation strategies.

 6 a) Draw the syntax tree and DAG for the expression (a*b)+(c-d)*(a*b)+b    

     b) Give the translation scheme that converts infix to postfix form for the following grammar. Also generate the annotated parse tree for input string 2+6+1

E-> E+T    E->T    T->0|1|2|3|4|5|6|7|8|9

  7 .  Write short notes on the following                                                 

a)      Activation Record

b)      Dynamic scope                              

c)      Call by reference

d)     Access links

UNIT V

1. a) Explain the design issues of a code generator.                                         

    b) What is a DAG? Mention its applications.

2. a) Explain about the peephole optimization.                                                 

    b) Machine dependent code generation?

3. a)  Explain the code generation algorithm with example?                            

    b) Write short notes on the following

        i) Frequency Reduction           ii) Unreachable code                     

4   a) Write shortly about DAG (Directed Acyclic Graph) representation. Draw the DAG for

      the expression a: = b *-c + b*-c.                                                                   

     b) Explain in detail about loop optimization techniques.              

5    a) What are the object code forms? Explain the issues in code generation?   

      b)  Construct the DAG for the following basic block

 d : = b * c

             e : = a +b

             b : = b * c

             a:= e- d                                                                                  

6 a) Discuss about the loop optimization techniques?                                        

    b) Explain the copy propagation and dead code elimination with  example.