exprparser
Copyright (C) 2002-6  Toby Thain <toby@telegraphics.com.au>

A simple lex/yacc based expression parser and evaluator.
This code reads an expression string, lexes and parses it to produce
an "expression tree", which can be later evaluated. 

Please contact the author with any questions, comments, bug fixes etc.

HISTORY
30-Dec-2002: first draft
02-Feb-2003: GPL release 1.0
03-Apr-2003: 1.1 - fix memory leak on failed parse
23-Apr-2003: 1.2 - add ?: conditional operator
28-Apr-2003: 1.3 - add relational operators

FEATURES
- Binary operators +, -, *, /, ^ (exponentiation) with usual precedence
- unary operators + (identity), - (negate)
- exponential notation (e.g. "4.3E7" = 4.3x10^7 = 43000000)
- parentheses control order of evaluation
- built-in named functions with one, two or three arguments:
  sin, cos, tan, exp, log, log10, sqrt (and two example 2- and 3-argument functions, fxy, fxyz)
- variable references (see main.c for the predefined variables); note assignment is not implemented,
  but would be trivial
- error reporting 

QUICKSTART
This code has been tested to build without changes on OS X, NetBSD and Linux.
It requires lex and yacc (or GNU flex and bison). 

To build:
	$ make
	  ...lines of build progress omitted...
	$
	
If you have any difficulties, please contact the author.

The program as distributed simply accepts expressions on standard input,
prints the expression tree as a depth-first hierarchy, and evaluates it once.

To run:
	$ ./parsertest 
	  ...you enter expressions, type control-D to finish...

Try these:
	1*2*3+4*(5-6)	Shows that precedence and parentheses are respected
	sin(.3)			Demonstrates a function invocation (and floating point constant)
	t+u/v			Variable references (these variables are given initial values in main.c)	

USING THIS CODE
Call the functions below to parse and evaluate expressions, and manipulate parse trees.
Compile and link with:
	lexer.l   (lexical analyser; this is translated by lex or flex into C)
	parser.y  (parser; this is translated by yacc or bison into C)
	node.c    (tree maintenance)
	main.c    (substitute your own main program)
	symtab.c  (symbol table maintenance)
See Makefile for details.

struct node *parseformula(char *s)
	parseformula() builds a parse tree from the input expression.
	If the expression cannot be parsed due to a lexical or grammatical error,
	the value returned is zero, and global variable errstr points to a string 
	describing the error. Global tokpos contains the index of the input character
	at which the error was detected. (The example code shows how these can be
	formatted into a readable error message.)
	If no error is detected, the return value points to the root of the newly created tree.

double eval(struct node *root)
	eval() evaluates the tree, with current values of variables, 
	and returns the numeric result.

void freetree(struct node *root)
	freetree() frees the memory blocks used by a parse tree. 
	Call it when you're finished with a tree.

void dumptree(struct node *root,int level)
	dumptree() is a debugging aid which prints a parse tree, depth-first.
	Call it with a pointer to the root of the tree, and level 0.

void init_symtab(struct sym_rec *)
	init_symtab() sets up the symbol table, for function and variable lookups.
	In the example code (main.c), the symbols are statically bound to C functions
	and global variables.
	(To facilitate user-defined variables, the symbol table is dynamic, 
	although neither assignment nor function definition are implemented.)

void dump_symbols()
	dump_symbols() lists the defined symbols on standard output.
	(It's really just a debugging tool.)