Perl: the Markov chain saw PerlMonks

### Comment on

 ( #3333=superdoc: print w/ replies, xml ) Need Help??
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
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
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'
...
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!
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;
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.
Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• 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! —
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• Outside of code tags, you may need to use entities for some characters:
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?
• See Writeup Formatting Tips and other pages linked from there for more info.

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (4)
As of 2013-05-25 01:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?