[GiNaC-devel] [SCM] GiNaC -- a C++ library for symbolic computations branch, master, updated. release_1-4-0-64-g1222eac

[Jens Vollinga]

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 at 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 at 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