> In any case, I was wondering if someone could provide me with an example of
> a mathematical expression parser (and evaluator).
> To properly compare to the others, it would need to handle the following
> operators
>
> +, - (left associative)
> *, /, % (left associative)
> ^ (right associative)
>
> handle parens 12 - (3 + 4)
>
> handle two functions sqrt() and abs() both of which must include the
> parens.
>
> If someone has time to do this for me, I would be appreciative. It might
> also serve as example documentation or cookbook ideas.
>
> I am specifically interested in examples that can be run in Perl 5 today
> without needing Pugs or Parrot.
It isn't specifically a parser designed for general language parsing, but
CGI::Ex::Template does have a mathematical expression parser. The parser is
located near the end of the parse_expr method. The output of the parse_expr
is an opcode data structure that can be played out through the play_expr
method.
The basic functionality is that a chain of operators is tokenized into a
single array. The apply_precedence method is then used to split the array
into the optree based upon the precedence and associativity of the operators.
The following is a sampling of the resulting "optrees" for the given
expressions (taken from the perldoc):
1 + 2 => [ \ [ '+', 1, 2 ], 0]
a + b => [ \ [ '+', ['a', 0], ['b', 0] ], 0 ]
a * (b + c) => [ \ [ '*', ['a', 0], [ \ ['+', ['b', 0], ['c', 0]], 0 ]],
0 ]
(a + b) => [ \ [ '+', ['a', 0], ['b', 0] ]], 0 ]
(a + b) * c => [ \ [ '*', [ \ [ '+', ['a', 0], ['b', 0] ], 0 ], ['c',
0] ], 0 ]
perl -e 'use CGI::Ex::Template; $s=CGI::Ex::Template::dump_parse("3 * 4 ** 2 +
5"); $s =~ s/\s+/ /g; print "$s\n"'
$VAR1 = [ \[ '+', [ \[ '*', '3', [ \[ '**', '4', '2' ], 0 ] ], 0 ], '5' ],
0 ];
I apologize that the expression parsing isn't a little more abstracted for
you, but the result should be usable. Also, the parse_expr is designed for
also parsing variable names in the TT2 language, so the first portion of the
method applies variable names. The entire thing could be cut down
considerably if all you want to parse is math (no variables).
Paul Seamons
