Enumerate valid grammars

[lshamis]

Is there a way to enumerate all valid grammars of a fixed length?

[ColinH]

Assuming that "enumerate" means "recursively enumerate", and that it's easy to agree on what the length of a grammar is, what's your definition of "valid"?

[lshamis]

Say I have:

struct token : sor< one<'A'>, one<'B'>, one<'C'> > {};
struct grammar : must< token, token, eof > {};

I'd like to run an action over the following: AA, AB, AC, BA, BB, BC, CA, CB, CC.

My actual grammar is infinite. I would like search for expressions satisfying the grammar in some form of iterative deepening. The exact form is not too important, maybe all expressions with 1 ast node, 2 ast nodes, 3 ast nodes, ...

[ColinH]

I'm sorry, I can't follow. What are the "valid" grammars you want to enumerate? How did you get from enumerating grammars to "searching" for expressions? What kind of "infinite grammars" are you using and how does the PEGTL fit in? Can you formally define what it is exactly you are trying to achieve?

[lshamis]

Sorry, I'm not super familiar with the nomenclature, but here's my best attempt.

I have a fixed grammar, describing a parse tree. Something similar to the grammar in example/pegtl/hello_world.cpp

struct grammar : pegtl::must< prefix, name, pegtl::one< '!' >, pegtl::eof > {};

I can use the grammar to parse an input string and apply an action:

pegtl::parse< hello::grammar, hello::action >( in, name );

But this requires an input string.

I'd like to generate possible input string, s.t. a call to parse would not throw parse_error. This is what I meant as valid, in the earlier post.

My end goal is to find an AST that satisfies some condition. The grammar accepts a superset of the ASTs I care about. By enumerating ASTs satisfying my grammar, I'm hoping to find the AST I care about. This is what I meant as searching.

My grammar has a Kleene star, so the number of parsable input strings is infinite.

Does this help explain my problem? I'm not sure how to formally define what I'm trying to achieve...

[ColinH]

Why can't the additional condition on the trees be encoded in/part of the grammar?

[lshamis]

Not really

[d-frey]

It sounds like you try to enumerate all inputs (not grammars) that satisfy a given grammar. For each input you'd like to check whether grammar accepts it and the AST satisfies some condition. If so, you might want to look for some scientific papers on the topic. We currently have no support for anything like that in the PEGTL.

[lshamis]

I guess inputs was the word I was missing :)

Thanks for the help

[ColinH]

Good luck, I hope you get things sorted out!