CODEWITHSUNDEEP
randomgrammarexpansiontatsu
bookofproofs
bookofproofs

Reputation: 354

Generate random grammar expansions in TatSu (Python)

I'm writing an interpreter for a grammar parser generated with TatSu. I'm looking for a convenient way to generate use cases for my grammar, so I can write unit tests for my interpreter. Currently, I'm generating my test cases by hand.

I wonder if the TatSu package does provide any (maybe undocumented) means to auto-generate random grammar derivations so I could use them as test cases for my interpreter. In addition, it would be desirable to specify the grammar rule, for which I need the random productions.

Upvotes: 1

Views: 170

Answers (2)

bookofproofs
bookofproofs

Reputation: 354

I've created an experimental public repository TatSu Random Derivation Generator that can generate random derivations for many rules of your grammars compiled with TatSu. If the grammars are very complex, the program runs into a RecursionError.

Nevertheless, it is useful for testing your grammars, especially if you want to test derivations for specific production rules.

The example.py as well as the many tests show you how to use the tool.

Upvotes: 0

Apalala
Apalala

Reputation: 9244

If you look at the __str__() method in grammars.py you'll see an example of walking through a grammar to transform it into something readable.

You could also use a Visitor.

Because the set of derivations for a grammar is potentially infinite, you need a strategy to generate some interesting samples before quitting (Ctrl-C):

  • go breadth-first, or the visitor will recurse until the runtime stack is exhausted
  • because of PEG, work first with the last option in a choice (|), which should be the one producing the shortest derivation

Because TatSu skips over whitespace, you'll probably need to add a step to pretty-print the output.

This is an interesting project, and it would be good if at the end you added it as a pull request to TatSu.

My apologies for providing only guidelines instead of an example.

Upvotes: 1

Related Questions