petit parser longest match
I talked to Lukas two years ago about parsing the longest match [1]. He committed it to PetitBeta back then. Now I need it and I had a look at the current parsers but didnât find one that can do the same. Is there a parser that can do longest match? If not I would propose adding that to the default petit parser package. Lukasâ proposal back then was LongestChoiceParser>>parseOn: aStream | start element longestEnd longestElement | start := aStream position. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. (longestEnd isNil or: [ longestEnd < aStream position ]) ifTrue: [ longestEnd := aStream position. longestElement := element ]. aStream position: start ]. aStream position: longestEnd. ^ longestElement Norbert [1] http://www.iam.unibe.ch/pipermail/moose-dev/2011-July/009365.html
Ho about this (replacement for yours, or just replace in PPChoiceParser - but it will result in different behavior for that method outside of your particular parser, so beware): parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered." | element longest | longest := #( 0 nil ). 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element I had a need for it in the past (and, just now, in fact - so minimally tested just now). -cbc On Wed, Nov 20, 2013 at 2:15 AM, Norbert Hartl <norbert@hartl.name> wrote:
I talked to Lukas two years ago about parsing the longest match [1]. He committed it to PetitBeta back then. Now I need it and I had a look at the current parsers but didnât find one that can do the same. Is there a parser that can do longest match?
If not I would propose adding that to the default petit parser package. Lukasâ proposal back then was
LongestChoiceParser>>parseOn: aStream | start element longestEnd longestElement | start := aStream position. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. (longestEnd isNil or: [ longestEnd < aStream position ]) ifTrue: [ longestEnd := aStream position. longestElement := element ]. aStream position: start ]. aStream position: longestEnd. ^ longestElement
Norbert
[1] http://www.iam.unibe.ch/pipermail/moose-dev/2011-July/009365.html
Actually, do this [the #( 0 nil ) meant it was shared with ALL choice parsers forever - not a good choice]. parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered." | element longest | longest := Array with: 0 with: nil. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element On Wed, Nov 20, 2013 at 1:35 PM, Chris Cunningham <cunningham.cb@gmail.com>wrote:
Ho about this (replacement for yours, or just replace in PPChoiceParser - but it will result in different behavior for that method outside of your particular parser, so beware):
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := #( 0 nil ). 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
I had a need for it in the past (and, just now, in fact - so minimally tested just now).
-cbc
On Wed, Nov 20, 2013 at 2:15 AM, Norbert Hartl <norbert@hartl.name> wrote:
I talked to Lukas two years ago about parsing the longest match [1]. He committed it to PetitBeta back then. Now I need it and I had a look at the current parsers but didnât find one that can do the same. Is there a parser that can do longest match?
If not I would propose adding that to the default petit parser package. Lukasâ proposal back then was
LongestChoiceParser>>parseOn: aStream | start element longestEnd longestElement | start := aStream position. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. (longestEnd isNil or: [ longestEnd < aStream position ]) ifTrue: [ longestEnd := aStream position. longestElement := element ]. aStream position: start ]. aStream position: longestEnd. ^ longestElement
Norbert
[1] http://www.iam.unibe.ch/pipermail/moose-dev/2011-July/009365.html
ehh, ignore this for now. Neither is working well enough. If I get something working well, I'll post back. On Wed, Nov 20, 2013 at 1:45 PM, Chris Cunningham <cunningham.cb@gmail.com>wrote:
Actually, do this [the #( 0 nil ) meant it was shared with ALL choice parsers forever - not a good choice].
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := Array with: 0 with: nil. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
On Wed, Nov 20, 2013 at 1:35 PM, Chris Cunningham <cunningham.cb@gmail.com
wrote:
Ho about this (replacement for yours, or just replace in PPChoiceParser - but it will result in different behavior for that method outside of your particular parser, so beware):
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := #( 0 nil ). 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
I had a need for it in the past (and, just now, in fact - so minimally tested just now).
-cbc
On Wed, Nov 20, 2013 at 2:15 AM, Norbert Hartl <norbert@hartl.name>wrote:
I talked to Lukas two years ago about parsing the longest match [1]. He committed it to PetitBeta back then. Now I need it and I had a look at the current parsers but didnât find one that can do the same. Is there a parser that can do longest match?
If not I would propose adding that to the default petit parser package. Lukasâ proposal back then was
LongestChoiceParser>>parseOn: aStream | start element longestEnd longestElement | start := aStream position. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. (longestEnd isNil or: [ longestEnd < aStream position ]) ifTrue: [ longestEnd := aStream position. longestElement := element ]. aStream position: start ]. aStream position: longestEnd. ^ longestElement
Norbert
[1] http://www.iam.unibe.ch/pipermail/moose-dev/2011-July/009365.html
I'm not sure what you are trying to improve. It works quite well :) Norbert
Am 20.11.2013 um 22:59 schrieb Chris Cunningham <cunningham.cb@gmail.com>:
ehh, ignore this for now. Neither is working well enough. If I get something working well, I'll post back.
On Wed, Nov 20, 2013 at 1:45 PM, Chris Cunningham <cunningham.cb@gmail.com> wrote: Actually, do this [the #( 0 nil ) meant it was shared with ALL choice parsers forever - not a good choice].
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := Array with: 0 with: nil. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
On Wed, Nov 20, 2013 at 1:35 PM, Chris Cunningham <cunningham.cb@gmail.com> wrote: Ho about this (replacement for yours, or just replace in PPChoiceParser - but it will result in different behavior for that method outside of your particular parser, so beware):
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := #( 0 nil ). 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
I had a need for it in the past (and, just now, in fact - so minimally tested just now).
-cbc
On Wed, Nov 20, 2013 at 2:15 AM, Norbert Hartl <norbert@hartl.name> wrote: I talked to Lukas two years ago about parsing the longest match [1]. He committed it to PetitBeta back then. Now I need it and I had a look at the current parsers but didnât find one that can do the same. Is there a parser that can do longest match?
If not I would propose adding that to the default petit parser package. Lukasâ proposal back then was
LongestChoiceParser>>parseOn: aStream | start element longestEnd longestElement | start := aStream position. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. (longestEnd isNil or: [ longestEnd < aStream position ]) ifTrue: [ longestEnd := aStream position. longestElement := element ]. aStream position: start ]. aStream position: longestEnd. ^ longestElement
Norbert
[1] http://www.iam.unibe.ch/pipermail/moose-dev/2011-July/009365.html
There are several things wrong with it, actually. First, in my example, I never did actually return the longest error - I just set the location to the longest error location. Not right at all. Next, setting the stream to the position of the error on the choice is not a good idea. The problem is when you have more than 1 choice depth. So, the first choice goes down path 1, which calls another choice (eventually), which fails and resets the location to some point further on in the stream. The the rollback to the first choice seems to get fouled up and doesn't work quite right. Probably. In any case, playing with how it is storing and returning, I am getting wildly different points of where the track fails. Finally, the array at each choice doesn't necessarily pick the furthest failure. If you consider a 4 choice depth parser (which is roughly what I'm working with - parsing Java source code), the 4th choice will fail on a couple of paths, and then eventually work on one. This might then return back to the 3rd choice successfully (so no error, so no returned error from that choice) and then later fails. That particular path might be much shorter (that it made it through) than the one that failed earlier (maybe a much more complex but also more consuming path, for example). The question is what exactly are you (we) looking for. * I think we want to know what was the parsing path the best describes the source file we are parsing, and where is it failing to parse. * I would also like to know what the path was that arrived at that point (the context) so that I can decide how to either fix the parser (if it is wrong) or fix the source. So, I'm still looking for a better answer than the two I tried to provide earlier. -cbc On Wed, Nov 20, 2013 at 5:03 PM, Norbert Hartl <norbert@hartl.name> wrote:
I'm not sure what you are trying to improve. It works quite well :)
Norbert
Am 20.11.2013 um 22:59 schrieb Chris Cunningham <cunningham.cb@gmail.com>:
ehh, ignore this for now. Neither is working well enough. If I get something working well, I'll post back.
On Wed, Nov 20, 2013 at 1:45 PM, Chris Cunningham <cunningham.cb@gmail.com
wrote:
Actually, do this [the #( 0 nil ) meant it was shared with ALL choice parsers forever - not a good choice].
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := Array with: 0 with: nil. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
On Wed, Nov 20, 2013 at 1:35 PM, Chris Cunningham < cunningham.cb@gmail.com> wrote:
Ho about this (replacement for yours, or just replace in PPChoiceParser - but it will result in different behavior for that method outside of your particular parser, so beware):
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := #( 0 nil ). 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
I had a need for it in the past (and, just now, in fact - so minimally tested just now).
-cbc
On Wed, Nov 20, 2013 at 2:15 AM, Norbert Hartl <norbert@hartl.name>wrote:
I talked to Lukas two years ago about parsing the longest match [1]. He committed it to PetitBeta back then. Now I need it and I had a look at the current parsers but didnât find one that can do the same. Is there a parser that can do longest match?
If not I would propose adding that to the default petit parser package. Lukasâ proposal back then was
LongestChoiceParser>>parseOn: aStream | start element longestEnd longestElement | start := aStream position. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. (longestEnd isNil or: [ longestEnd < aStream position ]) ifTrue: [ longestEnd := aStream position. longestElement := element ]. aStream position: start ]. aStream position: longestEnd. ^ longestElement
Norbert
[1] http://www.iam.unibe.ch/pipermail/moose-dev/2011-July/009365.html
I have a version I'm happier with, but it includes a fair amount of invasive changes. Latest .mcz in http://www.smalltalkhub.com/#!/~cbc/PetitParser It does change PPChoiceParser and has a significant change to PPFailure as well (from a previous enhancement). -cbc On Thu, Nov 21, 2013 at 8:10 AM, Chris Cunningham <cunningham.cb@gmail.com>wrote:
There are several things wrong with it, actually.
First, in my example, I never did actually return the longest error - I just set the location to the longest error location. Not right at all.
Next, setting the stream to the position of the error on the choice is not a good idea. The problem is when you have more than 1 choice depth. So, the first choice goes down path 1, which calls another choice (eventually), which fails and resets the location to some point further on in the stream. The the rollback to the first choice seems to get fouled up and doesn't work quite right. Probably. In any case, playing with how it is storing and returning, I am getting wildly different points of where the track fails.
Finally, the array at each choice doesn't necessarily pick the furthest failure. If you consider a 4 choice depth parser (which is roughly what I'm working with - parsing Java source code), the 4th choice will fail on a couple of paths, and then eventually work on one. This might then return back to the 3rd choice successfully (so no error, so no returned error from that choice) and then later fails. That particular path might be much shorter (that it made it through) than the one that failed earlier (maybe a much more complex but also more consuming path, for example).
The question is what exactly are you (we) looking for. * I think we want to know what was the parsing path the best describes the source file we are parsing, and where is it failing to parse. * I would also like to know what the path was that arrived at that point (the context) so that I can decide how to either fix the parser (if it is wrong) or fix the source.
So, I'm still looking for a better answer than the two I tried to provide earlier.
-cbc
On Wed, Nov 20, 2013 at 5:03 PM, Norbert Hartl <norbert@hartl.name> wrote:
I'm not sure what you are trying to improve. It works quite well :)
Norbert
Am 20.11.2013 um 22:59 schrieb Chris Cunningham <cunningham.cb@gmail.com
:
ehh, ignore this for now. Neither is working well enough. If I get something working well, I'll post back.
On Wed, Nov 20, 2013 at 1:45 PM, Chris Cunningham < cunningham.cb@gmail.com> wrote:
Actually, do this [the #( 0 nil ) meant it was shared with ALL choice parsers forever - not a good choice].
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := Array with: 0 with: nil. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
On Wed, Nov 20, 2013 at 1:35 PM, Chris Cunningham < cunningham.cb@gmail.com> wrote:
Ho about this (replacement for yours, or just replace in PPChoiceParser - but it will result in different behavior for that method outside of your particular parser, so beware):
parseOn: aStream "This is optimized code that avoids unnecessary block activations, do not change. When all choices fail, the last failure is answered."
| element longest | longest := #( 0 nil ). 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. element isPetitFailure ifTrue: [ aStream position > longest first ifTrue: [ longest at: 1 put: aStream position; at: 2 put: element ] ] ifFalse: [ ^ element ] ]. aStream position: longest first. ^ element
I had a need for it in the past (and, just now, in fact - so minimally tested just now).
-cbc
On Wed, Nov 20, 2013 at 2:15 AM, Norbert Hartl <norbert@hartl.name>wrote:
I talked to Lukas two years ago about parsing the longest match [1]. He committed it to PetitBeta back then. Now I need it and I had a look at the current parsers but didnât find one that can do the same. Is there a parser that can do longest match?
If not I would propose adding that to the default petit parser package. Lukasâ proposal back then was
LongestChoiceParser>>parseOn: aStream | start element longestEnd longestElement | start := aStream position. 1 to: parsers size do: [ :index | element := (parsers at: index) parseOn: aStream. (longestEnd isNil or: [ longestEnd < aStream position ]) ifTrue: [ longestEnd := aStream position. longestElement := element ]. aStream position: start ]. aStream position: longestEnd. ^ longestElement
Norbert
[1] http://www.iam.unibe.ch/pipermail/moose-dev/2011-July/009365.html
participants (2)
-
Chris Cunningham -
Norbert Hartl