語法分析基礎(chǔ)

yacc.py 用來對(duì)語言進(jìn)行語法分析。在給出例子之前，必須提一些重要的背景知識(shí)。首先，‘語法’通常用 BNF 范式來表達(dá)。例如，如果想要分析簡(jiǎn)單的算術(shù)表達(dá)式，你應(yīng)該首先寫下無二義的文法：

expression : expression + term
           | expression - term
           | term

term       : term * factor
           | term / factor
           | factor

factor     : NUMBER
           | ( expression )

在這個(gè)文法中，像NUMBER,+,-,*,/的符號(hào)被稱為終結(jié)符，對(duì)應(yīng)原始的輸入。類似term，factor等稱為非終結(jié)符，它們由一系列終結(jié)符或其他規(guī)則的符號(hào)組成，用來指代語法規(guī)則。

通常使用一種叫語法制導(dǎo)翻譯的技術(shù)來指定某種語言的語義。在語法制導(dǎo)翻譯中，符號(hào)及其屬性出現(xiàn)在每個(gè)語法規(guī)則后面的動(dòng)作中。每當(dāng)一個(gè)語法被識(shí)別，動(dòng)作就能夠描述需要做什么。比如，對(duì)于上面給定的文法，想要實(shí)現(xiàn)一個(gè)簡(jiǎn)單的計(jì)算器，應(yīng)該寫成下面這樣：

Grammar                             Action
--------------------------------    -------------------------------------------- 
expression0 : expression1 + term    expression0.val = expression1.val + term.val
            | expression1 - term    expression0.val = expression1.val - term.val
            | term                  expression0.val = term.val

term0       : term1 * factor        term0.val = term1.val * factor.val
            | term1 / factor        term0.val = term1.val / factor.val
            | factor                term0.val = factor.val

factor      : NUMBER                factor.val = int(NUMBER.lexval)
            | ( expression )        factor.val = expression.val

一種理解語法指導(dǎo)翻譯的好方法是將符號(hào)看成對(duì)象。與符號(hào)相關(guān)的值代表了符號(hào)的“狀態(tài)”（比如上面的 val 屬性），語義行為用一組操作符號(hào)及符號(hào)值的函數(shù)或者方法來表達(dá)。

Yacc 用的分析技術(shù)是著名的 LR 分析法或者叫移進(jìn)-歸約分析法。LR 分析法是一種自下而上的技術(shù)：首先嘗試識(shí)別右部的語法規(guī)則，每當(dāng)右部得到滿足，相應(yīng)的行為代碼將被觸發(fā)執(zhí)行，當(dāng)前右邊的語法符號(hào)將被替換為左邊的語法符號(hào)。（歸約）

LR 分析法一般這樣實(shí)現(xiàn)：將下一個(gè)符號(hào)進(jìn)棧，然后結(jié)合棧頂?shù)姆?hào)和后繼符號(hào)（譯者注：下一個(gè)將要輸入符號(hào)），與文法中的某種規(guī)則相比較。具體的算法可以在編譯器的手冊(cè)中查到，下面的例子展現(xiàn)了如果通過上面定義的文法，來分析 3 + 5 * ( 10 - 20 ) 這個(gè)表達(dá)式，$ 用來表示輸入結(jié)束

Step Symbol Stack           Input Tokens            Action
---- ---------------------  ---------------------   -------------------------------
1                           3 + 5 * ( 10 - 20 )$    Shift 3
2    3                        + 5 * ( 10 - 20 )$    Reduce factor : NUMBER
3    factor                   + 5 * ( 10 - 20 )$    Reduce term   : factor
4    term                     + 5 * ( 10 - 20 )$    Reduce expr : term
5    expr                     + 5 * ( 10 - 20 )$    Shift +
6    expr +                     5 * ( 10 - 20 )$    Shift 5
7    expr + 5                     * ( 10 - 20 )$    Reduce factor : NUMBER
8    expr + factor                * ( 10 - 20 )$    Reduce term   : factor
9    expr + term                  * ( 10 - 20 )$    Shift *
10   expr + term *                  ( 10 - 20 )$    Shift (
11   expr + term * (                  10 - 20 )$    Shift 10
12   expr + term * ( 10                  - 20 )$    Reduce factor : NUMBER
13   expr + term * ( factor              - 20 )$    Reduce term : factor
14   expr + term * ( term                - 20 )$    Reduce expr : term
15   expr + term * ( expr                - 20 )$    Shift -
16   expr + term * ( expr -                20 )$    Shift 20
17   expr + term * ( expr - 20                )$    Reduce factor : NUMBER
18   expr + term * ( expr - factor            )$    Reduce term : factor
19   expr + term * ( expr - term              )$    Reduce expr : expr - term
20   expr + term * ( expr                     )$    Shift )
21   expr + term * ( expr )                    $    Reduce factor : (expr)
22   expr + term * factor                      $    Reduce term : term * factor
23   expr + term                               $    Reduce expr : expr + term
24   expr                                      $    Reduce expr
25                                             $    Success!

（譯者注：action 里面的 Shift 就是進(jìn)棧動(dòng)作，簡(jiǎn)稱移進(jìn)；Reduce 是歸約）

在分析表達(dá)式的過程中，一個(gè)相關(guān)的自動(dòng)狀態(tài)機(jī)和后繼符號(hào)決定了下一步應(yīng)該做什么。如果下一個(gè)標(biāo)記看起來是一個(gè)有效語法（產(chǎn)生式）的一部分（通過棧上的其他項(xiàng)判斷這一點(diǎn)），那么這個(gè)標(biāo)記應(yīng)該進(jìn)棧。如果棧頂?shù)捻?xiàng)可以組成一個(gè)完整的右部語法規(guī)則，一般就可以進(jìn)行“歸約”，用產(chǎn)生式左邊的符號(hào)代替這一組符號(hào)。當(dāng)歸約發(fā)生時(shí)，相應(yīng)的行為動(dòng)作就會(huì)執(zhí)行。如果輸入標(biāo)記既不能移進(jìn)也不能歸約的話，就會(huì)發(fā)生語法錯(cuò)誤，分析器必須進(jìn)行相應(yīng)的錯(cuò)誤恢復(fù)。分析器直到棧空并且沒有另外的輸入標(biāo)記時(shí)，才算成功。 需要注意的是，這是基于一個(gè)有限自動(dòng)機(jī)實(shí)現(xiàn)的，有限自動(dòng)器被轉(zhuǎn)化成分析表。分析表的構(gòu)建比較復(fù)雜，超出了本文的討論范圍。不過，這構(gòu)建過程的微妙細(xì)節(jié)能夠解釋為什么在上面的例子中，解析器選擇在步驟 9 將標(biāo)記轉(zhuǎn)移到堆棧中，而不是按照規(guī)則 expr : expr + term 做歸約。