ply.yacc 模塊實(shí)現(xiàn)了 PLY 的分析功能，‘yacc’是‘Yet Another Compiler Compiler’的縮寫并保留了其作為 Unix 工具的名字。

一個例子

假設(shè)你希望實(shí)現(xiàn)上面的簡單算術(shù)表達(dá)式的語法分析，代碼如下：

# Yacc example

import ply.yacc as yacc

# Get the token map from the lexer.  This is required.
from calclex import tokens

def p_expression_plus(p):
    'expression : expression PLUS term'
    p[0] = p[1] + p[3]

def p_expression_minus(p):
    'expression : expression MINUS term'
    p[0] = p[1] - p[3]

def p_expression_term(p):
    'expression : term'
    p[0] = p[1]

def p_term_times(p):
    'term : term TIMES factor'
    p[0] = p[1] * p[3]

def p_term_div(p):
    'term : term DIVIDE factor'
    p[0] = p[1] / p[3]

def p_term_factor(p):
    'term : factor'
    p[0] = p[1]

def p_factor_num(p):
    'factor : NUMBER'
    p[0] = p[1]

def p_factor_expr(p):
    'factor : LPAREN expression RPAREN'
    p[0] = p[2]

# Error rule for syntax errors
def p_error(p):
    print "Syntax error in input!"

# Build the parser
parser = yacc.yacc()

while True:
   try:
       s = raw_input('calc > ')
   except EOFError:
       break
   if not s: continue
   result = parser.parse(s)
   print result

在這個例子中，每個語法規(guī)則被定義成一個 Python 的方法，方法的文檔字符串描述了相應(yīng)的上下文無關(guān)文法，方法的語句實(shí)現(xiàn)了對應(yīng)規(guī)則的語義行為。每個方法接受一個單獨(dú)的 p 參數(shù)，p 是一個包含有當(dāng)前匹配語法的符號的序列，p[i] 與語法符號的對應(yīng)關(guān)系如下：

def p_expression_plus(p):
    'expression : expression PLUS term'
    #   ^            ^        ^    ^
    #  p[0]         p[1]     p[2] p[3]

    p[0] = p[1] + p[3]

其中，p[i] 的值相當(dāng)于詞法分析模塊中對 p.value 屬性賦的值，對于非終結(jié)符的值，將在歸約時由 p[0] 的賦值決定，這里的值可以是任何類型，當(dāng)然，大多數(shù)情況下只是 Python 的簡單類型、元組或者類的實(shí)例。在這個例子中，我們依賴這樣一個事實(shí)：NUMBER 標(biāo)記的值保存的是整型值，所有規(guī)則的行為都是得到這些整型值的算術(shù)運(yùn)算結(jié)果，并傳遞結(jié)果。

注意：在這里負(fù)數(shù)的下標(biāo)有特殊意義--這里的 p[-1] 不等同于 p[3]。詳見下面的嵌入式動作部分

在 yacc 中定義的第一個語法規(guī)則被默認(rèn)為起始規(guī)則（這個例子中的第一個出現(xiàn)的 expression 規(guī)則）。一旦起始規(guī)則被分析器歸約，而且再無其他輸入，分析器終止，最后的值將返回（這個值將是起始規(guī)則的p[0]）。注意：也可以通過在 yacc() 中使用 start 關(guān)鍵字參數(shù)來指定起始規(guī)則

p_error(p) 規(guī)則用于捕獲語法錯誤。詳見處理語法錯誤部分

為了構(gòu)建分析器，需要調(diào)用 yacc.yacc() 方法。這個方法查看整個當(dāng)前模塊，然后試圖根據(jù)你提供的文法構(gòu)建 LR 分析表。第一次執(zhí)行 yacc.yacc()，你會得到如下輸出：

$ python calcparse.py
Generating LALR tables
calc >

由于分析表的得出相對開銷較大（尤其包含大量的語法的情況下），分析表被寫入當(dāng)前目錄的一個叫 parsetab.py 的文件中。除此之外，會生成一個調(diào)試文件 parser.out。在接下來的執(zhí)行中，yacc 直到發(fā)現(xiàn)文法發(fā)生變化，才會重新生成分析表和 parsetab.py 文件，否則 yacc 會從 parsetab.py 中加載分析表。注：如果有必要的話這里輸出的文件名是可以改的。

如果在你的文法中有任何錯誤的話，yacc.py 會產(chǎn)生調(diào)試信息，而且可能拋出異常。一些可以被檢測到的錯誤如下：

• 方法重復(fù)定義（在語法文件中具有相同名字的方法）
• 二義文法產(chǎn)生的移進(jìn)-歸約和歸約-歸約沖突
• 指定了錯誤的文法
• 不可終止的遞歸（規(guī)則永遠(yuǎn)無法終結(jié)）
• 未使用的規(guī)則或標(biāo)記
• 未定義的規(guī)則或標(biāo)記

下面幾個部分將更詳細(xì)的討論語法規(guī)則

這個例子的最后部分展示了如何執(zhí)行由 yacc() 方法創(chuàng)建的分析器。你只需要簡單的調(diào)用 parse()，并將輸入字符串作為參數(shù)就能運(yùn)行分析器。它將運(yùn)行所有的語法規(guī)則，并返回整個分析的結(jié)果，這個結(jié)果就是在起始規(guī)則中賦給 p[0] 的值。

將語法規(guī)則合并

如果語法規(guī)則類似的話，可以合并到一個方法中。例如，考慮前面例子中的兩個規(guī)則：

