Consider the following grammar S → aAb | aBc | bAd | bBe A→ n B→ n Assume K…
Consider the following grammar
S → aAb | aBc | bAd | bBe
A→ n
B→ n
Assume K represents the number of rows in LL(1) table in L in SLR(1) and M in LR(1) respectively. Which of the following is correct relation for the above grammar
Answer: B. K < L < M — Answer: K < L < M Explanation: LL(1) table rows correspond to nonterminals. The grammar has nonterminals S, A, B, so K = 3. SLR(1) uses the LR(0) canonical…
- A.
K = L = M
- B.
K < L < M
- C.
K < L = M
- D.
K = L < M
Attempted by 65 students.
Show answer & explanation
Correct answer: B
Answer: K < L < M
Explanation:
LL(1) table rows correspond to nonterminals. The grammar has nonterminals S, A, B, so K = 3.
SLR(1) uses the LR(0) canonical collection of states; building that collection for this grammar yields 13 states, so L = 13. (SLR reductions are based on FOLLOW sets but the states are LR(0) items grouped without lookahead.)
CLR(1)/LR(1) uses lookahead in items and can split LR(0) states into multiple LR(1) states. For this grammar the canonical LR(1) collection has 14 states, so M = 14.
Since 3 = K < L = 13 < M = 14, the correct relation is K < L < M.
Remarks: The solution states the concrete counts and briefly explains why LR(1) has at least as many states as SLR(1) and may have more due to lookahead distinctions.