Gate 2003 Questions on Compiler Design

GATE 2003 TWO MARK QUESTIONS

5. Consider the grammar shown below

SàiEtSS’|α

S’àeS|ԑ

Eà b

In the predictive parse table. M, of this grammar, the entries M[S’, ԑ] 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’à ԑ}

Answer: D

Explanation:

The grammar is

SàiEtSS’|a

S’àeS|ԑ

Eàb

            The predicted parser  table M is

      Non

 Terminal               a              b              c              I               t               $

---

                S           s->a                                   S->iEiSS’

                S’                                        S’->ԑ                                            S’->ԑ

                                                            S’->es

                E                      E->b

So M[S’, e] ={S’à ԑ,  S’->e S} M[S’, $]=Sà ԑ

6.Consider the following grammar shown below

SàCC

CàcC|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)

Answer: D

Explanation:

Consider the  grammar 

SàCC

CàcC|d

The given grammar is LR(1)  grammar. Every SLR(1) grammar is an LR(1) grammar but not every LALR(1) grammar is LR(1) grammar. The given grammar is canonical LR(1) grammar and  every canonical LR(1)grammar is LR(1) grammar.

7. Consider the translation scheme shown below

SàTR

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)95+2+

(c)952++

(d)  ++952

Answer: B

Explanation:

For the input ‘9+5+2’ the translation scheme is 95+2+ shown below:

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

Gate 2003 Questions on Theory of Computation

One mark Questions:

1. Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAP Problem to Π, and shyam shows a polynomial time deduction from Π to 3-SAP which of the following can be inferred from these reduction ?

(a) Π is NP-hard but not NP-complete.
(b) Π is in NP, but is not NP-complete.
(c) Π is NP-complete.
(d) Π is neither NP-hard, nor in NP.

Answer: c

Explanation:

Ram shows 3-SAT ≤_p Π
Shyam shows Π ≤_p 3-SAT

Step-I: Now if p₁ ≤_p p₂ and if p₁ is np-complete, we can say that p₂ is np-hard. Now Ram has shown 3-SAT ≤_p Π and we know that 3-SAT is an np-complete problem. Therefore, we can conclude that Π  np-hard.

Step-II: If p₁ ≤_p p₂ and if p₂ belongs to np than p₁ also must belongs to np.
But shyam has shown that Π ≤_p 3-SAT, and we know that 3-SAT is np-complete and hence it belongs to np.
So Π also must belongs to np.

In step-I we showed that Π is np-hard.
In step-II we showed that Π belongs to np.

So is Π np-complete.