Compiler-Design

Question 1

Consider the following grammar.

     S → aSB|d
     B → b 

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is _______.

A
7
       Compiler-Design       Parsers       GATE 2020       Video-Explanation
Question 1 Explanation: 

7 reductions total.
Question 2

Consider the following statements.

    I. Symbol table is accessed only during lexical analysis and syntax analysis.
    II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
    III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.

Which of the above statements is/are TRUE?

A
II only
B
I only
C
I and III only
D
None of I, II and III
       Compiler-Design       Run-Time-Environment       GATE 2020       Video-Explanation
Question 2 Explanation: 
I is wrong as Symbol table is also accessed during semantic analysis phase.
II is wrong as compilers which supports recursion require stack memory in run time environment.
III is wrong “any variable must be declared before its use” is a semantic error and not syntax error.
Question 3

Consider the productions A⟶PQ and A⟶XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.

    Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
    Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i 

Which one of the following is TRUE?

A
Only Rule 2 is L-attributed.
B
Neither Rule 1 nor Rule 2 is L-attributed.
C
Both Rule 1 and Rule 2 are L-attributed.
D
Only Rule 1 is L-attributed.
       Compiler-Design       Synthesized-Attribute       GATE 2020       Video-Explanation
Question 3 Explanation: 
In rule 2 for production A -> XY the attribute “i” is calculated from the right sibling Y in X.i = A.i + Y.s which is violating the L attribute definition, as in L attribute calculating attribute vale from RHS sibling is not allowed.
Question 4
Which one of the following statements is TRUE?
A
The LALR (1) parser for a grammar G cannot have reduce-reduce conflict if the LR (1) parser for G does not have reduce-reduce conflict.
B
Symbol table is accessed only during the lexical analysis phase.
C
Data flow analysis is necessary for run-time memory management.
D
LR (1) parsing is sufficient for deterministic context-free languages.
       Compiler-Design       Parsers       GATE 2022       Video-Explanation
Question 4 Explanation: 
Even though there is no reduce-reduce conflict in CLR(1) but in LALR(1) while merging the states differ in only lookahead may get reduce-reduce conflict. So the given statement is not true.
Symbol table is accessed in all the phases of compiler and not only in lexical analysis phase.
Data flow analysis is done in the control flow graph, in the code optimization phase. If LR(1) parses a grammar then definitely it is DCFL, so LR(1) parsing is sufficient for deterministic context-free languages.
Question 5
Consider the augmented grammar with { + , *, (, ), id } as the set of terminals.
A
5
       Compiler-Design       Parsers       GATE 2022       Video-Explanation
Question 5 Explanation: 
Question 6
Consider the following grammar along with translation rules.
A
80
       Compiler-Design       Parsers       GATE 2022       Video-Explanation
Question 6 Explanation: 
Question 7

The pass number for each of the following activities

    1. Object code generation
    2. Literals added to literal table
    3. Listing printed
    4. Address resolution of local symbols

That occur in a two pass assembler respectively are

A
1, 2, 1, 2
B
2, 1, 2, 1
C
2, 1, 1, 2
D
1, 2, 2, 2
       Compiler-Design       Assembler       GATE 1996
Question 7 Explanation: 
The functionalities from pass 1 and pass 2 are:
Pass 1:
1) Assign addresses to all statements in the program.
2) Save the values assigned to all labels for use in pass 2.
3) Perform some processing of assembler directives.
Pass 2:
1) Assemble instructions.
2) Generate data values defined by BYTE, WORD etc.
3) Perform processing of assembler directives not done during pass 1.
4) Write the program and assembling listing.
Question 8

Which of the following macros can put a micro assembler into an infinite loop?

(i)  .MACRO M1 X
     .IF EQ, X      ;if X=0 then
      M1 X + 1
     .ENDC
     .IF NE X       ;IF X≠0 then
     .WORD X        ;address (X) is stored here
     .ENDC
     .ENDM
(ii) .MACRO M2 X
     .IF EQ X
      M2 X
     .ENDC
     .IF NE, X
     .WORD X+1
     .ENDC
     .ENDM 
A
(ii) only
B
(i) only
C
both (i) and (ii)
D
None of the above
       Compiler-Design       Macros       GATE 1996