def p_expression_plus(p):
    'expression : expression PLUS term'
    p[0] = p[1] + p[3]

def p_expression_minus(t):
    'expression : expression MINUS term'
    p[0] = p[1] - p[3]

比起寫兩個方法，你可以像下面這樣寫在一個方法里面：

def p_expression(p):
    '''expression : expression PLUS term
                  | expression MINUS term'''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]

總之，方法的文檔字符串可以包含多個語法規(guī)則。所以，像這樣寫也是合法的（盡管可能會引起困惑）：

def p_binary_operators(p):
    '''expression : expression PLUS term
                  | expression MINUS term
       term       : term TIMES factor
                  | term DIVIDE factor'''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

如果所有的規(guī)則都有相似的結(jié)構(gòu)，那么將語法規(guī)則合并才是個不錯的注意（比如，產(chǎn)生式的項(xiàng)數(shù)相同）。不然，語義動作可能會變得復(fù)雜。不過，簡單情況下，可以使用len()方法區(qū)分，比如：

def p_expressions(p):
    '''expression : expression MINUS expression
                  | MINUS expression'''
    if (len(p) == 4):
        p[0] = p[1] - p[3]
    elif (len(p) == 3):
        p[0] = -p[2]

如果考慮解析的性能，你應(yīng)該避免像這些例子一樣在一個語法規(guī)則里面用很多條件來處理。因?yàn)?，每次檢查當(dāng)前究竟匹配的是哪個語法規(guī)則的時候，實(shí)際上重復(fù)做了分析器已經(jīng)做過的事（分析器已經(jīng)準(zhǔn)確的知道哪個規(guī)則被匹配了）。為每個規(guī)則定義單獨(dú)的方法，可以消除這點(diǎn)開銷。

字面字符

如果愿意，可以在語法規(guī)則里面使用單個的字面字符，例如：

def p_binary_operators(p):
    '''expression : expression '+' term
                  | expression '-' term
       term       : term '*' factor
                  | term '/' factor'''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

字符必須像'+'那樣使用單引號。除此之外，需要將用到的字符定義單獨(dú)定義在 lex 文件的literals列表里：

# Literals.  Should be placed in module given to lex()
literals = ['+','-','*','/' ]

字面的字符只能是單個字符。因此，像'<='或者'=='都是不合法的，只能使用一般的詞法規(guī)則（例如 t_EQ = r'==')。

空產(chǎn)生式

yacc.py 可以處理空產(chǎn)生式，像下面這樣做：

def p_empty(p):
    'empty :'
    pass

現(xiàn)在可以使用空匹配，只要將'empty'當(dāng)成一個符號使用：

def p_optitem(p):
    'optitem : item'
    '        | empty'
    ...

注意：你可以將產(chǎn)生式保持'空'，來表示空匹配。然而，我發(fā)現(xiàn)用一個'empty'規(guī)則并用其來替代'空'，更容易表達(dá)意圖，并有較好的可讀性。

改變起始符號

默認(rèn)情況下，在 yacc 中的第一條規(guī)則是起始語法規(guī)則（頂層規(guī)則）?？梢杂?start 標(biāo)識來改變這種行為：

start = 'foo'

def p_bar(p):
    'bar : A B'

# This is the starting rule due to the start specifier above
def p_foo(p):
    'foo : bar X'
...

用 start 標(biāo)識有助于在調(diào)試的時候?qū)⒋笮偷恼Z法規(guī)則分成小部分來分析。也可把 start 符號作為yacc的參數(shù)：

yacc.yacc(start='foo')

處理二義文法

上面例子中，對表達(dá)式的文法描述用一種特別的形式規(guī)避了二義文法。然而，在很多情況下，這樣的特殊文法很難寫，或者很別扭。一個更為自然和舒服的語法表達(dá)應(yīng)該是這樣的：

expression : expression PLUS expression
           | expression MINUS expression
           | expression TIMES expression
           | expression DIVIDE expression
           | LPAREN expression RPAREN
           | NUMBER

不幸的是，這樣的文法是存在二義性的。舉個例子，如果你要解析字符串"3 4 + 5"，操作符如何分組并沒有指明，究竟是表示"(3 4) + 5"還是"3 * (4 + 5)"呢？

如果在 yacc.py 中存在二義文法，會輸出"移進(jìn)歸約沖突"或者"歸約歸約沖突"。在分析器無法確定是將下一個符號移進(jìn)棧還是將當(dāng)前棧中的符號歸約時會產(chǎn)生移進(jìn)歸約沖突。例如，對于"3 * 4 + 5"，分析器內(nèi)部棧是這樣工作的：

Step Symbol Stack           Input Tokens            Action
---- ---------------------  ---------------------   -------------------------------
1    $                                3 * 4 + 5$    Shift 3
2    $ 3                                * 4 + 5$    Reduce : expression : NUMBER
3    $ expr                             * 4 + 5$    Shift *
4    $ expr *                             4 + 5$    Shift 4
5    $ expr * 4                             + 5$    Reduce: expression : NUMBER
6    $ expr * expr                          + 5$    SHIFT/REDUCE CONFLICT ????

在這個例子中，當(dāng)分析器來到第 6 步的時候，有兩種選擇：一是按照 expr : expr * expr 歸約，一是將標(biāo)記'+'繼續(xù)移進(jìn)棧。兩種選擇對于上面的上下文無關(guān)文法而言都是合法的。

