Compiler Design Week 5 NPTEL Assignment Answers 2025

NPTEL Compiler Design Week 5 Assignment Answers 2024

1. In a predictive parsing table, if any cell has multiple entries, the grammar is:

Options:

• (A) Ambiguous
• (B) Erroneous
• (C) Both ambiguous and erroneous
• (D) None of the other options

Answer: ✅ (A) Ambiguous

Explanation:
Predictive parsers (like LL(1)) require that each cell in the parsing table has at most one production. Multiple entries suggest ambiguity—meaning more than one way to parse a given input.

2. Consider the following grammar G:
S → iEtS | iEtSeS | a
E → b
After some transformation X, the grammar G becomes G’ as given below:
S → iEtSS’ | a
S’ → eS | ε
E → b
What is transformation X?

(A) Elimination of left recursion
(B) Left factoring
(C) Elimination of immediate left recursion
(D) None of the above

Answer: ✅ (B) Left factoring

Explanation:
The original grammar has a common prefix iEtS. Left factoring extracts this to reduce backtracking and make the grammar suitable for LL parsers.

---

3. In the name “LR Parser”, the ‘R’ stands for:

(A) Constructing a Rightmost Derivation
(B) Constructing a Rightmost Derivation in Reverse
(C) Constructing a Recursive Parser
(D) None of the other options

Answer: ✅ (B) Constructing a Rightmost Derivation in Reverse

Explanation:
LR parsers work by constructing rightmost derivations in reverse order—meaning they reduce the input back to the start symbol.

---

4. Assuming that lower-case characters are terminals and upper-case ones are non-terminals in a grammar, which rule prevents the grammar from being an operator grammar?

(A) S → aA
(B) S → AB
(C) S → AbB
(D) All of the other options

Answer: ✅ (C) S → AbB

Explanation:
Operator grammars do not allow adjacent non-terminals with terminals between them. Rule (C) violates this, so it’s not allowed in operator precedence grammars.

---

5. Which of the following cannot be performed by a parser?

Options:

• (A) Detection of misspelling a keyword
• (B) Detection of unbalanced parentheses in an arithmetic expression
• (C) Detection of variable re-declaration
• (D) All of the above

Answer: ✅ (C) Detection of variable re-declaration

Explanation:
This requires semantic analysis (symbol table tracking), which is not the parser’s job. A parser handles syntax only.

---

6. In operator precedence parsing, the shift and reduce operations are done based on priority between:

(A) The symbols referred by stack[top] and stack[top-1]
(B) The symbol referred by stack[top] and the current input symbol
(C) The current input symbol and the immediately next input symbol
(D) None of the above options

Answer: ✅ (B) The symbol referred by stack[top] and the current input symbol

Explanation:
Operator precedence parsing uses a precedence table to compare the operator at the top of the stack with the current input symbol to decide shift/reduce.

---

7. Consider the following grammar:
S → aABb
A → c | ε
B → d | ε
The LL(1) parsing table P is constructed for the above grammar. The production B → ε will be contained in which cell/cells of the table?

(A) P[B][d] and P[B][b] both
(B) P[B][a] only
(C) P[B][d] only
(D) P[B][b] only

Answer: ✅ (D) P[B][b] only

Explanation:
If B → ε, then FOLLOW(B) is used. From S → aABb, FOLLOW(B) = {b}, so B → ε goes in P[B][b].

---

8. Consider the following grammar:
S → aABb
A → c | ε
B → d | ε
The LL(1) parsing table P is constructed for the above grammar. The production A → ε will be contained in which cell/cells of the table?

(A) P[A][d] and P[A][b] both
(B) P[A][d] only
(C) P[A][b] only
(D) P[A][c] only

Answer: ✅ (A) P[A][d] and P[A][b] both

Explanation:
If A → ε, check FOLLOW(A). From S → aABb, FIRST(B) = {d, ε} and FOLLOW(S) = {b}. So FOLLOW(A) includes FIRST(B) – {ε} = {d} and also includes FOLLOW(S) if B → ε, so → {d, b}

---

9. Consider the following grammar G:
S → ( L ) | a
L → L , S | S
How many “Reduce” to be applied to parse the string ( a , ( a , a ) ) using the production rules of the grammar G?

(A) 15
(B) 12
(C) 9
(D) 5

Answer: ✅ (C) 9

Explanation:
The input ( a , ( a , a ) ) requires several recursive reductions due to the nested structure and commas. If traced manually using bottom-up parsing, it leads to 9 reduces.

---

10. You are to write an unambiguous grammar to generate the set of all strings over the alphabet {0, 1, +, -}. Here, ‘+’ and ‘-’ are binary infix operators. An incomplete grammar is given below for the same.
S → P | S – P
P → D
D → 0 | 1
Which production given below is most appropriate to complete the grammar written above.

(A) P → S
(B) P → P + D
(C) S → P + D
(D) None of the above options

Answer: ✅ (B) P → P + D

Explanation:
This ensures unambiguous left-associativity for +, and supports building expressions like 0 + 1 - 0 with the correct operator precedence and associativity.