【百度云搜索获讳，搜各種資料:http://bdy.lqkweb.com】

【搜網(wǎng)盤，搜各種資料:http://www.swpan.cn】

6.6 處理二義文法

上面例子中假哎，對表達式的文法描述用一種特別的形式規(guī)避了二義文法吝梅。然而员咽，在很多情況下，這樣的特殊文法很難寫力试，或者很別扭徙邻。一個更為自然和舒服的語法表達應(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中存在二義文法，會輸出”移進歸約沖突”或者”歸約歸約沖突”伍伤。在分析器無法確定是將下一個符號移進棧還是將當前棧中的符號歸約時會產(chǎ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 ????

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

默認情況下付翁，所有的移進歸約沖突會傾向于使用移進來處理。因此晃听，對于上面的例子百侧，分析器總是會將’+’進棧，而不是做歸約能扒。雖然在很多情況下佣渴，這個策略是合適的（像”if-then”和”if-then-else”），但這對于算術(shù)表達式是不夠的初斑。事實上辛润，對于上面的例子，將’+’進棧是完全錯誤的见秤，應(yīng)當先將expr * expr歸約砂竖，因為乘法的優(yōu)先級要高于加法。

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

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

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

由于為標記添加了數(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)

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

• 如果當前的標記的優(yōu)先級高于棧頂規(guī)則的優(yōu)先級脏款，移進當前標記
• 如果棧頂規(guī)則的優(yōu)先級更高，進行歸約
• 如果當前的標記與棧頂規(guī)則的優(yōu)先級相同裤园，如果標記是左結(jié)合的撤师，則歸約，否則拧揽，如果是右結(jié)合的則移進
• 如果沒有優(yōu)先級可以參考剃盾，默認對于移進歸約沖突執(zhí)行移進

比如，當解析到”expression PLUS expression”這個語法時淤袜，下一個標記是TIMES痒谴，此時將執(zhí)行移進，因為TIMES具有比PLUS更高的優(yōu)先級铡羡；當解析到”expression TIMES expression”积蔚，下一個標記是PLUS，此時將執(zhí)行歸約烦周，因為PLUS的優(yōu)先級低于TIMES尽爆。

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

使用precedence指定優(yōu)先級的技術(shù)會帶來一個問題漱贱，有時運算符的優(yōu)先級需要基于上下文。例如夭委，考慮”3 + 4 * -5”中的一元的’-‘幅狮。數(shù)學上講，一元運算符應(yīng)當擁有較高的優(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)先級應(yīng)用在該語法規(guī)則上捆交。

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

還可以在precedence表中指定”非關(guān)聯(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時挨厚，將產(chǎn)生語法錯誤，卻不影響形如a < b的表達式糠惫。

對于給定的符號集疫剃，存在多種語法規(guī)則可以匹配時會產(chǎn)生歸約/歸約沖突。這樣的沖突往往很嚴重寞钥，而且總是通過匹配最早出現(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ī)則將產(chǎn)生歸約/歸約沖突：

assignment  : ID EQUALS NUMBER
expression  : NUMBER

比如咨油，對于”a = 5”您炉，分析器不知道應(yīng)當按照assignment : ID EQUALS NUMBER歸約，還是先將5歸約成expression役电，再歸約成assignment : ID EQUALS expression赚爵。

應(yī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)

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

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

使用LR分析算法跟蹤移進/歸約沖突和歸約/歸約沖突是件樂在其中的事赐纱。為了輔助調(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)，代表了有效輸入標記的所有可能的組合疙描，這是依據(jù)文法規(guī)則得到的诚隙。當?shù)玫捷斎霕擞洉r，分析器將構(gòu)造一個棧起胰，并找到匹配的規(guī)則久又。每個狀態(tài)跟蹤了當前輸入進行到語法規(guī)則中的哪個位置，在每個規(guī)則中效五，’.’表示當前分析到規(guī)則的哪個位置籽孙，而且，對于在當前狀態(tài)下火俄，輸入的每個有效標記導(dǎo)致的動作也被羅列出來犯建。當出現(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ī)則并結(jié)合一些實例适瓦，通常能夠找到大部分沖突的根源。應(yīng)該強調(diào)的是谱仪，不是所有的移進歸約沖突都是不好的玻熙，想要確定解決方法是否正確，唯一的辦法就是查看parser.out疯攒。

6.8 處理語法錯誤

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

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

• 第一次錯誤產(chǎn)生時渠脉，用戶定義的p_error()方法會被調(diào)用宇整，出錯的標記會作為參數(shù)傳入；如果錯誤是因為到達文件結(jié)尾造成的芋膘，傳入的參數(shù)將為None鳞青。隨后，分析器進入到“錯誤恢復(fù)”模式为朋，該模式下不會在產(chǎn)生p_error()調(diào)用臂拓，直到它成功的移進3個標記，然后回歸到正常模式习寸。
• 如果在p_error()中沒有指定恢復(fù)動作的話胶惰，這個導(dǎo)致錯誤的標記會被替換成一個特殊的error標記。
• 如果導(dǎo)致錯誤的標記已經(jīng)是error的話霞溪，原先的棧頂?shù)臉擞泴⒈灰瞥?/li>
• 如果整個分析棧被放棄孵滞，分析器會進入重置狀態(tài)，并從他的初始狀態(tài)開始分析鸯匹。
• 如果此時的語法規(guī)則接受error標記坊饶，error標記會移進棧。
• 如果當前棧頂是error標記殴蓬，之后的標記將被忽略匿级，直到有標記能夠?qū)е?code>error的歸約。

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

