Left Recursion

TatSu supports direct and indirect left recursion in grammar rules using the the algorithm described by Nicolas Laurent and Kim Mens in their 2015 paper Parsing Expression Grammars Made Practical.

The design and implementation of left recursion was done by Vic Nightfall with research and help by Nicolas Laurent on Autumn, and research by Philippe Sigaud on PEGGED.

Left recursive rules produce left-associative parse trees (AST), as most users would expect, except if some of the rules involved recurse on the right (a pending topic).

Left recursion support is enabled by default in 竜 TatSu. To disable it for a particular grammar, use the @@left_recursion directive:

@@left_recursion :: False


Not all left-recursive grammars that use the 竜 TatSu syntax are PEG (the same happens with right-recursive grammars). The order of rules matters in PEG.

For right-recursive grammars the choices that parse the most input must come first. The same is true for left-recursive grammars.