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.

Left recursive rules produce left-associative parse trees (AST), as most users would expect.

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 in 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.

Additionally, for grammars with indirect left recursion, the rules containing choices must be the first invoked during a parse. The following grammar is correct,but it will not work if the start rule is changed to `start = mul ;`.

start = expr ;

    mul | identifier

    expr '*' identifier