What is Parsing? Types of Parser | Compiler Design

In this video, we will be specifically covering what is parsing & the types of parsers are. Parsing is a phase of the compiler that generally takes token strings as input and then tokens are converted into Parse Tree or Syntax Tree. This process of transforming the data from one format to another i.e. from token to Parse Tree is called Parsing.

Parser are mainly of two types: 1) Top-down parser 2) Bottom-up parser

Further Top-down and bottom-up parsers are categorized into different parsers: 1) Top-down Parser: The top-down parser generates parse for any given input string with the help of CFG grammar productions by expanding non-terminals i.e. starting from start symbol, expanding its productions and finally ending on terminals. Top-down parser uses left most derivation.

Top-down parsers can be further classified into two types: Recursive descent parser & Non-recursive descent parser

2) Bottom-up Parser: Bottom-up Parsers generate the syntax tree or parse tree for any given input with help of the grammar productions by compressing non-terminals of Grammar’s RHS i.e. it starts from the existing non-terminals and ends on the start symbol. It uses the reverse of the rightmost derivation.

Bottom-up parsers can be further classified into: - LR parsers & Operator precedence parser:

Types of Parsers in Compiler Design: https://www.geeksforgeeks.org/types-of-parsers-in-compiler-design/