Parsing Techniques

Parsing Techniques

Parsing builds parse tree from tokens using grammar rules.

Types of Parsing

1. Top-Down Parsing

Starts from start symbol, derives input string.

Approaches:

• Recursive descent
• LL parsing

LL Parser:

• Left-to-right scan
• Leftmost derivation
• Predictive parsing

LL(1) Parser:

• Uses 1 lookahead symbol
• Requires FIRST and FOLLOW sets

FIRST Set:

• Set of terminals that can start a string derived from a non-terminal

FOLLOW Set:

• Set of terminals that can follow a non-terminal

LL(1) Grammar:

• No left recursion
• No ambiguity
• No left factoring needed

2. Bottom-Up Parsing

Starts from input, reduces to start symbol.

Approaches:

• Shift-reduce parsing
• LR parsing

LR Parser:

• Left-to-right scan
• Rightmost derivation (reverse)
• Most powerful

LR Variants:

• LR(0): No lookahead
• SLR(1): Simple LR with 1 lookahead
• CLR(1): Canonical LR with 1 lookahead
• LALR(1): Look-Ahead LR with 1 lookahead

LR Parsing Actions:

• Shift: Move input symbol to stack
• Reduce: Replace handle with non-terminal
• Accept: Successful parse
• Error: Invalid input

Parsing Conflicts

Shift-Reduce Conflict

Occurs when: Parser cannot decide between shift and reduce.

Example: Ambiguous grammar

Reduce-Reduce Conflict

Occurs when: Parser cannot decide which production to reduce.

Example: Multiple productions match

GATE CS Important Points

1. LL(1) Parsing: FIRST, FOLLOW, parsing table
2. LR Parsing: LR(0), SLR(1), CLR(1), LALR(1)
3. Parsing Conflicts: Shift-reduce, reduce-reduce
4. Grammar Transformations: Remove left recursion, left factoring
5. Parse Tree Construction: Build parse tree

Practice Tips

1. FIRST/FOLLOW: Calculate for given grammar
2. LL(1) Table: Construct parsing table
3. LR Parsing: Build LR automaton
4. Resolve Conflicts: Handle shift-reduce conflicts
5. Previous Year Questions: Solve GATE parsing questions