Description: In this assignment, you need to implement a recursive descent parse
ID: 3791178 • Letter: D
Question
Description: In this assignment, you need to implement a recursive descent parser in C++ for the following CFG:
1. exps --> exp | exp NEWLINE exps
2. exp --> term {addop term}
3. addop --> + | -
4. term --> factor {mulop factor}
5. mulop --> * | /
6. factor --> ( exp ) | INT
The 1st production defines exps as an individual expression, or a sequence expressions separated by NEWLINE token.
The 2nd production describes an expression as a term followed by addop term zero, one, or more times, i.e. exp can be: term, or term addop term, or term addop term addop term, or term addop term addop term addop term, …
The 4th production describes the definition of term, which is pretty much similar to 2nd production.
The 6th production defines a factor either as an expression enclosed by a pair of parentheses or an integer.
In recursive descent parsing, a function is defined for each non-terminal, i.e. exps, exp, term, and factor in our case. The non-terminals addop and mulop are too simple so that we will process them directly in functions of exp and term respectively.
Explanation / Answer
#include<stdio.h>
#include<string.h>
#include<ctype.h>
char input[100];
int i,error;
void E();
void T();
void F();
void EXPS();
main()
{
i=0; // Global Variable
error=0; //Global Variable
printf("Enter an arithmetic expression : "); // Eg: a+a*a
gets(input);
EXPS(); //Start Evaluation of CFG
if(strlen(input)==i&&error==0)
printf(" Accepted ");
else printf(" Rejected ");
}
void EXPS()
{
E(); //call expression
}
void E()
{
T(); //Term
if(input[i]==' ') //after term it check if next char is newline token which means sequence of expressions
{
i++;
E();
}
}
void T()
{
F(); //calls factor
if(input[i]=='*' || input[i]=='/') //checks for next char
{
i++;
F();
}
else if(input[i]=='+' || input[i]=='-') //checks for addop if it was present after one occurence
{
i++;
T();
}
}
void F()
{
if(isalnum(input[i]))
i++;
else if(input[i]=='(')
{
i++;
E();
if(input[i]==')')
i++;
else error=1;
}
else if(input[i]=='*' || input[i]=='/')
{
i++;
F();
}
else error=1;
}