Compiler Design MCQs - Context-Free Grammars, FIRST-FOLLOW and LL(1) Parsing (Set 2)

Q1. Which statement about ambiguity of context-free grammars is correct?

a) Ambiguity can always be detected by building the LL(1) table

b) Every ambiguous grammar has an equivalent unambiguous grammar

c) An LL(1) grammar may still be ambiguous

d) Deciding whether an arbitrary CFG is ambiguous is undecidable

Q2. Using the grammar E -> E + E | E * E | id, how many distinct parse trees exist for the string id + id + id * id?

a) 5

b) 2

c) 3

d) 6

Q3. Which grammar results from removing the left recursion in A -> A x | y?

a) A -> x A', A' -> y A' | epsilon

b) A -> y A | x

c) A -> y A', A' -> x A' | epsilon

d) A -> A' y, A' -> x A' | epsilon

Q4. What is the main reason for applying left factoring to a grammar?

a) To let a predictive parser choose between alternatives using a single lookahead token

b) To remove ambiguity from any grammar

c) To convert the grammar into Chomsky normal form

d) To reduce the number of terminals

Q5. For the grammar below, what is FIRST(S)?

S -> A B
A -> a | epsilon
B -> b | epsilon

a) {a, b, epsilon}

b) {a}

c) {a, b}

d) {a, epsilon}

Q6. For the grammar below, with S as the start symbol, what is FOLLOW(B)?

S -> A c B | B d
A -> a | epsilon
B -> b | epsilon

a) {d}

b) {d, $}

c) {$}

d) {c, d, $}

Q7. In the name LL(1), what do the two L's and the 1 stand for?

a) Left-to-right scan, leftmost derivation, one parse table

b) Leftmost derivation, LR items, one stack

c) Left-to-right scan, last derivation, one lookahead token

d) Left-to-right scan, leftmost derivation, one lookahead token

Q8. For productions A -> alpha | beta, which condition is required for the grammar to be LL(1)?

a) FOLLOW(alpha) and FOLLOW(beta) are disjoint

b) alpha and beta have the same length

c) FIRST(alpha) and FIRST(beta) are disjoint, and if beta =>* epsilon then FIRST(alpha) and FOLLOW(A) are disjoint

d) Neither alpha nor beta contains a non-terminal

Q9. In LL(1) table construction, a production A -> alpha with alpha =>* epsilon is additionally entered under which columns of row A?

a) Every terminal in FIRST(A) only

b) Only the $ column

c) Every terminal of the grammar

d) Every terminal in FOLLOW(A), including $ if present

Q10. Which of the following grammars is LL(1)?

a) S -> a S | a

b) S -> a S b | epsilon

c) S -> S a | b

d) S -> a b | a c

Q11. Why does a naive recursive descent parser fail on the production E -> E + T?

a) The procedure for E calls itself before consuming any input, causing infinite recursion

b) It cannot handle the + terminal

c) It requires two lookahead tokens

d) It produces a rightmost derivation instead

Q12. Which string can be derived from the grammar S -> a S a | b S b | c?

a) abcab

b) abcba

c) aabcb

d) abccba

Q13. In the standard if-then-else grammar, the dangling-else ambiguity is usually resolved by which rule?

a) Each else is matched with the outermost if

b) An else is attached to the if that has the longest condition

c) Each else is matched with the closest preceding unmatched then

d) The program is rejected as erroneous

Q14. In the classic expression grammar below, what is FOLLOW(F)?

E  -> T E'
E' -> + T E' | epsilon
T  -> F T'
T' -> * F T' | epsilon
F  -> ( E ) | id

a) {*, $}

b) {+, ), $}

c) {(, id}

d) {*, +, ), $}

Q15. The grammar below is best described as

S -> A a | b
A -> S c | d

a) not left recursive

b) indirectly left recursive

c) directly left recursive

d) ambiguous

Q16. In the grammar E -> E - T | T, T -> id, the operator - is

a) right associative

b) left associative

c) non-associative

d) ambiguous in associativity

Q17. In panic-mode error recovery for an LL(1) parser, on an error with non-terminal A on the stack, which tokens are commonly used as synchronising tokens?

a) Tokens in FIRST of the start symbol only

b) All identifiers

c) Tokens in FOLLOW(A)

d) Only the end marker $

Q18. In a table-driven LL(1) parser, what does the parser do when the top of the stack is a terminal that matches the current input token?

a) Pops the terminal and advances the input pointer

b) Looks up the parse table and pushes a production

c) Reduces by the matching production

d) Reports an error and halts