# CD |Gate-2007| Previous Year Questions| Set-14 CD |Gate-2007| Compiler Design

1. Which one of the following is a top-down parser? [GATE – 2007]

a. Recursive descent parser.
b. Operator precedence parser.
c. An LR(k) parser.
d. An LALR(k) parser.

2. Consider the grammar with non-terminals N = {S,C,S1 },terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:

S –> iCtSS1|a
S1 –> eS|ε
C –> b

The grammar is NOT LL(1) because:  [GATE – 2007]

a. it is left recursive
b. it is right recursive
c. it is ambiguous
d. it is not context-free

3. Consider the following two statements:

P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar

Which of the following is TRUE? [GATE – 2007]

a. Both P and Q are true
b. P is true and Q is false
c. Both P and Q are false
d. P is false and Q is true

4. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules

S –> aB        S –> bA
B –> b         A –> a
B –> bS        A –> aS
B –> aBB       A –> bAA

Which of the following strings is generated by the grammar? [GATE – 2007]

a. aaaabb
b. aabbbb
c. aabbab
d. abbbba

5. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules

S –> aB        S –> bA
B –> b         A –> a
B –> bS        A –> aS
B –> aBB       A –> bAA

Which of the following strings is generated by the grammar? [GATE – 2007]

a. 1
b. 2
c. 3
d. 4

6. Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ? [GATE – 2007]

a. L (D) = L (G)
b. L (D) ⊃ L (G)
c. L (D) ⊂ L (G)
d. L (D) is empty