Android 18 has asked for the wisdom of the Perl Monks concerning the following question:

I'm writing a quazi calculator in Parse::RecDescent. It will function as a real calculator for a larger project I'm working on eventually, but only if I can figure this problem out ;)

My grammar so far is below. The problem is that it loops for a _really_ long time if you use ()'s in the string. And when I say long, I'm talking generating 2.8 megs of tracing data. And even then, it ends up ignoring it (as far as I can tell). My thought process was it shouldn't loop unless there are nested ()'s because the first ( should be consumed upon a successful match right?

Anyway here's my grammar. Can someone find what's wrong? 
    startrule   : lv1expr

    lv1expr     : lv2expr ADD lv1expr  {$return = $item[1] + $item[3]}
                | lv2expr SUB lv1expr  {$return = $item[1] - $item[3]}
                | lv2expr

    lv2expr     : lv3expr MULT lv2expr {$return = $item[1] * $item[3]}
                | lv3expr DIV lv2expr  {$return = $item[1] / $item[3]}
                | lv3expr

    lv3expr     : lv4expr EXP lv3expr  {$return = $item[1] ** $item[3]
+}
                | lv4expr

    lv4expr     : '(' startrule ')'    {$return = $item[2]}
                | NUM

    EXP         : '^'
    MULT        : '*'
    DIV         : '/'
    ADD         : '+'
    SUB         : '-'
    NUM         : /\d+(?:\.\d+)?/

[download]


Once bread becomes toast, it can never be bread again.

Replies are listed 'Best First'.
Re: Parse::RecDescent Puzzlement
by educated_foo (Vicar) on May 13, 2002 at 22:18 UTC
    Using the builtin "leftop" directive speeds things up quite a bit, e.g.: 
    lv1expr : <leftop:lv2expr addsub lv1expr>  {
        my @ops = @{$item[1]};
        my $res = shift @ops;
        while (@ops) {
                my ($op, $num) = (shift@ops, shift@ops);
                if ($op eq '+') { $res+= $num }
                else { $res -= $num; }
        }
        $return = $res;
    }
# ...
addsub: /[-+]/

    [download]
    /s
[reply]
[d/l]
Re: Parse::RecDescent Puzzlement
by Mr. Muskrat (Canon) on May 13, 2002 at 22:15 UTC
    I'm not going to try to answer your question, yet.
    You see, I too am trying to learn Parse::RecDescent.
    I will however share a node with you.
    Re: Re: VBA 2 Perl
    Perhaps, the links contained therein will be of help.
    Who says that programmers can't work in the Marketing Department?
    Or is that who says that Marketing people can't program?
[reply]
[reply]
Re: Parse::RecDescent Puzzlement
by krujos (Curate) on May 14, 2002 at 13:10 UTC
    It is hard to say without seeing your implementation, but it seems as to me that '(' and ')' should be checked in the higher levels. 
     
lv1expr   : lv2expr ADD lv1expr
          | '(' lv2expr ADD lv1expr ')'

    [download]

    It's not as pretty as what you have, but it doesn’t recurse as far for things that are technically level one exprs parens shouldn’t change the rule your matching, they are just there for precedence right? You still need to match the sub expr, which is just a lv1expr or lv2expr. Consider how deep you would have to go in the current grammar to parse ((((A + B)*A+C)*D)+X). This seems unnecessary. Again, I don’t know the whole situation, perhaps i am missing something.
    hope this helps, good luck.
[reply]
[d/l]
      I organized it in order of operator precedence, from loosest (+/-) to tightest (^) to the num itself.. ()'s group expression so they should be considered a number, but inside you just call the parser again to evaluate the inside. (yes there are probably better ways to do this but optimization comes later..) I just want do know why it's looping forever on input as simple as "1+(2+3)".

      It perplexes me.. ^_^

      Once bread becomes toast, it can never be bread again.
[reply]
Re: Parse::RecDescent Puzzlement
by jmcnamara (Monsignor) on May 14, 2002 at 15:09 UTC

    Perhaps you could use the demo_calc.pl example in the P::RE distro as a basis for your calulator. It is implemented using closures which may seem a little opaque at first glance but it is robust and functional.

    --
    John.

[reply]
      Ah. I did not know of such an example. Thank you very much I shall look at.

      Once bread becomes toast, it can never be bread again.
[reply]

Back to Seekers of Perl Wisdom