Re: [fonc] Debugging PEGs and Packrats
On 29 December 2011 09:04, John Leuner wrote: >>> I think the next step I would take (if that wasn't sufficient) is to >>> create a test suite that tests each grammar rule independently, >>> successively building up to the complex input that is failing. >> >> I'd been doing this for terminals, but it seems like non-terminals get >> harder to write as unit tests, parser state and all. I suppose integration >> tests could work, but it seems the more complex the grammatical structure, >> the more I experience diminishing returns with tests. I just end up with >> tests that fail mysteriously which is my original problem. Do you have any >> examples about? I wonder if maybe there's something essential I'm failing >> to understand. Maybe looking at your tests might send me along to an a-ha >> moment. > > I don't have any tests to show you but I will try to create an example of > what I mean. (I assume that the parser will fail if it cannot parse the > entire input). > > Given the following grammar rules: > > identifier = letter (letter | digit)* > > method-call = identifier (ws+ argument)+ > > (ws matches white space) > > argument = number-literal | identifier > > number-literal = digit+ > > > I would write tests something like this: > > test(number-literal, "1234") > test(identifier, "foo") > test(argument, "5") > test(argument, "bar") > test(method-call, "method a b c 3") > > > Obviously this is a made-up example but I hope it shows you what I mean. For some real-world examples you might want to check the PetitParser image. The plain source code for the tests of the grammars for the following languages is also visible here: Smalltalk: http://www.lukas-renggli.ch/dropbox/petitparser/grammars/PetitSmalltalk-Tests.st JSON: http://www.lukas-renggli.ch/dropbox/petitparser/grammars/PetitJson-Tests.st XML: http://www.lukas-renggli.ch/dropbox/petitparser/grammars/PetitXml-Tests.st The Smalltalk one is probably the most systematic, testing every idividual production of the grammar. Also interesting in this context might be our work on grammar test coverage: See Section 4.3 of http://scg.unibe.ch/archive/papers/Berg11b-Profiling.pdf. Lukas -- Lukas Renggli www.lukas-renggli.ch ___ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
>> I think the next step I would take (if that wasn't sufficient) is to >> create a test suite that tests each grammar rule independently, >> successively building up to the complex input that is failing. > > I'd been doing this for terminals, but it seems like non-terminals get > harder to write as unit tests, parser state and all. I suppose integration > tests could work, but it seems the more complex the grammatical structure, > the more I experience diminishing returns with tests. I just end up with > tests that fail mysteriously which is my original problem. Do you have any > examples about? I wonder if maybe there's something essential I'm failing > to understand. Maybe looking at your tests might send me along to an a-ha > moment. I don't have any tests to show you but I will try to create an example of what I mean. (I assume that the parser will fail if it cannot parse the entire input). Given the following grammar rules: identifier = letter (letter | digit)* method-call = identifier (ws+ argument)+ (ws matches white space) argument = number-literal | identifier number-literal = digit+ I would write tests something like this: test(number-literal, "1234") test(identifier, "foo") test(argument, "5") test(argument, "bar") test(method-call, "method a b c 3") Obviously this is a made-up example but I hope it shows you what I mean. John > Thanks again! > >> John >> >> >> On Tue, 2011-12-13 at 23:17 -0800, Casey Ransberger wrote: >>> I know this has come up before. Hopefully I'm not about to repeat a >>> lot. >>> >>> Debugging this stuff just seems really hard. And significantly harder >>> than what I've experienced working with e.g. Yacc. >>> >>> Hypothesis: Yacc had a lot of time to bake before I ever found it. PEGs >>> are new, so there's been less overall experience with debugging them. >>> >>> I've experimented in what little time I can devote with OMeta, >>> PetitParser, and Treetop. The debugging experience has been roughly >>> consistent across all three. >>> >>> One particular issue which has bugged me: memoization seems to carry a >>> lot of instance-state that's really hard to comprehend when the grammar >>> isn't working as I expect. It's just really hard to use that ocean of >>> information to figure out what I've done wrong. >>> >>> Given that with these new parsing technologies, we're pretty lucky to >>> see "parse error" as an error message, I can't help but think that it's >>> worth studying debugging strategies. Heh. :D I'm really not >>> complaining, I'm just pointing it out. >>> >>> Has anyone here found any technique(s) which makes debugging a grammar >>> written for a PEG/packrat less of a pain in the butt? >>> >>> I'd be really interested in hearing about it. >>> >>> >>> >>> ___ >>> fonc mailing list >>> [email protected] >>> http://vpri.org/mailman/listinfo/fonc >> >> >> >> ___ >> fonc mailing list >> [email protected] >> http://vpri.org/mailman/listinfo/fonc > ___ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
Inline. Thanks for your reply! On Dec 28, 2011, at 12:20 PM, John Leuner wrote: > Hi Casey > > In my OMeta implementations I have found that simply recording the > position of the deepest error and then printing out the remaining input > text was sufficient to debug my grammars. This is something I hadn't thought of. It would tell one where the grammar choked. That's interesting. > I think the next step I would take (if that wasn't sufficient) is to > create a test suite that tests each grammar rule independently, > successively building up to the complex input that is failing. I'd been doing this for terminals, but it seems like non-terminals get harder to write as unit tests, parser state and all. I suppose integration tests could work, but it seems the more complex the grammatical structure, the more I experience diminishing returns with tests. I just end up with tests that fail mysteriously which is my original problem. Do you have any examples about? I wonder if maybe there's something essential I'm failing to understand. Maybe looking at your tests might send me along to an a-ha moment. Thanks again! > John > > > On Tue, 2011-12-13 at 23:17 -0800, Casey Ransberger wrote: >> I know this has come up before. Hopefully I'm not about to repeat a lot. >> >> Debugging this stuff just seems really hard. And significantly harder than >> what I've experienced working with e.g. Yacc. >> >> Hypothesis: Yacc had a lot of time to bake before I ever found it. PEGs are >> new, so there's been less overall experience with debugging them. >> >> I've experimented in what little time I can devote with OMeta, PetitParser, >> and Treetop. The debugging experience has been roughly consistent across all >> three. >> >> One particular issue which has bugged me: memoization seems to carry a lot >> of instance-state that's really hard to comprehend when the grammar isn't >> working as I expect. It's just really hard to use that ocean of information >> to figure out what I've done wrong. >> >> Given that with these new parsing technologies, we're pretty lucky to see >> "parse error" as an error message, I can't help but think that it's worth >> studying debugging strategies. Heh. :D I'm really not complaining, I'm just >> pointing it out. >> >> Has anyone here found any technique(s) which makes debugging a grammar >> written for a PEG/packrat less of a pain in the butt? >> >> I'd be really interested in hearing about it. >> >> >> >> ___ >> fonc mailing list >> [email protected] >> http://vpri.org/mailman/listinfo/fonc > > > > ___ > fonc mailing list > [email protected] > http://vpri.org/mailman/listinfo/fonc ___ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
Hi Casey In my OMeta implementations I have found that simply recording the position of the deepest error and then printing out the remaining input text was sufficient to debug my grammars. I think the next step I would take (if that wasn't sufficient) is to create a test suite that tests each grammar rule independently, successively building up to the complex input that is failing. John On Tue, 2011-12-13 at 23:17 -0800, Casey Ransberger wrote: > I know this has come up before. Hopefully I'm not about to repeat a lot. > > Debugging this stuff just seems really hard. And significantly harder than > what I've experienced working with e.g. Yacc. > > Hypothesis: Yacc had a lot of time to bake before I ever found it. PEGs are > new, so there's been less overall experience with debugging them. > > I've experimented in what little time I can devote with OMeta, PetitParser, > and Treetop. The debugging experience has been roughly consistent across all > three. > > One particular issue which has bugged me: memoization seems to carry a lot of > instance-state that's really hard to comprehend when the grammar isn't > working as I expect. It's just really hard to use that ocean of information > to figure out what I've done wrong. > > Given that with these new parsing technologies, we're pretty lucky to see > "parse error" as an error message, I can't help but think that it's worth > studying debugging strategies. Heh. :D I'm really not complaining, I'm just > pointing it out. > > Has anyone here found any technique(s) which makes debugging a grammar > written for a PEG/packrat less of a pain in the butt? > > I'd be really interested in hearing about it. > > > > ___ > fonc mailing list > [email protected] > http://vpri.org/mailman/listinfo/fonc ___ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
http://languagejs.com/ is a JavaScript PEG library written for the Cappuccino project that claims to have a good approach to error handling. >From the page: The most unique addition Language.js makes to PEG is how it handles errors. > No parse ever fails in Language.js, instead SyntaxErrorNodes are placed > into the resultant tree. This makes it trivial to do things like write > syntax highlighters that have live error reporting. This also means that > Language.js is very competent at handling multiple errors (as opposed to > aborting on the first one that is reached). > > A new operator designed specifically to handle errors trivially and > declaratively is added on top of the normal PEG operators. The naughty OR > operator (%) behaves just like the choice operator (/), but only gets used > if the parse first completely fails. Because of this, performance is > guaranteed to never be affected, regardless of how many error rules you add > to the grammar. Thus, you are allowed to offer alternative "incorrect but > valid" grammars to provide increasingly useful errors to your users. > ___ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
At Wed, 14 Dec 2011 09:35:06 +0100,
Lukas Renggli wrote:
>
> > I've experimented in what little time I can devote with OMeta, PetitParser,
> > and Treetop. The debugging experience has been roughly consistent across
> > all three.
>
> Casey, did you try the PetitParser IDE? If so, what did you miss?
>
> If not, please check it out
> (http://jenkins.lukas-renggli.ch/job/PetitParser/lastSuccessfulBuild/artifact/PetitParser-OneClick.zip).
> It comes with dedicated tools for grammars (editor, visualizations,
> profiler, debugger, ...). An earlier version of the tool is described
> in Section 3.5 of this paper
> (http://scg.unibe.ch/archive/papers/Reng10cDynamicGrammars.pdf). We
> are currently working on an improved IDE with grammar refactorings.
Wow. Pretty cool.
I'm playing with it a bit, and trying to figure out how I'd detect
an error in my grammar. I introduced a bug in PPJsonGrammer by
changing string to read (omit the last $" asParser):
string
^ $" asParser , char star
and chose "Dynamic" and put {"a": 1, "b": 2} and said "parse". I see
the tree and the parse goes as far as position 3. But of course, it
is not easy to tell that #string has the problem from this. (I'd
think that this is the nature of grammar writing, where the parser
basically does not know what makes sense, especially if there are
other choices.
OMeta2/Squeak has a feature to pop up a Squeak debugger at the
position where the parse went as far as it could, and then you can
step execute it. But of course, it goes into the underlying
implementation and generated code, so it is quite tedious. What we
would like to see in that debugger is the original code and step
execution that makes sense.
Of course, Squeak debugger lets you "restart" a context, but this
does not help much as the parser is stateful. We contemplated Worlds
would help to really rewind a rule and try again...
-- Yoshiki
___
fonc mailing list
[email protected]
http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
I overlooked the IDE completely. I'll check it out as soon as I can. Thanks for the pointer:) On Dec 14, 2011, at 12:35 AM, Lukas Renggli wrote: >> I've experimented in what little time I can devote with OMeta, PetitParser, >> and Treetop. The debugging experience has been roughly consistent across all >> three. > > Casey, did you try the PetitParser IDE? If so, what did you miss? > > If not, please check it out > (http://jenkins.lukas-renggli.ch/job/PetitParser/lastSuccessfulBuild/artifact/PetitParser-OneClick.zip). > It comes with dedicated tools for grammars (editor, visualizations, > profiler, debugger, ...). An earlier version of the tool is described > in Section 3.5 of this paper > (http://scg.unibe.ch/archive/papers/Reng10cDynamicGrammars.pdf). We > are currently working on an improved IDE with grammar refactorings. > > Lukas > >> >> One particular issue which has bugged me: memoization seems to carry a lot >> of instance-state that's really hard to comprehend when the grammar isn't >> working as I expect. It's just really hard to use that ocean of information >> to figure out what I've done wrong. >> >> Given that with these new parsing technologies, we're pretty lucky to see >> "parse error" as an error message, I can't help but think that it's worth >> studying debugging strategies. Heh. :D I'm really not complaining, I'm just >> pointing it out. >> >> Has anyone here found any technique(s) which makes debugging a grammar >> written for a PEG/packrat less of a pain in the butt? >> >> I'd be really interested in hearing about it. >> >> >> >> ___ >> fonc mailing list >> [email protected] >> http://vpri.org/mailman/listinfo/fonc > > > > -- > Lukas Renggli > www.lukas-renggli.ch > > ___ > fonc mailing list > [email protected] > http://vpri.org/mailman/listinfo/fonc ___ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
> I've experimented in what little time I can devote with OMeta, PetitParser, > and Treetop. The debugging experience has been roughly consistent across all > three. Casey, did you try the PetitParser IDE? If so, what did you miss? If not, please check it out (http://jenkins.lukas-renggli.ch/job/PetitParser/lastSuccessfulBuild/artifact/PetitParser-OneClick.zip). It comes with dedicated tools for grammars (editor, visualizations, profiler, debugger, ...). An earlier version of the tool is described in Section 3.5 of this paper (http://scg.unibe.ch/archive/papers/Reng10cDynamicGrammars.pdf). We are currently working on an improved IDE with grammar refactorings. Lukas > > One particular issue which has bugged me: memoization seems to carry a lot of > instance-state that's really hard to comprehend when the grammar isn't > working as I expect. It's just really hard to use that ocean of information > to figure out what I've done wrong. > > Given that with these new parsing technologies, we're pretty lucky to see > "parse error" as an error message, I can't help but think that it's worth > studying debugging strategies. Heh. :D I'm really not complaining, I'm just > pointing it out. > > Has anyone here found any technique(s) which makes debugging a grammar > written for a PEG/packrat less of a pain in the butt? > > I'd be really interested in hearing about it. > > > > ___ > fonc mailing list > [email protected] > http://vpri.org/mailman/listinfo/fonc -- Lukas Renggli www.lukas-renggli.ch ___ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Debugging PEGs and Packrats
I use LPEG ( http://www.inf.puc-rio.br/~roberto/lpeg/ ) a lot for
writing grammars. I'm not familiar with the ones you mention so I
have no idea how similar they are. I too had a lot of trouble
debugging, so I ended up writing some tools that print out debugging
statements in a human readable form. The ones I've found most useful
are listing out the matched tokens in order, the tokens attempted, and
a trace of the grammar rules the parser follows. For reference, this
is a typical log of data I get (this one is for a Lua grammar):
1 1 -> block
1 2 -> chunk
1 3 -> stat
14 -> varlist
1 5 -> var
1 6 -> prefix
1 5 <-: prefix
14 <-: var
1 3 <-: varlist
14 -> functioncall
1 5 -> prefix
14 <-: prefix
1 3 <-: functioncall
24 -> funcname
2 3 <- funcname 3 MATCH
34 -> funcbody
4 5 -> parlist
4 6 -> namelist
8 5 <- namelist 9 MATCH
84 <- parlist 9 MATCH
10 5 -> block
10 6 -> chunk
10 7 -> stat
108 -> varlist
10 9 -> var
10 10 -> prefix
10 9 <- prefix 10 MATCH
11 10 -> suffix
11 11 -> call
1112 -> args
11 13 -> tableconstructor
1112 <-: tableconstructor
11 11 <-: args
11 10 <-: call
11 11 -> index
11 10 <-: index
11 9 <-: suffix
11 10 -> index
11 9 <-: index
108 <- var 11 MATCH
10 7 <- varlist 11 MATCH
108 -> functioncall
10 9 -> prefix
108 <- prefix 11 MATCH
11 9 -> suffix
11 10 -> call
11 11 -> args
1112 -> tableconstructor
11 11 <-: tableconstructor
11 10 <-: args
11 9 <-: call
11 10 -> index
11 9 <-: index
118 <-: suffix
11 9 -> call
11 10 -> args
11 11 -> tableconstructor
11 10 <-: tableconstructor
11 9 <-: args
118 <-: call
10 7 <-: functioncall
10 6 <-: stat
10 7 -> laststat
10 6 <-: laststat
9 5 <- chunk 11 MATCH
94 <- block 11 MATCH
3 3 <-: funcbody
1 2 <-: stat
1 3 -> laststat
1 2 <-: laststat
0 1 <- chunk 11 MATCH
00 <- block 11 MATCH
Rule Stack:
{
idx = 9,
[1] = "block",
[2] = "chunk",
[3] = "stat",
[4] = "funcbody",
[5] = "block",
[6] = "chunk",
[7] = "stat",
[8] = "functioncall",
[9] = "prefix",
}
Attempted Tokens List:
{
rules = {
[1] = "args",
[2] = "tableconstructor",
[3] = "args",
[4] = "call",
[5] = "index",
[6] = "index",
[7] = "varlist",
[8] = "stat",
},
tokens = {
[1] = "LEFT_PAREN",
[2] = "LEFT_BRACE",
[3] = "STRING",
[4] = "COLON",
[5] = "LEFT_BRACKET",
[6] = "DOT",
[7] = "COMMA",
[8] = "EQUALS",
},
}
___
fonc mailing list
[email protected]
http://vpri.org/mailman/listinfo/fonc
