![Compiler Design Tutorial](https://www.tutorialspoint.com/compiler_design/images/compiler-design-mini-logo.jpg)
- Compiler Design Tutorial
- Compiler Design - Home
- Compiler Design - Overview
- Compiler Design - Architecture
- Compiler Design - Phases of Compiler
- Compiler Design - Lexical Analysis
- Compiler - Regular Expressions
- Compiler Design - Finite Automata
- Compiler Design - Syntax Analysis
- Compiler Design - Types of Parsing
- Compiler Design - Top-Down Parser
- Compiler Design - Bottom-Up Parser
- Compiler Design - Error Recovery
- Compiler Design - Semantic Analysis
- Compiler - Run-time Environment
- Compiler Design - Symbol Table
- Compiler - Intermediate Code
- Compiler Design - Code Generation
- Compiler Design - Code Optimization
- Compiler Design Useful Resources
- Compiler Design - Quick Guide
- Compiler Design - Useful Resources
- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who
Compiler Design - Types of Parsing
Syntax analyzers follow production rules defined by means of context-free grammar. The way the production rules are implemented (derivation) divides parsing into two types : top-down parsing and bottom-up parsing.
![Types of Parser](https://www.tutorialspoint.com/compiler_design/images/types_of_parser.jpg)
Top-down Parsing
When the parser starts constructing the parse tree from the start symbol and then tries to transform the start symbol to the input, it is called top-down parsing.
Recursive descent parsing : It is a common form of top-down parsing. It is called recursive as it uses recursive procedures to process the input. Recursive descent parsing suffers from backtracking.
Backtracking : It means, if one derivation of a production fails, the syntax analyzer restarts the process using different rules of same production. This technique may process the input string more than once to determine the right production.
Bottom-up Parsing
As the name suggests, bottom-up parsing starts with the input symbols and tries to construct the parse tree up to the start symbol.
Example:
Input string : a + b * c
Production rules:
S → E E → E + T E → E * T E → T T → id
Let us start bottom-up parsing
a + b * c
Read the input and check if any production matches with the input:
a + b * c T + b * c E + b * c E + T * c E * c E * T E S