Regexp::Grammars Calculator

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Today I started to study with enthusiasm the module Regexp::Grammars. The demo directory of the current distribution Regexp-Grammars-1.001005 is a good starting point. Namely, the demo/demo_calc_class.pl example illustrates how to build a parser for arithmetic expressions

use v5.10;
use warnings;

my $calculator = do{
    use Regexp::Grammars;
    qr{
        <Answer>

        <objrule: Answer>
            <X=Mult> <Op=([+-])> <Y=Answer>
          | <MATCH=Mult>

        <objrule: Mult>
            <X=Pow> <Op=([*/%])> <Y=Mult>
          | <MATCH=Pow>

        <objrule: Pow>
            <X=Term> <Op=(\^)> <Y=Pow>
          | <MATCH=Term>

        <objrule: Term>
               <MATCH=Literal>
          | \( <MATCH=Answer> \)

        <objtoken: Literal>
            <value=( [+-]? \d++ (?: \. \d++ )?+ )>
    }xms
};

while (my $input = <>) {
    my $debug = $input =~ s{^show \s+}{}xms;

    if ($input =~ $calculator) {
        if ($debug) {
            use Data::Dumper 'Dumper';
            warn Dumper \%/;
        }
        else {
            say '--> ', $/{Answer}->eval();
        }
    }
}

sub Answer::eval {
    my ($self) = @_;

    my $x = $self->{X}->eval();
    my $y = $self->{Y}->eval();
    return $self->{Op} eq '+'  ?  $x + $y
         :                        $x - $y;
}

sub Mult::eval {
    my ($self) = @_;

    my $x = $self->{X}->eval();
    my $y = $self->{Y}->eval();
    return $self->{Op} eq '*'  ?  $x * $y
         : $self->{Op} eq '/'  ?  $x / $y
         :                        $x % $y;
}

sub Pow::eval {
    my ($self) = @_;

    return $self->{X}->eval() **  $self->{Y}->eval();
}

sub Term::eval {
    my ($self) = @_;

    return $self->{""}->eval();
}

sub Literal::eval {
    my ($self) = @_;

    return $self->{value};
}
[download]

But the interpreter does not match the traditional left associative semantics of the minus and division operators. See an execution:

$ perl5_10_1  demo_calc_class.pl
2-3-5
--> 4
[download]

The result must be -6. The same occurs with the division:

$ perl5_10_1  demo_calc_class.pl
8/4/2
--> 4
[download]

The expected result is 1.

Does anyone knows how to modify the grammar to make it work with the ordinary left-associative semantic?

Comment on Regexp::Grammars Calculator Select or Download Code

Replies are listed 'Best First'.
Re: Regexp::Grammars Calculator by jethro (Monsignor) on Aug 15, 2009 at 12:29 UTC
I have only done a quick look at Regexp::Grammar up to now, so I don't know the exact grammar you need, but basically you can reach your goal by first switching the operands around so that for example `<X=Mult> <Op=([+-])> <Y=Answer>` becomes `<X=Answer> <Op=([+-])> <Y=Mult>` This of course creates a left recursive grammar which you need to remove. So you need to change the grammar according to one of the recipes mentioned in Eliminating Left Recursion in Parse::RecDescent	[reply] [d/l] [select]
Re: Regexp::Grammars Calculator by roboticus (Chancellor) on Aug 15, 2009 at 13:58 UTC
Your grammar accepts "2-3-5" as: `Answer Op=- / \ Mult Answer Pow Op=- Term / \ Literal Mult Answer "2" Pow Mult Term Pow Literal Term "3" Literal "5"` [download] So it's evaluating as 2 - (3 - 5), as the grammar allows. If perhaps you can write your grammar in a more left-recursive fashion, such as: `<objrule: Answer> <X=Answer> <Op=([+-])> <Y=Mult> \| <MATCH=Mult>` [download] This sort of transformation carried throughout the grammar might do the trick. Disclaimer: I've not written a compiler, nor played around with grammars in quite a while, so take this with a grain of salt... ...roboticus	[reply] [d/l] [select]
Re: Regexp::Grammars Calculator by blokhead (Monsignor) on Aug 15, 2009 at 23:42 UTC
I couldn't find anything (after a very superficial look) in the documentation for Regexp::Grammars about associativity. If the parser-generator doesn't support it directly, then you'll have to get associativity and precedence by rewriting the grammar. In Re: Left-associative binary operators in Parse::RecDescent, I give an overview of how to rewrite a grammar for operator precedence & associativity. It might suit your needs. blokhead	[reply]


We don't bite newbies here... much
	PerlMonks