Compiler Design

Answer: (iii) Canonical LR

Explanation

Parsers can be ordered by the size of the grammar class they can handle (their power):

• Operator-precedence parsing: only works on operator grammars (no $\epsilon$, no two adjacent nonterminals) — the least general.
• SLR(1): uses the LR(0) items but decides reduce actions using the broad $\mathrm{FOLLOW}$ set of the left-hand nonterminal, ignoring the specific context of each item → weaker.
• LALR(1): merges LR(1) items that share the same core (same item, different lookahead). More powerful than SLR(1).
• Canonical LR / LR(1): keeps every lookahead separate, producing the most states and therefore accepting the largest set of grammars among the given options.

Hence the most powerful parser is:

$$\boxed{\text{(iii) Canonical LR (LR(1))}}$$

Order of power (weakest → strongest):
Operator-precedence < SLR(1) < LALR(1) < Canonical LR(1)

Answer: (iii) Leftmost derivation

Explanation

A top-down parser starts from the start symbol (root) and tries to derive the input string by expanding nonterminals in leftmost order — i.e. it always expands the leftmost nonterminal first.

• Leftmost derivation: each step replaces the leftmost nonterminal — this is exactly what a top-down (recursive-descent / predictive / LL) parser constructs.
• Rightmost derivation: each step replaces the rightmost nonterminal — not what a top-down parser does.
• Rightmost derivation in reverse / handle pruning: that is the basis of bottom-up parsing (LR parsers), not top-down.

Therefore a top-down parser generates a

$$\boxed{\text{(iii) Leftmost derivation}}$$

Answer: (i) Bottom-up parsing

Explanation

• A handle is a substring of a (right) sentential form that matches the right-hand side of a production, and whose reduction brings us one step closer to the start symbol when reduced.
• Handle pruning is the process of repeatedly finding the handles (finding the rightmost such substring during a rightmost reduction) and reducing them — from the input string up to the start symbol.
• This is precisely how a bottom-up parser (shift-reduce / LR parser) works: it repeatedly reduces handles until the entire input has been reduced to the start symbol.

Top-down parsing, predictive parsing, and recursive-descent parsing all work top-down (expanding the root) and do not prune handles.

$$\boxed{\text{(i) Bottom up parsing}}$$

Answer: (i) Not occurring of backtracking

Explanation

• Left factoring is a grammar transformation that factors out the common prefix of two or more production alternatives.
• It is used to remove uncertainty about which alternative to choose when a common prefix could lead to two different nonterminal, which otherwise forces the parser to backtrack while building a predictive (LL) parser.

How it works:
$$A \to \alpha\beta_1 \mid \alpha\beta_2 \;\Rightarrow\; A \to \alpha A', \quad A' \to \beta_1 \mid \beta_2$$

In an LL(1) (predictive top-down) parser the decision is made by looking at the first token; factoring out a common prefix ensures the choice is deterministic, so backtracking never occurs.

Hence left factoring guarantees:
$$\boxed{\text{(i) Not occurring of backtracking}}$$

Answer: (i) $A \to aA',\ A' \to S_1 \mid S_2$

Step 1 — left factoring

Given grammar:
$$A \to aS_1 \mid aS_2$$

The two alternatives share the common prefix a. We factor it out into a new nonterminal $A'$:

$$A \to aA'$$

$$A' \to S_1 \mid S_2$$

This is the standard left-factored (CFG) form that removes backtracking uncertainty, because after reading a the parser chooses between $S_1$ and $S_2$ by looking at the next input, not by backtracking.

Hence the correct answer is:

$$\boxed{\text{(i)}\ A \to aA',\ A' \to S_1 \mid S_2}$$

Answer: (i) The LR(1) parser for G has S–R conflicts

Explanation — LALR vs LR relationship

• LALR(1) parsers are built by merging the states of a canonical LR(1) parser that share the same core (same items, different lookaheads).
• Merging states can create a reduce–reduce (R–R) conflict (two different reduce actions that were separated by lookahead now share a cell).
• However, state-merging cannot create a new shift–reduce (S–R) conflict. Intuitively, a shift action exists on a terminal $t$ in a state only if $t$ is in that state's core in the LR(1) automaton too. So if the LALR(1) table has an S–R conflict, the same conflict must have already been present in the LR(1) table.

