1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
.. Copyright (c) 2017-2026 Juancarlo Añez (apalala@gmail.com)
.. SPDX-License-Identifier: BSD-4-Clause
.. include:: links.rst
Left Recursion
--------------
|TatSu| supports direct and indirect left recursion in grammar rules using
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 help and research by `Nicolas Laurent`_ on Autumn_, and `Philippe
Sigaud`_ on PEGGED_.
.. _Autumn: https://github.com/norswap/autumn
.. _PEGGED: https://github.com/PhilippeSigaud/Pegged/wiki/Left-Recursion
Left recursive rules produce left-associative parse trees (AST_), as most
users would expect, *except if some rules involved recurse on the right*.
.. _paper: http://norswap.com/pubs/sle2015.pdf
Left recursion support is enabled by default in |TatSu|. To disable it for a particular grammar, use the ``@@left_recursion`` directive:
.. code:: ocaml
@@left_recursion :: False
.. warning::
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.
|
