Auto-generate tests for a user grammar

[jsinger67]

This discussion is dedicated to the proposal made by @nblei here. We are trying to figure out how to generate useful test from a given grammar.

[nblei]

I see this as two distinct issues, one with a relatively simple solution.

The first issue is for context-free languages: generating example strings in the grammar. This is sufficient for languages which are truly context-free, and not just languages which use a context-free grammar to generate a parser (e.g., C++ which itself is recursively enumerable). In this case, it is possible for a generator with no knowledge other than the context-free grammar to enumerate all possible strings in the language represented by the grammar.

The second issue is for languages which are more complex than context-free languages. For example, many of the bugs we're identifying in the Veryl language implementation are due to namespaces. While a context-sensitive parser, such as https://arxiv.org/pdf/1609.05365.pdf, may be directly useful in this context, it still would not be sufficient for other languages which are not context-sensitive. To elucidate the problem

Consider

module foo {
    var x: logic = bar::x;
}

This is a valid Veryl program based on the context-free grammar described in https://github.com/dalance/veryl/blob/master/crates/parser/veryl.par. However, it is not a valid Veryl program because Veryl is not context-free --- the namespace foo does not exist, so accessing the scoped identifier bar::x should result in an error. Thus, we must come up with some mechanism to filter out illegal strings.

Perhaps, though, this is a bit like a dog chasing its own tail...

[jsinger67]

From parol's point of view all language constructs are context-free. Thats the definition of the languages covered by LL(k) grammars.
The principle you are talking about is the semantics behind the input processed by the grammar in regard, don't you?
So, for example, if a namespace is known or not at a given point in the input text can't be covered by a standard grammar definition, like parol's one.
Normally, this task is done by the language processing itself, i.e. whether it have seen a namespace bar so far or not.
I'm not an expert of veryl itself, but (I guess) If there has been a

module bar {
   var x;
}

before, your example would be perfectly right.
A grammar processing item would have registered this namespace (module?) and inserted it into some kind of symbol table to be accessible from other scopes.
parol itself utilizes this principle, e.g. to decide whether scanner state names are valid or whether user type definitions exist.

[nblei]

Yep, exactly. Which is why its likely difficult to use parol alone to generate strings. It may be able to generate string candidates, but then what checks to see if those string candidates are valid other than the compiler which is potentially buggy in the first place?

[jsinger67]

I think we must distinguish between grammar evaluation and evaluation of grammar processing.
Currently I tend to say that the first task can easily be fulfilled by parol alone simply by generating random valid input texts from the grammar description and let a language acceptor generated from the same grammar description parse them frequently.
This is exactly what the generate subcommand was defined for.
The second part in my opinion is hard to handle with parol alone. This task is, in my opinion, the responsibility of the grammar processing on the user side.

[nblei]

Makes sense. Thanks, Jörg.

…

On Sun, Aug 27, 2023 at 4:05 AM Jörg Singer ***@***.***> wrote: I think we must distinguish between grammar evaluation and evaluation of grammar processing. Currently I tend to say that the first task can easily be fulfilled by parol alone simply by generating random valid input texts from the grammar description and let a language acceptor generated from the same grammar description parse them frequently. This is exactly what the generate subcommand <https://urldefense.com/v3/__https://github.com/jsinger67/parol/blob/main/crates/parol/CHANGELOG.md*generation-of-sentences__;Iw!!DZ3fjg!8oGOz_dmeq1DDn7PCcDavG7RXhObvdxGX5TflDKGWZicy6WOe3Pub7ncvdW6fpQy_RVDwYs24pBZ_n2dSCoBae7rbXqx$> was defined for. The second part in my opinion is hard to handle with parol alone. This task is, in my opinion, the responsibility of the grammar processing on the user side. — Reply to this email directly, view it on GitHub <https://urldefense.com/v3/__https://github.com/jsinger67/parol/discussions/165*discussioncomment-6833669__;Iw!!DZ3fjg!8oGOz_dmeq1DDn7PCcDavG7RXhObvdxGX5TflDKGWZicy6WOe3Pub7ncvdW6fpQy_RVDwYs24pBZ_n2dSCoBaVdz6RST$>, or unsubscribe <https://urldefense.com/v3/__https://github.com/notifications/unsubscribe-auth/AFAMUBHFHNOOQ4I434EHY2LXXMET5ANCNFSM6AAAAAA3ADM3SY__;!!DZ3fjg!8oGOz_dmeq1DDn7PCcDavG7RXhObvdxGX5TflDKGWZicy6WOe3Pub7ncvdW6fpQy_RVDwYs24pBZ_n2dSCoBaaSpAn66$> . You are receiving this because you were mentioned.Message ID: ***@***.***>

-- Very Respectfully, Nathaniel Bleier ***@***.*** 773-531-8229 (Cell)

[jsinger67]

With commit 5647d26 the subcommand parol generate is available again.
I'll design a test template that generates an acceptor for a given grammar and applies generated input to it frequently.

[jsinger67]

@nblei ,
with commit 648c14e I fixewd issue #225
Have fun! ✌️