How to design tests for grammars and their parsers?

[Bruno Kim Medeiros Cesar]

Hey, folks!

Hypothesis looks specially valuable in a grammar and parser setting, and I'm trying to apply it now. However, while it's easy to create a generator that outputs some text given a grammar, not always the whole of what gives a text its validity is encoded in the grammar.

For example, I've written a grammar that can parse itself. It contains a CharRange(start, end) object, representing a range of letters that are accepted, like "[a-z]". In the grammar's self grammar, the rule is written as

char_range = "[" CHAR "-" CHAR "]";

And the visitor implements converting this to the proper object

def visit_char_range(tokens):
  _, start, _, end, _ = tokens

  return CharRange(start, end)

The check that 'start' must be less than 'end' is only encoded in the CharRange constructor, throwing a ValueError.

I've configured hypothesis to generate a text from the grammar, which becomes something like this:

@st.composite

def concat(draw):

  xs = []

  xs.append(draw(st.just("["))

  xs.append(draw(st.characters())

  xs.append(draw(st.just("-"))

  xs.append(draw(st.characters())

  xs.append(draw(st.just("]"))

  return "".join(xs)

Note that it is missing a check that ensures that start < end. Indeed, the first failure was trying to generate the char range "[0-0]".

How would you go about removing these undesirable errors from generated test cases? I can think of two options that don't seem too smart:
1. Add some annotation in my grammar that can be consumed by the hypothesis generator, and then make it as powerful as necessary to never generate an invalid text ever.

2. Filter out all such errors and stick to interesting cases.

The first option seems like a lot of work. The second one seems like it could generate too many instances, when we combine all such preconditions that the grammar isn't specific about. Is there another option on how I use hypothesis for this problem?

Thanks for your attention!