yacc.py用來對語言進行語法分析。在給出例子之前，必須提一些重要的背景知識。首先，‘語法’通常用BNF范式來表達。例如，如果想要分析簡單的算術表達式，你應該首先寫下無二義的文法： ~~~ expression : expression + term | expression - term | term term : term * factor | term / factor | factor factor : NUMBER | ( expression ) ~~~ 在這個文法中，像`NUMBER`,`+`,`-`,`*`,`/`的符號被稱為終結符，對應原始的輸入。類似`term`，`factor`等稱為非終結符，它們由一系列終結符或其他規則的符號組成，用來指代語法規則。 通常使用一種叫語法制導翻譯的技術來指定某種語言的語義。在語法制導翻譯中，符號及其屬性出現在每個語法規則后面的動作中。每當一個語法被識別，動作就能夠描述需要做什么。比如，對于上面給定的文法，想要實現一個簡單的計算器，應該寫成下面這樣： ~~~ 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 ~~~ 一種理解語法指導翻譯的好方法是將符號看成對象。與符號相關的值代表了符號的“狀態”（比如上面的val屬性），語義行為用一組操作符號及符號值的函數或者方法來表達。 Yacc用的分析技術是著名的LR分析法或者叫移進-歸約分析法。LR分析法是一種自下而上的技術：首先嘗試識別右部的語法規則，每當右部得到滿足，相應的行為代碼將被觸發執行，當前右邊的語法符號將被替換為左邊的語法符號。（歸約） LR分析法一般這樣實現：將下一個符號進棧，然后結合棧頂的符號和后繼符號（譯者注：下一個將要輸入符號），與文法中的某種規則相比較。具體的算法可以在編譯器的手冊中查到，下面的例子展現了如果通過上面定義的文法，來分析3 + 5 * ( 10 - 20 )這個表達式，$用來表示輸入結束 ~~~ 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是歸約） 在分析表達式的過程中，一個相關的自動狀態機和后繼符號決定了下一步應該做什么。如果下一個標記看起來是一個有效語法（產生式）的一部分（通過棧上的其他項判斷這一點），那么這個標記應該進棧。如果棧頂的項可以組成一個完整的右部語法規則，一般就可以進行“歸約”，用產生式左邊的符號代替這一組符號。當歸約發生時，相應的行為動作就會執行。如果輸入標記既不能移進也不能歸約的話，就會發生語法錯誤，分析器必須進行相應的錯誤恢復。分析器直到棧空并且沒有另外的輸入標記時，才算成功。 需要注意的是，這是基于一個有限自動機實現的，有限自動器被轉化成分析表。分析表的構建比較復雜，超出了本文的討論范圍。不過，這構建過程的微妙細節能夠解釋為什么在上面的例子中，解析器選擇在步驟9將標記轉移到堆棧中，而不是按照規則expr : expr + term做歸約。