Question 8 Explanation: 
If M2 macro is called with X=0, then it will go into an infinite loop.
Question 9

Given below are the transition diagrams for two finite state machine M1 and M2 recognizing languages L1 and L2 respectively.
(a) Display the transition diagram for a machine that recognizes L1.L2, obtained from transition diagrams for M1 and M2 by adding only ε transitions and no new states.
(b) Modify the transition diagram obtained in part(a) obtain a transition diagram for a machine that recognizes (L1.L2)∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).

A
Theory Explanation.
       Compiler-Design       Finite-State-Machine       GATE 1996
Question 10

Consider the syntax-directed translation schema (SDTS) shown below:

    E → E + E  {print “+”}
    E → E ∗ E  {print “.”}
    E → id     {print id.name}
    E → (E) 

An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.

(a+b)∗(c+d), using the SDTS given above. 
A
Theory Explanation.
       Compiler-Design       Syntax-Directed-Translation       GATE 1996
Question 11

In the following grammar

         X ::= X ⊕ Y/Y
         Y ::= Z * Y/Z
         Z ::= id  

Which of the following is true?

A
‘⊕’ is left associative while ‘*’ is right associative
B
Both ‘⊕’ and ‘*’ is left associative
C
‘⊕’ is right associative while ‘*’ is left associative
D
None of the above
       Compiler-Design       Grammar       GATE 1997
Question 11 Explanation: 

⊕ is left associative.
* is right associative.
Question 12

A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which of the following is true?

A
A compiler using static memory allocation can be written for L
B
A compiler cannot be written for L; an interpreter must be used
C
A compiler using dynamic memory allocation can be written for L
D
None of the above
       Compiler-Design       Run-Time-Environments       GATE 1997
Question 12 Explanation: 
Compiler is use dynamic memory allocation then the memory will be allocated to an array at runtime.
Question 13

The conditional expansion facility of macro processor is provided to

A
test a condition during the execution of the expanded program
B
to expand certain model statements depending upon the value of a condition during the execution of the expanded program
C
to implement recursion
D
to expand certain model statements depending upon the value of a condition during the process of macro expansion
       Compiler-Design       Macros       GATE 1997
Question 13 Explanation: 
Macro is expanded during the process of Macro expansion.
Question 14

Heap allocation is required for languages

A
that support recursion
B
that support dynamic data structures
C
that use dynamic scope rules
D
None of the above
       Compiler-Design       Run-Time-Environments       GATE 1997
Question 14 Explanation: 
Heap allocation is required for languages that support dynamic data structures.
Question 15

In a resident – OS computer, which of the following systems must reside in the main memory under all situations?

A
Assembler
B
Linker
C
Loader
D
Compiler
       Compiler-Design       Run-Time-Environments       GATE 1998
Question 15 Explanation: 
In many operating system loader is permanently resident in memory.
Some OS may allow virtual memory may allow the loader to be located in a region of memory that is in page table.
Question 16

Which of the following statements is true?

A
SLR parser is more powerful than LALR
B
LALR parser is more powerful than Canonical LR parser
C
Canonical LR parser is more powerful than LALR parser
D
The parsers SLR, Canonical CR, and LALR have the same power
       Compiler-Design       Parsers       GATE 1998
Question 16 Explanation: 
LR > LALR > SLR
Canonical LR parser is more powerful than LALR parser.
Question 17

Type checking is normally done during

A
lexical analysis
B
syntax analysis
C
syntax directed translation
D
code optimization
       Compiler-Design       Compilers       GATE 1998
Question 17 Explanation: 
Type checking is normally done during syntax directed translation.
Question 18

Let the attribute ‘val’ give the value of a binary number generated by S in the following grammar:

S → L.L | L 
L→ LB | B 
B → 0 | 1 

For example, an input 101.101 gives S.val = 5.625

Construct a syntax directed translation scheme using only synthesized attributes, to determine S.val.

A
Theory Explanation.
       Compiler-Design       Synthesized-and-L-Attribute       GATE 1998
Question 19

Which of the following is the most powerful parsing method?

A
LL (1)
B
Canonical LR
C
SLR
D
LALR
       Compiler-Design       Parsers       GATE 1999
