---
# System prepended metadata

title: Left Recursion & Factoring
tags: [Compiler]

---

Left Recursion & Factoring
===
---

###### tags: `Compiler`

這篇寫著 Left Recursion 是啥? 解決辦法? Left Factoring 是啥?

---

# Left Recursion
考慮一個 production 如下
```
A → Aα | β
```
會導致 **無限Parssssssssssssssssssse**
![](https://i.imgur.com/x57F0IE.png)
**這就是 Left Recursion**

這是簡單說的版本，其實這就是所謂的
- **Direct left recursion**

但聰明的你，想到還有更ㄎㄅ的Left Recursion狀況嗎

- **Indirect left recursion**
```
A0 -> β0A1α0
A1 -> β1A2α1
A2 -> β2A3α2
...
An -> βnA0αn
```
看的出來這個 ***真的*** 蠻母湯的吧

## Solution
### 簡單狀況
  **若有 A → Aα | β**
  就改成以下就好了~~
  ```
  A → β A’
  A’ → α A’ | є
  ```

### Direct left recursion
```
A -> Aα1 | ... | Aαn | β1 | ... | βm
```
以上是發生 Direct left recursion 的 production 的 General form
其中
:::info
α : nonempty sequence of nonterminals and terminals
β : sequence of nonterminals and terminals that does not start with A
:::

解法就是
用以下兩組 productions 取代這個滿滿bug的~~大平台~~production
```
A -> β1A' | ... | βmA'
A' -> α1A' | ... | αnA' | ε
```

其實上面說的簡單狀況，就是這一種解法的小小特例~

### All left recursion
1. Pseudo code
```c=
For each nonterminal Ai:
    Repeat until an iteration leaves the grammar unchanged:
        For each rule Ai -> αi:
        (ai being a sequence of terminals and nonterminals)
            if αi begins with a nonterminal Aj and j < i:
                Let βi be ai without its leading Aj
                Remove the rule Ai -> αi
                For each rule Aj -> αj
                    Add the rule Ai -> αjβi
    Remove direct left recursion for Ai as described above
    (Direct left recursion)
```
2. Example
```=
Left Recursion Rules:
S -> Aa | b
A -> Ac | Sd | ε

// Arrange the nonterminals in order S, A
// A1
// Nothing happens.

// A2
// ∃ Aj, Ai ∋ j < i in A -> Sd
βi = d
Remove A -> Sd
Add A -> Aad
Add A -> bd

Now, Rules are:
S -> Aa | b
A -> Ac | Aad | bd | ε

// Using the algorithm of Removing Direct Left Recursion
Remove A -> Ac | Aad | bd | ε
Add A -> bdA' | A'
Add A' -> cA' | adA' | ε

Now, Rules with no left recursion:
S -> Aa | b
A -> bdA' | A'
A' -> cA' | adA' | ε
```

好棒棒~~

# Left Factoring
這東西跟 Left Recursion 擺一起只是因為都有 Left 這個字
想說就做一下 Left Factoring 好了

若一個 rule 這樣寫
```
A -> qα0 | qα1 | qα2 | .... | qαn
```

Left Factoring 就只是取個共同都有的東東
變成
```
A -> qA'
A' -> α0 | α1 | α2 | .... | αn
```

Over.