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.