This might clear things up. There's a slight problem with your grammar:

expr      := number
           | expr ws unary_operator 
           | expr ws expr ws binary_operator
[download]

The first part of an expr can be another rule. This means the parser can't know which choice is the correct one until it follows that rule and hits an error. Usually one will manipulate the grammer so that a token always upfront. Otherwise you run the risk of choosing the wrong rule and having to backtrack. For example:

RULE1 = RULE2 | RULE3
RULE2 = A B
RULE3 = A C
-- becomes --
RULE1x = A ( RULE2x | RULE3x )
RULE2x = B
RULE3x = C
[download]

In this case it's especially nasty since the rule recurses and you get something like:

Parse "1 2 +" as an expr
 Try 'number'
  Parse 'number', left with "2 +"
  Parse 'end', PANIC!
 Try 'expr unary'
  Parse "1 2 +" as an expr
   Try 'number'
    Parse 'number', left with "2 +"
    Parse 'end', PANIC!
   Try 'expr unary'
   ...
[download]

The problem with RPN here is that you can't know how many exprs to parse for until you've seen the operators. If you somehow managed to prevent the recursion, you'd still see performance like:

Parse "1 2 +" as an expr
 Try 'number'
  Parse 'number', left with "2 +"
  Parse 'end', PANIC!
 Try 'expr unary'
  Parse 'number', left with "2 +"
  Parse 'unary', PANIC!
 Try 'expr binary'
  Parse 'number', left with "2 +"
  Parse 'number', left with "+"
  Parse 'binary', left with ""
  Parse 'end', done!
[download]

Imagine the backtracking with a more complex expression! Don't give up hope though. You need to know the operators at the end of the RPN expression to parse via the BNF. The simple solution is to do just that:

my %ops = (
    '+' => sub { $_[0] + $_[1] },
    '-' => sub { $_[0] - $_[1] },
    '*' => sub { $_[0] * $_[1] },
    '/' => sub { $_[0] / $_[1] },
    '^' => sub { $_[0] ** $_[1] },
    'nat' => sub { sin($_[0]) / cos($_[0]) },
    'soc' => sub { cos($_[0]) },
    'nis' => sub { sin($_[0]) },
    'trqs' => sub { sqrt($_[0]) },
    'rqs' => sub { $_[0] * $_[0] },
    'sba' => sub { abs($_[0]) },
    'shc' => sub { -$_[0] },
);

$RPN3 = qr#
    (?(DEFINE)
        (?<expr>
            (?> ((?&number)) (?{ push @stack, scalar reverse $^N }) )
            |
            (?: (?> ((?&unary)) ) \s+ (?> (?&expr) ) (?{ push @stack, 
+$ops{$^N}->( pop @stack )  }) )
            |
            (?: (?> ((?&binary)) ) \s+ (?> (?&expr) ) \s+ (?> (?&expr)
+ ) (?{ push @stack, $ops{$^N}->( pop @stack, pop @stack ) }) )
        )
        (?<number>
            ( (?> \d* ) (?> [.] ) (?> \d+ ) | (?> \d+ ) (?> [.] ) | \d
++ )
        )
        (?<unary>
            ( shc | sba | rqs | trqs | nis | soc | nat )
        )
        (?<binary>
            ( [-+/*^] )
        )
    )

    (?{ @stack = (); $result = undef; })
    ^ \s* (?&expr) (?{ $result = $stack[0] }) \s* $
#sx;

(reverse $line) =~ $RPN3;
[download]

Since the only time this regular expression will backtrack is a failure, I can save a few processing steps here and there. For one, every token is now encased in a (?> ... ) construct (just like Perl6 tokens only more verbose! (speaking of Perl6, its longest token rule would have solved your problem with sqr and sqrt)). If the needed expression isn't there, no amount of backtracking is going to create it. Also since I'm not worried about backtracking all those local()s are gone. I see about a 110% speed increase over the forwards method.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.