Recursive Descent Parser
Parsing is the process to determine whether the start symbol can derive the program or not. If the Parsing is successful then the program is a valid program otherwise the program is invalid.
There are generally two types of Parsers:
- Top-Down Parsers:
- In this Parsing technique we expand the start symbol to the whole program.
- Recursive Descent and LL parsers are the Top-Down parsers.
- Bottom-Up Parsers:
- In this Parsing technique we reduce the whole program to start symbol.
- Operator Precedence Parser, LR(0) Parser, SLR Parser, LALR Parser and CLR Parser are the Bottom-Up parsers.
Recursive Descent Parser:
It is a kind of Top-Down Parser. A top-down parser builds the parse tree from the top to down, starting with the start non-terminal. A Predictive Parser is a special case of Recursive Descent Parser, where no Back Tracking is required.
By carefully writing a grammar means eliminating left recursion and left factoring from it, the resulting grammar will be a grammar that can be parsed by a recursive descent parser.
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.
Example: Grammar:
C
#include <stdio.h> #include <string.h> #define SUCCESS 1 #define FAILED 0 // Function prototypes int E(), Edash(), T(), Tdash(), F(); const char *cursor; char string[64]; int main() { puts ( "Enter the string" ); scanf ( "%s" , string); // Read input from the user cursor = string; puts ( "" ); puts ( "Input Action" ); puts ( "--------------------------------" ); // Call the starting non-terminal E if (E() && *cursor == '\0' ) { // If parsing is successful and the cursor has reached the end puts ( "--------------------------------" ); puts ( "String is successfully parsed" ); return 0; } else { puts ( "--------------------------------" ); puts ( "Error in parsing String" ); return 1; } } // Grammar rule: E -> T E' int E() { printf ( "%-16s E -> T E'\n" , cursor); if (T()) { // Call non-terminal T if (Edash()) // Call non-terminal E' return SUCCESS; else return FAILED; } else return FAILED; } // Grammar rule: E' -> + T E' | $ int Edash() { if (*cursor == '+' ) { printf ( "%-16s E' -> + T E'\n" , cursor); cursor++; if (T()) { // Call non-terminal T if (Edash()) // Call non-terminal E' return SUCCESS; else return FAILED; } else return FAILED; } else { printf ( "%-16s E' -> $\n" , cursor); return SUCCESS; } } // Grammar rule: T -> F T' int T() { printf ( "%-16s T -> F T'\n" , cursor); if (F()) { // Call non-terminal F if (Tdash()) // Call non-terminal T' return SUCCESS; else return FAILED; } else return FAILED; } // Grammar rule: T' -> * F T' | $ int Tdash() { if (*cursor == '*' ) { printf ( "%-16s T' -> * F T'\n" , cursor); cursor++; if (F()) { // Call non-terminal F if (Tdash()) // Call non-terminal T' return SUCCESS; else return FAILED; } else return FAILED; } else { printf ( "%-16s T' -> $\n" , cursor); return SUCCESS; } } // Grammar rule: F -> ( E ) | i int F() { if (*cursor == '(' ) { printf ( "%-16s F -> ( E )\n" , cursor); cursor++; if (E()) { // Call non-terminal E if (*cursor == ')' ) { cursor++; return SUCCESS; } else return FAILED; } else return FAILED; } else if (*cursor == 'i' ) { printf ( "%-16s F -> i\n" , cursor); cursor++; return SUCCESS; } else return FAILED; } |
Contact Us