Faster, better (recursive descent) expression parser.

Faster, better (recursive descent) expression parser.

Ouch, it fails to compile. Here is a correct version:

From: Alexei Sheplyakov <varg@theor.jinr.ru>
Date: Tue, 19 Aug 2008 21:50:03 +0400
Subject: [PATCH] Faster, better (recursive descent) expression parser.

bison generated parser has a number of problems:

1. Bad performance. Parsing a sum seems to be O(N^{2 + a}) (a > 0) [1].
   For example, parsing a sum (actually, a univariate polynomial) of 32768
   terms takes about 90 sec. on my box, parsing a sum of 10^6 terms takes
   "eternity".
2. The user is expected to provide list of all symbols in the expression.
   Often this is very annoying (and useless).
3. Parser is not reentrant (bison *can* produce reentrant parsers, but that
   won't solve other problems).
4. Parser is difficult to extend.

Hence the new parser.

Features:

1. Parsing large sums and products is O(N).
2. Parser is reentrant (well, almost).
3. It's possible to insert (shell style) comments inside the expressions.
4. matrices, lists, FAIL are NOT handled. Yes, this *is* a feature :-)

Limitations:

1. Error handling is a bit terse: on error exception is thrown, and that's it.
2. Binary, octal, and hexadecimal numbers can not be parsed (yet).
3. Tensors, noncommutative products, etc. can not be parsed.

Other notes:

1. ex ctor still uses the old parser.
2. ginsh still uses the old parser.

[1] Mesured by this script (requires gnuplot):

make_expression_string ()
{
	printf "1 + x"
	local n=2
	while test $n -le $1; do
		printf " + %s*x^%s" $n $n
		n=$(expr $n + 1)
	done
}

single_test ()
{
	printf "$1 \t"
	( printf "time("; make_expression_string $1; printf ");" ) | \
	ginsh | sed -e 's/s$//'
}

benchmark ()
{
	local N=$1
	while test $N -le $2; do
		single_test $N
		N=$(expr $N \* 2)
	done

}

gnuplot_header ()
{
 	echo "set logscale xy"
	echo "set xlabel 'degree (# of terms)'"
	echo "set ylabel 'time, sec.'"
	echo "set xrange [${1}:${2}]"
	echo "plot '-' using 1:2 with lines title '1+x+2*x^2+...+n*x^n'"
}

gnuplot_footer ()
{
	echo "e"
}

benchmark_and_plot ()
{
	( gnuplot_header $1 $2
	  benchmark $1 $2 | tee $3.txt
	  gnuplot_footer ) | \
	gnuplot -persist '-'
}

N_ini=${1:-1024}
N_fin=${2:-32768}
out_base=${3:-parser_benchmark}

benchmark_and_plot $N_ini $N_fin $out_base