Let us learn how to develop a recursive descent parsing program in C programming language using functions.
The header file ctype.h is used because the definition for isalnum() function is defined in it and similarly the definitions of strlen() method is in string.h header file.
What is a Recursive Descent Parser?
A recursive descent parser is a top-down parser. This is one of the most simple forms of parsing. It is used to build a parse tree from top to bottom and reads the input from left to right.
A form of recursive descent parsing that does not require backtracking algorithm is known as a predictive parser. The parsers that use backtracking may require exponential time. This parser is normally used for compiler designing purpose.
The parser gets an input and reads it from left to right and checks it. If the source code fails to parse properly, then the parser exits by giving an error (flag) message. If it parses the source code properly then it exits without giving an error message.
Must Read: C Program To Find First and Follow of a Grammar
Recursive Descent Parser Algorithm
1 2 3 4 5 6 | for a = 1 to limit for b = 1 to Array - 1 do begin Increase Production: Array[a] ->Array[b] end for Remove Immediate Left recursion from A[a] End for |
C Program To Develop A Recursive Descent Parser
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include<stdio.h> #include<ctype.h> #include<string.h> void Tprime(); void Eprime(); void E(); void check(); void T(); char expression[10]; int count, flag; int main() { count = 0; flag = 0; printf("\nEnter an Algebraic Expression:\t"); scanf("%s", expression); E(); if((strlen(expression) == count) && (flag == 0)) { printf("\nThe Expression %s is Valid\n", expression); } else { printf("\nThe Expression %s is Invalid\n", expression); } } void E() { T(); Eprime(); } void T() { check(); Tprime(); } void Tprime() { if(expression[count] == '*') { count++; check(); Tprime(); } } void check() { if(isalnum(expression[count])) { count++; } else if(expression[count] == '(') { count++; E(); if(expression[count] == ')') { count++; } else { flag = 1; } } else { flag = 1; } } void Eprime() { if(expression[count] == '+') { count++; T(); Eprime(); } } |
Output
If you have any compilation error or doubts in this C program for recursive descent parser code, let us know about it in the comment section below.
At last, I found a working program for this code. I am developing a basic compiler using recursive descent parsing technique. I hope it goes well.
the prgm is really gud
LL parsing technique is much more efficient than recursive descent parsing in C programming. Please try to implement LL parsing in C programming. LL parsers are always linear in time too.
Thanks for this parser generator c program. Recursive Descent Parsers can actually handle greater classes of grammars than LL1 Parsers. Both have their own pros and cons.
Can you enlist other parsing algorithms as well?
Apart from Recursive Descent Parser, there are so many other parsing algorithms used in compiler designing such as:
This recursive descent parser in C programming is really good. Thanks for the efforts.
Actually it process the following strings also e=
e=e any symbols e*e/ so if any terminals
Other than ( *,+,digit/num )these symbols it just
Comes out of all recursive procedures
SOL:
so in order to correct it keep the following
Additional condition to flag ==0 && (count==length)
Where length=strlen(expression)
If any symbols other than above mentioned symbols occurs it comes out so count does
Not gets equal to length it means it met with terminal that is not written in our code .
hi
can anybody give me production rule for above parser code
what can we do to handle multiple digits like 88*22
Hi, which grammare are you used in above code plz tell me
could you please post the grammar used in this code