Using Rules Today

[Joshua Gatcomb]

All:
I have a for-fun project that I am working on exploring various different
parsers and their methods. So far I have looked at things like
Parse::RecDescent, Parse::YAPP, Parse::Earley, and HOP::Parser. I had
Perl6::Rules on my list, but it is my understanding that
Pugs::Compiler::Rule is more up to date.

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.

Cheers,
Joshua Gatcomb
a.k.a. Limbic~Region

[Flavio S. Glock]

2006/7/3, Joshua Gatcomb <joshua....@gmail.com>:

>
> I am specifically interested in examples that can be run in Perl 5 today
> without needing Pugs or Parrot.

http://svn.openfoundry.org/pugs/perl5/Pugs-Compiler-Rule/compile_p6grammar.pl
- doesn't do exactly what you want, but you can see what the syntax
looks like for writing an evaluator using rules in p5.

http://svn.openfoundry.org/pugs/perl5/Pugs-Compiler-Rule/lib/Pugs/Grammar/Rule/Rule.pm
- this is the grammar for rules, written in rules.
The last rules have looser precedence; the rules at the start of the
file have tighter precedence.
This grammar is compiled to p5 using lrep.

- Flavio S. Glock

[Paul Seamons]

> 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

[Joshua Gatcomb]

On 7/3/06, Paul Seamons <ma...@seamons.com> wrote:
>
>
> It isn't specifically a parser designed for general language parsing, but
> CGI::Ex::Template does have a mathematical expression parser.

Thanks, but this falls into the realm of existing wheels which is a
different part of this project.

> 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 ];

Ok, but where is the evaluation? I know it wouldn't be too hard to write
something that could evaluate this data structure to produce the correct
results but that is what this project is all about. Some parsers make this
easier than others. Some allow the expression to be evaluated as it is
parsed while some require additional homegrown code to parse the resulting
parse tree (data structure).

I have not had a chance to look at Flavio's links yet. Since no one who
actually knows rules seemed to be inspired to write an example for me - I
will *eventually* figure it out on my own and post back to the list as an
FYI.

Paul Seamons

[Flavio S. Glock]

2006/7/5, Joshua Gatcomb <joshua....@gmail.com>:

>
> I have not had a chance to look at Flavio's links yet. Since no one who
> actually knows rules seemed to be inspired to write an example for me - I
> will *eventually* figure it out on my own and post back to the list as an
> FYI.

Here is a simple one that handles '+' and '*' - it could be simplified
a bit, but this one works for me:
---
use Data::Dumper;
use strict;
use Pugs::Compiler::Token;
use Pugs::Runtime::Match::Ratchet;
use base 'Pugs::Grammar::Base';

Pugs::Compiler::Token->install( 'mul','
(<alnum>+)
[ \\* <mul> { return ( $/[0]()*$/{mul}() ) }
| <\'\'>
]
' );
Pugs::Compiler::Token->install( 'sum','
<mul>
[ \\+ <sum> { return $/{mul}()+$/{sum}() }
| <\'\'> { return $/{mul}() }
]
' );

my $s = shift;
my $match = main->sum( $s );
print $match->();
---

- Flavio S. Glock