This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GiNaC -- a C++ library for symbolic computations". The branch, master has been updated via 1222eac51cee964961d2aad889dc4ceccb144a36 (commit) from 321d5c941f81b1d0b86de91f3f17c5af5b6e4642 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 1222eac51cee964961d2aad889dc4ceccb144a36 Author: Alexei Sheplyakov <varg@theor.jinr.ru> Date: Tue Aug 19 23:48:03 2008 +0400 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 ----------------------------------------------------------------------- Summary of changes: INSTALL | 3 +- check/Makefile.am | 8 ++- check/time_parser.cpp | 79 +++++++++++++++++ configure.ac | 4 + ginac/Makefile.am | 31 ++++++- ginac/parser/builtin_fcns.def | 90 +++++++++++++++++++ ginac/parser/debug.hpp | 35 ++++++++ ginac/parser/default_reader.tpl | 50 +++++++++++ ginac/parser/lexer.cpp | 132 ++++++++++++++++++++++++++++ ginac/parser/lexer.hpp | 45 ++++++++++ ginac/parser/parse_binop_rhs.cpp | 176 ++++++++++++++++++++++++++++++++++++++ ginac/parser/parse_context.cpp | 27 ++++++ ginac/parser/parse_context.hpp | 78 +++++++++++++++++ ginac/parser/parser.cpp | 173 +++++++++++++++++++++++++++++++++++++ ginac/parser/parser.hpp | 95 ++++++++++++++++++++ 15 files changed, 1021 insertions(+), 5 deletions(-) create mode 100644 check/time_parser.cpp create mode 100644 ginac/parser/builtin_fcns.def create mode 100644 ginac/parser/debug.hpp create mode 100644 ginac/parser/default_reader.tpl create mode 100644 ginac/parser/lexer.cpp create mode 100644 ginac/parser/lexer.hpp create mode 100644 ginac/parser/parse_binop_rhs.cpp create mode 100644 ginac/parser/parse_context.cpp create mode 100644 ginac/parser/parse_context.hpp create mode 100644 ginac/parser/parser.cpp create mode 100644 ginac/parser/parser.hpp hooks/post-receive -- GiNaC -- a C++ library for symbolic computations