默認(rèn)情況下，所有的移進(jìn)歸約沖突會傾向于使用移進(jìn)來處理。因此，對于上面的例子，分析器總是會將'+'進(jìn)棧，而不是做歸約。雖然在很多情況下，這個策略是合適的（像"if-then"和"if-then-else"），但這對于算術(shù)表達(dá)式是不夠的。事實(shí)上，對于上面的例子，將'+'進(jìn)棧是完全錯誤的，應(yīng)當(dāng)先將expr * expr歸約，因?yàn)槌朔ǖ膬?yōu)先級要高于加法。

為了解決二義文法，尤其是對表達(dá)式文法，yacc.py 允許為標(biāo)記單獨(dú)指定優(yōu)先級和結(jié)合性。需要像下面這樣增加一個 precedence 變量：

precedence = (
    ('left', 'PLUS', 'MINUS'),
    ('left', 'TIMES', 'DIVIDE'),
)

這樣的定義說明 PLUS/MINUS 標(biāo)記具有相同的優(yōu)先級和左結(jié)合性，TIMES/DIVIDE 具有相同的優(yōu)先級和左結(jié)合性。在 precedence 聲明中，標(biāo)記的優(yōu)先級從低到高。因此，這個聲明表明 TIMES/DIVIDE（他們較晚加入 precedence）的優(yōu)先級高于 PLUS/MINUS。

由于為標(biāo)記添加了數(shù)字表示的優(yōu)先級和結(jié)合性的屬性，所以，對于上面的例子，將會得到：

PLUS      : level = 1,  assoc = 'left'
MINUS     : level = 1,  assoc = 'left'
TIMES     : level = 2,  assoc = 'left'
DIVIDE    : level = 2,  assoc = 'left'

隨后這些值被附加到語法規(guī)則的優(yōu)先級和結(jié)合性屬性上，這些值由最右邊的終結(jié)符的優(yōu)先級和結(jié)合性決定：

expression : expression PLUS expression                 # level = 1, left
           | expression MINUS expression                # level = 1, left
           | expression TIMES expression                # level = 2, left
           | expression DIVIDE expression               # level = 2, left
           | LPAREN expression RPAREN                   # level = None (not specified)
           | NUMBER                                     # level = None (not specified)

當(dāng)出現(xiàn)移進(jìn)歸約沖突時，分析器生成器根據(jù)下面的規(guī)則解決二義文法：

1. 如果當(dāng)前的標(biāo)記的優(yōu)先級高于棧頂規(guī)則的優(yōu)先級，移進(jìn)當(dāng)前標(biāo)記
2. 如果棧頂規(guī)則的優(yōu)先級更高，進(jìn)行歸約
3. 如果當(dāng)前的標(biāo)記與棧頂規(guī)則的優(yōu)先級相同，如果標(biāo)記是左結(jié)合的，則歸約，否則，如果是右結(jié)合的則移進(jìn)
4. 如果沒有優(yōu)先級可以參考，默認(rèn)對于移進(jìn)歸約沖突執(zhí)行移進(jìn)

比如，當(dāng)解析到"expression PLUS expression"這個語法時，下一個標(biāo)記是 TIMES，此時將執(zhí)行移進(jìn)，因?yàn)?TIMES 具有比 PLUS 更高的優(yōu)先級；當(dāng)解析到"expression TIMES expression"，下一個標(biāo)記是 PLUS，此時將執(zhí)行歸約，因?yàn)?PLUS 的優(yōu)先級低于 TIMES。

如果在使用前三種技術(shù)解決已經(jīng)歸約沖突后，yacc.py 將不會報(bào)告語法中的沖突或者錯誤（不過，會在 parser.out 這個調(diào)試文件中輸出一些信息）

使用 precedence 指定優(yōu)先級的技術(shù)會帶來一個問題，有時運(yùn)算符的優(yōu)先級需要基于上下文。例如，考慮"3 + 4 * -5"中的一元的'-'。數(shù)學(xué)上講，一元運(yùn)算符應(yīng)當(dāng)擁有較高的優(yōu)先級。然而，在我們的 precedence 定義中，MINUS 的優(yōu)先級卻低于 TIMES。為了解決這個問題，precedene 規(guī)則中可以包含"虛擬標(biāo)記"：

precedence = (
    ('left', 'PLUS', 'MINUS'),
    ('left', 'TIMES', 'DIVIDE'),
    ('right', 'UMINUS'),            # Unary minus operator
)

在語法文件中，我們可以這么表示一元算符：

def p_expr_uminus(p):
    'expression : MINUS expression %prec UMINUS'
    p[0] = -p[2]

在這個例子中，%prec UMINUS 覆蓋了默認(rèn)的優(yōu)先級（MINUS 的優(yōu)先級），將 UMINUS 指代的優(yōu)先級應(yīng)用在該語法規(guī)則上。

起初，UMINUS 標(biāo)記的例子會讓人感到困惑。UMINUS 既不是輸入的標(biāo)記也不是語法規(guī)則，你應(yīng)當(dāng)將其看成 precedence 表中的特殊的占位符。當(dāng)你使用 %prec 宏時，你是在告訴 yacc，你希望表達(dá)式使用這個占位符所表示的優(yōu)先級，而不是正常的優(yōu)先級。

還可以在 precedence 表中指定"非關(guān)聯(lián)"。這表明你不希望鏈?zhǔn)竭\(yùn)算符。比如，假如你希望支持比較運(yùn)算符'<'和'>'，但是你不希望支持 a < b < c，只要簡單指定規(guī)則如下：

