Re: prefix notation in an array

Update: I am so sorry. I didn't read your post thoroughly enough. This is actually an infix-expression parser. I posted code that solves your problem in a reply to this post. -- Steffen

The following code should solve your problem including operator precedence (and > or > == > !).

Note, however, that it will be very slow when dealing with long strings.

use strict;
use warnings;
use Data::Dumper;
use Parse::RecDescent;

my $grammar = <<'GRAMMAR';

boolean_expr:   and_expr                        { $item[1] }
              | terminal                        { $item[1] }
              | <error>

and_expr:       <leftop: or_expr 'and' or_expr>
                {
                        my $ary = $item[1];
                        my $return = $ary->[0];
                        foreach (@{$ary}[1..$#$ary]) {
                                $return = ['and', $return, $_];
                        }
                        $return;
                }

or_expr:        <leftop: eq_expr 'or' eq_expr>
                {
                        my $ary = $item[1];
                        my $return = $ary->[0];
                        foreach (@{$ary}[1..$#$ary]) {
                                $return = ['or', $return, $_];
                        }
                        $return;
                }

eq_expr:        <leftop: unary_expr '==' unary_expr>
                {
                        my $ary = $item[1];
                        my $return = $ary->[0];
                        foreach (@{$ary}[1..$#$ary]) {
                                $return = ['==', $return, $_];
                        }
                        $return;
                }

unary_expr:     '!' term                        { ['!', $item[2]] }
              | term                            { $item[1] }


term:           '(' boolean_expr ')'            { $item[2] }
              | terminal                        { $item[1] }

terminal:       /\w+/                           { $item[1] }

GRAMMAR

my $parser = Parse::RecDescent->new($grammar);

while (<STDIN>) {
        chomp;
        my $parsed;
        $parsed = $parser->boolean_expr($_);
        next unless defined $parsed;
        print Dumper $parsed;
}
[download]

For a more involved example of a Parse::RecDescent grammar for parsing similar expressions, have a look at the Math::Symbolic::Parser module (algebraic expressions in that case).

Steffen

Comment on Re: prefix notation in an array Download Code

Replies are listed 'Best First'.
Re: Re: prefix notation in an array by tsee (Curate) on Mar 26, 2004 at 15:18 UTC
I am sorry, the code that actually solves the outlined problem is the following. You can enter prefix boolean expressions in brackets ( "`[and, a, [==, b, [!, c]]]`" ). After you entered the first valid expression, you may instead add new expressions as "</code>or, d`" which will be applied to the previous expression. Entering "<code>!`" negates the current expression. use strict; use warnings; use Data::Dumper; use Parse::RecDescent; my $grammar = <<'GRAMMAR'; boolean_expr: '[' /and\|or\|==/ ',' boolean_expr ',' boolean_expr ']' { [ $item[2], $item[4], $item[6] ] } \| '[' '!' ',' boolean_expr ']' { [ '!', $item[4] ] } \| /and\|or\|==/ ',' boolean_expr { [ $item[1], $item[3] ] } \| '!' \| terminal { $item[1] } \| <error> terminal: /\w+/ { $item[1] } GRAMMAR my $parser = Parse::RecDescent->new($grammar); my $old; while (<STDIN>) { chomp; my $parsed = $parser->boolean_expr($_); next unless defined $parsed; if (ref $parsed eq 'ARRAY' and @$parsed == 2 and $parsed->[0] =~ /and\|or\|==/ ) { warn("Cannot add clause if no " . "starting term was defined."), next if not defined $old; $old = [$parsed->[0], $old, $parsed->[1]]; } elsif ($parsed eq '!') { warn("Cannot add clause if no " . "starting term was defined."), next if not defined $old; $old = ['!', $old]; } else { $old = $parsed; } print Dumper $old; } [download] Update: Fixed line breaks for display. Steffen	[reply] [d/l] [select]
Re: Re: prefix notation in an array by amw1 (Friar) on Mar 26, 2004 at 15:43 UTC
I played around with RecDescent a bit last night after posting. I think for the types of things I'm trying to express it may be more than I need (though it will definately do it) I have pretty strict control over how these things get added (adding clauses via a web form) so I don't need to deal with the vaugeries of human typed input. I came up with this which appears to be working for me. Just a fragment that's going to be inserted into a larger bit of code, no error handling/strict etc. Just a poc at this point. #!/usr/bin/perl + + use Data::Dumper; my $clauses; push(@$clauses, ["==","a","b"]); push(@$clauses, "and"); push(@$clauses, ["==","c","d"]); push(@$clauses, "or"); push(@$clauses, ["==","e","f"]); push(@$clauses, "and"); push(@$clauses, ["==","g","h"]); $Data::Dumper::Indent = 0; + + my $list = BuildList($clauses); print Dumper($list). "\n"; sub BuildList($) { my $clauses = shift(); my $list; while(my $clause = shift(@$clauses)) { if($clause eq "and") { $list = ['AND',[$list], [shift(@$clauses)]]; } elsif($clause eq "or") { $list = ["OR",[$list, BuildList($clauses)]]; } else { $list = $clause } } return($list); } [download] This gives me `['OR',[['AND',[['==','a','b']],[['==','c','d']]],['AND',[['==','e','f' +]],[['==','g','h']]]]]` [download] Thanks for all the input. Update: It's also important to note, that I don't really care about what's in each clause. The clauses are going to be pretty tightly controlled by the creation mechanisim.	[reply] [d/l] [select]