PetitParser PPCompositeParser, Infinite loop ?
Locked
PetitParser PPCompositeParser, Infinite loop ?
 
|
Hi,
To explain my problem I will take this sample , my parser is a PPCompositeParser.
ClassOrInterfaceType: ClassType / InterfaceType ClassType:TypeDeclSpecifier, TypeArgumentsopt InterfaceType: TypeDeclSpecifier, TypeArgumentsopt TypeDeclSpecifier: TypeName / ClassOrInterfaceType . Identifier TypeName: Identifier /TypeName . Identifier Ok, so Identifier works well, no problem but when I tested typeDeclSpecifier, I lost the contral of Pharo but I don't know why because I use a PPCompositeParser. For the moment I use some tricks but I would like it works normally. Thanks for your help. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
Can we meet in next 3 days at Inria?
On 17 Dec 2013, at 23:22, Benjamin AREZKI <[hidden email]> wrote:
_______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
Unfortunately no, I am actually in an other university ... Do you have any idea about this problem ? 2013/12/17 Uko2 [via Smalltalk] <[hidden email]>
|
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
well one thing I can see is that there is no way to decide between ClassType and InterfaceType because both have the exact same definition (or is it a mistake in the mail?) I wouldn't think this can crash petitparser, I would have think it would just always go for classtype and never interfacetype But this sure looks strange. Why would you need both? if they are the same? Another thing I am spotting is that there is a kind of recursive loop: ClassOrInterfaceType > ClassType > TypeDeclSpecifier > ClassOrInterfaceType So may be it is entering an infinite recursion always following this same path ... ? In a typical grammar, you would need something before the recursive call to make sure some token is consumed at some point otherwise it can just call rules recursively without consuming any otken in the input stream nicolas On 12/17/2013 11:32 PM, Benjamin AREZKI
wrote:
-- Nicolas Anquetil -- RMod research team (Inria) _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
In reply to this post by Benjamin AREZKI
Hi, this part is probably your issue: TypeName: Identifier /TypeName . Identifier If your TypeDeclSpecifier starts out with something that isn't an Identifier, then the TypeName: will fail the first choice (Identifier), then try the second choice - which immediately calls TypeName again, which will fail the first choice (Identifier) and call itself again - and so on until it crashes or you break the processing.
In general, any time that a parser can start out by calling itself directly (without some other action occurring before), it will probably go into a loop. (This might be something that would be nice to have PetitParser catch - infinite loops. Not easy, probably not cheap, but doable.)
Also, you generally want to make the most specific option first in your parsers - if TypeName could be 'Identifier' or 'Identifier . Identifier', then you would want to check for 'Identifier . Identifier' first.
-cbc On Tue, Dec 17, 2013 at 2:22 PM, Benjamin AREZKI <[hidden email]> wrote:
_______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
In reply to this post by Nicolas Anquetil
No it's not a mistake, both have exact same definition but the not the same and it's useful because I use those rules in other parts of the grammar and it helps for the comprehension. Yeah I think it create an infinite recursion but normally I can't have this problem with PPCompositeParser ..
2013/12/17 Nicolas Anquetil <[hidden email]>
_______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
Thanks, Chris this is not this problem because I had already solve this one by doing this : typeName ^ identifier, (($. asParser,identifier) star).
Sorry because I did not say that. 2013/12/17 Benjamin AREZKI <[hidden email]>
_______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
In reply to this post by Benjamin AREZKI
You will not have infinite recursion at the instanciation of the parser, but if you have a cycle that does not consume any character it means you have an infinite loop when you parse. Try to interrupt the infinite loop where you fall; you will see the concerned parsers.
You should also use the GT-PetitParserDebugger from andrei
2013/12/17 Benjamin AREZKI <[hidden email]>
Guillaume Larcheveque _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
In reply to this post by Benjamin AREZKI
ben there is nothing magic about PPCompositeParser, it is a parser like all the other one and if you call rules without consuming any input + have a loop in the rule calls, then there will be a infinite loop The idea is PetitParser tries to consume something by calling a rule, if this rules calls another one then it tries it etc ... As long as no rule consume anything, it will just continue calling them and you will have an infinite rule So this is an issue. Now about the other 2 rules that are the same, this is strange too. You normally don't do that in a parser nicolas On 12/17/2013 11:55 PM, Benjamin AREZKI
wrote:
-- Nicolas Anquetil -- RMod research team (Inria) _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
Le 18/12/2013 11:15, Nicolas Anquetil a écrit : > > ben there is nothing magic about PPCompositeParser, it is a parser like > all the other one > and if you call rules without consuming any input + have a loop in the > rule calls, then there will be a infinite loop Yes and no. Some parsers can't handle left-recursion in rules (petit parser? LL parsers can't), some parsers don't have any problem with left recursion (LR parsers like SmaCC). The only thing is that most (all) grammars for programming languages are left recursives... > The idea is PetitParser tries to consume something by calling a rule, if > this rules calls another one then it tries it etc ... > As long as no rule consume anything, it will just continue calling them > and you will have an infinite rule > So this is an issue. > > Now about the other 2 rules that are the same, this is strange too. > You normally don't do that in a parser In that particluar case, a parser would be unable to make a difference between choosing ClassType or InterfaceType, since both are defined as exactly the same production. Then, depending on the Parser, it would select only the first, or complain that it can't choose between both :) Thierry > nicolas > > On 12/17/2013 11:55 PM, Benjamin AREZKI wrote: >> No it's not a mistake, both have exact same definition but the not the >> same and it's useful because I use those rules in other parts of the >> grammar and it helps for the comprehension. Yeah I think it create an >> infinite recursion but normally I can't have this problem with >> PPCompositeParser .. >> >> >> 2013/12/17 Nicolas Anquetil <[hidden email] >> <mailto:[hidden email]>> >> >> >> well one thing I can see is that there is no way to decide between >> ClassType and InterfaceType >> because both have the exact same definition (or is it a mistake in >> the mail?) >> >> I wouldn't think this can crash petitparser, I would have think it >> would just always go for classtype and never interfacetype >> But this sure looks strange. Why would you need both? if they are >> the same? >> >> >> >> Another thing I am spotting is that there is a kind of recursive loop: >> >> ClassOrInterfaceType > ClassType > TypeDeclSpecifier > >> ClassOrInterfaceType >> >> So may be it is entering an infinite recursion always following >> this same path ... ? >> In a typical grammar, you would need something before the >> recursive call to make sure some token is consumed at some point >> otherwise it can just call rules recursively without consuming any >> otken in the input stream >> >> >> nicolas >> >> >> On 12/17/2013 11:32 PM, Benjamin AREZKI wrote: >>> Unfortunately no, I am actually in an other university ... Do you >>> have any idea about this problem ? >>> >>> >>> 2013/12/17 Uko2 [via Smalltalk] <[hidden email] >>> <http://user/SendEmail.jtp?type=node&node=4730847&i=0>> >>> >>> Can we meet in next 3 days at Inria? >>> >>> On 17 Dec 2013, at 23:22, Benjamin AREZKI <[hidden email] >>> <http://user/SendEmail.jtp?type=node&node=4730845&i=0>> wrote: >>> >>>> Hi, >>>> >>>> To explain my problem I will take this sample , my parser is >>>> a PPCompositeParser. >>>> >>>> ClassOrInterfaceType: ClassType / InterfaceType >>>> >>>> ClassType:TypeDeclSpecifier, TypeArgumentsopt >>>> >>>> InterfaceType: TypeDeclSpecifier, TypeArgumentsopt >>>> >>>> TypeDeclSpecifier: TypeName / ClassOrInterfaceType . Identifier >>>> >>>> TypeName: Identifier /TypeName . Identifier >>>> >>>> Ok, so Identifier works well, no problem but when I tested >>>> typeDeclSpecifier, I lost the contral of Pharo but I don't >>>> know why because I use a PPCompositeParser. For the moment >>>> I use some tricks but I would like it works normally. >>>> >>>> Thanks for your help. >>>> >>>> _______________________________________________ >>>> Moose-dev mailing list >>>> [hidden email] >>>> <http://user/SendEmail.jtp?type=node&node=4730845&i=1> >>>> https://www.iam.unibe.ch/mailman/listinfo/moose-dev >>> >>> >>> _______________________________________________ >>> Moose-dev mailing list >>> [hidden email] >>> <http://user/SendEmail.jtp?type=node&node=4730845&i=2> >>> https://www.iam.unibe.ch/mailman/listinfo/moose-dev >>> >>> >>> ------------------------------------------------------------------------ >>> If you reply to this email, your message will be added to the >>> discussion below: >>> http://forum.world.st/PetitParser-PPCompositeParser-Infinite-loop-tp4730844p4730845.html >>> >>> To start a new topic under Moose, email [hidden email] >>> <http://user/SendEmail.jtp?type=node&node=4730847&i=1> >>> To unsubscribe from Smalltalk, click here. >>> NAML >>> <http://forum.world.st/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml> >>> >>> >>> >>> >>> ------------------------------------------------------------------------ >>> View this message in context: Re: PetitParser PPCompositeParser, >>> Infinite loop ? >>> <http://forum.world.st/PetitParser-PPCompositeParser-Infinite-loop-tp4730844p4730847.html> >>> Sent from the Moose mailing list archive >>> <http://forum.world.st/Moose-f1310756.html> at Nabble.com. >>> >>> >>> _______________________________________________ >>> Moose-dev mailing list >>> [hidden email] <mailto:[hidden email]> >>> https://www.iam.unibe.ch/mailman/listinfo/moose-dev >> >> -- >> Nicolas Anquetil -- RMod research team (Inria) >> >> >> _______________________________________________ >> Moose-dev mailing list >> [hidden email] <mailto:[hidden email]> >> https://www.iam.unibe.ch/mailman/listinfo/moose-dev >> >> >> >> >> _______________________________________________ >> Moose-dev mailing list >> [hidden email] >> https://www.iam.unibe.ch/mailman/listinfo/moose-dev > > -- > Nicolas Anquetil -- RMod research team (Inria) > > > > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev > -- Thierry Goubier CEA list Laboratoire des Fondations des Systèmes Temps Réel Embarqués 91191 Gif sur Yvette Cedex France Phone/Fax: +33 (0) 1 69 08 32 92 / 83 95 _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
On 12/18/2013 11:27 AM, Goubier Thierry
wrote:
I meant PPCompositeParser within PetitParser All parsers PPParsers behave more or less the same way when we come to this. If other can't handle correctly left-recursion ther eis no reasonnable reason to hope that PPCompositeParser composite parser will do. Moreover, being a recursive descent parser, PetitParser naturally can't handle left recursivity In this case, you will need to convert the grammar to a right recursive one, for example like this (which is more or less the same thing I believe): ClassOrInterfaceType:
ClassType
"/ InterfaceType -- this option is useless here as it is equal
to ClassType" TypeDeclSpecifier:
TypeName { . TypeDeclSpecifier } TypeName: Identifier TypeArgumentsopt InterfaceType: TypeDeclSpecifier, TypeArgumentsopt Some of the rules are not really needed, but that way it sticks closer to the reference grammar nicolas -- Nicolas Anquetil -- RMod research team (Inria) _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
RE : Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
De : [hidden email] [[hidden email]] de la part de Nicolas Anquetil [[hidden email]]
Date d'envoi : mercredi 18 décembre 2013 13:34 À : Moose-related development Objet : [Moose-dev] Re: PetitParser PPCompositeParser, Infinite loop ? Ok, now I understand what you meant Moreover, being a recursive descent parser, PetitParser naturally can't handle left recursivity You have a point :)
In this case, you will need to convert the grammar to a right recursive one, for example like this (which is more or less the same thing I believe):In that particular problem (InterfaceType = ClassType), PetitParser would select the first alternative everytime, since they are both equal, and would never reach InterfaceType ? Regards, Thierry nicolas _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: RE : Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
On 12/18/2013 07:00 PM, GOUBIER Thierry
wrote:
yes either they both fail, or only ClassType succeeds
-- Nicolas Anquetil -- RMod research team (Inria) _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
Hi!
Today with Jan, we started to “paint” grammars using Roassal: https://www.facebook.com/ObjectProfile The code is available in PetitGui. Just send #visualize to a grammar Cheers, Alexandre On Dec 18, 2013, at 9:46 PM, Nicolas Anquetil <[hidden email]> wrote: > > On 12/18/2013 07:00 PM, GOUBIER Thierry wrote: >> >> De : [hidden email] [[hidden email]] de la part de Nicolas Anquetil [[hidden email]] >> Date d'envoi : mercredi 18 décembre 2013 13:34 >> À : Moose-related development >> Objet : [Moose-dev] Re: PetitParser PPCompositeParser, Infinite loop ? >> In that particular problem (InterfaceType = ClassType), PetitParser would select the first alternative everytime, since they are both equal, and would never reach InterfaceType ? >> > yes > either they both fail, or only ClassType succeeds >> Regards, >> >> Thierry > > -- > Nicolas Anquetil -- RMod research team (Inria) > > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
RE : Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
Hi Alexandre,
I will really look into that, I have a need to draw SmaCC Grammars ;) Is the visualisation able to draw recursive definitions ? Thierry ________________________________________ De : [hidden email] [[hidden email]] de la part de Alexandre Bergel [[hidden email]] Date d'envoi : mercredi 18 décembre 2013 23:16 À : Moose-related development Objet : [Moose-dev] Re: PetitParser PPCompositeParser, Infinite loop ? Hi! Today with Jan, we started to “paint” grammars using Roassal: https://www.facebook.com/ObjectProfile The code is available in PetitGui. Just send #visualize to a grammar Cheers, Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: RE : Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
Nice. And you integrated it in the GTInspector, too :). Just, please call these methods view*, not visualize*. Doru
On Wed, Dec 18, 2013 at 11:30 PM, GOUBIER Thierry <[hidden email]> wrote: Hi Alexandre, "Every thing has its own flow"
_______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
Yes, Jan and Andrei did a good job :-)
Alexandre On Dec 19, 2013, at 5:52 AM, Tudor Girba <[hidden email]> wrote: > Nice. And you integrated it in the GTInspector, too :). > > Just, please call these methods view*, not visualize*. > > Doru > > > On Wed, Dec 18, 2013 at 11:30 PM, GOUBIER Thierry <[hidden email]> wrote: > Hi Alexandre, > > I will really look into that, I have a need to draw SmaCC Grammars ;) Is the visualisation able to draw recursive definitions ? > > Thierry > ________________________________________ > De : [hidden email] [[hidden email]] de la part de Alexandre Bergel [[hidden email]] > Date d'envoi : mercredi 18 décembre 2013 23:16 > À : Moose-related development > Objet : [Moose-dev] Re: PetitParser PPCompositeParser, Infinite loop ? > > Hi! > > Today with Jan, we started to “paint” grammars using Roassal: > https://www.facebook.com/ObjectProfile > > The code is available in PetitGui. Just send #visualize to a grammar > > Cheers, > Alexandre > > -- > _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: > Alexandre Bergel http://www.bergel.eu > ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. > > > > > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev > > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev > > > > -- > www.tudorgirba.com > > "Every thing has its own flow" > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
In reply to this post by Goubier Thierry
> I will really look into that, I have a need to draw SmaCC Grammars ;) Is the visualisation able to draw recursive definitions ?
I guess it should. Let see about this today! Alexandre > ________________________________________ > De : [hidden email] [[hidden email]] de la part de Alexandre Bergel [[hidden email]] > Date d'envoi : mercredi 18 décembre 2013 23:16 > À : Moose-related development > Objet : [Moose-dev] Re: PetitParser PPCompositeParser, Infinite loop ? > > Hi! > > Today with Jan, we started to “paint” grammars using Roassal: > https://www.facebook.com/ObjectProfile > > The code is available in PetitGui. Just send #visualize to a grammar > > Cheers, > Alexandre > > -- > _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: > Alexandre Bergel http://www.bergel.eu > ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. > > > > > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev > > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: PetitParser PPCompositeParser, Infinite loop ?
|
|
In reply to this post by abergel
Cool. For a way too complex picture, I tried the PetitDelphi grammar. That gets so large that exporting to png hangs the image... And firefox and chrome refuse to open the svg. Chrome complains about an error somewhere around character 601000 of line 1 :)
Stephan _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
Oh… I’ve just exported the JavaParser, and I have faced similar problem. Here is how I solve it, it is a bit hacky, but it seems to works.
1 - export the PetitDelphi grammar info an svg file, let’s call it delphi.svg 2 - open emacs on it within a terminal: emacs delphi.svg 3 - convert the mac file into the unix format: C-x RET f undecided-unix 4 - Save it: C-c C-X 5 - Open the file with your web browser, it will now indicate you the culprit line 6 - Fix the SVG by removing “<“ and “&” characters Does this makes sense? The proper solution is to use escape character in the SVG. Something we should do… https://dl.dropboxusercontent.com/u/31543901/TMP/Java.svg Alexandre On Dec 19, 2013, at 11:19 AM, Stephan Eggermont <[hidden email]> wrote: > Cool. For a way too complex picture, I tried the PetitDelphi grammar. That gets so large that exporting to png hangs the image... And firefox and chrome refuse to open the svg. Chrome complains about an error somewhere around character 601000 of line 1 :) > > Stephan > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
«
Return to Moose
|
1 view|%1 views
| Free forum by Nabble | Edit this page |