COSC3302 Program-3 Due: April 4, 2013
Expression Parser Construction
Objectives:
1. Understanding simple grammars and parsing
2. Implementing a Recursive-Descent Parser.
Consider the following grammar that defines all possible
arithmetic expressions provided that:
a. we have only three operators: +, -, and *
b. we have only three operands: A, B, and C
c. we have any number of parentheses in the normal way.
d. we want the usual operator precedence incorporated into
any expression we get.
EXP -> EXP + Term
EXP -> EXP - Term
EXP -> Term
Term -> Term * Fact
Term -> Fact
Fact -> A
Fact -> B
Fact -> C
Fact -> ( EXP )
Task:
Write a program that does:
1. Read one expression (as a character string, of course)
after another and check to see if it is an expression
of the expected kind, and
2. Print the input expression followed by a message that
indicates whether or not it is a legitimate expression.
Suggestion for Program Design
1. Set up Global variables:
int exp[50] // to contain an input expression
int current // the current input expression character index
// i.e., exp[current] is the current exp char.
2. Set a function for each nonterminal of the grammar.
3. main()
3a. establish an input file stream // To read input exps from a file.
3b. while (input-not-over)
read next input expression in a global var, exp[].
echo-print the input expression.
append an end=marker ($) to the input expression.
initial current to zero.
if(E()&&exp[current]=='$')
cout << " INPUT EXPRESSION LEGITIMATE. \n"
else cout << " INPUT EXPRESSION NOT LEGITIMATE. \n"
4. parsing function setup
int E() // return 1 if successful else 0
// EXP -> Term {+ Term || - Term}* { if (!Term()) return 0; //the very first term is not found, hence a failure
else
{ while (exp[current] == '+' || exp[current] == '-') { current++; if (!Term()) return 0;
} // All terms are found in success, so return in success
return 1;
}
}
////////////////////////////////
int Term() // This function can be set up more or less like E() above.
////////////////////////////////
int Fact() // A factor is either 'A', 'B', 'C', or "(EXP)"
{ char Cur = exp[current]; if (Cur=='A' || Cur=='B' || Cur=='C')
{ current++; return 1;
}
else if (Cur=='(') // a case of (E) { current++; if(!E()) return 0;
else if (exp[current]==')')
{ current++; return 1;
}
else return 0; // matching right-paren missing
}
else // A missing factor.
return 0;
}
Inputs:
For the sake of simplicity, we can assume that an input
expression does not contain any embedded blanks.
And, that each input expression is no longer than 50 characters.
((A+A*B)-B*C)
(((A+B-C)))+A))
(A+B*C)(A+B*C)
(((A*B*C))-A*B+C)*A
(A+B*C+((A+B*C)*C)))
A*B+()*B+A