how to tackle cycle-dep problem?

[cppden]

Hi gurus, was going to try use your master-piece to build ASN.1 compiler but after defining grammar in PEGTL it turned out to have a lot of cycle dependencies (loops) shown with pegtl::analyze:

problem: cycle without progress detected at rule class asn1::Type
problem: cycle without progress detected at rule class asn1::BuiltinValue
problem: cycle without progress detected at rule class asn1::BuiltinValue
problem: cycle without progress detected at rule class asn1::ConstrainedType

Can you please give a hint how to resolve it? I mean how should I change grammar to get rid of such loops?

[ColinH]

First step, let's look at the cycles in the grammar. The first one around Type is easy to spot, given the rules

struct Type : peg::sor< BuiltinType, ReferencedType, ConstrainedType > {};
struct ConstrainedType : peg::sor< peg::seq< Type, sp, Constraint >, TypeWithConstraint > {};

we can see how Type can immediately (without consuming antyhing prior) call ConstrainedType which in turn can immediately call Type again.

The cycles around BuiltinValue are not so easy to spot, I'll see whether I can easily extend the grammar analysis to print the rules along the cycle, that should make it easier.

Regarding a solution for this cycle one needs to analyse the context of these grammar rules and see what one can come up with, do you know how to tackle this? I'll take a look at the first cycle above and see whether I can come up with something when I have a bit more time.

Further, considering the grammar and these issues I'm getting the idea that the grammar was actually a CFG and not a PEG, which also means that there might be other problems, i.e. other places where simply using the CFG as PEG does not create equivalent matching behaviour, have you in general looked into this for your ASN.1 grammar?

[ColinH]

There might be more than one cycle containingBuiltinValue. The first one that I found starts with BuiltinValue which is an sor which can call InstanceOfValue which is Value which in turn is an sor with BuiltinValue. This is unfortunately not very PEG-esque...

[cppden]

Yes, this grammar isn't PEG-based since ASN.1 is rather old (not even written in ABNF but in its own style of CFG-like grammar).
But is there a way to change such grammar to be PEG? I mean any trick(s) how to unwind/break those loops (manually)?
With Bison/Yacc it is possible but I really like PEGTL so much more than clumsy Flex/Bison syntax...

[ColinH]

The good news is that yes, it is possible, however the bad news is that it can be difficult. As an example, have you looked at the comments at the beginning of src/example/pegtl/lua53.hpp?

[cppden]

I do know you have the Lua grammar but didn't look into it yet. Now you've got me thrilled. :)

[cppden]

Thanks, just read it... now I understand "the bad news". :(

bummer indeed as I'm not so grammar-friendly to come up with your trick applied there but at least I have an example to give it a try. Thanks a lot!

P.S.: still I wouldn't mind to have pegtl::analyze improved a bit showing cycles in depth. :)

[ColinH]

I just pushed a change that lets analyze() output more information when called with an argument greater than 0, however it's not pretty because the analysis doesn't analyse the actual structure of the grammar, it analyses an equivalent form that is reduced to as few basic combinators as possible in order to simplify the algorithm. Therefore some of the rules that will be listed as part of a cycle will be rules that don't actually occur in the original grammar in that form. Still, it's better than nothing, and it is what helped me find the second cycle mentioned above...

[ColinH]

Good luck with the CFG-to-PEG transformation, let us know if you get stuck and we'll see what we can do. You're at a good point if you now understand the "bad news"...

[ColinH]

Final note: The grammar analysis does a good job of telling you that a problem exists, however the printed details on what and where exactly the problem are not always reliable, that's a long-term work-in-progress.

[cppden]

Thank you very much @ColinH! I'll try new analyze and to come up with any idea to break the loops.

let us know if you get stuck and we'll see what we can do.

I really appretiate your generocity but will use it only as a last resort of course. :)