15,264 views
24 votes
24 votes

Consider the grammar:

$$S \rightarrow (S) \mid a$$

Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be $n_1, n_2$ and $n_3$ respectively. The following relationship holds good:

  1. $n_1 < n_2 < n_3$
  2. $n_1 = n_3 < n_2$
  3. $n_1 = n_2 = n_3$
  4. $n_1 \geq n_3 \geq n_2$

2 Answers

Best answer
38 votes
38 votes

ans B

Both in SLR(1) and LALR(1), states are the LR(0) items (LALR uses LR(1) items to form the states but then merges the ones having same items and different lookaheads) while in LR(1) the states are LR(1) set of items. Number of LR(0) items can never be greater than number of LR(1) items. So, $n_1 = n_3 \leq n_2$, B choice.  If we construct the states for the grammar we can replace $\leq$ with $<$.

Reference: https://gatecse.in/lr-parsing-part-4-slr-clr-lalr-and-summary/

edited by
1 votes
1 votes
LALR(1) is formed by merging states of LR(1) ( also called CLR(1)), hence no of states in LALR(1) is less than no of states in LR(1), therefore n3 < n2. And SLR(1) and LALR(1) have same no of states, i.e ( n1 = n3).

Hence n1 = n3 < n2
Answer:

Related questions

31 votes
31 votes
2 answers
1
go_editor asked Nov 27, 2016
11,341 views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.$$\begin{array}{l|l} E\rightarrow numbe...
56 votes
56 votes
7 answers
2
37 votes
37 votes
4 answers
3
Kathleen asked Sep 22, 2014
23,298 views
The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is:ambiguousleft-recursiveright-recursivean operator-gram...