1 # Left Recursion in BP
   2 
   3 Left recursion presents a special difficulty for parsing expression grammars.
   4 A regular recursive rule looks like this:
   5 
   6 ```
   7 rec: "{" *rec "}"
   8 ```
   9 
  10 This is a relatively simple case to handle, because we're always making forward
  11 progress. In other words, calling `match(<rec>, str)` might call
  12 `match(<rec>, str + 1)` but it will never recursively call the same function
  13 with the same arguments: `match(<rec>, str)`.
  14 
  15 Left-recursive rules, on the other hand, are rules that may attempt to match
  16 themselves at the same position. For example:
  17 
  18 ```
  19 laugh: (laugh "ha") / "Ha"
  20 ```
  21 
  22 The rule above is functionally equivalent to `laugh: "Ha" (*"ha")`, but it's
  23 written in a recursive style. It should be obvious by inspection that the
  24 string `Hahaha` matches both versions of the rule, but a naive implementation
  25 of `match()` would cause `match(<laugh>, str)` to call `match(<laugh>, str)`
  26 before doing anything else, which results in infinite recursion and a stack
  27 overflow. One option is to simply detect left recursion and cause a compilation
  28 error (this is what LPEG does). However, it is possible to actually match left
  29 recursive rules without overflowing the stack.
  30 
  31 ## Matching Left Recursion
  32 
  33 The solution used in BP is the following:
  34 
  35 1. Whenever matching a named rule, `foo`, against string `str`, first get the
  36    originally defined pattern for that rule. Call this
  37    `foo-original-definition`.
  38 2. Temporarily define `match(<foo>, str) := signal left recursion and return
  39    Fail` (In other words, `<foo>` is temporarily defined to signal left
  40    recursion and then fail to match if matching against the string `str`.)
  41 3. Run `result := match(<foo-original-definition>, str)`.
  42 4. If the match failed, then return failure.
  43 5. If the match was successful and did not trigger left recursion, return `result`.
  44 6. If the match was successful, but did trigger left recursion, then:
  45 
  46     a. If `result` is not longer than any previous `result`, stop looping and
  47        return the longest `result` to avoid an infinite loop.
  48     b. Otherwise: temporarily define `match(<foo>, str) := signal left recursion and return <result>`
  49     c. Go to step 3.
  50 
  51 This handles left recursion as a simple loop and successfully matches left
  52 recursive patterns, even ones that are indirectly or nontrivially left
  53 recursive.
  54 
  55 ## Example
  56 
  57 Consider the rule `laugh: laugh "ha" / "Ha"` being applied to the input text `"Hahaha!"`:
  58 
  59 | Temp. definition of `match(<laugh>, "Hahaha!")` | Result of `match(<laugh "ha" / "Ha">, "Hahaha!")` |
  60 |------------------------------------------|---------------------------------------------------|
  61 |`Fail`                                    | `Match{"Ha"}`                                     |
  62 |`Match{"Ha"}`                             | `Match{"Haha"}`                                   |
  63 |`Match{"Haha"}`                           | `Match{"Hahaha"}`                                 |
  64 |`Match{"Hahaha"}`                         | `Match{"Ha"}` (Forward progress stops being made) |
  65 
  66 As you can see in this example, each successive iteration builds up a final
  67 match incrementally until progress is no longer being made. At that point,
  68 the longest match is returned: `Match{"Hahaha"}`.