Parsers are available in two different types:
- Top-Down Parser:
1.
These parsers commence parsing from the root of the tree and progress towards the leaf nodes. Two illustrations of top-down parsers include the Recursive Descent Parser and LL parsers.
- In contrast, Bottom-Up Parsers:
By employing this parsing method, the complete program is condensed down to the initial symbol. The Operator Precedence Parser, LR(0) Parser, SLR Parser, LALR Parser, and CLR Parser are all examples of Bottom-Up parsers.
What is a Recursive Descent Parser?
Continuative Descent Top-down parsers, such as Parser, build the parse tree from the highest node to the lowest leaf. They identify the input by utilizing recursive functions and can optionally utilize backtracking. Predictive parsing is an alternate term for the recursive descent parser variation that operates without the need for backtracking.
Backtracking:
You can follow the several steps to utilize backtracking:
- It repeatedly scans the input until we locate the right path.
- The following qualities of the grammar must be present in order to create a recursive descent parser:
- It shouldn't be allowed to repeat.
- It needs to be left-factored . Alternatives shouldn't share a prefix.
- Recursion should be possible in languages.
- Backtracking will be required by the recursive descent parser if the grammar is not left-factored.
Example
| Before removing left recursion | After removing left recursion | ||||||
|---|---|---|---|---|---|---|---|
| E -> E + T | TT -> T * F | FF ->( E ) | id | E -> T E'E' -> + T E' | eT -> F T'T' -> * F T' | eF ->( E ) | id |
**Here e is Epsilon
Now, we will develop an individual program for every variable present in the recursive descent parser.
Program:
#include <stdio.h>
#include <string.h>
#define SUCCESS 1
#define FAILED 0
int E(), Edash(), T(), Tdash(), F();
const char *cursor;
char string[64];
int main()
{
puts("Enter the string");
// scanf("%s", string);
sscanf("i+(i+i)*i", "%s", string);
cursor = string;
puts("");
puts("Input Action");
puts("--------------------------------");
if (E() && *cursor == '\0') {
puts("--------------------------------");
puts("String is successfully parsed");
return 0;
} else {
puts("--------------------------------");
puts("Error in parsing String");
return 1;
}
}
int E()
{
printf("%-16s E -> T E'\n", cursor);
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
}
int Edash()
{
if (*cursor == '+') {
printf("%-16s E' -> + T E'\n", cursor);
cursor++;
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
} else {
printf("%-16s E' -> $\n", cursor);
return SUCCESS;
}
}
int T()
{
printf("%-16s T -> F T'\n", cursor);
if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
}
int Tdash()
{
if (*cursor == '*') {
printf("%-16s T' -> * F T'\n", cursor);
cursor++;
if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
} else {
printf("%-16s T' -> $\n", cursor);
return SUCCESS;
}
}
int F()
{
if (*cursor == '(') {
printf("%-16s F -> ( E )\n", cursor);
cursor++;
if (E()) {
if (*cursor == ')') {
cursor++;
return SUCCESS;
} else
return FAILED;
} else
return FAILED;
} else if (*cursor == 'i') {
cursor++;
printf("%-16s F ->i\n", cursor);
return SUCCESS;
} else
return FAILED;
}
Output:
Enter the string
Input Action
--------------------------------
i+(i+i)*i E -> T E'
i+(i+i)*i T -> F T'
+(i+i)*i F ->i
+(i+i)*i T' -> $
+(i+i)*i E' -> + T E'
(i+i)*i T -> F T'
(i+i)*i F -> ( E )
i+i)*i E -> T E'
i+i)*i T -> F T'
+i)*i F ->i
+i)*i T' -> $
+i)*i E' -> + T E'
i)*i T -> F T'
)*i F ->i
)*i T' -> $
)*i E' -> $
*i T' -> * F T'
F ->i
T' -> $
E' -> $
--------------------------------
String is successfully parsed
Recursive Descent Parser: Advantages and Drawbacks
There are numerous benefits and drawbacks associated with Recursive Descent Parser. Below are some key advantages and disadvantages of Recursive Descent Parser:
Advantages:
- Constructing Recursive Descent parsers is quite straightforward. They are ideal for rapid and basic parsing requirements.
- These parsers are slower than some of the other parsers. They are ineffective for parses requiring arbitrary long lookahead .
- Only languages that support recursive procedure calls can implement Left-recursion is a problem that it has.