# Download Previous Year Compiler Design Solved Gate Question by Kanodia PDF

Title Previous Year Compiler Design Solved Gate Question by Kanodia 501.7 KB 28
##### Document Text Contents
Page 1

GATE CS Topic wise Questions
Compiler Design

www.gatehelp.com

YEAR 2001

Question. 1
Which of the following statements is false ?

(A) An unambiguous grammar has same left most and right most
derivation

(B) An ( )LL 1 parser is a top-down parser

(C) LALR is more powerful than SLR

(D) An ambiguous grammar can never be ( )LR K for any k

SOLUTION

Yes, the ( )LL 1 parser is top down parser.
Order of strength LR SLR LALR< < .
So (A) & (C) are, true.
An ambiguous grammar can’t be ( )LR K
So option (A) is false since an unambiguous grammar has unique
right most derivation & left most derivations but both are not same.
Hence (A) is correct option

YEAR 2002

Question. 2

Dynamic linking can cause security concerns because

(A) Security is dynamic

(B) The path for searching dynamic libraries is not known till run

Page 2

CS Topicwise 2001-2010
Compiler Design

Page 2

www.gatehelp.com

time.

(D) Cryptographic procedures are not available for dynamic linking

SOLUTION

Dynamic linking is type of linking in which libraries required by the
program are linked during run time. But at this time cryptographic
procedures are not available, so make this process insecure.

Hence (D) is correct option.

YEAR 2003

Question. 3

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 this

SOLUTION

If a grammar has left recursion & left factoring then it is ambiguous.
So to convert a CFG to ( )LL 1 grammar both removal of left recursion
& left factoring need to be done.

Hence (C) is correct option.

Question. 4

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

Page 14

CS Topicwise 2001-2010
Compiler Design

Page 14

www.gatehelp.com

( )|S S a"

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

(A) n n n< <1 2 3 (B) n n n<1 3 2=

(C) n n n1 2 3= = (D) n n n1 3 2\$ \$

SOLUTION

The no. of states for ( )SLR 1 & ( )LALR 1 are equal so n n1 3= , but
( )CLR 1 or ( )LR 1 will have no. of states greater than LALR & ( )LR 0

both.
Hence (B) is correct option.

Question. 22

Consider line number 3 of the following C-program.

int main (){ | * Line 1 * |
int 1, N; | * line 2 * |
fro (i �,1 � N,1 );� �� | * Line 3 * |
}
object-module

(A) No compilation error

(B) Only a lexical error

(C) Only syntactic errors

(D) Both lexical and syntactic errors

SOLUTION

There are no lexical errors for C because all the wrong spelled keywords
would be considered as identifiers until the syntax is checked.
So the compiler would give syntax errors.
Hence (C) is correct option.

Data for Q. 23 & 24 are given below.

Solve the problems and choose the correct answers.

Consider the following expression grammar. The semantic rules for

Page 15

CS Topicwise 2001-2010
Compiler Design

Page 15

www.gatehelp.com

expression calculation are stared next to each grammar production.

E " number Eval number�val�
�E� ��� E���.val E���� .VAL E���� .val
�E� �E# E���.val E���� .VAL E���� .val
;

Question. 23

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

SOLUTION

Yace tool is used to create a ( )LALR 1 parser. This parser can detect
the conflicts but to resolve the conflicts it actually prefers shift over
reduce action.
Hence (C) is correct option.

Question. 24

Assume the conflicts 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 ' 'x is higher than that of ‘+’, and both operators
are left associative; expression is evaluated to 7

Page 27

CS Topicwise 2001-2010
Compiler Design

Page 27

www.gatehelp.com

(B) Those that use dynamic scoping

(C) Those that allow dynamic data structure

(D) Those that use global variables

SOLUTION

Dynamic memory allocation is maintained by heap data structure. So
to allow dynamic data structure heap is required.
Hence (C) is correct option.

Question. 44

The grammar S " aSA|bS|c is

(A) LL (1) but not LR (1) (B) LR (1) but not LL(1)

(C) Both LL (1) and LR (1) (D) Neither LL (1) nor LR (1)

SOLUTION

Given grammar
S aSA"
S bS"
S c"
This grammar is not ambiguous so it is ( )LL 1 also ( )LR 1 grammar
since all grammars are ( )LR 1 .
Hence (C) is correct option.

**********

Page 28

By NODIA and Company

Available in Two Volumes