語法分析基礎(chǔ)

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

expression : expression + term
           | expression - term
           | term

term       : term * factor
           | term / factor
           | factor

factor     : NUMBER
           | ( expression )

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

通常使用一種叫語法制導(dǎo)翻譯的技術(shù)來指定某種語言的語義。在語法制導(dǎo)翻譯中，符號及其屬性出現(xiàn)在每個語法規(guī)則后面的動作中。每當一個語法被識別，動作就能夠描述需要做什么。比如，對于上面給定的文法，想要實現(xiàn)一個簡單的計算器，應(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)翻譯的好方法是將符號看成對象。與符號相關(guān)的值代表了符號的“狀態(tài)”（比如上面的 val 屬性），語義行為用一組操作符號及符號值的函數(shù)或者方法來表達。

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

LR 分析法一般這樣實現(xiàn)：將下一個符號進棧，然后結(jié)合棧頂?shù)姆柡秃罄^符號（譯者注：下一個將要輸入符號），與文法中的某種規(guī)則相比較。具體的算法可以在編譯器的手冊中查到，下面的例子展現(xiàn)了如果通過上面定義的文法，來分析 3 + 5 * ( 10 - 20 ) 這個表達式，$ 用來表示輸入結(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 就是進棧動作，簡稱移進；Reduce 是歸約）

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