B.Tech. Pt-III (IT) 2nd Semester Examination, 2024 --- Compiler Design (IT601)

Department of Engineering and Technological 

Studies, 

University of Kalyani

B.Tech. Pt-III (IT) 2^nd Semester 

Examination, 2024

Subject: Compiler Design

Paper: IT601

Full marks=70 Time: 3 Hours

The figures in the right-hand margin indicate 

marks.

Candidate are required to give their answers 

in their own words as far as possible.

The notations follow their standard 

meanings.

Answer question number one and

 any five from rest.

1.   Answer any ten questions:                                                                

                                                                                                                            (2 x 10 = 20)

    a)     What do you mean by utility program?

    b)     Define cross-compiler.

    c)     What do you mean by 

               Incremental-compiler?

    d)     Define top-down and bottom-up parsing.

    e)     What do you mean by shift / reduce 

            and reduce / reduce conflict?

    f)     What is the relation between regular

             expressions a* and a+ ?

    g)     What do you mean by intermediate

             code generation ?

    h)     What are the purpose of 

                activation record ?

    i)     Discuss the importance of symbol

             table in compiler design.

    j)     What are the role of laxical analyzer

             in compiler design?

    k)     What are the role of syntax analyzer

             in compiler design?

    l)     What are the role of semantic analysis

             in compiler design?

    m)   Write down the advantage of optimized

             code over non-optimized code.

    n)    Show that for improving the locality

         of reference the optimizer exchange the

         inner loops with outer loops.

    o)     Compare the expression A * B and A + A + ... + A(B-times) in terms of strength

            reduction from code.

2. a)     Represents the relationship between

             the phases of a compiler.

    b)     Match all items in Group 1 with correct 

            options from those given in Group 2.

Group 1	Group 2
Regular expression	Syntax analysis
Pushdown  automata	Code generation
Dataflow analysis	Laxical analysis
Register allocation	Code optimization

 c)     Distinguish between NFA and DFA. 

            Compare their powers as token

             recognizer.

                                                                                                                                            (4+2+4)

3. a)     What do you mean by left recursive 

            grammar? 

            Eliminate the left recursion from

            the following grammar rule 

A -> Aɑ₁ | Aɑ₂ | ... | Aɑ_m | β₁ | β₂ | ... | β_n .

    b)     What do you mean by operator 

grammar? Give example.

    c)     What are the different types of 

common error occuring in programs?

                                                                                                                                            (4+3+3)

4. a)     Define First(A), Follow(A), and

 nullable(A) for a grammer.

   

 b)    Find the First, Follow and nullable for 

each of the non-terminal in the following 

grammar     

E -> ME’ , E’ -> ɛ , E’ -> +ME’ , M -> AM’ , 

M’ -> ɛ , M’ -> *AM’ , A -> num , A -> (E) .

    c)     What do you mean by LR parsing ? 

Write down different methods to perform

 LR parsing.    

                                                                                                                                                                                                                                                                                                                       

                                                                                                                                                (3+5+2) 

5. a)     Define non-recursive predictive 

parsing-LL(k) parsing.

    b)     Write down the conditions that a given

 grammar is LL(1) grammar.

    c)     Prove that the grammar 

S -> A | B, A -> cA + b | a, B -> cB + a | b 

is not LL(1).

                                                                                                                                                (2+3+5)

6. a)     What do you mean by code 

optimization? 

Discuss different types of code 

            optimization technique.

   

     b)     Discuss loop fission, loop fusion, 

loop unrolling in a loop optimization technique.

    c)     Consider following piece of program:

                a = c + d , e = a + b , f = e – 1

            What is the fewest number of register 

that are needed for the program ?

                                                                                                                                            (5+3+2)

7. a)     What do you mean by Abstract Syntax

 Trees (AST) ?

    b)     Draw a Abstract Syntax Trees (AST) 

of the following piece of code.

               

         If x > 0 then x = 3 * (y + 1) else y = y + 1

c)     What do you mean by Directed Acyclic

 Graphs (DAGs)?

d) Construct a Directed Acyclic Graphs (DAGs)

     of the following piece of code.

   If x > 0 then x = 3 * (y + 1) else y = y + 1

    

                                                                                                                                            (2+3+2+3)

8.     Short notes:

                                                                                                                                                    (2 x 5)

        Answer any two of the following:

        a)     Compiler vs. Interpreter.

        b)     The lexical analysis tool-LEX.

        c)     Parser generator-YACC.

        d)     Challenges in complier design and

                 its application.

--------------------End-------------------