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

一個例子

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

# 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 的方法，方法的文檔字符串描述了相應的上下文無關文法，方法的語句實現(xiàn)了對應規(guī)則的語義行為。每個方法接受一個單獨的 p 參數(shù)，p 是一個包含有當前匹配語法的符號的序列，p[i] 與語法符號的對應關系如下：

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

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

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

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

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

$ python calcparse.py
Generating LALR tables
calc >

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

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

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

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

這個例子的最后部分展示了如何執(zhí)行由 yacc() 方法創(chuàng)建的分析器。你只需要簡單的調用 parse()，并將輸入字符串作為參數(shù)就能運行分析器。它將運行所有的語法規(guī)則，并返回整個分析的結果，這個結果就是在起始規(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ī)則都有相似的結構，那么將語法規(guī)則合并才是個不錯的注意（比如，產生式的項數(shù)相同）。不然，語義動作可能會變得復雜。不過，簡單情況下，可以使用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]

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

字面字符

如果愿意，可以在語法規(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]

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

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

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

空產生式

yacc.py 可以處理空產生式，像下面這樣做：

def p_empty(p):
    'empty :'
    pass

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

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

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

改變起始符號

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

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 標識有助于在調試的時候將大型的語法規(guī)則分成小部分來分析。也可把 start 符號作為yacc的參數(shù)：

yacc.yacc(start='foo')

處理二義文法

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

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 中存在二義文法，會輸出"移進歸約沖突"或者"歸約歸約沖突"。在分析器無法確定是將下一個符號移進棧還是將當前棧中的符號歸約時會產生移進歸約沖突。例如，對于"3 * 4 + 5"，分析器內部棧是這樣工作的：

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 ????

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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 覆蓋了默認的優(yōu)先級（MINUS 的優(yōu)先級），將 UMINUS 指代的優(yōu)先級應用在該語法規(guī)則上。

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

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

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

此時，當輸入形如 a < b < c 時，將產生語法錯誤，卻不影響形如 a < b 的表達式。

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

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ī)則將產生歸約/歸約沖突：

assignment  : ID EQUALS NUMBER
expression  : NUMBER

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

應當指出的是，只是簡單的查看語法規(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)

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

parser.out調試文件

使用 LR 分析算法跟蹤移進/歸約沖突和歸約/歸約沖突是件樂在其中的事。為了輔助調試，yacc.py 在生成分析表時會創(chuàng)建出一個調試文件叫 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)，代表了有效輸入標記的所有可能的組合，這是依據(jù)文法規(guī)則得到的。當?shù)玫捷斎霕擞洉r，分析器將構造一個棧，并找到匹配的規(guī)則。每個狀態(tài)跟蹤了當前輸入進行到語法規(guī)則中的哪個位置，在每個規(guī)則中，'.'表示當前分析到規(guī)則的哪個位置，而且，對于在當前狀態(tài)下，輸入的每個有效標記導致的動作也被羅列出來。當出現(xià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ī)則并結合一些實例，通常能夠找到大部分沖突的根源。應該強調的是，不是所有的移進歸約沖突都是不好的，想要確定解決方法是否正確，唯一的辦法就是查看 parser.out。

處理語法錯誤

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

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

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

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

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

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

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

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

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

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

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

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

這是因為，第一個導致錯誤的標記會使得該規(guī)則立刻歸約，進而使得在后面還有錯誤標記的情況下，恢復變得困難。

悲觀恢復模式

另一個錯誤恢復方法是采用“悲觀模式”：該模式下，開始放棄剩余的標記，直到能夠達到一個合適的恢復機會。

悲觀恢復模式都是在 p_error() 方法中做到的。例如，這個方法在開始丟棄標記后，直到找到閉合的'}'，才重置分析器到初始化狀態(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()

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

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() 這個方法將分析器從恢復模式切換回正常模式。這會使得不會產生 error 標記，并重置內部的 error 計數(shù)器，而且下一個語法錯誤會再次產生 p_error() 調用
• yacc.token() 這個方法用于得到下一個標記
• yacc.restart() 這個方法拋棄當前整個分析棧，并重置分析器為起始狀態(tài)

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

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

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

從產生式中拋出錯誤

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

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

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

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

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

錯誤恢復總結

對于通常的語言，使用 error 規(guī)則和再同步標記可能是最合理的手段。這是因為你可以將語法設計成在一個相對容易恢復和繼續(xù)分析的點捕獲錯誤。悲觀恢復模式只在一些十分特殊的應用中有用，這些應用往往需要丟棄掉大量輸入，再尋找合理的同步點。

行號和位置的跟蹤

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

• 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() 方法只會返回的結束位置是最后一個符號的起始位置。

雖然，PLY 對所有符號的行號和位置的跟蹤很管用，但經常是不必要的。例如，你僅僅是在錯誤信息中使用行號，你通?？梢詢H僅使用關鍵標記的信息，比如：

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)

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

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

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

構造抽象語法樹

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

一個最為簡單的構造方法是為每個語法規(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é)點創(chuàng)建一系列的數(shù)據(jù)結構，并賦值給 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])

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

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

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 使用的分析技術只允許在規(guī)則規(guī)約后執(zhí)行動作。假設有如下規(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 移進分析棧后立即執(zhí)行。p[-1] 指代的是在分析棧上緊跟在 seen_A 左側的符號。在這個例子中，是 A 符號。像其他普通的規(guī)則一樣，在嵌入式行為中也可以通過為 p[0] 賦值來返回某些值。

使用嵌入式動作可能會導致移進歸約沖突，比如，下面的語法是沒有沖突的：

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 :"

會產生移進歸約沖，只是由于對于兩個規(guī)則 abcd 和 abcx 中的 C，分析器既可以根據(jù) abcd 規(guī)則移進，也可以根據(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í)行?？梢允钦{正內部符號表或者其他方面。statements_block 一完成，代碼可能會撤銷在嵌入動作時的操作（比如，pop_scope())

Yacc 的其他

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

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

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

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