Question 19 Explanation: 
Canonical LR is most powerful.
LR > LALR > SLR
Question 20

The number of tokens in the Fortran statement DO 10 I = 1.25 is

A
3
B
4
C
5
D
None of the above
       Compiler-Design       Compile       GATE 1999
Question 20 Explanation: 
DO → 1
10 → 2
I → 3
= → 4
1.25 → 5
Question 21

Let synthesized attribute val give the value of the binary number generated by S in the following grammar. For example, on output 101.101, S.val = 5.625.

   S → LL|L 
   L → LB|B 
   B → 0|1 

Write S-attributed values corresponding to each of the productions to find S.val.

A
Theory Explanation.
       Compiler-Design       Synthesized-and-L-Attribute       GATE 1999
Question 22

The number of tokens in the following C statement.

printf("i = %d, &i = %x", i, &i); 

is

A
3
B
26
C
10
D
21
       Compiler-Design       Compilers       GATE 2000
Question 22 Explanation: 
We have six different types of tokens are available
(i) Keyword
(ii) Identifier
(iii) Constant
(iv) Variable
(v) String
(vi) Operator
Print = Token 1
( = Token 2
“i=%d%x” = Token 3 [Anything inside ” ” is one Token]
, = Token 4
i = Token 5
, = Token 6
& = Token 7
i = Token 8
) = Token 9
; = Token 10
Here, totally 10 Tokens are present in the equation.
Question 23

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

A
Leftmost derivation
B
Leftmost derivation traced out in reverse
C
Rightmost derivation
D
Rightmost derivation traced out in reverse
       Compiler-Design       Parsers       GATE 2000
Question 23 Explanation: 
Top-down parser – Leftmost derivation
Bottom-Up parser – Reverse of rightmost derivation
Question 24

Given the following expression grammar:

    E → E * F | F + E | F
    F → F - F | id  

which of the following is true?

A
* has higher precedence than +
B
– has higher precedence than *
C
+ and – have same precedence
D
+ has higher precedence than *
       Compiler-Design       Grammar       GATE 2000
Question 24 Explanation: 
The operator which is in low level that can have high preference.
Order of precedence is *, +, -.
Here * and + have equal preference, ‘-‘ can have higher precedence than + and *.
Question 25

Consider the syntax directed translation scheme (SDTS) given in the following.
Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

 E → E1 * T {E.val = E1.val * T.val}
 E → T {E.val = T.val}
 T → F – T1{T.val = F.val – T1.val}
 T → F {T.val = F.val}
 F → 2 {F.val = 2}
 F → 4 {F.val = 4} 

(a) Using this SDTS, construct a parse tree for the expression
4 – 2 – 4 * 2
and also compute its E.val.

(b) It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find E.red, the number of reductions performed while reducing an input to E.

A
Theory Explanation is given below.
       Compiler-Design       Descriptive       GATE 2000
Question 26

(a) Construct all the parse trees corresponding to i + j * k for the grammar

      E → E+E
      E → E*E
      E → id  
    (b) In this grammar, what is the precedence of the two operators * and +?
    (c) If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is non-ambiguous?
A
Theory Explanation is given below.
       Compiler-Design       Descriptive       GATE 2002
Question 27

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

A
Removing left recursion alone
B
Factoring the grammar alone
C
Removing left recursion and factoring the grammar
D
None of the above
       Compiler-Design       Grammar       GATE 2003
Question 27 Explanation: 
Left recursion removing (or) factoring the given grammar are not sufficient to convert an arbitrary CFG to an LL(1) grammar.
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 28

Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:

A
n1 is necessarily less than n2
B
n1 is necessarily equal to n2
C
n1 is necessarily greater than n2
D
None of the above
       Compiler-Design       Parsers       GATE 2003
Question 28 Explanation: 
No. of states in SLR and LALR are equal and no. of states in SLR and LALR are less than or equal to LR(1).
Question 29

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

A
always be evaluated
B
be evaluated only if the definition is L-attributed
C
be evaluated only if the definition has synthesized attributes
D
never be evaluated
       Compiler-Design       Syntax-Directed-Translation       GATE 2003
Question 29 Explanation: 
L-Attributed grammar can able to inherits either inherited attributes (or) synthesized attributes.
L-Attributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parse-tree.
Question 30

Which of the following statements is FALSE?

A
In statically typed languages, each variable in a program has a fixed type
B
In un-typed languages, values do not have any types
C
In dynamically typed languages, variables have no types
D
In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program
       Compiler-Design       Run-Time-Environments       GATE 2003
Question 30 Explanation: 
Dynamic typed languages are those languages in which variable must necessarily be defined before they are used. Then dynamic typed languages have types.
Question 31

Consider the grammar shown below

S → i E t S S' | a
S' → e S | ε
E → b 

In the predictive parse table. M, of this grammar, the entries M[S’, e] and M[S’, $] respectively are

A
{S’→e S} and {S’→ε}
B
{S’→e S} and { }
C
{S’→ε} and {S’→ε}
D
{S’→e S, S’→ε} and {S’→ε}
       Compiler-Design       Parsers       GATE 2003
Question 31 Explanation: 
First(S) = {1,a}
First(S’) = {e,ε}
First(E) = {b}
Follow(S’) = {e,$}
Only when ‘First’ contains ε, we need to consider FOLLOW for getting the parse table entry.

Hence, option (D) is correct.
Question 32

Consider the grammar shown below.

S → C C
C → c C | d

The grammar is

A
LL(1)
B
SLR(1) but not LL(1)
C
LALR(1) but not SLR(1)
D
LR(1) but not LALR(1)
       Compiler-Design       Parsers       GATE 2003
Question 32 Explanation: 

Hence, it is LL(1).
Question 33

Consider the translation scheme shown below.

S → T R
R → + T {print ('+');} R|ε
T → num {print(num.val);}

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string ‘9 + 5 + 2’, this translation scheme will print

A
9 + 5 + 2
B
9 5 + 2 +
C
9 5 2 + +
D
+ + 9 5 2
       Compiler-Design       Syntax-Directed-Translation       GATE 2003
Question 33 Explanation: 

Now traverse the tree and whatever comes first to print, just print it.
Answer will be 9 5 + 2 +.
Question 34

Consider the syntax directed definition shown below.

S → id := E           {gen (id.place = E.place;);}
E → E1 + E2           {t = newtemp ( ); 
                      gen(t = E1.place + E2.place;); 
                      E.place = t}
E → id                {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti’s are the temporary variable names generated by newtemp. For the statement ‘X: = Y + Z’, the 3-address code sequence generated by this definition is

A
X = Y + Z
B
t1 = Y + Z; X = t1
C
t1= Y; t2 = t1 + Z; X = t2
D
t1 = Y; t2 = Z; t3 = t1 + t2; X = t3
       Compiler-Design       Syntax-Directed-Translation       GATE 2003
Question 34 Explanation: 
Question 35

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

A
Smaller sizes of executable files
B
Lesser overall page fault rate in the system
C
Faster program startup
D
Existing programs need not be re-linked to take advantage of newer versions of libraries
       Compiler-Design       Run-Time-Environments       GATE 2003
Question 35 Explanation: 
Dynamic link libraries takes more time in program setup (in loading and linking phase to set up the global offset table and load and link the required libraries).
Question 36

Which of the following grammar rules violate the requirements of an operator grammar? P,Q,R are nonterminals, and r,s,t are terminals.

    (i) P → Q R
    (ii) P → Q s R
    (iii) P → ε
    (iv) P → Q t R r
A
(i) only
B
(i) and (iii) only
C
(ii) and (iii) only
D
(iii) and (iv) only
       Compiler-Design       Parsers       GATE 2004
Question 36 Explanation: 
Operator values doesn’t contains nullable values and two adjacent non-terminals on RHS production.
i) On RHS it contains two adjacent non-terminals.
ii) Have nullable values.
Question 37

Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2, the reference will be resolved at

A
Edit time
B
Compile time
C
Link time
D
Load time
       Compiler-Design       Compilers       GATE 2004
Question 37 Explanation: 
The link time can gives the reference to the executable file when the functions are present in the other modules.
Question 38

Consider the grammar rule E → E1 – E2 for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E1 and E2 do not have any common sub expression, in order to get the shortest possible code

