Implementing a recursive descent parser for the given grammar with the sample input '(a)'.
The output of this program is to check if the input read by the user is parsed successfully or not. As of how the flow of the program should go for this particular input...
main()
calls the start symbol E() -> T() -> T1()
[ which evaluates to false ] hence tracing back to its parent function T()
which now calls T2()
(which also evaluates to false), hence T() -> T3() -> E() -> E1() -> T() -> T1()
(evaluates to true).
Eventually E()
should also be true and the last condition termial(')')
in the statement return termial('(') && E() && termial(')');
from the function T3()
should be performed with ')'
as the value for token
. However, it turns out that token == '('
still and hence the output of the program results in
Parsed Unsuccessfully
Not really sure why token
is not equal to ')'
//Grammar :
//E -> T | T + E
//T -> a | a * T | (E)
//
//Input :
//(a)
#include <stdio.h>
char *next;
int E();
int E1();
int E2();
int T();
int T1();
int T2();
int T3();
int termial(char token){
return (*next++ == token);
}
int E1(){
return T();
}
int E2(){
return T() && termial('+') && E();
}
int E(){
char *temp = next;
return (next = temp, E1()) || (next = temp, E2());
}
int T1(){
return termial('a');
}
int T2(){
return termial('a') && termial('*') && T();
}
int T3(){
return termial('(') && E() && termial(')');
}
int T(){
char *temp = next;
return (next = temp, T1()) || (next = temp, T2()), (next = temp, T3());
}
int main(int argc, const char * argv[]) {
char str[10];
int result;
printf("INPUT a string to be parsed : ");
scanf("%s", str);
next = &str[0];
result = E();
result == 1 ? printf("Parsed Successfully") : printf("Parsed Unsuccessfully");
printf("\n");
return 0;
}
In T()
:
int T(){
char *temp = next;
return (next = temp, T1()) || (next = temp, T2()), (next = temp, T3());
}
(next = temp, T3())
is always called (there's no short-circuit at the comma before it), and will return false
in most of your cases, causing all sorts of failures when T1()
or T2()
succeed and should have ended the function with success.
Change that line to:
return (next = temp, T1()) || (next = temp, T2()) || (next = temp, T3());