Ambiguity Evaluatora read
When defining grammars, it is useful to know whether they are ambiguous,
ie. whether the same output can be attained by two separate paths through
the syntax tree. For example, given the grammar
S := aS, aaS, ε, the string
“aa” can be obtained either by applying the 1st rule twice or the 2nd rule
There is no general purpose algorithm to determine whether a grammar is ambiguous or not, and so here is a brute-force approach which enumerates all the words up to a certain depth (say, 5 rule applications) and determines whether the grammar is definitely ambiguous or potentially not.