precedence = (
    ('nonassoc', 'LESSTHAN', 'GREATERTHAN'),  # Nonassociative operators
    ('left', 'PLUS', 'MINUS'),
    ('left', 'TIMES', 'DIVIDE'),
    ('right', 'UMINUS'),            # Unary minus operator
)

此時，當(dāng)輸入形如 a < b < c 時，將產(chǎn)生語法錯誤，卻不影響形如 a < b 的表達(dá)式。

對于給定的符號集，存在多種語法規(guī)則可以匹配時會產(chǎn)生歸約/歸約沖突。這樣的沖突往往很嚴(yán)重，而且總是通過匹配最早出現(xiàn)的語法規(guī)則來解決。歸約/歸約沖突幾乎總是相同的符號集合具有不同的規(guī)則可以匹配，而在這一點(diǎn)上無法抉擇，比如：

assignment :  ID EQUALS NUMBER
           |  ID EQUALS expression

expression : expression PLUS expression
           | expression MINUS expression
           | expression TIMES expression
           | expression DIVIDE expression
           | LPAREN expression RPAREN
           | NUMBER

這個例子中，對于下面這兩條規(guī)則將產(chǎn)生歸約/歸約沖突：

assignment  : ID EQUALS NUMBER
expression  : NUMBER

比如，對于"a = 5"，分析器不知道應(yīng)當(dāng)按照 assignment : ID EQUALS NUMBER 歸約，還是先將 5 歸約成 expression，再歸約成 assignment : ID EQUALS expression。

應(yīng)當(dāng)指出的是，只是簡單的查看語法規(guī)則是很難減少歸約/歸約沖突。如果出現(xiàn)歸約/歸約沖突，yacc()會幫助打印出警告信息：

WARNING: 1 reduce/reduce conflict
WARNING: reduce/reduce conflict in state 15 resolved using rule (assignment -> ID EQUALS NUMBER)
WARNING: rejected rule (expression -> NUMBER)

上面的信息標(biāo)識出了沖突的兩條規(guī)則，但是，并無法指出究竟在什么情況下會出現(xiàn)這樣的狀態(tài)。想要發(fā)現(xiàn)問題，你可能需要結(jié)合語法規(guī)則和parser.out調(diào)試文件的內(nèi)容。

parser.out調(diào)試文件

使用 LR 分析算法跟蹤移進(jìn)/歸約沖突和歸約/歸約沖突是件樂在其中的事。為了輔助調(diào)試，yacc.py 在生成分析表時會創(chuàng)建出一個調(diào)試文件叫 parser.out：

Unused terminals:

Grammar

Rule 1     expression -> expression PLUS expression
Rule 2     expression -> expression MINUS expression
Rule 3     expression -> expression TIMES expression
Rule 4     expression -> expression DIVIDE expression
Rule 5     expression -> NUMBER
Rule 6     expression -> LPAREN expression RPAREN

Terminals, with rules where they appear

TIMES                : 3
error                : 
MINUS                : 2
RPAREN               : 6
LPAREN               : 6
DIVIDE               : 4
PLUS                 : 1
NUMBER               : 5

Nonterminals, with rules where they appear

expression           : 1 1 2 2 3 3 4 4 6 0

Parsing method: LALR

state 0

    S' -> . expression
    expression -> . expression PLUS expression
    expression -> . expression MINUS expression
    expression -> . expression TIMES expression
    expression -> . expression DIVIDE expression
    expression -> . NUMBER
    expression -> . LPAREN expression RPAREN

    NUMBER          shift and go to state 3
    LPAREN          shift and go to state 2

state 1

    S' -> expression .
    expression -> expression . PLUS expression
    expression -> expression . MINUS expression
    expression -> expression . TIMES expression
    expression -> expression . DIVIDE expression

    PLUS            shift and go to state 6
    MINUS           shift and go to state 5
    TIMES           shift and go to state 4
    DIVIDE          shift and go to state 7

state 2

    expression -> LPAREN . expression RPAREN
    expression -> . expression PLUS expression
    expression -> . expression MINUS expression
    expression -> . expression TIMES expression
    expression -> . expression DIVIDE expression
    expression -> . NUMBER
    expression -> . LPAREN expression RPAREN

    NUMBER          shift and go to state 3
    LPAREN          shift and go to state 2

state 3

    expression -> NUMBER .

    $               reduce using rule 5
    PLUS            reduce using rule 5
    MINUS           reduce using rule 5
    TIMES           reduce using rule 5
    DIVIDE          reduce using rule 5
    RPAREN          reduce using rule 5

state 4

    expression -> expression TIMES . expression
    expression -> . expression PLUS expression
    expression -> . expression MINUS expression
    expression -> . expression TIMES expression
    expression -> . expression DIVIDE expression
    expression -> . NUMBER
    expression -> . LPAREN expression RPAREN

    NUMBER          shift and go to state 3
    LPAREN          shift and go to state 2

state 5

    expression -> expression MINUS . expression
    expression -> . expression PLUS expression
    expression -> . expression MINUS expression
    expression -> . expression TIMES expression
    expression -> . expression DIVIDE expression
    expression -> . NUMBER
    expression -> . LPAREN expression RPAREN

    NUMBER          shift and go to state 3
    LPAREN          shift and go to state 2

state 6

    expression -> expression PLUS . expression
    expression -> . expression PLUS expression
    expression -> . expression MINUS expression
    expression -> . expression TIMES expression
    expression -> . expression DIVIDE expression
    expression -> . NUMBER
    expression -> . LPAREN expression RPAREN

    NUMBER          shift and go to state 3
    LPAREN          shift and go to state 2

state 7

    expression -> expression DIVIDE . expression
    expression -> . expression PLUS expression
    expression -> . expression MINUS expression
    expression -> . expression TIMES expression
    expression -> . expression DIVIDE expression
    expression -> . NUMBER
    expression -> . LPAREN expression RPAREN

    NUMBER          shift and go to state 3
    LPAREN          shift and go to state 2

state 8

    expression -> LPAREN expression . RPAREN
    expression -> expression . PLUS expression
    expression -> expression . MINUS expression
    expression -> expression . TIMES expression
    expression -> expression . DIVIDE expression

    RPAREN          shift and go to state 13
    PLUS            shift and go to state 6
    MINUS           shift and go to state 5
    TIMES           shift and go to state 4
    DIVIDE          shift and go to state 7

state 9

    expression -> expression TIMES expression .
    expression -> expression . PLUS expression
    expression -> expression . MINUS expression
    expression -> expression . TIMES expression
    expression -> expression . DIVIDE expression

    $               reduce using rule 3
    PLUS            reduce using rule 3
    MINUS           reduce using rule 3
    TIMES           reduce using rule 3
    DIVIDE          reduce using rule 3
    RPAREN          reduce using rule 3

  ! PLUS            [ shift and go to state 6 ]
  ! MINUS           [ shift and go to state 5 ]
  ! TIMES           [ shift and go to state 4 ]
  ! DIVIDE          [ shift and go to state 7 ]

state 10

    expression -> expression MINUS expression .
    expression -> expression . PLUS expression
    expression -> expression . MINUS expression
    expression -> expression . TIMES expression
    expression -> expression . DIVIDE expression

    $               reduce using rule 2
    PLUS            reduce using rule 2
    MINUS           reduce using rule 2
    RPAREN          reduce using rule 2
    TIMES           shift and go to state 4
    DIVIDE          shift and go to state 7

  ! TIMES           [ reduce using rule 2 ]
  ! DIVIDE          [ reduce using rule 2 ]
  ! PLUS            [ shift and go to state 6 ]
  ! MINUS           [ shift and go to state 5 ]

state 11

    expression -> expression PLUS expression .
    expression -> expression . PLUS expression
    expression -> expression . MINUS expression
    expression -> expression . TIMES expression
    expression -> expression . DIVIDE expression

    $               reduce using rule 1
    PLUS            reduce using rule 1
    MINUS           reduce using rule 1
    RPAREN          reduce using rule 1
    TIMES           shift and go to state 4
    DIVIDE          shift and go to state 7

  ! TIMES           [ reduce using rule 1 ]
  ! DIVIDE          [ reduce using rule 1 ]
  ! PLUS            [ shift and go to state 6 ]
  ! MINUS           [ shift and go to state 5 ]

state 12

    expression -> expression DIVIDE expression .
    expression -> expression . PLUS expression
    expression -> expression . MINUS expression
    expression -> expression . TIMES expression
    expression -> expression . DIVIDE expression

    $               reduce using rule 4
    PLUS            reduce using rule 4
    MINUS           reduce using rule 4
    TIMES           reduce using rule 4
    DIVIDE          reduce using rule 4
    RPAREN          reduce using rule 4

  ! PLUS            [ shift and go to state 6 ]
  ! MINUS           [ shift and go to state 5 ]
  ! TIMES           [ shift and go to state 4 ]
  ! DIVIDE          [ shift and go to state 7 ]

state 13

    expression -> LPAREN expression RPAREN .

    $               reduce using rule 6
    PLUS            reduce using rule 6
    MINUS           reduce using rule 6
    TIMES           reduce using rule 6
    DIVIDE          reduce using rule 6
    RPAREN          reduce using rule 6

文件中出現(xiàn)的不同狀態(tài)，代表了有效輸入標(biāo)記的所有可能的組合，這是依據(jù)文法規(guī)則得到的。當(dāng)?shù)玫捷斎霕?biāo)記時，分析器將構(gòu)造一個棧，并找到匹配的規(guī)則。每個狀態(tài)跟蹤了當(dāng)前輸入進(jìn)行到語法規(guī)則中的哪個位置，在每個規(guī)則中，'.'表示當(dāng)前分析到規(guī)則的哪個位置，而且，對于在當(dāng)前狀態(tài)下，輸入的每個有效標(biāo)記導(dǎo)致的動作也被羅列出來。當(dāng)出現(xiàn)移進(jìn)/歸約或歸約/歸約沖突時，被忽略的規(guī)則前面會添加!，就像這樣：

! TIMES           [ reduce using rule 2 ]
  ! DIVIDE          [ reduce using rule 2 ]
  ! PLUS            [ shift and go to state 6 ]
  ! MINUS           [ shift and go to state 5 ]

通過查看這些規(guī)則并結(jié)合一些實(shí)例，通常能夠找到大部分沖突的根源。應(yīng)該強(qiáng)調(diào)的是，不是所有的移進(jìn)歸約沖突都是不好的，想要確定解決方法是否正確，唯一的辦法就是查看 parser.out。

處理語法錯誤

