This table contains everything you need to score full marks on any FIRST & FOLLOW question.

Example Grammar 4.28

E  → T E'
E' → + T E' | ε  
T  → F T'  
T' → * F T' | ε  
F  → ( E ) | id

Example Grammar 4.29

S → c A d  
A → a b | a

Example 4.12

S → ( S ) S | ε

Example 4.22

S → i E t S | i E t S e S | a  
E → b

Exercise 4.2.1

S → S S + | S S - | a

Exercise 4.2.2(a)

S → 0 S 1 | 0 1

Exercise 4.2.2(b)

S → + S S | - S S | a

Exercise 4.2.2(c)

S → S ( S ) S | ε

Exercise 4.2.2(d)

S → S + S | S S | ( S ) | S - | a

Exercise 4.2.2(e)

S → ( L ) | a  
L → L ; S | S

Exercise 4.2.2(f)

S → a S b S | b S a S | ε

Exercise 4.2.2(g)

bexpr   → bexpr or bterm | bterm  
bterm   → bterm and bfactor | bfactor  
bfactor → not bfactor | ( bexpr ) | true | false

Exercise 4.4.5

S → a S a | a a

These left-factored grammars are now suitable for predictive parsing (LL(1)).

Example 4.22

Original:

S → i E t S | i E t S e S | a
E → b

Left Factored:

S → i E t S S' | a  
S' → e S | ε  
E → b

Exercise 4.3.1

Original:

rexpr → rexpr + rterm | rterm  
rterm → rterm rfactor | rfactor  
rfactor → rfactor * | rprimary  
rprimary → a | b

Left Factored:

rexpr → rterm rexpr'  
rexpr' → + rterm rexpr' | ε  

rterm → rfactor rterm'  
rterm' → rfactor rterm' | ε  

rfactor → rprimary rfactor'  
rfactor' → * rfactor' | ε  

rprimary → a | b

Exercise 4.2.1

Original:

S → S S + | S S * | a

Left Factored:

S → S S S' | a  
S' → + | *

Exercise 4.2.2(a)

Original:

S → 0 S 1 | 0 1

Left Factored:

S → 0 S'  
S' → S 1 | 1

Exercise 4.2.2(b)

Original:

S → + S S | - S S | a

Already Factored — no common prefix ✅

Exercise 4.2.2(c)

Original:

S → S ( S ) S | ε

Left Factored:

S → S S' | ε  
S' → ( S ) S

Exercise 4.2.2(d)

Original:

S → S + S | S S | ( S ) | S * | a

Left Factored:

S → S S' | ( S ) | a  
S' → + S | S | * | ε

Exercise 4.2.2(e)

Original:

S → ( L ) | a  
L → L ; S | S

Left Factored:

S → ( L ) | a  
L → S L'  
L' → ; S L' | ε

Exercise 4.2.2(g)

Boolean Expressions

Original:

bexpr → bexpr or bterm | bterm  
bterm → bterm and bfactor | bfactor  
bfactor → not bfactor | ( bexpr ) | true | false

Left Factored:

bexpr → bterm bexpr'  
bexpr' → or bterm bexpr' | ε  

bterm → bfactor bterm'  
bterm' → and bfactor bterm' | ε  

bfactor → not bfactor | ( bexpr ) | true | false

Parse Table for Expression Grammar (Example 4.32)

E  → TE'
E' → +TE' | ε
T  → FT'
T' → *FT' | ε
F  → id | (E)

Parse Table for Dangling Else Grammar (Example 4.33)

S  → iEtSS' | a  
S' → eS | ε  
E  → b

Note: Conflict in S' → Grammar is ambiguous and not LL(1).

Parse Table for Statement Grammar (Exercise 4.4.12)

stmt      → if e then stmt stmtTail  
          | while e do stmt  
          | begin list end  
          | s  
stmtTail  → else stmt | ε  
list      → stmt listTail  
listTail  → ; list | ε

This parse table is to be built using Algorithm 4.31 (Predictive Parsing Table construction). Guidelines:

• Prefer stmtTail → else stmt when else is in input.
• Use synchronizing symbols for error handling.