Therefore the correct statement is the one in option (i) — the LR(1) parser for $G$ has S–R conflicts (with LAR(1) in the paper being a typo for LR(1)).

$$\boxed{\text{(i) The LR(1) parser for G has S.R conflicts}}$$

Advantages of LALR(1) parsing over SLR(1) and canonical LR (CLR)

Method	Number of states	Power	Slots management
SLR(1)	fewest	weakest (uses FOLLOW)	smallest
LALR(1)	same as SLR	between SLR and CLR	larger
Canonical LR (CLR/CLR(1))	the most	strongest	largest

Advantages of LALR over SLR:

1. LALR(1) accepts a larger grammar class than SLR(1): SLR reduces using $\mathrm{FOLLOW}$, which may cause spurious reduce–reduce and shift–reduce conflicts, because it ignores which attribute context produced the follow. LALR uses the precise lookahead symbols from the LR(1) items (merged by core), so fewer conflicts arise. Many grammars that are not SLR are LALR.
2. It is still simple: LALR(1) lookaheads are "compatible" — no shift–reduce conflict is introduced by merging states.

Advantages of LALR over canonical LR (CLR):

1. Fewer states — In practice LALR(1) has roughly the same number of states as SLR(1), whereas a canonical LR(1) parser can have a very large state space (up to exponential in the grammar size). This makes LALR tables much more compact and memory-efficient.
2. Faster table construction — merging reduces the number of states to process.
3. It is the method of choice in practice: LALR(1) is used in tools like YACC / Bison because it is strong enough for almost all practical grammars yet keeps the table small — the "sweet spot" between SLR (too weak) and CLR (too many states).

Trade-off: CLR may parse a slightly larger class, but its cost (huge state) is not justified in most cases. So LALR(1) is the best power/size ratio.

$$\boxed{\text{LALR(1) : smaller (SLR-like) state count, near-CLR power → most practical; wins for memory and speed.}}$$

Algorithm to compute FIRST and FOLLOW

Notation: $X$ = nonterminal/terminal; $\alpha,\beta$ = strings of grammar symbols; $\epsilon$ = empty string; $ = end marker.

FIRST

Compute $FIRST(X_1\dots X_n))$ = set of terminals that can start any string derivable from $X_1X_2\dots X_n$ (plus $\epsilon$ if the whole can derive $\epsilon$).

Rules (for individual symbol):

1. If $X$ is a terminal, then $\mathrm{FIRST}(X) = \{X\}$.
2. If $X$ is $\epsilon$ production i.e. $X\to\epsilon$, add $\epsilon$ to $\mathrm{FIRST}(X)$.
3. If $X$ is a nonterminal and $X\to Y_1Y_2\dots Y_k$, then:
   • Put $\mathrm{FIRST}(Y_1)$ \textbackslash}{\epsilon} into $\mathrm{FIRST}(X)$.
   • If $Y_1$ derives $\epsilon$, also put $\mathrm{FIRST}(Y_2)\setminus\{\epsilon\}$, and so on.
   • If $Y_1..Y_k$ all can derive $\epsilon$, then put $\epsilon$ into $\mathrm{FIRST}(X)$.
   • Order: For each production, apply until no more additions; repeat the whole loop until no change.

For a string $\alpha = X_1X_2\dots X_n$ :
$\mathrm{FIRST}(\alpha) = \mathrm{FIRST}(X_1) \setminus \{\epsilon\}$; if $\epsilon\in \mathrm{FIRST}(X_1)$, add $\mathrm{FIRST}(X_2)\setminus\{\epsilon\}$, etc.; if all $X_i$ derive $\epsilon$, add $\epsilon$ to $\mathrm{FIRST}(\alpha)$.

2. Compute FOLLOW(X) for every nonterminal X

Rule to find the set of terminals that can appear immediately to the right of $X$ in some sentential form.

1. If $X$ is the start symbol, place `$` in$\mathrm{FOLLOW}(X)$.
2. For a production $A\to\alpha B\beta$: everything in $\mathrm{FIRST}(\beta)$ except $\epsilon$ goes into $\mathrm{FOLLOW}(B)$.
3. If there is a production $A\to\alpha B$ or $A\to\alpha B\beta$ where $\beta \rightsquigarrow \epsilon$ (i.e. $\beta$ is nullable), then everything in $\mathrm{FOLLOW}(A)$ gets added to $\mathrm{FOLLOW}(B)$.
4. Repeat these steps until no further additions occur.

