5.7 Recursion and cycles

If any symbol in the grammar non-trivially produces a symbol string containing itself, the grammar is said to be recursive. If any symbol non-trivially produces a symbol string in which it is the leftmost symbol, the grammar is said to be left-recursive. If any symbol non-trivially produces a symbol string in which it is the rightmost symbol, the grammar is said to be right-recursive. Marpa can handle all recursive grammars, including grammars which are left-recursive, grammars which are right-recursive, and grammars which contain both left- and right-recursion.

A cycle is a non-trivial derivation of a string of symbols from itself. If it is not possible for any derivation using a grammar to contain a cycle, then that grammar is said to be cycle-free. Traditionally, a grammar is considered useless if it is not cycle-free.

The traditional deprecation of cycles is well-founded. A cycle is the parsing equivalent of an infinite loop. Once a cycle appears, it can be repeated over and over again. Even a very short input sentence can have an infinite number of parses when the grammar is not cycle-free.

For that reason, a grammar which contains a cycle is also called infinitely ambiguous. Marpa can parse with grammars which are not cycle-free, but use of this feature is deprecated. See Cycles.