Computer Science & Engineering Materials: 2017

UNIT-I

Each question carries 5 marks.

1.    Briefly explain the different phases of the compiler?
        OR
2.    Describe analysis phase and synthesis phase?

3.    Define the role of lexical analysis & its function?
         OR
4.    Define the regular expression with example and list out the different types of languages?

5.    With example explain about the recursive descent parsing?
           OR
6.    Briefly explain about LL(1) parser with an example?

7.    Describe the first & follow function with example?
            OR
8.    Briefly explain about the predictive parsing technique?

9.    Briefly explain about the top down parsing and its drawbacks?
              OR
10.    Describe what is left factoring and left recursion?

11.    Define the following things
a)    Symbol table b) boot strapping c)pass and phase
             OR
12.    Define compilers & types of compilers.

Objective Questions

1.    Let the language
         L1={hope, fear}
        L2={less, more}
        Then L1L2 denotes                                                                           [    ]
        a. {hopeless, hopemore, fearless, fearmore}
       b. {lesshope, lessfear, morehope, moref ear}
        c. {hopemore, fearless, }
        d. {hopeless, feamore}
2.    The main difference between NFA & DFA.                                      [    ]
       a. NFA gives more powerful definition   b. DFA contain less number of states
       c. DFA contain NULL transitions     d. NFA Contain multi-valued transitions

3.    The difference between lexeme and token                                 [ ]
          a. Lexeme represents class of tokens         b. Both are generated during parsing
          c. Token is one of the Lexeme                    d. Token represents class of Lexemes

4.    The number of Tokens in the following linguistic statement (Ignore blanks) in
              a=b*c+d;                                            [ ]
           a. 9              b. 8                 c. 12                   d. 7
5.    LL(1)stands                                                                                                [ ]
a. Scanning the input string from left to right and applying right most derivation   with one input symbol look head.
b. Scanning the input string from left to right and applying left most derivation with one input symbol look ahead
c. Scanning the input string from left to right and applying reverse leftmost derivation with one input symbol look a head
d. Scanning the input string from right to left and applying left most derivation with one input symbol look ahead
Fill in the Blanks

1.    The sequence of characters in the program that is matched by the pattern for a token is known as_____________.

2.    A compiler which runs on one machine and produces code for another is called as_________.

3.    Non-recursive descent parsing is free from _______________.
4.    Left factoring is the process of factoring out the common __________________.
5.    A grammar having more than one parse tree is said to be___________.

                                                          UNIT-II

1.    Define the bottom up parsing & and construct the parse tree for the given grammar
E->E+T/T,
T->F/F,
F->(id)/E,
F->(E)/id    find the string     id*id
             OR
2.    Construct the parse tree for the given grammar
S->TL,
T->int | float,
L->L, id | id    the input string is float id , id ;

3.    Briefly explain about the Shift Reduce parser.
               OR
4.    Consider the grammar
E->E+T|T,
T->F*/F,
F->(E)/id     perform the shift reduce parsing for the string id*id
5.    Define LR parsing & explain the LR parsing algorithm
               OR
6.    Define the different types of LR parser’s & explain the structure at the LR parsing table.
7.    Consider the grammar & compute CLOSURE(I),GOTO(I)
S->As|b,
A->SA|a
            OR
8.    Consider the grammar and construct the closure(I) and goto functions
E->E+T,
E->T,
T->T*F,
T->F,
F->(E),
F->id
9.    Define SLR parsing & describe the algorithm construct the SLR parsing table
             OR
10.    Construct the SLR parsing table for the given grammar
E->E+T,
E->T,
T->T*F,
T->F,
F->(E),
F->id
11.    Explain the procedure to parse the input string using parsing table (SLR)
                OR
12.    Define the LR(1) parser & describe the steps to construct the LR(1) parser.
13.    For the grammar
S’->S,
S->CC,
C->aC/d         construct the LR(1) set of items.
                     OR
14.    Construct the LR(1) parsing table, LR(1) items for the grammar
S->CC,
C->aC,
C->d
15.    Define LALR parser and explain the procedure to construct LALR parser.
                    OR
16.    Construct the LALR parser and parsing table for the given grammar
S->CC,
C->aC
C->d
17.    Define Ambiguous grammar with an example
                      OR
18.    Define YACC with a sample program.
Objective Questions

