Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Recursive Descent Parser?
2.1.
Example
2.2.
Implementation
2.3.
C
3.
Advantages of  Recursive Descent Parser
4.
Disadvantages of  Recursive Descent Parser
5.
Frequently Asked Questions
5.1.
Can recursive descent parser used for left recursive grammar?
5.2.
What is the difference between recursive descent and non-recursive descent parser?
5.3.
What are the limitations of recursive descent parsing? 
5.4.
What is recursive descent parsing also known as?
5.5.
What is the difference between recursive descent parser and LL parser?
6.
Conclusion
Last Updated: Apr 21, 2024
Medium

Recursive Descent Parser

Author Jaglike Makkar
3 upvotes
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

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.

recursive descent parsing in compiler design


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:

  1. It should not be left recursive.
  2. It should be left-factored. (Alternates should not have common prefixes).
  3. 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 recursionAfter 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

  • C

C

#include <stdio.h>
#include <string.h>
#define SUCCESS 1
#define FAILED 0

int E(), Edash(), T(), Tdash(), F();

const char *pt;
char grammar[64];

int main() {
sscanf("i+(i+i)*i", "%s", grammar);
pt = grammar;
puts("");
puts("Input Action");

if (E() && *pt == '\0') {
puts("String is successfully parsed");
return 0;
}
else {
puts("Error in parsing String");
return 1;
}
}

int E() {
printf("%-16s E -> T E'\n", pt);
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
}
else
return FAILED;
}

int Edash() {
if (*pt == '+') {
printf("%-16s E' -> + T E'\n", pt);
pt++;
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
}
else
return FAILED;
}
else
printf("%-16s E' -> $\n", pt);
return SUCCESS;
}

int T() {
printf("%-16s T -> F T'\n", pt);
if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
}
else
return FAILED;
}

int Tdash() {
if (*pt == '*') {
printf("%-16s T' -> *F T'\n", pt);
pt++;
if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
}
else
return FAILED;
}
else {
printf("%-16s T' -> $\n", pt);
return SUCCESS;
}
}

int F() {
if (*pt == '(') {
printf("%-16s F -> (E)\n", pt);
pt++;
if (E()) {
if (*pt == ')') {
pt++;
return SUCCESS;
}
else
return FAILED;
}
else
return FAILED;
}
else if (*pt == 'i') {
pt++;
printf("%-16s F -> i\n", pt);
return SUCCESS;
}
else
return FAILED;
}

Output

Output of Recursive Descent Parser
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Advantages of  Recursive Descent Parser

There are several advantages of a recursive descent parser:

  • It mirrors grammar, making it easy to understand and maintain
     
  • It efficiently predicts parsing paths
     
  • Programmers have full control and can tailor parsers to specific languages
     
  • It can be optimized for specific languages
     
  • It doesn't rely on external tools or generators

Disadvantages of  Recursive Descent Parser

Along with the advantages, there are some disadvantages of recursive descent parser:

  • It is most effective with LL(1) grammars, requiring adjustments for complex grammars
     
  • Handling left recursion, left-factoring, and some constructs can be challenging
     
  • Custom error handling is needed, making error recovery complex
     
  • Efficiency may be lower for deeply nested or complex syntax
     
  • Development is more manual and time-consuming compared to parser generators

Frequently Asked Questions

Can recursive descent parser used for left recursive grammar?

No, The main limitation of recursive descent parsing (and top-down parsing algorithms in general) is that they don't work for left recursive grammar.

What is the difference between recursive descent and non-recursive descent parser?

Predictive parsing is a special form of recursive descent parsing, where no backtracking is required, so this can predict which products to use to replace the input string. Non-recursive predictive parsing or table-driven is also known as LL(1) parser. This parser follows the leftmost derivation (LMD).

What are the limitations of recursive descent parsing? 

One of the major drawbacks or recursive-descent parsing is that it can be implemented only for those languages that support recursive procedure calls and it suffers from the problem of left-recursion.

What is recursive descent parsing also known as?

Recursive descent parsing is also known as a "top-down parser" because of the direction it takes when analyzing the input. The term "top-down" reflects the way the parser starts its analysis from the top-level constructs in the grammar and proceeds downward through the grammar rules to reach the terminals (tokens) in the input.

What is the difference between recursive descent parser and LL parser?

A recursive descent parser is an implementation of top-down parsing that uses a set of recursive procedures to process input. An LL parser, a specific type of top-down parser, uses a lookahead buffer to parse input based on an LL grammar.

Conclusion

In this article, we learned about the recursive descent parser and how to implement it using procedures. We also saw various pros and cons of recursive descent parsers. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass