[Day16] Yacc - Recursion (1)

15th鐵人賽

BarleyTea

2023-09-16 10:53:35

993 瀏覽

分享至

本篇內容

介紹Yacc的遞迴規則(Recursion)

前言

在前面實作的簡易計算機範例中，我們只讀取了三個元素：兩個數字與一個運算符號(+號)。然而，若是要一次把很多個數字加起來呢?

在不知道有多少個數字相加的情況下，沒辦法使用先前的規則寫法。那麼，有辦法解決這個問題嗎？

當然有！若是要讀取連續的字串，並視作同一個群體，我們只需要用Recursion的規則寫法，就能輕鬆做到這件事。

遞迴（Recursion）是一種在程式設計中常見的概念，它指的是一個函數或算法可以直接或間接地調用自己的能力。遞迴通常在解決問題時使用，其中問題可以分解為類似但規模較小的子問題。

在Yacc中，將一個非終端符號不斷呼叫自己的方式，便能透過Shift & Reduce，將相同的架構不斷彙整簡化。

Yacc的Recursion語法

在Yacc中，Recursion分為兩種：left recursion / right recursion (左遞迴與右遞迴)。
顧名思義，兩種遞迴的方式就是從左方或是從右方開始。
然而，這兩種方式有甚麼差別嗎?

我們分別用左遞迴與右遞迴來實作一個將多個數字加總的parser，來看看兩者的匹配過程。

左遞迴

左遞迴的語法如下

// left recursion
sum:
		  element          { $$ = $1; }
		| sum '+' element  { $$ += $3; }
		;

從上述的語法中，可以看到兩個規則：

sum: element           (規則1)
sum: sum '+' element   (規則2)

規則1比較好理解，就是當只有一個數字時，總和便是該數字。

規則2則是運用到遞迴的概念，就是當數字要加總時，將該數字加入sum這個變數中。

我們提供下列的input，一起來看看Yacc是如何對此進行規則匹配吧！

1+2+4

由於目前buffer內沒東西，所以shift第一個token
```
1
```
此時，element 1可以匹配到規則1，因此進行reduce
首先，先將匹配的字串組(1)從stack中移出。
進行化簡後，element 1的數值將被assign到sum變數，最終得到一個非終端符號sum，數值為1。
最後，將sum放回buffer內
```
sum
```
接著，我們繼續shift第二個element
```
sum '+'
```
由於沒有匹配到對應的規則，所以繼續shift第三個token
```
sum '+' 2
```
此時，Yacc出現了兩種匹配方式：
1. 序列”2”可以匹配到規則1
2. 序列”sum+2”可以匹配到規則2
那麼，Yacc會匹配到哪種規則呢?
1. 使用最長匹配原則（Longest Match）： Yacc 將優先選擇匹配最長的規則。這意味著當多個規則都可以匹配輸入時，Yacc 會選擇那個使輸入最長的規則。
2. 使用最早定義原則（Earliest Defined）： 如果有多個規則具有相同的匹配長度，Yacc 將選擇最早定義的規則。這是因為在 Yacc 文件中，規則通常按照它們的定義順序排序。
根據上述的定義，先比較規則的長度。由於規則2長度較長，因此使用最長匹配原則，進行規則2的reduce。
首先，先將匹配的字串組(”sum+2”)從stack中移出。
進行化簡後，將數值2加到sum變數中，得到一個非終端符號sum，其值為3
最後，將sum放回buffer內
```
sum
```
接著，我們繼續shift第四個element
```
sum '+'
```
由於沒有匹配到對應的規則，我們繼續shift第五個element
```
sum '+' 4
```
此時，Yacc一樣出現了兩種匹配方式
根據步驟5，我們進行規則2的化簡，內容同步驟5
最後得到一個非終端符號sum，其值為7，並將其放回buffer內
```
sum
```

至此，整個文本的讀取就大功告成了。

右遞迴

右遞迴的語法如下

// right recursion
sum:
		  element
		| element '+' sum
		;

從上述的語法中，可以看到兩個規則：

sum: element           (規則1)
sum: element '+' sum   (規則2)

這裡的規則2寫法跟左遞迴不同，當數字要加總時，sum跟element的相對位置不同。

你可能會想說：既然都是相加，總和不是都一樣嗎?
總和是會一樣，但是Yacc的匹配過程可是天差地遠喔！

我們一樣從下列的input開始，看看Yacc如何以右遞迴方式進行規則匹配。

1+2+4

由於目前buffer內沒東西，所以shift第一個token
```
1
```
此時，element 1同時符合匹配到規則1跟2的條件
這裡看似有些奇怪，一開始好像覺得只符合條件1啊？
但是，由於之後的token尚未放入，所以也不能排除符合規則2的可能性。
根據剛剛提到的最長匹配原則，我們在兩條以上規則皆匹配的情況下，要選長度較長的。
因此，這裡會先不匹配規則1，等待規則2的匹配結果。
```
1
```
接著，我們繼續shift第二個element
```
1 '+'
```
由於沒有匹配到對應的規則，所以繼續shift第三個token
```
1 '+' 2
```
此時，Yacc出現了跟第2步相同的情況
因此，這裡一樣先不做reduce
```
1 '+' 2
```
接著，我們繼續shift第四個element
```
1 '+' 2 '+'
```
由於沒有匹配到對應的規則，我們繼續shift第五個element
```
1 '+' 2 '+' 4
```
此時所有token皆已讀入。
因此，我們從stack頂部開始進行規則匹配。
由於後面沒有其他token了，此時序列”4”僅能匹配規則1，我們便用規則1做reduce。
首先，先將匹配的字串組(”4”)從stack中移出。
進行化簡後，將數值4 assign 到 sum 變數中，得到一個非終端符號sum，其值為4
最後，將sum放回buffer內
```
1 '+' 2 '+' sum
```
接著，我們對序列”2+sum”進行匹配，符合規則2，然後進行reduce。
首先，先將匹配的字串組(”2+sum”)從stack中移出。
進行化簡後，將數值2 加到 sum 變數中，得到一個非終端符號sum，其值為6
最後，將sum放回buffer內
```
1 '+' sum
```
接著，我們對序列”1+sum”進行匹配，符合規則2，然後進行reduce。
首先，先將匹配的字串組(”1+sum”)從stack中移出。
進行化簡後，將數值1 加到 sum 變數中，得到一個非終端符號sum，其值為7
最後，將sum放回buffer內
```
sum
```

至此，整個文本的讀取就完成了。

比較 - 左遞迴 vs 右遞迴

透過剛剛的兩個例子，我們來比較左遞迴與右遞迴的差異。

左遞迴的reduce從字串序列頭(左方)開始，右遞迴的reduce從字串序列尾(右方)開始
左遞迴在將shift期間會不斷做reduce，故遇到無限長的文本時，會造成無限遞迴。
右遞迴會將所有token做shift之後才進行reduce。若是遇到長文本時，可能有token數超出buffer長度的狀況。

總體來說，由於文本幾乎不會是無限長，故通常不太會遇到第2點的問題。然而，第3點的問題卻很難處理。因為在讀取文本之前，我們通常不知道文本長度。因此，我們一般都是用左遞迴來處理這類的文本資料。然而，有些情況下，只有右遞迴可以達到需求(像是化簡順序一定要從右方開始)，這時就要特別留意buffer長度。

結語

今天介紹了一個非常實用的規則：Recursion。它可以處理連續的相同結構，像是array類型的資訊。

我們明天會實際用一個範例說明遞迴的應用。

參考資料

Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
Tom Niemann. Lex & Yacc
Bison Manual - Recursive Rules
Left-recursive versus right-recursive lists in LR parsers