A
E1 should be evaluated first
B
E2 should be evaluated first
C
Evaluation of E1 and E2 should necessarily be interleaved
D
Order to evaluation of E1 and E2 is of no consequence
       Compiler-Design       Target-Code-Generation       GATE 2004
Question 38 Explanation: 
After evaluating E2 first and then E1, we will have E2 in the register and then we can simply do SUB operation with E2 which will be in memory. And if we do E1 first and then E2, then we must move E2 to memory and again bring back E1 to the register before doing SUB operation, which will increase load.
Question 39

Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T     {E.value = E1.value * T.value}
    |    T     {E.value = T.value}
T → T1 & F     {T.value = T1.value + F.value}
    |    F     {T.value = F.value}
F → num        {F.value = num.value}  

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

A
200
B
180
C
160
D
40
       Compiler-Design       Grammar       GATE 2004
Question 39 Explanation: 
Given expression is
2 # 3 & 5 # 6 & 4
→ Here # means multiplication (*)
& means addition (+)
→ & is having more precedence because it is far from starting symbol, here # and & are left associatives.
2 # 3 & 5 # 6 & 4
⇒ (2 * (3+5)) * (6+4)
⇒ (2 * 8) * (10)
⇒ 16 * 10 = 160
Question 40

Consider the following grammar G:

S → bS| aA| b
A → bA| aB
B → bB| aS |a 

Let Na(w) and Nb(w) denote the number of a’s and b’s in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is

A
{w|Na(w) > 3Nb(w)}
B
{w|Nb(w) > 3Na(w)}
C
{w|Na(w) = 3k, k ∈ {0, 1, 2, …}}
D
{w|Nb(w) = 3k, k ∈ {0, 1, 2, …}}
       Compiler-Design       Grammar       GATE 2004
