Faster, better (recursive descent) expression parser.
authorAlexei Sheplyakov <varg@theor.jinr.ru>
Tue, 19 Aug 2008 19:48:03 +0000 (23:48 +0400)
committerJens Vollinga <jensv@nikhef.nl>
Thu, 21 Aug 2008 20:45:07 +0000 (22:45 +0200)
commit1222eac51cee964961d2aad889dc4ceccb144a36
treea85c16388ca49d03203370f108801d75185f76b2
parent321d5c941f81b1d0b86de91f3f17c5af5b6e4642
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
15 files changed:
INSTALL
check/Makefile.am
check/time_parser.cpp [new file with mode: 0644]
configure.ac
ginac/Makefile.am
ginac/parser/builtin_fcns.def [new file with mode: 0644]
ginac/parser/debug.hpp [new file with mode: 0644]
ginac/parser/default_reader.tpl [new file with mode: 0644]
ginac/parser/lexer.cpp [new file with mode: 0644]
ginac/parser/lexer.hpp [new file with mode: 0644]
ginac/parser/parse_binop_rhs.cpp [new file with mode: 0644]
ginac/parser/parse_context.cpp [new file with mode: 0644]
ginac/parser/parse_context.hpp [new file with mode: 0644]
ginac/parser/parser.cpp [new file with mode: 0644]
ginac/parser/parser.hpp [new file with mode: 0644]