⏱️
15 questions · 23 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT.
Q1NAT1 markDerivation
In S → a S b | ε, how many derivation steps produce aaabbb?
Numerical answer: ________
Q2NAT2 marksAmbiguity
How many parse trees does id + id * id * id have in E → E + E | E * E | id?
Numerical answer: ________
Q3MCQ1 markLeft recursion
Removing left recursion from A → A a | b gives:
- (A) A → b A′, A′ → a A′ | ε
- (B) A → a A′ | b
- (C) A → b | a A
- (D) A′ → A a | ε
Q4MSQ2 marksFIRST/FOLLOW
For S → A B, A → a A | ε, B → b B | c, which are true?
- (A) FIRST(S) = { a, b, c }
- (B) FOLLOW(A) = { b, c }
- (C) FOLLOW(B) = { $ }
- (D) ε ∈ FIRST(S)
Q5NAT2 marksLL(1) table
How many non-empty cells does the LL(1) table of S → a A B | b A, A → c A | ε, B → d | ε have?
Numerical answer: ________
Q6MCQ1 markLL(1)
Which grammar is LL(1)?
- (A) S → S a | b
- (B) S → a S | a
- (C) S → a S | b
- (D) S → a b | a c
Q7MCQ1 markRecursive descent
A recursive-descent parser cannot be written directly for a grammar that is:
- (A) right recursive
- (B) left recursive
- (C) LL(1)
- (D) left-factored
Q8NAT1 markItems
How many LR(0) items does the augmented grammar of S → a S | a have?
Numerical answer: ________
Q9NAT2 marksStates
How many states does the LALR(1) automaton of S → L = R | R, L → * R | id, R → L have?
Numerical answer: ________
Q10MCQ2 marksClassification
S → L = R | R, L → * R | id, R → L is:
- (A) LR(0)
- (B) SLR(1) but not LALR(1)
- (C) LALR(1) but not SLR(1)
- (D) not LR(1)
Q11MCQ1 markConflicts
Merging CLR states into LALR states can produce:
- (A) only shift/reduce conflicts
- (B) only reduce/reduce conflicts
- (C) both
- (D) neither
Q12MSQ2 marksShift-reduce
Which are true about shift-reduce parsing?
- (A) The handle is always on top of the stack.
- (B) It traces a leftmost derivation.
- (C) The set of viable prefixes is regular.
- (D) An ambiguous grammar always causes a conflict.
Q13NAT2 marksYACC
E → E + E | E * E | ( E ) | n, with every shift/reduce conflict resolved by shifting. Value of 2 + 3 * 4 + 5?
Numerical answer: ________
Q14MCQ1 markAssociativity
In E → E − T | T, T → n, the expression 10 − 3 − 2 evaluates to:
- (A) 5
- (B) 9
- (C) −5
- (D) 11
Q15MCQ2 marksLR(0) conflict
In the LR(0) automaton of E → E + T | T, T → T * F | F, F → ( E ) | id, the state reached from I0 on T contains:
- (A) E → T• only
- (B) E → T• and T → T•*F
- (C) T → F• and F → id•
- (D) E′ → E• and E → E•+T
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 41 mark
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb: 4.
Re-read: Lesson 2.1.1 — Context-free grammar primer: productions, derivations (leftmost/rightmost), parse trees
Q2 Answer: 52 marks
Three operators: 5 (computed).
Re-read: Lesson 2.1.2 — Ambiguity; encoding operator precedence and associativity in a grammar
Q3 Answer: (A)1 mark
A → Aα | β ⇒ A → βA′, A′ → αA′ | ε.
- (B) is wrong: Changes the language.
- (C) is wrong: Changes the language.
- (D) is wrong: Still left recursive.
Re-read: Lesson 2.2 — Grammar transformations: eliminating left recursion (direct and indirect); left factoring
Q4 Answer: (A) (B) (C)2 marks
B is not nullable, so S is not nullable (computed).
Re-read: Lesson 2.3.2 — FIRST and FOLLOW sets
Q5 Answer: 72 marks
S: a, b (2). A: c; ε under FOLLOW(A) = {d, $} (3). B: d; ε under {$} (2). Total 7.
Re-read: Lesson 2.3.3 — LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a string
Q6 Answer: (C)1 mark
Alternatives start with a and b.
- (A) is wrong: Left recursive.
- (B) is wrong: Both start with a.
- (D) is wrong: Both start with a.
Re-read: Lesson 2.3.3 — LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a string
Q7 Answer: (B)1 mark
Left recursion makes a procedure call itself before consuming input.
- (A) is wrong: Right recursion is fine.
- (C) is wrong: LL(1) grammars are ideal.
- (D) is wrong: Left factoring helps.
Re-read: Lesson 2.3.1 — Recursive-descent parsing and backtracking
Q8 Answer: 71 mark
S′→S: 2, S→aS: 3, S→a: 2 → 7.
Re-read: Lesson 2.4.2 — LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) table
Q9 Answer: 102 marks
Same as its LR(0) automaton: 10 (CLR has 14).
Re-read: Lesson 2.4.5 — LALR(1): merging states and which conflicts merging can create
Q10 Answer: (C)2 marks
SLR S/R conflict on =; lookaheads resolve it.
- (A) is wrong: Already SLR fails.
- (B) is wrong: SLR ⊂ LALR, and here SLR fails.
- (D) is wrong: It is CLR with 14 states.
Re-read: Lesson 2.4.6 — Power and state-count comparison of LL(1), LR(0), SLR, LALR, CLR; grammar-classification drills
Q11 Answer: (B)1 mark
Shift entries depend on cores only.
- (A) is wrong: Impossible.
- (C) is wrong: S/R cannot be new.
- (D) is wrong: R/R can appear.
Re-read: Lesson 2.4.5 — LALR(1): merging states and which conflicts merging can create
Q12 Answer: (A) (C) (D)2 marks
It traces a rightmost derivation in reverse.
Re-read: Lesson 2.4.1 — Shift-reduce parsing; handles; viable prefixes; shift/reduce and reduce/reduce conflicts
Q13 Answer: 292 marks
Right grouping: 2 + (3 * (4 + 5)) = 29.
Re-read: Lesson 2.4.7 — Operator-precedence parsing (brief); YACC conflict resolution with precedence and associativity; panic-mode error recovery (brief)
Q14 Answer: (A)1 mark
Left associative: (10 − 3) − 2 = 5.
- (B) is wrong: That is right grouping.
- (C) is wrong: No grouping gives −5.
- (D) is wrong: No grouping gives 11.
Re-read: Lesson 2.1.2 — Ambiguity; encoding operator precedence and associativity in a grammar
Q15 Answer: (B)2 marks
Which is why LR(0) has a shift/reduce conflict on * there.
- (A) is wrong: T → T•*F is also there.
- (C) is wrong: Those are other states.
- (D) is wrong: That is the state on E.
Re-read: Lesson 2.4.2 — LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) table
Wrong on Q → re-read
| Question | Topic | Re-read |
|---|---|---|
| Q1 | Derivation | Lesson 2.1.1 |
| Q2 | Ambiguity | Lesson 2.1.2 |
| Q3 | Left recursion | Lesson 2.2 |
| Q4 | FIRST/FOLLOW | Lesson 2.3.2 |
| Q5 | LL(1) table | Lesson 2.3.3 |
| Q6 | LL(1) | Lesson 2.3.3 |
| Q7 | Recursive descent | Lesson 2.3.1 |
| Q8 | Items | Lesson 2.4.2 |
| Q9 | States | Lesson 2.4.5 |
| Q10 | Classification | Lesson 2.4.6 |
| Q11 | Conflicts | Lesson 2.4.5 |
| Q12 | Shift-reduce | Lesson 2.4.1 |
| Q13 | YACC | Lesson 2.4.7 |
| Q14 | Associativity | Lesson 2.1.2 |
| Q15 | LR(0) conflict | Lesson 2.4.2 |