Question 40 Explanation: 
S→bS
S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
Na(w) > 3Nb(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
Nb(w) > 3Nb(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
Nb(w) = 3k
2 = 3k(✖️)
S = aA
S→aA
S→abA
S→abaB
S→abaa
n(a)=3
|n(a)|=3
→ Answer: Option C(✔️)
Question 41

The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:

A
ambiguous
B
left-recursive
C
right-recursive
D
an operator-grammar
       Compiler-Design       Parsers       GATE 2005
Question 41 Explanation: 
The given grammar can be turned into a infinite parse tree. So it is ambiguous.
It have A → AA has left recursion.
Question 42

Consider the grammar:

  E → E + n | E × n | n 

For a sentence n + n × n, the handles in the right-sentential form of the reduction are:

A
n, E + n and E + n × n
B
n, E + n and E + E × n
C
n, n + n and n + n × n
D
n, E + n and E × n
       Compiler-Design       Grammar       GATE 2005
Question 42 Explanation: 
E → E + n {Applying E → E+n}
→ E + E * n {Applying E → E * n}
→ E + n * n {Applying E → n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
Question 43

Consider the grammar:

   S → (S) | a 

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good:

A
n1 < n2 < n3
B
n1 = n3 < n2
C
n1 = n2 = n3
D
n1 ≥ n3 ≥ n2
       Compiler-Design       Parsers       GATE 2005
Question 43 Explanation: 
→ SLR(1) and LALR(1) both are be the states of LR(0) items then SLR(1) = LALR(1).
→ LR(1) be the states of LR(1) items.
→ LR(0) items never be greater than LR(1) items then SLR(1) = LALR(1) < LR(1)
n1 = (n3) < (n2)
Question 44

Consider line number 3 of the following C-program.

int main ( ) {                   /* Line 1 */
  int I, N;                      /* Line 2 */
  fro (I = 0, I < N, I++);       /* Line 3 */
} 

Identify the compiler's response about this line while creating the object-module:

A
No compilation error
B
Only a lexical error
C
Only syntactic errors
D
Both lexical and syntactic errors
       Compiler-Design       Compilers       GATE 2005
Question 44 Explanation: 
There is no error in the above code. Actually it is a link error. Here compiler fro is a function which is not declared. Hence, it will not produce any error. It will only throw a warning in C.
Question 45

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number 	 E.val = number. val
    |E '+' E 	 E(1).val = E(2).val + E>sup>(3).val
    |E '×' E	 E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

A
It detects recursion and eliminates recursion
B
It detects reduce-reduce conflict, and resolves
C
It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
D
It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
       Compiler-Design       Parsres       GATE 2005
Question 45 Explanation: 
Yacc favours shift move in case of SR conflict.
Question 46

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number 	 E.val = number. val
    |E '+' E 	 E(1).val = E(2).val + E>sup>(3).val
    |E '×' E	 E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

A
Equal precedence and left associativity; expression is evaluated to 7
B
Equal precedence and right associativity; expression is evaluated to 9
C
Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7
D
Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9
       Compiler-Design       Parsers       GATE 2005
Question 46 Explanation: 
First of all, it is ambiguous grammar. Hence, equal precedence and associativity. Now as Yacc resolved it with shift move we will shift until the last operator and then we will start reducing.

Hence, the answer is 9 and right associative.
Question 47

Consider the following grammar.

   S → S * E
   S → E
   E → F + E
   E → F
   F → id 

Consider the following LR(0) items corresponding to the grammar above.

(i) S → S * .E
(ii) E → F. + E
(iii) E → F + .E 

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
None of the above
       Compiler-Design       Parsers       GATE 2006
Question 47 Explanation: 
As we can see in the below given LR(0) items, that all three belongs to different state (sets).
Question 48

Consider these two functions and two statements S1 and S2 about them

int work1(int *a, int i, int j)          int work2(int *a, int i, int j)
{                                          {      
    int x = a[i+2];                            int t1 = i+2;
    a[j] = x+1;                                int t2 = a[t1]; 
    return a[i+2] – 3;                         a[j] = t2+1;
}                                              return t2 – 3; 
                                           } 
    S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1
    S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1
A
S1 is false and S2 is false
B
S1 is false and S2 is true
C
S1 is true and S2 is false
D
S1 is true and S2 is true
       Compiler-Design       Code-Optimization       GATE 2006
Question 48 Explanation: 
We cannot compare the program on the basis of runtime with respect to any inputs.
So, given statement is wrong.
S1: Let us assume an array = {1,2,3,4,5} and i=0.
Let j = i+2 = 0+2 = 2
For the respective example work1 and work2 results 1 and 0, so S1 statement is False.
Question 49

Consider the following grammar:

   S → FR
   R → S | ε
   F → id

In the predictive parser table, M, of the grammar the entries M[S,id] and M[R,$] respectively.

A
{S → FR} and {R → ε}
B
{S → FR} and { }
C
{S → FR} and {R → *S}
D
{F → id} and {R → ε}
       Compiler-Design       Parsers       GATE 2006
Question 49 Explanation: 
Predictive parsing table for the mentioned grammar:

The representation M[X,Y] means X represents Variable (rows) and Y represents terminals (columns).
The productions are filled in parsing table by the below mentioned rules:
For every production P → α, we have:
Rule 1: If P → α is a production then add this production for each terminal “t” which is in FIRST of [α] i.e., ADD P → α to M[P, a]
Rule 2: If “ϵ” belongs to FIRST of [P] then add P → α to M[P, b] where “b” represents terminals FOLLOW[P].
By the above rules, we can see that production S → FR will go M[S, a] where “a” is FIRST [FR] which is equal to FIRST[F] = id, So S → FR will go in M[S,id].
Since in the production R→ϵ , FIRST[ϵ] = ϵ, hence the production will go in M[R, b] where “b” represents terminals FOLLOW[R] and FOLLOW[R] = $, so production R→ϵ will go in M[R,$]
Question 50

Consider the following translation scheme.

   S → ER 
   R → *E{print("*");}R|ε 
   E → F + E {print("+");}|F 
   F → (S)|id {print(id.value);} 

Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints

A
2 * 3 + 4
B
2 * +3 4
C
2 3 * 4 +
D
2 3 4+*
       Compiler-Design       Syntax-Directed-Translation       GATE 2006
Question 50 Explanation: 

Now perform post order evaluation, you will get output as,
2 3 4 + *
There are 50 questions to complete.

Access subject wise (1000+) question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now