Introduction
Parsing is the process of checking whether the given program is valid or not. It takes a string as input and checks whether it follows the existing grammar.

There are two types of parsers:
1.Top-Down Parser:
These parsers construct a parse tree from the root and move down to the tree's leaf. Some examples of top-down parsers are the Recursive Descent Parser and LL parsers.
2. Bottom-Up Parser:
These parsers build the parse tree from leaves to the tree's root. Some examples of bottom-up parsers are the LR parser, SLR parser, CLR parser, etc.
What is a Recursive Descent Parser?
A recursive descent parser is a specific parsing technique. It is commonly employed in computer science and compiler design to dissect the syntax and structure of a program or language, guided by a predefined grammar. This parsing approach is termed "top-down" because it initiates its analysis from the highest-level constructs in the grammar, such as the start symbol or main production rule. As it processes the input, the parser recursively descends through the text, continually attempting to align it with the production rules stipulated by the grammar. The form of recursive descent parser that does not require backtracking is also called predictive parsing.
Backtracking: Making repeated input scans until we find a correct path.
To implement a recursive descent parser, the grammar must hold the following properties:
- It should not be left recursive.
- It should be left-factored. (Alternates should not have common prefixes).
- Language should have a recursion facility.
If the grammar is not left-factored, the recursive descent parser will have to use backtracking.
Example
Before removing left recursion | After removing left recursion |
---|---|
E –> E + T | T T –> T * F | F F –> ( E ) | id | E –> T E’ E’ –> + T E’ | e T –> F T’ T’ –> * F T’ | e F –> ( E ) | id |
**Here e is Epsilon
For Recursive Descent Parser, we are going to write one program for every variable.
Implementation
Output
