6.4 空產生式 · 【譯】Python Lex Yacc手冊

### 6.6 處理二義文法上面例子中，對表達式的文法描述用一種特別的形式規避了二義文法。然而，在很多情況下，這樣的特殊文法很難寫，或者很別扭。一個更為自然和舒服的語法表達應該是這樣的： ~~~ 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歸約，一是將標記’+’繼續移進棧。兩種選擇對于上面的上下文無關文法而言都是合法的。默認情況下，所有的移進歸約沖突會傾向于使用移進來處理。因此，對于上面的例子，分析器總是會將’+’進棧，而不是做歸約。雖然在很多情況下，這個策略是合適的（像”if-then”和”if-then-else”），但這對于算術表達式是不夠的。事實上，對于上面的例子，將’+’進棧是完全錯誤的，應當先將expr * expr歸約，因為乘法的優先級要高于加法。為了解決二義文法，尤其是對表達式文法，yacc.py允許為標記單獨指定優先級和結合性。需要像下面這樣增加一個precedence變量： ~~~ precedence = ( ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ) ~~~ 這樣的定義說明PLUS/MINUS標記具有相同的優先級和左結合性，TIMES/DIVIDE具有相同的優先級和左結合性。在precedence聲明中，標記的優先級從低到高。因此，這個聲明表明TIMES/DIVIDE（他們較晚加入precedence）的優先級高于PLUS/MINUS。由于為標記添加了數字表示的優先級和結合性的屬性，所以，對于上面的例子，將會得到： ~~~ PLUS : level = 1, assoc = 'left' MINUS : level = 1, assoc = 'left' TIMES : level = 2, assoc = 'left' DIVIDE : level = 2, assoc = 'left' ~~~ 隨后這些值被附加到語法規則的優先級和結合性屬性上，這些值由最右邊的終結符的優先級和結合性決定： ~~~ 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) ~~~ 當出現移進歸約沖突時，分析器生成器根據下面的規則解決二義文法： 1. 如果當前的標記的優先級高于棧頂規則的優先級，移進當前標記 2. 如果棧頂規則的優先級更高，進行歸約 3. 如果當前的標記與棧頂規則的優先級相同，如果標記是左結合的，則歸約，否則，如果是右結合的則移進 4. 如果沒有優先級可以參考，默認對于移進歸約沖突執行移進比如，當解析到”expression PLUS expression”這個語法時，下一個標記是TIMES，此時將執行移進，因為TIMES具有比PLUS更高的優先級；當解析到”expression TIMES expression”，下一個標記是PLUS，此時將執行歸約，因為PLUS的優先級低于TIMES。如果在使用前三種技術解決已經歸約沖突后，yacc.py將不會報告語法中的沖突或者錯誤（不過，會在parser.out這個調試文件中輸出一些信息）使用precedence指定優先級的技術會帶來一個問題，有時運算符的優先級需要基于上下文。例如，考慮”3 + 4 * -5”中的一元的’-‘。數學上講，一元運算符應當擁有較高的優先級。然而，在我們的precedence定義中，MINUS的優先級卻低于TIMES。為了解決這個問題，precedene規則中可以包含”虛擬標記”： ~~~ 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覆蓋了默認的優先級（MINUS的優先級），將UMINUS指代的優先級應用在該語法規則上。起初，UMINUS標記的例子會讓人感到困惑。UMINUS既不是輸入的標記也不是語法規則，你應當將其看成precedence表中的特殊的占位符。當你使用%prec宏時，你是在告訴yacc，你希望表達式使用這個占位符所表示的優先級，而不是正常的優先級。還可以在precedence表中指定”非關聯”。這表明你不希望鏈式運算符。比如，假如你希望支持比較運算符’’，但是你不希望支持 a < b < c，只要簡單指定規則如下： ~~~ precedence = ( ('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ('right', 'UMINUS'), # Unary minus operator ) ~~~ 此時，當輸入形如 a < b < c時，將產生語法錯誤，卻不影響形如 a < b 的表達式。對于給定的符號集，存在多種語法規則可以匹配時會產生歸約/歸約沖突。這樣的沖突往往很嚴重，而且總是通過匹配最早出現的語法規則來解決。歸約/歸約沖突幾乎總是相同的符號集合具有不同的規則可以匹配，而在這一點上無法抉擇，比如： ~~~ assignment : ID EQUALS NUMBER | ID EQUALS expression expression : expression PLUS expression | expression MINUS expression | expression TIMES expression | expression DIVIDE expression | LPAREN expression RPAREN | NUMBER ~~~ 這個例子中，對于下面這兩條規則將產生歸約/歸約沖突： ~~~ assignment : ID EQUALS NUMBER expression : NUMBER ~~~ 比如，對于”a = 5”，分析器不知道應當按照assignment : ID EQUALS NUMBER歸約，還是先將5歸約成expression，再歸約成assignment : ID EQUALS expression。應當指出的是，只是簡單的查看語法規則是很難減少歸約/歸約沖突。如果出現歸約/歸約沖突，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) ~~~ 上面的信息標識出了沖突的兩條規則，但是，并無法指出究竟在什么情況下會出現這樣的狀態。想要發現問題，你可能需要結合語法規則和`parser.out`調試文件的內容。 ### 6.7 parser.out調試文件使用LR分析算法跟蹤移進/歸約沖突和歸約/歸約沖突是件樂在其中的事。為了輔助調試，yacc.py在生成分析表時會創建出一個調試文件叫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 ~~~ 文件中出現的不同狀態，代表了有效輸入標記的所有可能的組合，這是依據文法規則得到的。當得到輸入標記時，分析器將構造一個棧，并找到匹配的規則。每個狀態跟蹤了當前輸入進行到語法規則中的哪個位置，在每個規則中，’.’表示當前分析到規則的哪個位置，而且，對于在當前狀態下，輸入的每個有效標記導致的動作也被羅列出來。當出現移進/歸約或歸約/歸約沖突時，被忽略的規則前面會添加!，就像這樣： ~~~ ! TIMES [ reduce using rule 2 ] ! DIVIDE [ reduce using rule 2 ] ! PLUS [ shift and go to state 6 ] ! MINUS [ shift and go to state 5 ] ~~~ 通過查看這些規則并結合一些實例，通常能夠找到大部分沖突的根源。應該強調的是，不是所有的移進歸約沖突都是不好的，想要確定解決方法是否正確，唯一的辦法就是查看parser.out。 ### 6.8 處理語法錯誤如果你創建的分析器用于產品，處理語法錯誤是很重要的。一般而言，你不希望分析器在遇到錯誤的時候就拋出異常并終止，相反，你需要它報告錯誤，盡可能的恢復并繼續分析，一次性的將輸入中所有的錯誤報告給用戶。這是一些已知語言編譯器的標準行為，例如C,C++,Java。在PLY中，在語法分析過程中出現錯誤，錯誤會被立即檢測到（分析器不會繼續讀取源文件中錯誤點后面的標記）。然而，這時，分析器會進入恢復模式，這個模式能夠用來嘗試繼續向下分析。LR分析器的錯誤恢復是個理論與技巧兼備的問題，yacc.py提供的錯誤機制與Unix下的yacc類似，所以你可以從諸如O’Reilly出版的《Lex and yacc》的書中找到更多的細節。當錯誤發生時，yacc.py按照如下步驟進行： 1. 第一次錯誤產生時，用戶定義的p_error()方法會被調用，出錯的標記會作為參數傳入；如果錯誤是因為到達文件結尾造成的，傳入的參數將為None。隨后，分析器進入到“錯誤恢復”模式，該模式下不會在產生`p_error()`調用，直到它成功的移進3個標記，然后回歸到正常模式。 2. 如果在p_error()中沒有指定恢復動作的話，這個導致錯誤的標記會被替換成一個特殊的error標記。 3. 如果導致錯誤的標記已經是error的話，原先的棧頂的標記將被移除。 4. 如果整個分析棧被放棄，分析器會進入重置狀態，并從他的初始狀態開始分析。 5. 如果此時的語法規則接受error標記，error標記會移進棧。 6. 如果當前棧頂是error標記，之后的標記將被忽略，直到有標記能夠導致error的歸約。 #### 6.8.1 根據error規則恢復和再同步最佳的處理語法錯誤的做法是在語法規則中包含error標記。例如，假設你的語言有一個關于print的語句的語法規則： ~~~ def p_statement_print(p): 'statement : PRINT expr SEMI' ... ~~~ 為了處理可能的錯誤表達式，你可以添加一條額外的語法規則： ~~~ def p_statement_print_error(p): 'statement : PRINT error SEMI' print "Syntax error in print statement. Bad expression" ~~~ 這樣（expr錯誤時），error標記會匹配任意多個分號之前的標記（分號是`SEMI`指代的字符）。一旦找到分號，規則將被匹配，這樣error標記就被歸約了。這種類型的恢復有時稱為”分析器再同步”。error標記扮演了表示所有錯誤標記的通配符的角色，而緊隨其后的標記扮演了同步標記的角色。重要的一個說明是，通常error不會作為語法規則的最后一個標記，像這樣： ~~~ def p_statement_print_error(p): 'statement : PRINT error' print "Syntax error in print statement. Bad expression" ~~~ 這是因為，第一個導致錯誤的標記會使得該規則立刻歸約，進而使得在后面還有錯誤標記的情況下，恢復變得困難。 #### 6.8.2 悲觀恢復模式另一個錯誤恢復方法是采用“悲觀模式”：該模式下，開始放棄剩余的標記，直到能夠達到一個合適的恢復機會。悲觀恢復模式都是在p_error()方法中做到的。例如，這個方法在開始丟棄標記后，直到找到閉合的’}’，才重置分析器到初始化狀態： ~~~ 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計數器，而且下一個語法錯誤會再次產生p_error()調用 * `yacc.token()`?這個方法用于得到下一個標記 * `yacc.restart()`?這個方法拋棄當前整個分析棧，并重置分析器為起始狀態注意：這三個方法只能在`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 從產生式中拋出錯誤如果有需要的話，產生式規則可以主動的使分析器進入恢復模式。這是通過拋出`SyntacError`異常做到的： ~~~ def p_production(p): 'production : some production ...' raise SyntaxError ~~~ raise SyntaxError錯誤的效果就如同當前的標記是錯誤標記一樣。因此，當你這么做的話，最后一個標記將被彈出棧，當前的下一個標記將是error標記，分析器進入恢復模式，試圖歸約滿足error標記的規則。此后的步驟與檢測到語法錯誤的情況是完全一樣的，p_error()也會被調用。手動設置錯誤有個重要的方面，就是p_error()方法在這種情況下不會調用。如果你希望記錄錯誤，確保在拋出SyntaxError錯誤的產生式中實現。注：這個功能是為了模仿yacc中的`YYERROR`宏的行為 #### 6.8.4 錯誤恢復總結對于通常的語言，使用error規則和再同步標記可能是最合理的手段。這是因為你可以將語法設計成在一個相對容易恢復和繼續分析的點捕獲錯誤。悲觀恢復模式只在一些十分特殊的應用中有用，這些應用往往需要丟棄掉大量輸入，再尋找合理的同步點。 #### 6.9 行號和位置的跟蹤位置跟蹤通常是個設計編譯器時的技巧性玩意兒。默認情況下，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對所有符號的行號和位置的跟蹤很管用，但經常是不必要的。例如，你僅僅是在錯誤信息中使用行號，你通常可以僅僅使用關鍵標記的信息，比如： ~~~ 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()實現的，例如： ~~~ def p_fname(p): 'fname : ID' p[0] = p[1] p.set_lineno(0,p.lineno(1)) ~~~ 對于已經完成分析的規則，PLY不會保留行號信息，如果你是在構建抽象語法樹而且需要行號，你應該確保行號保留在樹上。 ### 6.10 構造抽象語法樹 yacc.py沒有構造抽像語法樹的特殊方法。不過，你可以自己很簡單的構造出來。一個最為簡單的構造方法是為每個語法規則創建元組或者字典，并傳遞它們。有很多中可行的方案，下面是一個例子： ~~~ 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]) ~~~ 另一種方法可以是為不同的抽象樹節點創建一系列的數據結構，并賦值給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]) ~~~ 這種方式的好處是在處理復雜語義時比較簡單：類型檢查、代碼生成、以及其他針對樹節點的功能。為了簡化樹的遍歷，可以創建一個通用的樹節點結構，例如： ~~~ 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使用的分析技術只允許在規則規約后執行動作。假設有如下規則： ~~~ 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都完成后才能執行。可是有的時候，在中間階段執行一小段代碼是有用的。假如，你想在A完成后立即執行一些動作，像下面這樣用空規則： ~~~ 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 ~~~ 在這個例子中，空規則seen_A將在A移進分析棧后立即執行。p[-1]指代的是在分析棧上緊跟在seen_A左側的符號。在這個例子中，是A符號。像其他普通的規則一樣，在嵌入式行為中也可以通過為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 :" ~~~ 會產生移進歸約沖，只是由于對于兩個規則abcd和abcx中的C，分析器既可以根據abcd規則移進，也可以根據abcx規則先將空的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作為嵌入式行為，在左大括號{之后立即執行。可以是調正內部符號表或者其他方面。statements_block一完成，代碼可能會撤銷在嵌入動作時的操作（比如，pop_scope()) ### 6.12 Yacc的其他 * 默認的分析方法是LALR，使用SLR請像這樣運行 yacc()：yacc.yacc(method=”SLR”)注意：LRLR生成的分析表大約要比SLR的大兩倍。解析的性能沒有本質的區別，因為代碼是一樣的。由于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()將在每次運行的時候重新構建分析表（這里耗費的時候取決于語法文件的規模） * 想在分析過程中輸出豐富的調試信息，使用：yacc.parse(debug=1) * yacc.yacc()方法會返回分析器對象，如果你想在一個程序中支持多個分析器： ~~~ p = yacc.yacc() ... p.parse() ~~~ 注意：yacc.parse()方法只綁定到最新創建的分析器對象上。 * 由于生成生成LALR分析表相對開銷較大，先前生成的分析表會被緩存和重用。判斷是否重新生成的依據是對所有的語法規則和優先級規則進行MD5校驗，只有不匹配時才會重新生成。生成分析表是合理有效的辦法，即使是面對上百個規則和狀態的語法。對于復雜的編程語言，像C語言，在一些慢的機器上生成分析表可能要花費30-60秒，請耐心。 * 由于LR分析過程是基于分析表的，分析器的性能很大程度上取決于語法的規模。最大的瓶頸可能是詞法分析器和語法規則的復雜度。 ## 7 多個語法和詞法分析器在高級的分析器程序中，你可能同時需要多個語法和詞法分析器。依照規則行事不會有問題。不過，你需要小心確定所有東西都正確的綁定(hooked up)了。首先，保證將lex()和yacc()返回的對象保存起來： ~~~ lexer = lex.lex() # Return lexer object parser = yacc.yacc() # Return parser object ~~~ 接著，在解析時，確保給parse()方法一個正確的lexer引用： ~~~ parser.parse(text,lexer=lexer) ~~~ 如果遺漏這一步，分析器會使用最新創建的lexer對象，這可能不是你希望的。詞法器和語法器的方法中也可以訪問這些對象。在詞法器中，標記的lexer屬性指代的是當前觸發規則的詞法器對象： ~~~ def t_NUMBER(t): r'\d+' ... print t.lexer # Show lexer object ~~~ 在語法器中，lexer和parser屬性指代的是對應的詞法器對象和語法器對象 ~~~ def p_expr_plus(p): 'expr : expr PLUS expr' ... print p.parser # Show parser object print p.lexer # Show lexer object ~~~ 如果有必要，lexer對象和parser對象都可以附加其他屬性。例如，你想要有不同的解析器狀態，可以為為parser對象附加更多的屬性，并在后面用到它們。 ## 8 使用Python的優化模式由于PLY從文檔字串中獲取信息，語法解析和詞法分析信息必須通過正常模式下的Python解釋器得到（不帶有-O或者-OO選項）。不過，如果你像這樣指定optimize模式： ~~~ lex.lex(optimize=1) yacc.yacc(optimize=1) ~~~ PLY可以在下次執行，在Python的優化模式下執行。但你必須確保第一次執行是在Python的正常模式下進行，一旦詞法分析表和語法分析表生成一次后，在Python優化模式下執行，PLY會使用生成好的分析表而不再需要文檔字串。注意：在優化模式下執行PLY會禁用很多錯誤檢查機制。你應該只在程序穩定后，不再需要調試的情況下這樣做。使用優化模式的目的應該是大幅減少你的編譯器的啟動時間（萬事俱備只欠東風時） ## 9 高級調試調試一個編譯器不是件容易的事情。PLY提供了一些高級的調試能力，這是通過Python的logging模塊實現的，下面兩節介紹這一主題： ### 9.1 調試lex()和yacc()命令 lex()和yacc()命令都有調試模式，可以通過debug標識實現： ~~~ lex.lex(debug=True) yacc.yacc(debug=True) ~~~ 正常情況下，調試不僅輸出標準錯誤，對于yacc()，還會給出parser.out文件。這些輸出可以通過提供logging對象來精細的控制。下面這個例子增加了對調試信息來源的輸出： ~~~ # 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，大量的調試信息可以通過分級來控制。典型的是將調試信息分為DEBUG,INFO,或者WARNING三個級別。 PLY的錯誤和警告信息通過日志接口提供，可以從errorlog參數中傳入日志對象 ~~~ lex.lex(errorlog=log) yacc.yacc(errorlog=log) ~~~ 如果想完全過濾掉警告信息，你除了可以使用帶級別過濾功能的日志對象，也可以使用lex和yacc模塊都內建的Nulllogger對象。例如： ~~~ yacc.yacc(errorlog=yacc.NullLogger()) ~~~ ### 9.2 運行時調試為分析器指定debug選項，可以激活語法分析器的運行時調試功能。這個選項可以是整數（表示對調試功能是開還是關），也可以是logger對象。例如： ~~~ log = logging.getLogger() parser.parse(input,debug=log) ~~~ 如果傳入日志對象的話，你可以使用其級別過濾功能來控制內容的輸出。INFO級別用來產生歸約信息；DEBUG級別會顯示分析棧的信息、移進的標記和其他詳細信息。ERROR級別顯示分析過程中的錯誤相關信息。對于每個復雜的問題，你應該用日志對象，以便輸出重定向到文件中，進而方便在執行結束后檢查。 ## 10 如何繼續 PLY分發包中的example目錄包含幾個簡單的示例。對于理論性的東西以及LR分析發的實現細節，應當從編譯器相關的書籍中學習。