Expression Parsing (was: parsing equations)
Keith....@dcs.qmw.ac.uk
>I am looking for tools or examples to help implement a spreadsheet-like
>equation parser for an internal application we need to write. We need to
>handle arbitrary nesting and complexity... everything from
>
>A1 + B1 / C1
>
>to
>
>((0.75 + RAND() * 0.5) * AVERAGE($A3:$A19)) / (1 + LN( MAX(C3:C19) ) )
...
>Patrick Parker
>[It's certainly been done a thousand times, but it'd be nice to have a
>documented expression parser packaged up and ready to go. -John]
I have a demo expression parser written in C++, about 200 lines, but
essentially just C code. It uses the recursive descent precedence
method I posted in 1992 (sorry, I don't have a reference, but someone
reposted it in March this year).
It started as an example for teaching, & shows how to achieve various
effects that are occasionally asked for, such as juxtaposition, C-like
precedences, postfix ops, etc. It could easily handle constructs like
expr?expr:expr
too, but I haven't bothered.
Keith Clarke
---
Code for the archive:
// This program reads an integer expression terminated by an equals sign,
// calculates its value and prints it.
// It allows spaces before each operator, number and '='.
// It uses a simple recursive precedence parser
// featuring prefix, postfix, infix operators; juxtaposition/function calls;
// left-associative infix ops; right-assoc infix ops.
// BNF
// expr = primary
// | expr ^ expr exponentiation
// | expr expr juxtaposition (subtraction, here!)
// | expr / expr division
// | expr * expr mult
// | expr + expr addition
// | expr - expr subtraction
// | expr & expr logical and
// | expr | expr logical or
// primary
// = ( expr )
// | digits
// | - expr integer negation
// | ! expr logical negation
// | expr ( expr ) division (bizarrely!)
//
// The ambiguities in the above BNF have been resolved to make the
// behaviour of this example C-like. Postfix beats prefix
// beats infix; usual C precedences except juxtaposition (same as subtraction);
// the usual function-call syntax is made to mean division, thus 100(5)(2)=10.
// I've chosen non-associative operations so it's easy to see that this code
// gives left-associative behaviour.
//
//
// There are comments in the code to show how other behaviours might be
// realised.
//
// Permission is given to use this source provided an acknowledgement is given.
// I'd also like to know if you've found it useful.
// The following Research Report describes the idea, and shows how the
// parsing method may be understood as an encoding of the usual family-of-
// parsing-procedures technique as used e.g. in Pascal compilers.
// @techreport{QMW-DCS-383-1986a,
// author ="Clarke, Keith",
// title ="The Top-Down Parsing of Expressions",
// institution ="Department of Computer Science, Queen Mary College,
University of London, England",
// year ="1986",
// month ="June",
// number ="QMW-DCS-1986-383",
// scope ="theory",
// abstractURL
="http://www.dcs.qmw.ac.uk/publications/report_abstracts/1986/383",
// keywords ="Recursive-descent parsing, expression parsing,
operator precedence parsing."
// }
// A formal proof of the algorithm was made, as part of his PhD thesis work,
// by A.M. Abbas of QMC, London, in the framework of Constructive Set Theory.
// copyright Keith Clarke, Dept of Computer Science, QMW, University of London,
// England. email kei...@dcs.qmw.ac.uk
#include <stream.h>
#include <assert.h>
#include <ctype.h>
void readprimary(int&);
void readexpr(int&,int);
void printnum(int);
void readnum(int&);
int fact(int);
// C-like highest-precedence postfix ops are handled in readprimary().
// Lower precedence postfix ops should be given a precedence in prio()
// and parsed by readexpr().
int postfix(char ch) {
return ch=='(' || ch=='!';
}
// This function is used only if you want to use juxtaposition of two
// expressions with a precedence like a ordinary operator, such as using
// a+bc^d to mean a+(b*(c^d)) as in ordinary arithmetic.
// When an expr can be formed from one expression immediately followed
// by a phrase P, then any of the symbols in the first set of P should
// be given a precedence suitable for the binding power of the construct.
// For true juxtaposition this would be FIRST(expr); but I've made it only
// digits so I can illustrate C-like behaviour of "function calls" e.g. f(x)(y)
// in readprimary().
int firstjuxta(char ch) {
switch(ch) {
// case '(' : return 1;
// return true for any digit, variable etc
// to allow e.g. (f 3) for a function application,
// or, in this example calculator (4 3) to mean the same as (4-3).
default: return isdigit(ch);
}
}
// Infix operators and maybe juxtaposition & postfix operators.
// This function tabulates the required behaviour of infix operators
// larger numbers bind more tightly.
// 0 means the symbol isn't an infix operator.
// It can be useful to give postfix ops a non-zero precedence - see readexpr()
int prio(char ch) {
switch(ch) {
case '|' : return 1;
case '&' : return 2;
case '+' : return 3;
case '-' : return 3;
case '*' : return 4;
case '/' : return 4;
case '^' : return 5;
default:
if(firstjuxta(ch)) return 3;
else return 0;
}
}
// Infix operators.
// True if it is, False if it isn't; doesn't matter if the symbol isn't
// even an infix op.
int rightassoc(char ch) {
switch(ch) {
case '^' : return 1;
default: return 0;
}
}
// END OF PRECEDENCE INFO
void skipspaces() {char ch; while(cin.get(ch),isspace(ch)) ; cin.putback(ch); }
int power(int n,int m) {
int k=1;
while(m>0) {k*=n; m--;}
return k;
}
// Read an infix expression containing top-level operators that bind at least
// as tightly as the given precedence.
// Don't consume the first non-digit character after the last number.
// Complain if you can't even find the first number,
// or if there is an operator with no following number.
void readexpr(int& ans,int prec) {
int number, thisprec;
char ch;
readprimary(ans);
skipspaces();
while ( cin >> ch, thisprec=prio(ch), thisprec>=prec ) {
// We're here because prio(ch) is large enough,
// but if firstjuxta(ch) is true, then ch is the first
// character of the following expression, not an infix operator.
if(firstjuxta(ch)) cin.putback(ch);
// if ch is a symbol which is postfix not infix,
// don't read the following expression here
readexpr(number,rightassoc(ch)?thisprec:thisprec+1);
switch(ch) {
case '+' : ans+=number; break;
case '*' : ans*=number; break;
case '-' : ans-=number; break;
case '/' : ans/=number; break;
case '^' : ans=power(ans,number); break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
// for illustration, I've made juxtaposition mean subtraction
// I've already made "juxtaposition expressions" only parse
// when the second one starts with a digit, in fn. firstjuxta()
ans-=number; break;
default: cout << "Panic: don't know the meaning of the operator "
<< ch << endl;
};
}
// We just read a character that wasn't an operator, and we don't
// have any use for it - but the next input function might - put it back
cin.putback(ch);
// no return value
}
// read a single number; a whole expression in parentheses; prefix op
void readprimary(int& ans) {
char ch;
if(cin>>ch,ch=='(') {
// must be an expression; we've consumed the opening parenthesis
readexpr(ans,1);
// and since readsum didn't care what followed the sum, the
// closing parenthesis is still there waiting to be consumed
if(cin>>ch,ch!=')') {
cout << "Missing right parenthesis\n";
// maybe we just consumed the = sign - put it back, just in case
cin.putback(ch);
}
} else if (isdigit(ch)) {
// whoops, we've read the first digit of the number already...
cin.putback(ch);
readnum(ans);
// illustrative prefix operators
} else if (ch=='-') {
readexpr(ans,1); ans = -ans;
} else if (ch=='!') {
readexpr(ans,1); ans = !ans;
} else
cout << "Number, left bracket or prefix operator expected\n";
// Parsing postfix ops here gives them HIGHER precedence than any
// infix operation; HIGHER precedence than prefix operators.
// You can give a postfix op a lower prec
// by handling it as though it were infix - see readexpr()
// illustrative postfix operators
while(cin>>ch,postfix(ch)) {
if(ch=='!') {
ans=fact(ans);
} else if(ch=='(') {
// make this "function call" syntax mean division
int number;
readexpr(number,1);
ans/=number;
if(cin.get(ch),ch!=')') {
cout << "Missing right parenthesis in function call\n";
}
} else
cout << "Panic: don't know the meaning of postfix op "
<< ch << endl;
}
cin.putback(ch);
}
// print an integer in decimal, one char at a time
// For pedagogic purposes only!
void printnum(const int N) {
if(N<10) { cout << N%10; }
else {
printnum(N/10);
cout << N%10;
}
}
int digitvalue(char ch) {
return (ch - '0');
}
// Each function checks all of its phrase, even if the caller has already
// made sure the first symbol is OK
void readnum(int& N) {
char ch;
N=0;
while(cin.get(ch),isspace(ch)) ;
if(!isdigit(ch)) {
cout << "Number expected\n";
return;
}
while(isdigit(ch)) {
N = N*10+digitvalue(ch);
cin.get(ch);
}
cin.putback(ch);
}
int fact(int n) {
return n==0?1:n*fact(n-1);
}
main() {
int total; char ch;
cout << "Type an integer expression terminated by an '=' character";
// No doubt there's a better way to do this, but who cares...
while(cout << "\n? ",cin.get(ch),cin.putback(ch),!cin.eof()) {
readexpr(total,1);
skipspaces();
cin >> ch;
if(ch=='=') {
printnum(total);
} else {
cout << "Expected an '=' character after the last number";
}
while(cin.get(ch),ch!='\n') ;
}
}
--
Send compilers articles to comp...@iecc.com,
meta-mail to compiler...@iecc.com.