GrammarFuzzer max cost expansion strategy can lead to infinite loops

[michaelmera]

The first expansion strategy used by the GrammarFuzzer tries to widen the derivation tree until reaching min_nonterminals unexpanded non-terminals.

There are cases however where it is not possible to create a tree with enough unexpended non-terminals, potentially leading to infinite loops if recursive production rules are chosen, e.g.:

from fuzzingbook.GrammarFuzzer import GrammarFuzzer
from fuzzingbook.ExpectError import ExpectTimeout

grammar = {
    '<start>': ['<A>'],
    '<A>': ['a<A>', 'a'],
}

fuzzer = GrammarFuzzer(grammar, min_nonterminals=2, max_nonterminals=10, log=True)

with ExpectTimeout(2):
    fuzzer.fuzz()

Actually, the current implementation maximizes the risk to encounter these infinite loops because recursive non-terminal expansions are assigned an infinite cost (so they will always be picked first by the max-cost expansion algorithm).

This entire expansion step feels weird to me. Why not go for a (best effort) minimum width for the derivation tree (terminals included) instead of saying that we want to only consider the non-terminals?