(Terminals/symbol ) that are not nonterminals have no FOLLOW.)

These First/Follow results are then used to build the predictive (LL(1)) parsing table: for $A\to\alpha$, put the production into M[A][a] for each a in $\mathrm{FIRST}(\alpha)$; if $\alpha$ nullable, put it into M[A][b] for each b in $\mathrm{FOLLOW}(A)$.

What is a shift–reduce conflict?

A shift–reduce conflict (S–R conflict) is a parsing-table conflict in an LR-family bottom-up parser: in one state (looking at one input symbol), the parser has both a valid shift action and a valid reduce action.

Why it happens: When constructing the parsing table, a single cell $M[\text{state}, \text{terminal}]$ ends up with two entries: one saying "shift a (push onto the stack / go to next state)" and the other saying "reduce using production $A\to\alpha$". Since the parser cannot decide deterministically, the grammar is not LR with the given method (and the table entry is ambiguous).

Example grammar with S–R conflict: classic ambiguous grammar
$$E\to E+E \mid E*E \mid (E) \mid \text{id}$$
produces S–R conflict in LR(0)/SLR(1)/LALR(1) because, e.g. after parsing E + E . with input + or *, the parser doesn't know whether to shift the operator (deferring) or reduce E+E.

Remedies:

• Add precedence/associativity (%left, %right, %prec in YACC) — e.g. make * bind tighter than +.
• Refactor the grammar to an unambiguous form (e.g. with separate term/factor levels).
• Use a more powerful parsing method (canonical LR can resolve conflicts that SLR can't) — but a true ambiguity cannot be removed by switching methods.

Reduction internal form: in LR table notation, a cell with both s and r actions is marked as a conflict, and the grammar is rejected by the parser generator (unless a rule like "shift wins on S–R conflict" is chosen YACC's default: prefer shift).

$$\boxed{\text{S–R conflict = a parsing table state where shift and reduce are both valid → grammar not LR for that method.}}$$

First and Follow for the given grammar

Grammar:
$$\begin{array}{rcl} S &\to& aBDh\\ B &\to& cC\\ C &\to& bC \mid \epsilon\\ D &\to& EF\\ E &\to& g \mid \epsilon\\ F &\to& f \mid \epsilon \end{array}$$

Step 1 — FIRST sets

Compute allowed terminals that begin derivations (plus $\epsilon$ if nullable).

• $\mathrm{FIRST}(a) = \{a\},\ \mathrm{FIRST}(b)=\{b\},\ \mathrm{FIRST}(c)=\{c\},\ \mathrm{FIRST}(g)=\{g\},\ \mathrm{FIRST}(f)=\{f\},\ \mathrm{FIRST}(h)=\{h\}$
• $\mathrm{FIRST}(C) = \{b, \epsilon\}$ (from $C\to bC$ and $C\to\epsilon$)
• $\mathrm{FIRST}(E) = \{g, \epsilon\}$
• $\mathrm{FIRST}(F) = \{f, \epsilon\}$
• $\mathrm{FIRST}(D)$: $D\to EF$. FIRST(E)=$\{g,\epsilon\}$ → take $g$; since E nullable, take FIRST(F)=$\{f,\epsilon\}$ → $f$; since both nullable, include $\epsilon$.
  $$\mathrm{FIRST}(D) = \{g, f, \epsilon\}$$
• $\mathrm{FIRST}(B) = \{c\}$ (from $B\to cC$). (B is not nullable since $c$ is a terminal.)
• $\mathrm{FIRST}(S)$: $S\to aBDh$ → starts with terminal a.
  $$\mathrm{FIRST}(S) = \{a\}$$

Step 2 — FOLLOW sets

The follow of a nonterminal $X$ is the set of terminals that can appear immediately to the right of $X$ in some sentential form.

• $FOLLOW(S)$: S is the start symbol → ${$}$.
  $$\mathrm{FOLLOW}(S) = \{\$\}$$

• $FOLLOW(B)$: from $S\to a\,B\,D\,h$, after $B$ comes $D$, so we add $\mathrm{FIRST}(D)\setminus\{\epsilon\} = \{g,f\}$. Also $D$ is nullable, so we add $\mathrm{FOLLOW}(S) = {$}$.
  $$\mathrm{FOLLOW}(B) = \{g,\ f,\ \$\}$$

• $FOLLOW(C)$: from $B\to c\,C$ (C at the end), so $\mathrm{FOLLOW}(C) = \mathrm{FOLLOW}(B)$.
  $$\mathrm{FOLLOW}(C) = \{g,\ f,\ \$\}$$

• $FOLLOW(D)$: from $S\to aBD\,h$, after $D$ comes terminal h.
  $$\mathrm{FOLLOW}(D) = \{h\}$$

• $FOLLOW(E)$: from $D\to E\,F$, after $E$ comes $F$, so add $\mathrm{FIRST}(F)\setminus\{\epsilon\} = \{f\}$. Since $F$ is nullable, also add $\mathrm{FOLLOW}(D)=\{h\}$.
  $$\mathrm{FOLLOW}(E) = \{f,\ h\}$$

• $FOLLOW(F)$: from $D\to EF$ (F at the end), so $\mathrm{FOLLOW}(F) = \mathrm{FOLLOW}(D)$.
  $$\mathrm{FOLLOW}(F) = \{h\}$$

Final answer:
$${\small \mathrm{FIRST}(S)=\{a\},\quad \mathrm{FIRST}(B)=\{c\},\quad \mathrm{FIRST}(C)=\{b,\epsilon\},\quad \mathrm{FIRST}(D)=\{g,f,\epsilon\},\quad \mathrm{FIRST}(E)=\{g,\epsilon\},\quad \mathrm{FIRST}(F)=\{f,\epsilon\}}$$
$${\small \mathrm{FOLLOW}(S)=\{\$\},\quad\mathrm{FOLLOW}(B)=\{g,f,\$\},\quad\mathrm{FOLLOW}(C)=\{g,f,\$\},\quad\mathrm{FOLLOW}(D)=\{h\},\quad\mathrm{FOLLOW}(E)=\{f,h\},\quad\mathrm{FOLLOW}(F)=\{h\}}$$

Predictive (LL(1)) parsing table

Grammar:
$$S \to AaAb \mid BbBa\\ A \to \epsilon\\ B \to \epsilon$$

Step 1 — FIRST and FOLLOW

$\mathrm{FIRST}(A) = \{\epsilon\}$, $\mathrm{FIRST}(B) = \{\epsilon\}$.

For $S\to AAAb$ : because $A\to\epsilon$, the first of the right-hand string is a. For $S\to BbBa$: the first is b. Hence:
$$\mathrm{FIRST}(S) = \{a, b\}$$

FOLLOW:

• $S$ is start → $\mathrm{FOLLOW}(S) = {$ }$.
• From $S\to AaAb$: the first $A$ is followed by a, the second $A$ by b.
  $$\mathrm{FOLLOW}(A) = \{a, b\}$$
• From $S\to BbBa$: first $B$ followed by b, second $B$ by a.
  $$\mathrm{FOLLOW}(B) = \{a, b\}$$

Step 2 — build table $M[X][\text{terminal}]$

For each production $X\to\alpha$, put $X\to\alpha$ into $M[X][t]$ for every $t\in \mathrm{FIRST}(\alpha)$; if $\alpha \Rightarrow \epsilon$, also put it into $M[X][t]$ for every $t\in\mathrm{FOLLOW}(X)$.

• For $S \to AaAb$: $\mathrm{FIRST}(AaAb)=\{a\}$ → entry $M[S][a] = S\to AaAb$.
• For $S \to BbBa$: $\mathrm{FIRST}=\{b\}$ → $M[S][b] = S\to BbBa$.
• For $A\to\epsilon$: place under $\mathrm{FOLLOW}(A)=\{a,b\}$ → $M[A][a]=A\to\epsilon$, $M[A][b]=A\to\epsilon$.
• For $B\to\epsilon$: $\mathrm{FOLLOW}(B)=\{a,b\}$ → $M[B][a]=B\to\epsilon$, $M[B][b]=B\to\epsilon$.

Predictive parsing table (blank cells = error, no production):

Nonterminal	a	b	$
$S$	$S\to AaAb$	$S\to BbBa$	—
$A$	$A\to\epsilon$	$A\to\epsilon$	—
$B$	$B\to\epsilon$	$B\to\epsilon$	—

Verification: Every cell has at most one entry, so the grammar is LL(1) — no conflicts. This is the classic example of an LL(1) grammar with $A\to\epsilon,\ B\to\epsilon$ that resolves the choice using lookahead.

Handle; reduction of id + id * id with grammar $E\to E+E \mid E*E \mid \text{id}$

What is a handle?

A handle of a (right) sentential form is a substring that matches the right-hand side of some production, and whose reduction to the left-hand-side nonterminal is a step in a rightmost (reverse) derivation — that is, the rightmost handle that, when reduced, produces a valid step toward the start symbol.

In shift–reduce parsing we repeatedly prune handles: shift symbols onto the stack until the top stack symbols match a production RHS, then reduce (replace the handle by its nonterminal).

Find the handles for id + id * id

Grammar: $E\to E+E \mid E*E \mid id$. The (unique, rightmost) reduction sequence:

Stack (top shown last)	Input	Action	Handle reduced
id	+ id * id	shift id	—
E	+ id * id	reduce id → E	handle id
E +	id * id	shift +	—
E + id	* id	shift id	—
E + E	* id	reduce	handle id (2nd)
E + E *	id	shift *	—
E + E * id	(empty)	shift	—
E + E * E		reduce	handle id (3rd)
E + E		reduce E*E → E	handle E*E
E		reduce E+E → E	handle E+E

Handles (in reduction order), with the actual substrings:

• id (first id on the left)
• id (the middle id)
• id (the id after *)
• E * E (the redex E*E → E)
• E + E (the redex E+E → E)

Written against the original string, the reduction is a reverse of the rightmost derivation:
$$id + id * id \;\xrightarrow{\text{reduce id}} E + id*id \xrightarrow{\text{reduce id}} E+E*id \xrightarrow{} E+E*E \xrightarrow{E+E} \xrightarrow{E}$$
The seeds/handles reduced, going left-to-right on the string: the *ids**, then EE, then E + E`.

Ambiguous grammar; ambiguity removal; is $A \to AA \mid (A) \mid a$ ambiguous?

1. When is a grammar called ambiguous?

A grammar is called ambiguous when there exists at least one string in its language that has two or more distinct parse trees (equivalently, two different leftmost or two different rightmost derivations).

2. Techniques to remove ambiguity

• Grammar rewriting (precedence/associativity): restructure the grammar with separate levels, e.g. expr → expr + term | term, term → term * factor | factor, so that operators bind with the intended precedence and associativity.
• Parser-tool directives: in YACC/Bison, use precedence declarations %left / %right / %nonassoc to resolve conflicts (e.g. %left '+', %left '*').
• Explicit structure: for left-associative operators use left recursion; for the dangling-else problem use separate matched/unmatched statement nonterminals.
• Caveat: removing ambiguity from an arbitrary grammar is undecidable in general, but for practical expression grammars these techniques work.

3. Justify whether $A \to AA \mid (A) \mid a$ is ambiguous

Yes — this grammar is ambiguous.

The string aaa has two distinct parse trees:

• Tree 1 (grouping as a (a a)): root A → A A, left A → a, right A → A A with children a a:

       A
      / \
     a   A
        / \
       a   a

• Tree 2 (grouping as (a a) a): root A → A A, left A → A A with children a a, right A → a:

       A
      / \
     A   a
   / \
  a   a

Both trees derive the same string aaa with different structure ⇒ the grammar is ambiguous. The root cause is the production $A \to AA$ — two adjacent occurrences of the same nonterminal admit two groupings of any consecutive run of a's.

A fix for this grammar: make the concatenation left- or right-associative explicitly, e.g. $A \to A\,\mathbf{star}$, or add a priority marker — but more importantly, grammar $A\to AA\mid a\mid (A)$ is inherently ambiguous, so a parser generator such as YACC would report a conflict for it. In practice prepend associativity info (%left) or rewrite to an unambiguous grammar such as $A \to A\,\text{cat} \mid (A) \mid a$ with cat a real operator.

$$\boxed{\text{A} \to A A \mid (A) \mid a\ \text{IS ambiguous — the string } aaa \text{ has two parse trees.}}$$

Operator-Precedence Parser

1. What it is

An operator-precedence (OP) parser is a bottom-up shift–reduce parser whose shift/reduce decision is based only on a precedence relation table between terminal symbols (operators) — not on a full LR state machine.

2. Operator grammar preconditions

The grammar must be an operator grammar:

• no $\epsilon$-production,
• no two adjacent nonterminals on any right-hand side.

3. Precedence relations

Between terminals a and b:

• $a \lessdot b$ — a has lower precedence than b (→ shift b)
• $a \doteq b$ — equal precedence (→ shift)
• $a \gtrdot b$ — a has higher precedence than b (→ reduce)

Computed from the grammar using the FIRST/LAST terminal sets:

• if $\alpha\, a\, B\, \beta$ and $b\in \mathrm{FIRST}(B)$ then $a \lessdot b$;
• if $A\to \alpha\, a b\, \beta$ then $a \doteq b$;
• if $A\to \alpha\, B\, b\,\beta$ and $a\in \mathrm{LAST}(B)$ then $a \gtrdot b$.

This yields the operator-precedence matrix $M[t_1][t_2]$ for all terminal pairs.

4. Algorithm (stack with $` at bottom; input ends with `$):

1. Compare precedence of the input symbol with the relevant top-of-stack terminal.
2. If top $\lessdot$ next, or top $\doteq$ next → shift the next token.
3. If top $\gtrdot$ next → a handle boundary has been found: scan back until the first preceding $\lessdot$ relation; the substring between them is the handle → reduce it to its nonterminal. No state/lookahead table needed.
4. Accept when the stack holds exactly the start symbol with no input left.

5. Example — id + id * id with precedence * > +

stack: $ id + id * id
shift id, shift +, shift id
when `*` (input) and top `id` reduce id→E... 
then top `*` vs input `+`: since `*` ⋗ `+`, reduce E*E before E+ 
→ matches the expected "multiply before add" behaviour.

6. Advantages & disadvantages

Advantages:

• very fast (simple matrix lookup), small table,
• easy to implement (no GOTO states).

Disadvantages:

• works only for operator grammars (no adjacent nonterminals, no $\epsilon$),
• handle detection is purely local — it ignores surrounding context, so many real languages need LR/LALR instead,
• usually used in small/expression-oriented compilers or inside calculator-style evaluators.

Example precedence table (* binds tighter than +):

op	+	*
+	$\doteq, \gtrdot$	$\lessdot$
*	$\gtrdot$	$\gtrdot$

Rule: shift on $\lessdot$ / $\doteq$, reduce on $\gtrdot$ — which reproduces standard arithmetic precedence.

SLR parse for the grammar $E\to E+T\mid T$, $T\to T*F\mid F$, $F\to \mathbf{id}$

(The paper spells the token td; we treat it as the identifier token id.)

Augment with $E'\to E$.

Productions numbering:

1. $E\to E+T$
2. $E\to T$
3. $T\to T*F$
4. $T\to F$
5. $F\to\mathbf{id}$

LR(0) canonical collection (states $I_0$–$I_8$):

• $I_0$: $E'\to\cdot E,\ E\to\cdot E+T,\ E\to\cdot T,\ T\to\cdot T*F,\ T\to\cdot F,\ F\to\cdot\mathbf{id}$
• $I_1 = goto(I_0,E)$: $E'\to E\cdot$, $E\to E\cdot+T$
• $I_2 = goto(I_0,T)$: $E\to T\cdot$, $T\to T\cdot*F$
• $I_3 = goto(I_0,F)$: $T\to F\cdot$
• $I_4 = goto(I_0,id)$: $F\to \mathbf{id}\cdot$
• $I_5 = goto(I_1,+)$: $E\to E+\cdot T$, $T\to\cdot T*F$, $T\to\cdot F$, $F\to\cdot\mathbf{id}$
• $I_6 = goto(I_2,*)$: $T\to T*\cdot F$, $F\to\cdot\mathbf{id}$
• $I_7 = goto(I_5,T)$: $E\to E+T\cdot$, $T\to T\cdot*F$
• $I_8 = goto(I_6,F)$: $T\to T*F\cdot$

GOTO transitions: $0\xrightarrow{E}1,\ 0\xrightarrow{T}2,\ 0\xrightarrow{F}3,\ 0\xrightarrow{id}4$;
$1\xrightarrow{+}5$; $2\xrightarrow{*}6$; $5\xrightarrow{T}7,\ 5\xrightarrow{F}3,\ 5\xrightarrow{id}4$; $6\xrightarrow{F}8,\ 6\xrightarrow{id}4$; $7\xrightarrow{*}6$.

(This is the state-transition diagram; every state is a node and every label above is an edge.)

FOLLOW sets:

• $\mathrm{FOLLOW}(E)={+, $}$(start) ∪ `+` from$E\to E+T$.
• $\mathrm{FOLLOW}(T)={+,,$}$ (E→E+T ⇒ FOLLOW(E), T→TF ⇒ *).
• $\mathrm{FOLLOW}(F)={+,*,$}$.

SLR parsing table (ACTION + GOTO):

State	id	+	*	$	E	T	F
0	s4				1	2	3
1		s5		acc
2		r2	s6	r2
3		r4	r4	r4
4		r5	r5	r5
5	s4					7	3
6	s4						8
7		r1	s6	r1
8		r3	r3	r3

• s n = shift and go to state n; r k = reduce by production $k$ (list above); acc = accept.
• Uses FOLLOW: r4/r5 in states 3/4 for +, *, $ (in FOLLOW(T)/FOLLOW(F)) etc.

No cell has two actions → the grammar is SLR(1) (a conflict-free table), and id + id * id is accepted.

LR(1) sets of items for $S\to CC$, $C\to cC\mid d$

Augmented grammar: $S'\to S$.

Items are written $[A\to\alpha\cdot\beta,\ a]$ where a is the lookahead terminal.

Closure hint: from $[S\to \cdot CC,\ $]$, the symbol after the dot is$C$and the lookahead context of$C\to\cdots$is$\mathrm{FIRST}(C$)={c,d}$, so inner$C$-items receive lookaheads${c,d}$.

Canonical LR(1) collection:

• $I_0$: $[S'\to\cdot S,$],\ [S\to\cdot CC,$],\ [C\to\cdot cC,\ c/d],\ [C\to\cdot d,\ c/d]$
• $I_1$ = goto$(I_0,S)$: $[S'\to S\cdot,$]$
• $I_2$ = goto$(I_0,C)$: $[S\to C\cdot C,$],\ [C\to\cdot cC,$],\ [C\to\cdot d,$]$
• $I_3$ = goto$(I_0,c)$: $[C\to c\cdot C,\ c/d],\ [C\to\cdot cC,\ c/d],\ [C\to\cdot d,\ c/d]$
• $I_4$ = goto$(I_0,d)$: $[C\to d\cdot,\ c/d]$
• $I_5$ = goto$(I_2,C)$: $[S\to CC\cdot,$]$
• $I_6$ = goto$(I_2,c)$: $[C\to c\cdot C,$],\ [C\to\cdot cC,$],\ [C\to\cdot d,$]$
• $I_7$ = goto$(I_2,d)$: $[C\to d\cdot,$]$
• $I_8$ = goto$(I_3,C)$: $[C\to cC\cdot,\ c/d]$
• $I_9$ = goto$(I_6,C)$: $[C\to cC\cdot,$]$

GOTO function:

• goto$(I_0,S)$= $I_1$; goto$(I_0,C)$=$I_2$; goto$(I_0,c)$=$I_3$; goto$(I_0,d)$=$I_4$
• goto$(I_2,C)$=$I_5$; goto$(I_2,c)$=$I_6$; goto$(I_2,d)$=$I_7$
• goto$(I_3,C)$=$I_8$; goto$(I_3,c)$=$I_3$; goto$(I_3,d)$=$I_4$
• goto$(I_6,C)$=$I_9$; goto$(I_6,c)$=$I_6$; goto$(I_6,d)$=$I_7$

So the canonical LR(1) machine has 10 states ($I_0$–$I_9$).

Reduce actions: $I_4$: $C\to d$ on $\{c,d\}$; $I_7$: $C\to d$ on $$$;$I_8$:$C\to cC$on${c,d}$;$I_9$:$C\to cC$on `$; $I_5$: $S\to CC$ on $`;$I_1$: accept on `$`.

Bonus — LALR(1): merging states with equal cores ($I_4\cup I_7$, $I_3\cup I_6$, $I_8\cup I_9$) gives the 7-state LALR(1) automaton, free of conflicts for this grammar.