Loading

SET 3


  Question 1

The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

A : Finite state automata
B : Deterministic pushdown automata
C : Non-Deterministic pushdown automata
D : Turing machine


  •  
    .

     Correct answer is :A

     Solution :
      Lexical Analysis is implemented by finite automata

  •   Question 2

    In a compiler, keywords of a language are recognized during

    A : parsing of the program
    B : the code generation
    C : the lexical analysis of the program
    D : dataflow analysis


  •  
    .

     Correct answer is :C

     Solution :
      Any identifier is also a token so it is recognized in lexical Analysis

  •   Question 3

    For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.



    A : B :
    C : D :


  •  
    .

     Correct answer is :A

     Solution :
      First (A) = First (S) = First (aAbB) U First (bAaB) U First (ε)
    ={a} U {b} U {ε} = {ε , a,b}
    First (B)= First (S) = {ε,a,b}
    Follow (A) = First (bB) = First (aB) = {a,b}
    Follow (B) = Follow (S)= {$} U Follow (A) ={ $,a,b}

  •   Question 4

    For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.
    The appropriate entries for E1, E2, and E3 are


    A : E1: S->aAbB, A->S
    E2: S->bAaB, B->S
    E3: B->S

    B : E1: S->aAbB, S->ε
    E2: S->bAaB, S->ε
    E3: S->ε

    C : E1: S->aAbB, S->ε
    E2: S->bAaB, S->ε
    E3: B->S

    D : E1: A->S, S->ε
    E2: B->S, S->ε
    E3 : B ->S



  •  
    .

     Correct answer is :C


  •   Question 5

    What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A -> ∈and A->a) to parse a string with n tokens?

    A : n/2
    B : n-1
    C : 2n-1
    D : 2n


  •  
    .

     Correct answer is :B

     Solution :
      Say string is pqrs and we want to parse it and the grammar is
    A->pB
    B->qC
    C->rs
    Derivation is like pB->pqC->pqrs so total 3 steps for length 4 string

  •   Question 6

    Consider the following two sets of LR(1) items of an LR(1) grammar
    Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
    1. Cannot be merged since look aheads are different
    2. Can be merged but will result in SR conflict
    3. Can be merged but will result in RR conflict
    4. Cannot be merged since goto on c will lead to two different sets




    A : 1 only
    B : 2 only
    C : 1 and 4 only
    D : 1,2,3 and 4


  •  
    .

     Correct answer is :D

     Solution :
      1. Merging of two states depends on core part (production rule with dot operator), not on look aheads.
    2. The two states are not containing Reduce item ,So after merging, the merged state can not contain any S-R conflict
    3. As there is no Reduce item in any of the state, so cant have R-R conflict.
    4.Merging of stats does not depend on further goto on any terminal. So all statements are false.


  •   Question 7

    The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand. Assume that all variables are dead after this code segment
    c =a+ b;
    d= c * a;
    e= c+ a;
    x= c *c;
    if (x >a )
    {
    y = a * a;
    }
    else {
    d =d * d;
    e= e * e;
    }
    Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?


    A : 0
    B : 1
    C : 2
    D : 3


  •  
    .

     Correct answer is :B


  •   Question 8

    The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand. Assume that all variables are dead after this code segment
    c =a+ b;
    d= c * a;
    e= c+ a;
    x= c *c;
    if (x >a )
    {
    y = a * a;
    }
    else {
    d =d * d;
    e= e * e;
    }
    What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation


    A : 3
    B : 4
    C : 5
    D : 6


  •  
    .

     Correct answer is :B


  • MY REPORT
    TOTAL = 8
    ANSWERED =
    CORRECT / TOTAL = /8
    POSITIVE SCORE =
    NEGATIVE SCORE =
    FINAL SCORE =