最佳的處理語法錯誤的做法是在語法規(guī)則中包含error標記染厅。例如痘绎，假設(shè)你的語言有一個關(guān)于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標記就被歸約了。

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

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

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

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

6.8.2 悲觀恢復(fù)模式

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

悲觀恢復(fù)模式都是在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() 這個方法將分析器從恢復(fù)模式切換回正常模式。這會使得不會產(chǎn)生error標記庆寺，并重置內(nèi)部的error計數(shù)器蚊夫，而且下一個語法錯誤會再次產(chǎn)生p_error()調(diào)用
• 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

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

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

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

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

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

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

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

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

6.9 行號和位置的跟蹤

位置跟蹤通常是個設(shè)計編譯器時的技巧性玩意兒便贵。默認情況下，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()方法只會返回的結(jié)束位置是最后一個符號的起始位置承璃。

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

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

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

6.10 構(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é)點創(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é)點的功能。

為了簡化樹的遍歷蛮位，可以創(chuàng)建一個通用的樹節(jié)點結(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])

6.11 嵌入式動作

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í)行土至」憾裕可是有的時候，在中間階段執(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左側(cè)的符號。在這個例子中烘苹，是A符號躲株。像其他普通的規(guī)則一樣，在嵌入式行為中也可以通過為p[0]賦值來返回某些值镣衡。

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

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)生移進歸約沖望浩，只是由于對于兩個規(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í)行啦吧∧酰可以是調(diào)正內(nèi)部符號表或者其他方面。statements_block一完成授滓，代碼可能會撤銷在嵌入動作時的操作（比如琳水，pop_scope())

6.12 Yacc的其他

• 默認的分析方法是LALR，使用SLR請像這樣運行yacc()：yacc.yacc(method=”SLR”)注意：LRLR生成的分析表大約要比SLR的大兩倍褒墨。解析的性能沒有本質(zhì)的區(qū)別炫刷，因為代碼是一樣的。由于LALR能力稍強郁妈，所以更多的用于復(fù)雜的語法浑玛。
• 默認情況下，yacc.py依賴lex.py產(chǎn)生的標記噩咪。不過顾彰，可以用一個等價的詞法標記生成器代替：yacc.parse(lexer=x) 這個例子中，x必須是一個Lexer對象胃碾，至少擁有x.token()方法用來獲取標記涨享。如果將輸入字串提供給yacc.parse()，lexer還必須具有x.input()方法仆百。
• 默認情況下厕隧，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()將在每次運行的時候重新構(gòu)建分析表（這里耗費的時候取決于語法文件的規(guī)模）
• 想在分析過程中輸出豐富的調(diào)試信息，使用：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)的語法争舞。對于復(fù)雜的編程語言，像C語言疗韵，在一些慢的機器上生成分析表可能要花費30-60秒兑障，請耐心。
• 由于LR分析過程是基于分析表的蕉汪，分析器的性能很大程度上取決于語法的規(guī)模流译。最大的瓶頸可能是詞法分析器和語法規(guī)則的復(fù)雜度。

7 多個語法和詞法分析器

在高級的分析器程序中者疤，你可能同時需要多個語法和詞法分析器福澡。

依照規(guī)則行事不會有問題。不過驹马，你需要小心確定所有東西都正確的綁定(hooked up)了革砸。首先，保證將lex()和yacc()返回的對象保存起來：

lexer  = lex.lex()       # Return lexer object
parser = yacc.yacc()     # Return parser object

接著糯累，在解析時算利，確保給parse()方法一個正確的lexer引用：

parser.parse(text,lexer=lexer)

如果遺漏這一步，分析器會使用最新創(chuàng)建的lexer對象泳姐，這可能不是你希望的效拭。