如果你創(chuàng)建的分析器用于產(chǎn)品，處理語法錯誤是很重要的。一般而言，你不希望分析器在遇到錯誤的時候就拋出異常并終止，相反，你需要它報(bào)告錯誤，盡可能的恢復(fù)并繼續(xù)分析，一次性的將輸入中所有的錯誤報(bào)告給用戶。這是一些已知語言編譯器的標(biāo)準(zhǔn)行為，例如 C,C++,Java。在 PLY 中，在語法分析過程中出現(xiàn)錯誤，錯誤會被立即檢測到（分析器不會繼續(xù)讀取源文件中錯誤點(diǎn)后面的標(biāo)記）。然而，這時，分析器會進(jìn)入恢復(fù)模式，這個模式能夠用來嘗試?yán)^續(xù)向下分析。LR 分析器的錯誤恢復(fù)是個理論與技巧兼?zhèn)涞膯栴}，yacc.py 提供的錯誤機(jī)制與 Unix 下的 yacc 類似，所以你可以從諸如 O'Reilly 出版的《Lex and yacc》的書中找到更多的細(xì)節(jié)。

當(dāng)錯誤發(fā)生時，yacc.py 按照如下步驟進(jìn)行：

1. 第一次錯誤產(chǎn)生時，用戶定義的 p_error()方法會被調(diào)用，出錯的標(biāo)記會作為參數(shù)傳入；如果錯誤是因?yàn)榈竭_(dá)文件結(jié)尾造成的，傳入的參數(shù)將為 None。隨后，分析器進(jìn)入到“錯誤恢復(fù)”模式，該模式下不會在產(chǎn)生p_error()調(diào)用，直到它成功的移進(jìn) 3 個標(biāo)記，然后回歸到正常模式。
2. 如果在 p_error() 中沒有指定恢復(fù)動作的話，這個導(dǎo)致錯誤的標(biāo)記會被替換成一個特殊的 error 標(biāo)記。
3. 如果導(dǎo)致錯誤的標(biāo)記已經(jīng)是 error 的話，原先的棧頂?shù)臉?biāo)記將被移除。
4. 如果整個分析棧被放棄，分析器會進(jìn)入重置狀態(tài)，并從他的初始狀態(tài)開始分析。
5. 如果此時的語法規(guī)則接受 error 標(biāo)記，error 標(biāo)記會移進(jìn)棧。
6. 如果當(dāng)前棧頂是 error 標(biāo)記，之后的標(biāo)記將被忽略，直到有標(biāo)記能夠?qū)е?error 的歸約。

根據(jù) error 規(guī)則恢復(fù)和再同步

最佳的處理語法錯誤的做法是在語法規(guī)則中包含 error 標(biāo)記。例如，假設(shè)你的語言有一個關(guān)于 print 的語句的語法規(guī)則：

def p_statement_print(p):
     'statement : PRINT expr SEMI'
     ...

為了處理可能的錯誤表達(dá)式，你可以添加一條額外的語法規(guī)則：

def p_statement_print_error(p):
     'statement : PRINT error SEMI'
     print "Syntax error in print statement. Bad expression"

這樣（expr 錯誤時），error 標(biāo)記會匹配任意多個分號之前的標(biāo)記（分號是SEMI指代的字符）。一旦找到分號，規(guī)則將被匹配，這樣 error 標(biāo)記就被歸約了。

這種類型的恢復(fù)有時稱為"分析器再同步"。error 標(biāo)記扮演了表示所有錯誤標(biāo)記的通配符的角色，而緊隨其后的標(biāo)記扮演了同步標(biāo)記的角色。

重要的一個說明是，通常 error 不會作為語法規(guī)則的最后一個標(biāo)記，像這樣：

def p_statement_print_error(p):
    'statement : PRINT error'
    print "Syntax error in print statement. Bad expression"

這是因?yàn)椋谝粋€導(dǎo)致錯誤的標(biāo)記會使得該規(guī)則立刻歸約，進(jìn)而使得在后面還有錯誤標(biāo)記的情況下，恢復(fù)變得困難。

悲觀恢復(fù)模式

另一個錯誤恢復(fù)方法是采用“悲觀模式”：該模式下，開始放棄剩余的標(biāo)記，直到能夠達(dá)到一個合適的恢復(fù)機(jī)會。

悲觀恢復(fù)模式都是在 p_error() 方法中做到的。例如，這個方法在開始丟棄標(biāo)記后，直到找到閉合的'}'，才重置分析器到初始化狀態(tài)：

def p_error(p):
    print "Whoa. You are seriously hosed."
    # Read ahead looking for a closing '}'
    while 1:
        tok = yacc.token()             # Get the next token
        if not tok or tok.type == 'RBRACE': break
    yacc.restart()

下面這個方法簡單的拋棄錯誤的標(biāo)記，并告知分析器錯誤被接受了：

def p_error(p):
    print "Syntax error at token", p.type
    # Just discard the token and tell the parser it's okay.
    yacc.errok()

在p_error()方法中，有三個可用的方法來控制分析器的行為：

• yacc.errok() 這個方法將分析器從恢復(fù)模式切換回正常模式。這會使得不會產(chǎn)生 error 標(biāo)記，并重置內(nèi)部的 error 計(jì)數(shù)器，而且下一個語法錯誤會再次產(chǎn)生 p_error() 調(diào)用
• yacc.token() 這個方法用于得到下一個標(biāo)記
• yacc.restart() 這個方法拋棄當(dāng)前整個分析棧，并重置分析器為起始狀態(tài)

注意：這三個方法只能在p_error()中使用，不能用在其他任何地方。

p_error()方法也可以返回標(biāo)記，這樣能夠控制將哪個標(biāo)記作為下一個標(biāo)記返回給分析器。這對于需要同步一些特殊標(biāo)記的時候有用，比如：

def p_error(p):
    # Read ahead looking for a terminating ";"
    while 1:
        tok = yacc.token()             # Get the next token
        if not tok or tok.type == 'SEMI': break
    yacc.errok()

    # Return SEMI to the parser as the next lookahead token
    return tok

從產(chǎn)生式中拋出錯誤

如果有需要的話，產(chǎn)生式規(guī)則可以主動的使分析器進(jìn)入恢復(fù)模式。這是通過拋出SyntaxError異常做到的：

def p_production(p):
    'production : some production ...'
    raise SyntaxError

raise SyntaxError 錯誤的效果就如同當(dāng)前的標(biāo)記是錯誤標(biāo)記一樣。因此，當(dāng)你這么做的話，最后一個標(biāo)記將被彈出棧，當(dāng)前的下一個標(biāo)記將是 error 標(biāo)記，分析器進(jìn)入恢復(fù)模式，試圖歸約滿足 error 標(biāo)記的規(guī)則。此后的步驟與檢測到語法錯誤的情況是完全一樣的，p_error() 也會被調(diào)用。

手動設(shè)置錯誤有個重要的方面，就是 p_error() 方法在這種情況下不會調(diào)用。如果你希望記錄錯誤，確保在拋出 SyntaxError 錯誤的產(chǎn)生式中實(shí)現(xiàn)。

注：這個功能是為了模仿 yacc 中的YYERROR宏的行為

錯誤恢復(fù)總結(jié)

對于通常的語言，使用 error 規(guī)則和再同步標(biāo)記可能是最合理的手段。這是因?yàn)槟憧梢詫⒄Z法設(shè)計(jì)成在一個相對容易恢復(fù)和繼續(xù)分析的點(diǎn)捕獲錯誤。悲觀恢復(fù)模式只在一些十分特殊的應(yīng)用中有用，這些應(yīng)用往往需要丟棄掉大量輸入，再尋找合理的同步點(diǎn)。

行號和位置的跟蹤

位置跟蹤通常是個設(shè)計(jì)編譯器時的技巧性玩意兒。默認(rèn)情況下，PLY 跟蹤所有標(biāo)記的行號和位置，這些信息可以這樣得到：

• p.lineno(num) 返回第 num 個符號的行號
• p.lexpos(num) 返回第 num 個符號的詞法位置偏移

例如：

def p_expression(p):
    'expression : expression PLUS expression'
    p.lineno(1)        # Line number of the left expression
    p.lineno(2)        # line number of the PLUS operator
    p.lineno(3)        # line number of the right expression
    ...
    start,end = p.linespan(3)    # Start,end lines of the right expression
    starti,endi = p.lexspan(3)   # Start,end positions of right expression

注意：lexspan() 方法只會返回的結(jié)束位置是最后一個符號的起始位置。

雖然，PLY 對所有符號的行號和位置的跟蹤很管用，但經(jīng)常是不必要的。例如，你僅僅是在錯誤信息中使用行號，你通常可以僅僅使用關(guān)鍵標(biāo)記的信息，比如：

def p_bad_func(p):
    'funccall : fname LPAREN error RPAREN'
    # Line number reported from LPAREN token
    print "Bad function call at line", p.lineno(2)

類似的，為了改善性能，你可以有選擇性的將行號信息在必要的時候進(jìn)行傳遞，這是通過 p.set_lineno() 實(shí)現(xiàn)的，例如：

def p_fname(p):
    'fname : ID'
    p[0] = p[1]
    p.set_lineno(0,p.lineno(1))

對于已經(jīng)完成分析的規(guī)則，PLY 不會保留行號信息，如果你是在構(gòu)建抽象語法樹而且需要行號，你應(yīng)該確保行號保留在樹上。

構(gòu)造抽象語法樹

yacc.py 沒有構(gòu)造抽像語法樹的特殊方法。不過，你可以自己很簡單的構(gòu)造出來。

一個最為簡單的構(gòu)造方法是為每個語法規(guī)則創(chuàng)建元組或者字典，并傳遞它們。有很多中可行的方案，下面是一個例子：

def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression'''

    p[0] = ('binary-expression',p[2],p[1],p[3])

def p_expression_group(p):
    'expression : LPAREN expression RPAREN'
    p[0] = ('group-expression',p[2])

def p_expression_number(p):
    'expression : NUMBER'
    p[0] = ('number-expression',p[1])

另一種方法可以是為不同的抽象樹節(jié)點(diǎn)創(chuàng)建一系列的數(shù)據(jù)結(jié)構(gòu)，并賦值給 p[0]：

class Expr: pass

class BinOp(Expr):
    def __init__(self,left,op,right):
        self.type = "binop"
        self.left = left
        self.right = right
        self.op = op

class Number(Expr):
    def __init__(self,value):
        self.type = "number"
        self.value = value

def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression'''

    p[0] = BinOp(p[1],p[2],p[3])

def p_expression_group(p):
    'expression : LPAREN expression RPAREN'
    p[0] = p[2]

def p_expression_number(p):
    'expression : NUMBER'
    p[0] = Number(p[1])

這種方式的好處是在處理復(fù)雜語義時比較簡單：類型檢查、代碼生成、以及其他針對樹節(jié)點(diǎn)的功能。

為了簡化樹的遍歷，可以創(chuàng)建一個通用的樹節(jié)點(diǎn)結(jié)構(gòu)，例如：

class Node:
    def __init__(self,type,children=None,leaf=None):
         self.type = type
         if children:
              self.children = children
         else:
              self.children = [ ]
         self.leaf = leaf

def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression'''

    p[0] = Node("binop", [p[1],p[3]], p[2])

嵌入式動作

yacc 使用的分析技術(shù)只允許在規(guī)則規(guī)約后執(zhí)行動作。假設(shè)有如下規(guī)則：

def p_foo(p):
    "foo : A B C D"
    print "Parsed a foo", p[1],p[2],p[3],p[4]

方法只會在符號 A,B,C和D 都完成后才能執(zhí)行?？墒怯械臅r候，在中間階段執(zhí)行一小段代碼是有用的。假如，你想在 A 完成后立即執(zhí)行一些動作，像下面這樣用空規(guī)則：

def p_foo(p):
    "foo : A seen_A B C D"
    print "Parsed a foo", p[1],p[3],p[4],p[5]
    print "seen_A returned", p[2]

def p_seen_A(p):
    "seen_A :"
    print "Saw an A = ", p[-1]   # Access grammar symbol to left
    p[0] = some_value            # Assign value to seen_A

在這個例子中，空規(guī)則 seen_A 將在 A 移進(jìn)分析棧后立即執(zhí)行。p[-1] 指代的是在分析棧上緊跟在 seen_A 左側(cè)的符號。在這個例子中，是 A 符號。像其他普通的規(guī)則一樣，在嵌入式行為中也可以通過為 p[0] 賦值來返回某些值。

使用嵌入式動作可能會導(dǎo)致移進(jìn)歸約沖突，比如，下面的語法是沒有沖突的：

def p_foo(p):
    """foo : abcd
           | abcx"""

def p_abcd(p):
    "abcd : A B C D"

def p_abcx(p):
    "abcx : A B C X"

可是，如果像這樣插入一個嵌入式動作：

def p_foo(p):
    """foo : abcd
           | abcx"""

def p_abcd(p):
    "abcd : A B C D"

def p_abcx(p):
    "abcx : A B seen_AB C X"

def p_seen_AB(p):
    "seen_AB :"

會產(chǎn)生移進(jìn)歸約沖，只是由于對于兩個規(guī)則 abcd 和 abcx 中的 C，分析器既可以根據(jù) abcd 規(guī)則移進(jìn)，也可以根據(jù) abcx 規(guī)則先將空的 seen_AB 歸約。

嵌入動作的一般用于分析以外的控制，比如為本地變量定義作用于。對于 C 語言：

def p_statements_block(p):
    "statements: LBRACE new_scope statements RBRACE"""
    # Action code
    ...
    pop_scope()        # Return to previous scope

def p_new_scope(p):
    "new_scope :"
    # Create a new scope for local variables
    s = new_scope()
    push_scope(s)
    ...

在這個例子中，new_scope 作為嵌入式行為，在左大括號{之后立即執(zhí)行?？梢允钦{(diào)正內(nèi)部符號表或者其他方面。statements_block 一完成，代碼可能會撤銷在嵌入動作時的操作（比如，pop_scope())

Yacc 的其他

• 默認(rèn)的分析方法是 LALR，使用 SLR 請像這樣運(yùn)行 yacc()：yacc.yacc(method="SLR") 注意：LRLR 生成的分析表大約要比 SLR 的大兩倍。解析的性能沒有本質(zhì)的區(qū)別，因?yàn)榇a是一樣的。由于 LALR 能力稍強(qiáng)，所以更多的用于復(fù)雜的語法。
• 默認(rèn)情況下，yacc.py 依賴 lex.py 產(chǎn)生的標(biāo)記。不過，可以用一個等價的詞法標(biāo)記生成器代替： yacc.parse(lexer=x) 這個例子中，x 必須是一個 Lexer 對象，至少擁有 x.token() 方法用來獲取標(biāo)記。如果將輸入字串提供給 yacc.parse()，lexer 還必須具有 x.input() 方法。
• 默認(rèn)情況下，yacc 在調(diào)試模式下生成分析表（會生成 parser.out 文件和其他東西），使用 yacc.yacc(debug=0) 禁用調(diào)試模式。
• 改變 parsetab.py 的文件名：yacc.yacc(tabmodule="foo")
• 改變 parsetab.py 的生成目錄：yacc.yacc(tabmodule="foo",outputdir="somedirectory")
• 不生成分析表：yacc.yacc(write_tables=0)。注意：如果禁用分析表生成，yacc()將在每次運(yùn)行的時候重新構(gòu)建分析表（這里耗費(fèi)的時候取決于語法文件的規(guī)模）
• 想在分析過程中輸出豐富的調(diào)試信息，使用：yacc.parse(debug=1)
• yacc.yacc()方法會返回分析器對象，如果你想在一個程序中支持多個分析器：

p = yacc.yacc()
...
p.parse()

注意：yacc.parse() 方法只綁定到最新創(chuàng)建的分析器對象上。

• 由于生成生成 LALR 分析表相對開銷較大，先前生成的分析表會被緩存和重用。判斷是否重新生成的依據(jù)是對所有的語法規(guī)則和優(yōu)先級規(guī)則進(jìn)行 MD5 校驗(yàn)，只有不匹配時才會重新生成。生成分析表是合理有效的辦法，即使是面對上百個規(guī)則和狀態(tài)的語法。對于復(fù)雜的編程語言，像 C 語言，在一些慢的機(jī)器上生成分析表可能要花費(fèi) 30-60 秒，請耐心。
• 由于 LR 分析過程是基于分析表的，分析器的性能很大程度上取決于語法的規(guī)模。最大的瓶頸可能是詞法分析器和語法規(guī)則的復(fù)雜度。