1.    LR(K) denote                                                                                         [ ]
      a. Right to left scanning the input, Revere Rightmost derivation, K-symbols look a head
      b. Right to left scanning the input, Reverse Left most derivation, K-symbols Look a head
      c. Left to right scanning of the input, Right most derivation in reverse, K symbols Look a head
      d. Left to right scanning of the input, Left most derivation in reverse, K-symbols look a head

2.    In SLR passing Table if AIα . (Reduce) belongs to I, then AI   is written in all places of M [I , a] where a                                                                                 [   ]
a. a ЄFIRST (α)                               b. a Є FIRST (A)
           c. a Є FOLLOW (A)                         d. a Є FOLLOW (α)
3.    LR stands for                                                                                           [ ]
              a. Left to Right scanning of input and right-most derivation in reverse
               b. Left to Right input scanning of input
               c. Left to Right scanning of input and Right to left reduction
               d. Left to Right reduction
4.    Which of the following passer is most powerful?                              [ ]
            a. SLR              b. Operator precedence               c. CALR                d. LALR
5.    __________________ is a parser generator. [ ]
    a. YACC    b. LEX        d. BISON    d. FLEX
Fill in the blanks
1.    A rightmost parser generates _________________.
2.    Sub strings that matches the right side of production is called as____.
3.    Operator precedence parsing is ______________parsing.
4.    Bottom Up parser attempt to find the ___________________for an input string.
5.    An LR parser can detect ___________as soon as it is possible to do on a left-to-right scan of the input.

                                                          UNIT-III

1.    Define Semantic analysis and the need of semantic analysis
             OR
2.    Define intermediate code & different forms of intermediate code
3.    What is Abstract syntax tree, construct the tree for the input string X= -a * b + ( -a * b ) and draw the DAG structure.
             OR
4.    Construct the syntax tree & post fix notation for the following expression
( a + ( b * c ) ) ↑ - e / ( f + g )
5.    Define three address code & its representation with an example
                OR
6.    Briefly explain about Syntax Directed definition(SDD) and its types
7.    Define L-attribute and S-attribute definitions
             OR
8.    Construct the parse tree, syntax tree, Annotated parse tree for the input string 5 * 6 + 7 by the grammar
S->EN,
E->E+T,
E->E-T,
E->T,
T->T*F,
T->T | F,
T->F,
F->(E),
F->digit
N->;
9.    Define inherited attribute and explain the steps to compute inherited attributes.
                OR
10.    What is type casting and define the type checking rules
11.    What is symbol table and define the attributes of symbol table
              OR
12.    Define attributed grammar, syntax directed translation
13.    Briefly explain the different data structures used to construct or organized the symbol table
            OR
14.    Explain the different block structured storage allocation strategies
15.    Explain about the non-block structured storage allocation strategies
             OR
16.    Define activation record and its usage.
Objective Questions
1.    Intermediate code generation is ________ phase in compiler.           [    ]
a. Second        b. First                      c. Fourth                  d. Third
2.    An attribute grammar in which all the attributes are ___________ then it is called S-
attributed   grammar.                                                                                      [   ]
1. Parsed              2. Inherited               3. A-attributed                4. Synthesized.
3.    Uniform symbol table                                                                                           [ ]
     a. Contains all constants in program.
           b. Is a permanent table of decision rules in the form of patterns for matching with the
              uniform symbol table to discover syntactic structure
           c. Consists of full or partial list of tokens as they appear in program created by lexical
               analysis and used for syntax analysis and interpretation.
           d. A permanent table which lists all key words and special symbols of language in
               symbolic form.
4.    The allocation which manages storage for all data objects at compile time is [ ]
a. Dynamic             b. static                c. heap                   d. stack
5.    The following strategy manages runtime storage                                                 [ ]
            a. Static                  b. dynamic           c. heap                   d. stack

Fill in the blanks

1.    ____________________ is a data structure used by the compiler to keep track of semantics of the variables.
2.    Activation record is also called as _____________.
3.    In a _______________ tree the parent nodes are operators and leaf nodes are symbols.
4.    A Graph showing dependencies is called a ________________.
5.    Another name for postfix form is _____________.

                                                                     UNIT-IV
1.    Define Loop optimization and explain about
a.    Code motion
b.    Induction variable
             OR