詞法器和語法器的方法中也可以訪問這些對象。在詞法器中胖秒，標記的lexer屬性指代的是當前觸發(fā)規(guī)則的詞法器對象：

def t_NUMBER(t):
   r'\d+'
   ...
   print t.lexer           # Show lexer object

在語法器中缎患，lexer和parser屬性指代的是對應(yīng)的詞法器對象和語法器對象

def p_expr_plus(p):
   'expr : expr PLUS expr'
   ...
   print p.parser          # Show parser object
   print p.lexer           # Show lexer object

如果有必要，lexer對象和parser對象都可以附加其他屬性阎肝。例如挤渔，你想要有不同的解析器狀態(tài)，可以為為parser對象附加更多的屬性风题，并在后面用到它們判导。

8 使用Python的優(yōu)化模式

由于PLY從文檔字串中獲取信息锚扎，語法解析和詞法分析信息必須通過正常模式下的Python解釋器得到（不帶有-O或者-OO選項）洞翩。不過检号，如果你像這樣指定optimize模式：

lex.lex(optimize=1)
yacc.yacc(optimize=1)

PLY可以在下次執(zhí)行赴肚，在Python的優(yōu)化模式下執(zhí)行稽鞭。但你必須確保第一次執(zhí)行是在Python的正常模式下進行鸟整，一旦詞法分析表和語法分析表生成一次后，在Python優(yōu)化模式下執(zhí)行朦蕴，PLY會使用生成好的分析表而不再需要文檔字串篮条。

注意：在優(yōu)化模式下執(zhí)行PLY會禁用很多錯誤檢查機制。你應(yīng)該只在程序穩(wěn)定后吩抓，不再需要調(diào)試的情況下這樣做涉茧。使用優(yōu)化模式的目的應(yīng)該是大幅減少你的編譯器的啟動時間（萬事俱備只欠東風時）

9 高級調(diào)試

調(diào)試一個編譯器不是件容易的事情。PLY提供了一些高級的調(diào)試能力疹娶，這是通過Python的logging模塊實現(xiàn)的伴栓，下面兩節(jié)介紹這一主題：

9.1 調(diào)試lex()和yacc()命令

lex()和yacc()命令都有調(diào)試模式，可以通過debug標識實現(xiàn)：

lex.lex(debug=True)
yacc.yacc(debug=True)

正常情況下雨饺，調(diào)試不僅輸出標準錯誤钳垮，對于yacc()，還會給出parser.out文件额港。這些輸出可以通過提供logging對象來精細的控制饺窿。下面這個例子增加了對調(diào)試信息來源的輸出：

# Set up a logging object
import logging
logging.basicConfig(
    level = logging.DEBUG,
    filename = "parselog.txt",
    filemode = "w",
    format = "%(filename)10s:%(lineno)4d:%(message)s"
)
log = logging.getLogger()

lex.lex(debug=True,debuglog=log)
yacc.yacc(debug=True,debuglog=log)

如果你提供一個自定義的logger，大量的調(diào)試信息可以通過分級來控制移斩。典型的是將調(diào)試信息分為DEBUG,INFO,或者WARNING三個級別肚医。

PLY的錯誤和警告信息通過日志接口提供，可以從errorlog參數(shù)中傳入日志對象

lex.lex(errorlog=log)
yacc.yacc(errorlog=log)

如果想完全過濾掉警告信息向瓷，你除了可以使用帶級別過濾功能的日志對象肠套，也可以使用lex和yacc模塊都內(nèi)建的Nulllogger對象。例如：

yacc.yacc(errorlog=yacc.NullLogger())

9.2 運行時調(diào)試

為分析器指定debug選項猖任，可以激活語法分析器的運行時調(diào)試功能你稚。這個選項可以是整數(shù)（表示對調(diào)試功能是開還是關(guān)），也可以是logger對象超升。例如：

log = logging.getLogger()
parser.parse(input,debug=log)

如果傳入日志對象的話入宦，你可以使用其級別過濾功能來控制內(nèi)容的輸出。INFO級別用來產(chǎn)生歸約信息室琢；DEBUG級別會顯示分析棧的信息乾闰、移進的標記和其他詳細信息。ERROR級別顯示分析過程中的錯誤相關(guān)信息盈滴。

對于每個復(fù)雜的問題涯肩，你應(yīng)該用日志對象轿钠，以便輸出重定向到文件中，進而方便在執(zhí)行結(jié)束后檢查病苗。

10 如何繼續(xù)

PLY分發(fā)包中的example目錄包含幾個簡單的示例疗垛。對于理論性的東西以及LR分析發(fā)的實現(xiàn)細節(jié)，應(yīng)當從編譯器相關(guān)的書籍中學習硫朦。