Canonical LR Parsing Table (Example 4.57)

S → CC  
C → cC | d

Productions:

• 1. S → CC
• 2. C → cC
• 3. C → d

Let's take this grammar:

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | id

Step 1: Check for Left Recursion

No rule has a non-terminal on the leftmost side of RHS (like E → E α)

✅ No Left Recursion

Step 2: Check for Left Factoring

Each non-terminal has distinct starts:

• E → T E' ✔️
• E' → + T E' | ε → starts with + or empty ✔️
• T → F T' ✔️
• T' → * F T' | ε → starts with * or empty ✔️
• F → ( E ) | id → starts with ( or id ✔️

✅ No Left Factoring needed

Step 3: FIRST Sets

Step 4: FOLLOW Sets

Step 5: LL(1) Conditions

E' → + T E' | ε

• FIRST(+ T E') = { + }
• FIRST(ε) = { ε }
• FOLLOW(E') = { $, ) }
• → FIRST(+ T E') ∩ FOLLOW(E') = ∅
• ✅ OK

T' → * F T' | ε

• FIRST(* F T') = { * }
• FIRST(ε) = { ε }
• FOLLOW(T') = { +, $, ) }
• → FIRST(* F T') ∩ FOLLOW(T') = ∅
• ✅ OK

FINAL VERDICT:

✅ This grammar is LL(1).

• All rules follow the LL(1) conditions
• No left recursion
• No FIRST/FIRST or FIRST/FOLLOW conflict

This is the standard expression grammar used in compilers, and it works perfectly with LL(1) parsers.

Let's take this grammar:

S → i E t S | i E t S e S | a
E → b

This is a classic "dangling else" grammar.

Step 1: Left Recursion

No rule like S → S α

✅ No Left Recursion

Step 2: Left Factoring

Check:

S → i E t S  
S → i E t S e S

Both start with i E t S → Needs Left Factoring

❌ Not Left Factored

Left Factored Version:

S → i E t S S'
S'→ e S | ε
E → b

Now it's clean for LL(1) checking.

Step 3: FIRST Sets

Step 4: FOLLOW Sets

Let's assume start symbol = S

Step 5: Check LL(1) Conditions

S → iEtSS' | a

• FIRST(iEtSS') = { i }
• FIRST(a) = { a }
• ✅ FIRST sets are disjoint → OK

S' → eS | ε

• FIRST(eS) = { e }
• FIRST(ε) = { ε }
• FOLLOW(S') = { $, e }
• → Check: FIRST(eS) ∩ FOLLOW(S') = { e }
• ❌ Conflict because e in both FIRST and FOLLOW

Final Verdict:

This grammar (even after factoring) is not LL(1) due to:

• FIRST/FOLLOW conflict in S'
• Parser won't know whether to take eS or ε on lookahead e

Why?

This is the famous "dangling else problem" – it's inherently ambiguous and hard to parse with only 1 lookahead.

❌ Final Answer:

This grammar is not LL(1) even after factoring.

Let's take this grammar:

A → a B | b C  
B → d  
C → d

Step 1: Left Recursion

No rule like A → A α

✅ No Left Recursion

Step 2: Left Factoring

Check A → a B | b C

→ They start with different terminals: a, b

✅ No Left Factoring Needed

Step 3: FIRST Sets

Step 4: FOLLOW Sets

Assuming A is the start symbol, so $ ∈ FOLLOW(A).

Step 5: LL(1) Conditions

A → aB | bC

• FIRST(aB) = { a }
• FIRST(bC) = { b }
• ✅ FIRST sets disjoint → OK

B → d and C → d

• Both have same FIRST (d), but they are not in the same rule set
• B and C are called separately, only one used depending on A
• ✅ No conflict, since B and C are not alternative rules for the same non-terminal

Final Verdict:

• No Left Recursion
• No Left Factoring Needed
• FIRST/FIRST disjoint
• No FIRST/FOLLOW conflict (no ε involved)

✅ Grammar is LL(1) – safe for table-driven parsing with one lookahead.