Deyaccify
Deyaccification means converting recursive definitions to iterative ones where possible. The name comes from YACC, or Yet Another Compiler Compiler, a tool which underlying parsing technology limits were enforcing the usage of recursive definitions back in the 1970s. However, it somehow became common practice to remain within them even when grammar engineers do not use yacc as such at all.
The name of a nonterminal must be provided as an argument, then the transformation engine checks if the grammar productions for this nonterminal fit into one of the yaccified patterns. If not, the error is reported, otherwise the definition is replaced by one that uses regular expression operators instead of epsilon, choice, and recursion.
Both left- and right-recursive forms can be factored with this transformation.
deyaccify:
nonterminal::nonterminal
Deyaccification uses several general patterns. Left recursion like this:
foo:
bar
foo:
foo wez
Becomes:
foo:
bar wez*
Right recursion like this:
foo:
bar
foo:
wez foo
Becomes:
foo:
wez* bar
In either case, it is checked if bar and wez are the same nonterminal.
If they are, the result is more concise:
foo:
bar+
- Deyaccify is a part of XBGF
- DeyaccifyAll is a grammar mutation with similar semantics (for more aggressive manipulation)