Parsing and it’s classification in Compiler Design- Top down parsing/bottom up parsing/Crecursive

Parsing and it’s classification in Compiler Design- Top down parsing/bottom up parsing/Crecursive

https://www.gyanodhan.com/video/7B2.%20GATE%20CSEIT/Compiler%20Design/272.%20Parsing%20and%20it%27s%20classification%20in%20Compiler%20Design-%20Top%20down%20parsing%2C%20bottom%20up%20parsing%2Crecursive%2CLR.mp4

Parsing and Its Classification in Compiler Design

 What is Parsing?

Parsing is the process of analyzing a sequence of tokens (from lexical analysis) to check if they follow the syntax rules of a grammar. It helps in syntax analysis and is a crucial part of a compiler.

 Classification of Parsing

Parsing is broadly classified into two types:
Top-Down Parsing
Bottom-Up Parsing

 Top-Down Parsing

In top-down parsing, the parser starts from the start symbol (S) and tries to derive the input string step by step by applying production rules.

Types of Top-Down Parsing:

• Recursive Descent Parsing (Uses recursive functions)
• Predictive Parsing (Uses a parsing table, LL(1) Parsing)

 Recursive Descent Parsing

• Uses recursive functions for each non-terminal.
• Backtracking may be required (which is inefficient).

Example:

For input id + id, the parser starts from E and applies rules step by step.

 Predictive Parsing (LL(1) Parsing)

• No backtracking required.
• Uses a parsing table to decide the next step.
• Works for LL(1) grammars (Left-to-right scan, Leftmost derivation, 1 token lookahead).

Example:
Grammar:

LL(1) table helps decide which production to apply next.

 Bottom-Up Parsing

In bottom-up parsing, the parser starts with the input string and reduces it step by step to the start symbol using reverse derivations.

Types of Bottom-Up Parsing:

• Shift-Reduce Parsing (LR Parsing)
• Operator Precedence Parsing

 Shift-Reduce Parsing (LR Parsing)

• Uses a stack to hold symbols.
• Shift: Push tokens onto the stack.
• Reduce: Replace a sequence of symbols with a non-terminal based on production rules.
• Common types: LR(0), SLR(1), LALR(1), CLR(1).

Example:
Grammar:

For input id + id, the parser shifts tokens onto the stack and reduces them using rules.

 Key Differences: Top-Down vs. Bottom-Up Parsing

Feature	Top-Down Parsing	Bottom-Up Parsing
Start Point	From the start symbol	From the input string
Direction of Parsing	Left-to-right derivation	Right-to-left reduction
Backtracking	May require (in Recursive Descent)	No backtracking
Common Techniques	Recursive Descent, Predictive Parsing (LL(1))	Shift-Reduce Parsing (LR, SLR, CLR, LALR)
Complexity	Easier to implement	More powerful but complex

 Conclusion

Top-Down Parsing is simpler but may not handle all types of grammars.
Bottom-Up Parsing is more powerful and can handle complex grammars.

 Would you like an example of LL(1) or LR(1) parsing? Let me know!