2.    Describe the following loop optimization techniques
a.    Loop Fusion
b.    Loop unrolling
c.    Reduction in Strength
3.    Define the following
a.    Copy propagation
b.    Dead code elimination
                OR
4.    List out different local optimization techniques and describe constant folding.
5.    Write a short notes on Busy expressions
                OR
6.    Describe Global optimization in detail
7.    Define KILL & GEN sets with examples
                OR
8.    Write a short notes on live variable analysis
9.    Define the data flow equations for the programming constructs
                     OR
10.    Describe basic block analysis and its implementation
11.    Describe flow graph analysis with an example
                      OR
12.    Describe the common sub expressions in detail
13.    Briefly explain about the data flow analysis
                        OR
14.    What is code optimization and describe copy propagation
15.    Explain about the induction variable analysis in detail
                      OR
16.    Briefly explain the concept of data flow analysis
Objective Questions
1.    The following refers to the techniques a compiler can employ in an attempt to produce a better object language program than is most obvious for a given source program is [    ]
           a. Code generation           b. code optimization         c. code execution   d. code debugging
2.    Peep-hole optimization is form of                                                                [    ]
a. Local optimization          b. constant folding       c. copy propagation d. data flow analysis
3.    The replacement of an expensive operation by a cheaper one [    ]
    a. Operator overriding                                   b. Operator overloading
                c. Reduction in strength                                 d. Operator elimination

      4. Machine Independent code optimization can be applied to _________________.   [     ]
           1. Source Code               2. Intermediate Representation
           3. Object Code                4. Run-Time-Output
5. At a point in a program if the value of variable can be used subsequently, then that variable is                                                                    [         ]
   1. Live           2. Dead                3. Duplicate              4. Aliasing

Fill in the blanks

1.    The most heavily traveled parts of programs are ________________ .
2.    Common expressions can be obtained from _________.
3.    __________ often turns the copy statement into dead code.
4.    Assignment of the form c:= d is called __________________.
5.    The loop which does not contain any other loops are ________ loop.

                                                                   UNIT-V
1.    Define the state of object code generation and its basic properties.
               OR
2.    Explain the different object code forms in detail.
3.    What is machine dependent code optimization list out its techniques
                   OR
4.    Briefly explain about the peephole optimization
5.    List out and explain any two different peephole optimization transformations
                        OR
6.    Explain the following
a.    Redundant instruction elimination
b.    Un reachable code

7.    Explain the following
a.    Flow control optimization
b.    Algebraic Simplification
                OR
8.    Explain the following
a.    Reduction in strength
b.    Use of machine idioms
9.    Briefly explain about the different register allocation strategies
                      OR
10.    Describe the Graph coloring method for Register allocation
11.    Explain about the Global register allocation method
                OR
12.    Explain the following
a.    Usage count
b.    DAG.

Objective Questions
1. Which of the following is not a peephole optimization? [    ]
a. Removal of unreachable code                 b. Elimination of Multiple Jumps
c. Elimination of loop invariant computation          d. None
2. Important use of live –variable information comes ____________.     [   ]
a. During Source Code                     b. During Construction of Flow Graph
c. during Generation of Object Code      d. During error correction
3. The ______ can be done through peephole optimization.      [   ]
a. Dynamic Programming                     b. Greedy method
c. Unreachable code elimination            d. Code generation
4. The __________ is the small moving window in target program.   [    ]
a. Screen saver      b. Graphics    c. Peephole              d. Greedy window
5. Object code _________.                                                                 [   ]
a. Is ready to execute              b. Is the output of computer but not assembler?
c. Must be loaded before execution         d must be rewritten before execution

Computer Science & Engineering Materials

Wednesday, September 6, 2017

COMPILER DESIGN LAB MANUAL

Saturday, July 22, 2017

ITWS,OOPS-JAVA,DS C++ LAB OBSERVATIONS

CSE LAB OBSERVATION'S FOR II,III,IV YEAR - I SEM

OPERATING SYSTEM LAB OBSERVATION

COMPILER DESIGN LAB OBSERVATION

Thursday, July 20, 2017

LEXICAL ANALYSIS

LEX PROGRAMS

COMPILER DESIGN NOTES PART-2

COMPILER DESIGN NOTES PART-1

COMPILER DESIGN UNIT WISE QUESTIONS FOR WEEKLY TEST

LEX & YACC TUTORIAL