How to speed up a grammar

2009-06-06 Thread Richard Hainsworth 

Leon Timmermans wrote:

If you want to write a fast parser for XML, preventing backtracking is
going to be quite essential. I suspect the problem is your grammar,
not the grammar engine itself. You could post it to perl6-users and
ask for advice on it.

Leon


Below is the grammar.

I am only interested in tag names xs1:text xs1:playlist (and within 
playlist) xs1:item

The only attributes I want are 'author', 'title', and 'id'

grammar sony_grammar;
rule TOP {
 ^
 xmldecl?
 root=element
 $
}

rule xmldecl {
  '?xml'
  'version'  '=' '' $version=-[\]+ ''
  'encoding' '=' '' $encoding=-[\]+ ''
  '?'
}

rule element {
 '' name attribute*
 [
 | '/'
 | '' element* '/' $name ''
 ]
}

rule attribute { name '=' '' $value=-[]* '' }

token name { namespace? $ename=ident }
token namespace { ident ':' }

Re: RPN calculator in Perl 6

2009-06-06 Thread Daniel Carrera 

Daniel Ruoso wrote:

TIMTOWTDI ;)


The objective of the blog was more about the learning + teaching 
experience than anything else.




http://sial.org/pbot/37075



 % perl rpn.pl 2 2 +
Semicolon seems to be missing at rpn.pl line 2.
String found where operator expected at rpn.pl line 13, near where '+'
(Do you need to predeclare where?)
Array found where operator expected at rpn.pl line 14, near ] 
(Missing operator before  ?)
Scalar found where operator expected at rpn.pl line 14, near @($a
(Missing operator before $a?)
String found where operator expected at rpn.pl line 17, near where '-'
(Do you need to predeclare where?)
Array found where operator expected at rpn.pl line 18, near ] 
(Missing operator before  ?)
Scalar found where operator expected at rpn.pl line 18, near @($a
(Missing operator before $a?)
String found where operator expected at rpn.pl line 21, near where '*'
(Do you need to predeclare where?)
Array found where operator expected at rpn.pl line 22, near *] 
(Missing operator before  ?)
Scalar found where operator expected at rpn.pl line 22, near @($a
(Missing operator before $a?)
Semicolon seems to be missing at rpn.pl line 24.
String found where operator expected at rpn.pl line 25, near where '/'
(Do you need to predeclare where?)
Semicolon seems to be missing at rpn.pl line 28.
String found where operator expected at rpn.pl line 30, near fail 
'Error parsing expression near '

(Do you need to predeclare fail?)
Array found where operator expected at rpn.pl line 33, near ] 
(Missing operator before  ?)
Bareword found where operator expected at rpn.pl line 33, near @*ARGS
(Missing operator before ARGS?)
Operator or semicolon missing before *ARGS at rpn.pl line 33.
Ambiguous use of * resolved as operator * at rpn.pl line 33.
syntax error at rpn.pl line 1, near \.
Missing right curly or square bracket at rpn.pl line 34, at end of line
Execution of rpn.pl aborted due to compilation errors.

Re: RPN calculator in Perl 6

2009-06-06 Thread Daniel Carrera 

Daniel Carrera wrote:

http://sial.org/pbot/37075


 % perl rpn.pl 2 2 +


Tee hee... that should have been perl6. :-)

Ok, try again:

% perl6 rpn.pl 2 2+
2 2

Re: How to speed up a grammar

2009-06-06 Thread Minimiscience 

On Jun 6, 2009, at 10:32 AM, Richard Hainsworth wrote:

rule element {
'' name attribute*
[
| '/'
| '' element* '/' $name ''
]
}


This is just a wild, uneducated, possibly delusional guess, but I  
don't think that vertical bar before the '/' should be there.  I  
think it might be causing the grammar engine to check whether it can  
omit the ending of each tag and attach it to the enclosing tag  
instead, which it can't confirm without examining the whole file at  
least once for each tag.


-- Minimiscience

Re: RPN calculator in Perl 6

2009-06-06 Thread Minimiscience 
[I just realized I sent this directly to Daniel rather than to the  
list, so for the benefit of onlookers...]


On Jun 6, 2009, at 1:51 PM, Daniel Carrera wrote:

Daniel Ruoso wrote:

Yes... that's what wasn't implemented... But now it is ;)
http://sial.org/pbot/37085


Close, but...

% perl6 rpn.pl 5 4 + 3 / 5 3 - *
-6

That should be a positive 6.


I think I see the problem (assuming it hasn't already been pointed out  
off-list).  The infix:rpn(@a, $op where ...) operators call .shift  
on the arrays to get the operands, yet the infix:rpn(... , $b where / 
Num/) operators place the numbers on the *end* of the stack, where  
the next reverse-polish operator should read them from.  Thus, when  
the '-' is processed, the stack is 3 5 3, where the first three is  
the result of 5 4 + 3 /, and the first two numbers are shifted off  
for subtraction rather than the last two.  In order to fix this,  
either change the first two infix:rpn() functions so that they place  
new numbers at the *beginning* of the array, or else change each  
occurrence of


   my $ls = @a.shift;
   my $rs = @a.shift;

To:

   my $rs = @a.pop;
   my $ls = @a.pop;

(Note that, in addition to the use of .pop, $rs is now acquired before  
$ls.)


At least, I think that's how it works.

-- Minimiscience