25 Jun
2011
25 Jun
'11
8:48 p.m.
Am 25.06.2011 um 18:01 schrieb Lukas Renggli:
Yes, this is essentially the trick.
Have a look at some of the other references to PPFailure, for example
- in PPXmlParser>>element we ensure that the open and close tag are the same,
- in PPSmalltalkGrammar>>number an external parser is used to validate
and extract the number, and
- in PPObjectTest>>testFibonacci the input must be a fibonacci
sequence (quite complicated code).
Now this seems to be quite a common pattern, so it might be worth to
add a helper method to PetitParser. I imagine something along the
lines of
(#digit asParser , #digit asParser)
condition: [ :nodes | nodes first = nodes second ]
message: 'not the same value'
Did you see the class comment and the method comment in the factory
method of PPMemoizedParser?
PPParser>>memoized
"Answer a new memoized parser, for refraining redundant computations.
This ensures polynomial time O(n^4) for left-recursive grammars and
O(n^3) for non left-recursive grammars in the worst case. Not
necessary for most grammars that are carefully written and in O(n)
anyway."
^ PPMemoizedParser on: self
So, this is to cache repeated parses of the same rule, at the same
position, and in the same input stream. In almost all cases it is not
useful and actually slows things down. In rare cases it is necessary,
but then you should probably rather fix your grammar.
The basic idea behind memoization is explained in "Packrat parsing:
simple, powerful, lazy, linear time" by Bryan Ford
(http://arxiv.org/pdf/cs/0603077). The implementation of PetitParser
is actually based on ideas presented in "Packrat Parsers Can Support
Left Recursion" by Alessandro Warth
(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.7466&rep=re…)ype=pdf).
Note that the PetitParser implementation of PPMemoizedParser has the
same problem as the one of Warth leading to invalid parses on some
PEGs. Details can be found in "Direct Left-Recursive Parsing
Expressing Grammars" by Laurence Tratt
(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.7945&rep=r…)ype=pdf).
Thanks for the pointers. I hope I find some time to get into this. I played a little with
memoized parser because my grammar used some left recursive rules. But with memoized
parsers I had pretty strange effects with white spaces and trimming. So I wanted to know
how it works to test this exactly. At the end I reworked the grammar to be not left
recursive which gave me an additional speed up as well.
thanks,
Norbert
Is there a way to do something like:
#digit asParser, 'same digit that I just parsed' asParser ?
I'm not sure if there is a possibility in declarative way. But you can work
on the products of the individual parsers. You can do it like this:
twoEqualDigits
^ #digit asParser, #digit asParser ==> [:nodes|
(nodes first = nodes second)
ifTrue: [ nodes ]
ifFalse: [ PPFailure message: 'not the same value' at: 0]]
I snooped
around and saw PPMemoizedParser, but didn't exactly understand the
test for it.
I would like to know exactly, too :)