Gate 2003 Questions on Compiler Design

One Mark Questions and Answers

1.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

Answer: C

Explanation:
To convert an arbitrary CFG to an LL(1) grammar we must remove left recursion and left factoring if we can't remove these then grammar becomes ambiguous and LL(1) parser can't parse it.

2.Assume that the SLR parser for a grammar G has n₁ states  and the LALR parser for G has n₂ states. The relationship between n₁ and n₂ is
(a) n₁ is necessarily less than n₂
(b)n₁ is necessarily equal to n₂
(c)n₁ is necessarily greater than n₂
(d)None of the above

Answer: B

Explanation:
SLR parser has n₁ states for a  grammar G LALR parser has n₂ states for a  grammar G. The states of SLR and LALR parser are the states of corresponding states in a deterministic finite automata which recognizes the viable prefixes and both deterministic finite automate contains the equal number of states so n₁=n₂.


3.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

Answer: C

Explanation:
Every S(Synthesized)-attributed definition is L-attributed. For implementing inherited attributed during bottom-up parsing, extends to some, but not LR grammars. Consider the following example

Production   Semantic Rule
S-->L        L.count:=0
L-->L₁ 1       L.count:=L.count:+1
L-->E      print(L.count)
in the example above the nonterminal L in L-->E inherits the count of the number of 1's generated by S. Since the production L-->E is the first that a bottom-up burser would reduce by, the translater at the time can't know the number of 1's in the input. So in a bottom-up evaluation of a syntax directed definition, inherits  attributes can't be  evaluated if the definition is L-attributed in the given example. So we can say that L-attribute definition is based on simple LR(1) grammar, but it can't be implemented always but inherits attributes can be evaluated only if the definition has synthesized attributes.

4.
Which of the following statements is FALSE?
(a)In statically typed language, each variable  in a program has a fixed type
(b)In untyped 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

Answer: C

Explanation:
This grammar is SLR,LR,LALR all the types but is not LL(1).