【百度云搜索睡陪，搜各種資料:http://bdy.lqkweb.com】
【搜網(wǎng)盤寺渗，搜各種資料:http://www.swpan.cn】
原博客地址為：http://www.pchou.info/open-source/2014/01/18/52da47204d4cb.html,已經(jīng)不能訪問匿情，但是覺得文檔不錯，就保存了下了信殊，以供后來者學(xué)習(xí)炬称。
我寫的SQLflow機(jī)器學(xué)習(xí)平臺開源項目就是用到這篇文章的詞法分析語法解析。SQLflow開源git地址：https://github.com/lqkweb/sqlflow
本文是PLY (Python Lex-Yacc)的中文翻譯版涡拘。轉(zhuǎn)載請注明出處玲躯。
如果你從事編譯器或解析器的開發(fā)工作，你可能對lex和yacc不會陌生鳄乏，PLY是David Beazley實現(xiàn)的基于Python的lex和yacc跷车。作者最著名的成就可能是其撰寫的Python Cookbook, 3rd Edition。我因為偶然的原因接觸了PLY橱野，覺得是個好東西朽缴，但是似乎國內(nèi)沒有相關(guān)的資料。于是萌生了翻譯的想法水援，雖然內(nèi)容不算多密强，但是由于能力有限，很多概念不了解蜗元，還專門補習(xí)了編譯原理或渤，這對我有很大幫助。為了完成翻譯许帐，經(jīng)過初譯劳坑，復(fù)審，排版等成畦，花費我很多時間，最終還是堅持下來了涝开，希望對需要的人有所幫助循帐。另外，第一次大規(guī)模翻譯英文舀武，由于水平有限拄养，如果錯誤或者不妥的地方還請指正，非常感謝银舱。
0 一些翻譯約定
| 英文 | 翻譯 |
|---|---|
| token | 標(biāo)記 |
| context free grammar | 上下文無關(guān)文法 |
| syntax directed translation | 語法制導(dǎo)的翻譯 |
| ambiguity | 二義 |
| terminals | 終結(jié)符 |
| non-terminals | 非終結(jié)符 |
| documentation string | 文檔字符串（python中的_docstring_） |
| shift-reduce | 移進(jìn)-歸約 |
| Empty Productions | 空產(chǎn)生式 |
| Panic mode recovery | 悲觀恢復(fù)模式 |
1 前言和預(yù)備
本文指導(dǎo)你使用PLY進(jìn)行詞法分析和語法解析的瘪匿，鑒于解析本身是個復(fù)雜性的事情，在你使用PLY投入大規(guī)模的開發(fā)前寻馏，我強(qiáng)烈建議你完整地閱讀或者瀏覽本文檔棋弥。
PLY-3.0能同時兼容Python2和Python3。需要注意的是诚欠，對于Python3的支持是新加入的顽染，還沒有廣泛的測試（盡管所有的例子和單元測試都能夠在Pythone3下通過）漾岳。如果你使用的是Python2，應(yīng)該使用Python2.4以上版本粉寞，雖然尼荆，PLY最低能夠支持到Python2.2，不過一些可選的功能需要新版本模塊的支持唧垦。
2 介紹
PLY是純粹由Python實現(xiàn)的Lex和yacc（流行的編譯器構(gòu)建工具）捅儒。PLY的設(shè)計目標(biāo)是盡可能的沿襲傳統(tǒng)lex和yacc工具的工作方式，包括支持LALR(1)分析法振亮、提供豐富的輸入驗證野芒、錯誤報告和診斷。因此双炕，如果你曾經(jīng)在其他編程語言下使用過yacc狞悲，你應(yīng)該能夠很容易的遷移到PLY上。
2001年妇斤，我在芝加哥大學(xué)教授“編譯器簡介”課程時開發(fā)了的早期的PLY摇锋。學(xué)生們使用Python和PLY構(gòu)建了一個類似Pascal的語言的完整編譯器，其中的語言特性包括：詞法分析站超、語法分析荸恕、類型檢查、類型推斷死相、嵌套作用域融求，并針對SPARC處理器生成目標(biāo)代碼等。最終他們大約實現(xiàn)了30種不同的編譯器算撮！PLY在接口設(shè)計上影響使用的問題也被學(xué)生們所提出生宛。從2001年以來，PLY繼續(xù)從用戶的反饋中不斷改進(jìn)肮柜。為了適應(yīng)對未來的改進(jìn)需求陷舅，PLY3.0在原來基礎(chǔ)上進(jìn)行了重大的重構(gòu)。
由于PLY是作為教學(xué)工具來開發(fā)的审洞，你會發(fā)現(xiàn)它對于標(biāo)記和語法規(guī)則是相當(dāng)嚴(yán)謹(jǐn)?shù)睦痴觯@一定程度上是為了幫助新手用戶找出常見的編程錯誤。不過芒澜，高級用戶也會發(fā)現(xiàn)這有助于處理真實編程語言的復(fù)雜語法仰剿。還需要注意的是，PLY沒有提供太多花哨的東西（例如痴晦，自動構(gòu)建抽象語法樹和遍歷樹）南吮，我也不認(rèn)為它是個分析框架。相反阅酪，你會發(fā)現(xiàn)它是一個用Python實現(xiàn)的旨袒，基本的汁针，但能夠完全勝任的lex/yacc。
本文的假設(shè)你多少熟悉分析理論砚尽、語法制導(dǎo)的翻譯施无、基于其他編程語言使用過類似lex和yacc的編譯器構(gòu)建工具。如果你對這些東西不熟悉必孤，你可能需要先去一些書籍中學(xué)習(xí)一些基礎(chǔ)猾骡，比如：Aho, Sethi和Ullman的《Compilers: Principles, Techniques, and Tools》（《編譯原理》），和O’Reilly’出版的John Levine的《lex and yacc》敷搪。事實上兴想，《lex and yacc》和PLY使用的概念幾乎相同。
3 PLY概要
PLY包含兩個獨立的模塊：lex.py和yacc.py赡勘，都定義在ply包下嫂便。lex.py模塊用來將輸入字符通過一系列的正則表達(dá)式分解成標(biāo)記序列，yacc.py通過一些上下文無關(guān)的文法來識別編程語言語法闸与。yacc.py使用LR解析法毙替，并使用LALR(1)算法（默認(rèn)）或者SLR算法生成分析表。
這兩個工具是為了一起工作的践樱。lex.py通過向外部提供token()方法作為接口厂画，方法每次會從輸入中返回下一個有效的標(biāo)記。yacc.py將會不斷的調(diào)用這個方法來獲取標(biāo)記并匹配語法規(guī)則拷邢。yacc.py的的功能通常是生成抽象語法樹(AST)袱院，不過，這完全取決于用戶瞭稼，如果需要忽洛，yacc.py可以直接用來完成簡單的翻譯。
就像相應(yīng)的unix工具弛姜，yacc.py提供了大多數(shù)你期望的特性脐瑰，其中包括：豐富的錯誤檢查、語法驗證廷臼、支持空產(chǎn)生式、錯誤的標(biāo)記绝页、通過優(yōu)先級規(guī)則解決二義性荠商。事實上，傳統(tǒng)yacc能夠做到的PLY都應(yīng)該支持续誉。
yacc.py與Unix下的yacc的主要不同之處在于莱没，yacc.py沒有包含一個獨立的代碼生成器，而是在PLY中依賴反射來構(gòu)建詞法分析器和語法解析器酷鸦。不像傳統(tǒng)的lex/yacc工具需要一個獨立的輸入文件饰躲，并將之轉(zhuǎn)化成一個源文件牙咏，Python程序必須是一個可直接可用的程序，這意味著不能有額外的源文件和特殊的創(chuàng)建步驟（像是那種執(zhí)行yacc命令來生成Python代碼）嘹裂。又由于生成分析表開銷較大妄壶，PLY會緩存生成的分析表，并將它們保存在獨立的文件中寄狼，除非源文件有變化丁寄，會重新生成分析表，否則將從緩存中直接讀取泊愧。
4 Lex
lex.py是用來將輸入字符串標(biāo)記化伊磺。例如，假設(shè)你正在設(shè)計一個編程語言删咱，用戶的輸入字符串如下：
x = 3 + 42 * (s - t)
標(biāo)記器將字符串分割成獨立的標(biāo)記：
'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')'
標(biāo)記通常用一組名字來命名和表示：
'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES','LPAREN','ID','MINUS','ID','RPAREN'
將標(biāo)記名和標(biāo)記值本身組合起來：
('ID','x'), ('EQUALS','='), ('NUMBER','3'),('PLUS','+'), ('NUMBER','42), ('TIMES','*'),('LPAREN','('), ('ID','s'),('MINUS','-'),('ID','t'), ('RPAREN',')
正則表達(dá)式是描述標(biāo)記規(guī)則的典型方法屑埋，下一節(jié)展示如何用lex.py實現(xiàn)。
4.1 Lex的例子
下面的例子展示了如何使用lex.py對輸入進(jìn)行標(biāo)記
# -----------------------------------------------------------
# calclex.py
#
# tokenizer for a simple expression evaluator for
# numbers and +,-,*,/
# ------------------------------------------------------------
import ply.lex as lex
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
# Build the lexer
lexer = lex.lex()
為了使lexer工作痰滋，你需要給定一個輸入摘能，并傳遞給input()方法。然后即寡，重復(fù)調(diào)用token()方法來獲取標(biāo)記序列徊哑，下面的代碼展示了這種用法：
# Test it out
data = '''
3 + 4 * 10
+ -20 *2
'''
# Give the lexer some input
lexer.input(data)
# Tokenize
while True:
tok = lexer.token()
if not tok: break # No more input
print tok
程序執(zhí)行法焰，將給出如下輸出：
$ python example.py
LexToken(NUMBER,3,2,1)
LexToken(PLUS,'+',2,3)
LexToken(NUMBER,4,2,5)
LexToken(TIMES,'*',2,7)
LexToken(NUMBER,10,2,10)
LexToken(PLUS,'+',3,14)
LexToken(MINUS,'-',3,16)
LexToken(NUMBER,20,3,18)
LexToken(TIMES,'*',3,20)
LexToken(NUMBER,2,3,21)
Lexers也同時支持迭代忙芒，你可以把上面的循環(huán)寫成這樣：
for tok in lexer:
print tok
由lexer.token()方法返回的標(biāo)記是LexToken類型的實例强衡，擁有tok.type,tok.value,tok.lineno和tok.lexpos屬性剃法，下面的代碼展示了如何訪問這些屬性：
# Tokenize
while True:
tok = lexer.token()
if not tok: break # No more input
print tok.type, tok.value, tok.line, tok.lexpos
tok.type和tok.value屬性表示標(biāo)記本身的類型和值杖虾。tok.line和tok.lexpos屬性包含了標(biāo)記的位置信息攘烛，tok.lexpos表示標(biāo)記相對于輸入串起始位置的偏移嗓袱。
4.2 標(biāo)記列表
詞法分析器必須提供一個標(biāo)記的列表臼朗，這個列表將所有可能的標(biāo)記告訴分析器奸披，用來執(zhí)行各種驗證昏名，同時也提供給yacc.py作為終結(jié)符。
在上面的例子中阵面，是這樣給定標(biāo)記列表的：
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
4.3 標(biāo)記的規(guī)則
每種標(biāo)記用一個正則表達(dá)式規(guī)則來表示轻局，每個規(guī)則需要以”t_“開頭聲明，表示該聲明是對標(biāo)記的規(guī)則定義样刷。對于簡單的標(biāo)記仑扑，可以定義成這樣（在Python中使用raw string能比較方便的書寫正則表達(dá)式）：
t_PLUS = r'\+'
這里，緊跟在t_后面的單詞置鼻，必須跟標(biāo)記列表中的某個標(biāo)記名稱對應(yīng)镇饮。如果需要執(zhí)行動作的話，規(guī)則可以寫成一個方法箕母。例如储藐，下面的規(guī)則匹配數(shù)字字串俱济，并且將匹配的字符串轉(zhuǎn)化成Python的整型：
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
如果使用方法的話，正則表達(dá)式寫成方法的文檔字符串钙勃。方法總是需要接受一個LexToken實例的參數(shù)蛛碌，該實例有一個t.type的屬性（字符串表示）來表示標(biāo)記的類型名稱，t.value是標(biāo)記值（匹配的實際的字符串）肺缕，t.lineno表示當(dāng)前在源輸入串中的作業(yè)行左医，t.lexpos表示標(biāo)記相對于輸入串起始位置的偏移。默認(rèn)情況下同木，t.type是以t_開頭的變量或方法的后面部分浮梢。方法可以在方法體里面修改這些屬性。但是彤路，如果這樣做秕硝，應(yīng)該返回結(jié)果token，否則洲尊，標(biāo)記將被丟棄远豺。
在lex內(nèi)部，lex.py用re模塊處理模式匹配坞嘀，在構(gòu)造最終的完整的正則式的時候躯护，用戶提供的規(guī)則按照下面的順序加入：
- 所有由方法定義的標(biāo)記規(guī)則，按照他們的出現(xiàn)順序依次加入
- 由字符串變量定義的標(biāo)記規(guī)則按照其正則式長度倒序后丽涩，依次加入（長的先入）
- 順序的約定對于精確匹配是必要的棺滞。比如，如果你想?yún)^(qū)分‘=’和‘==’矢渊，你需要確奔套迹‘==’優(yōu)先檢查。如果用字符串來定義這樣的表達(dá)式的話矮男，通過將較長的正則式先加入移必，可以幫助解決這個問題。用方法定義標(biāo)記毡鉴，可以顯示地控制哪個規(guī)則優(yōu)先檢查崔泵。
為了處理保留字，你應(yīng)該寫一個單一的規(guī)則來匹配這些標(biāo)識猪瞬，并在方法里面作特殊的查詢：
reserved = {
'if' : 'IF',
'then' : 'THEN',
'else' : 'ELSE',
'while' : 'WHILE',
...
}
tokens = ['LPAREN','RPAREN',...,'ID'] + list(reserved.values())
def t_ID(t):
r'[a-zA-Z_][a-zA-Z_0-9]*'
t.type = reserved.get(t.value,'ID') # Check for reserved words
return t
這樣做可以大大減少正則式的個數(shù)管削，并稍稍加快處理速度。注意：你應(yīng)該避免為保留字編寫單獨的規(guī)則撑螺，例如，如果你像下面這樣寫：
t_FOR = r'for'
t_PRINT = r'print'
但是崎弃，這些規(guī)則照樣也能夠匹配以這些字符開頭的單詞甘晤，比如’forget’或者’printed’含潘，這通常不是你想要的。
4.4 標(biāo)記的值
標(biāo)記被lex返回后线婚，它們的值被保存在value屬性中遏弱。正常情況下，value是匹配的實際文本塞弊。事實上漱逸，value可以被賦為任何Python支持的類型。例如游沿，當(dāng)掃描到標(biāo)識符的時候饰抒，你可能不僅需要返回標(biāo)識符的名字，還需要返回其在符號表中的位置诀黍，可以像下面這樣寫：
def t_ID(t):
...
# Look up symbol table information and return a tuple
t.value = (t.value, symbol_lookup(t.value))
...
return t
需要注意的是袋坑，不推薦用其他屬性來保存值，因為yacc.py模塊只會暴露出標(biāo)記的value屬性眯勾，訪問其他屬性會變得不自然枣宫。如果想保存多種屬性，可以將元組吃环、字典也颤、或者對象實例賦給value。
4.5 丟棄標(biāo)記
想丟棄像注釋之類的標(biāo)記郁轻，只要不返回value就行了翅娶，像這樣：
def t_COMMENT(t):
r'\#.*'
pass
# No return value. Token discarded
為標(biāo)記聲明添加”ignore_“前綴同樣可以達(dá)到目的：
t_ignore_COMMENT = r'\#.*'
如果有多種文本需要丟棄，建議使用方法來定義規(guī)則范咨，因為方法能夠提供更精確的匹配優(yōu)先級控制（方法根據(jù)出現(xiàn)的順序故觅，而字符串的正則表達(dá)式依據(jù)正則表達(dá)式的長度）
4.6 行號和位置信息
默認(rèn)情況下，lex.py對行號一無所知渠啊。因為lex.py根本不知道何為”行”的概念（換行符本身也作為文本的一部分）输吏。不過，可以通過寫一個特殊的規(guī)則來記錄行號：
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
在這個規(guī)則中替蛉，當(dāng)前l(fā)exer對象t.lexer的lineno屬性被修改了贯溅，而且空行被簡單的丟棄了，因為沒有任何的返回躲查。
lex.py也不自動做列跟蹤它浅。但是，位置信息被記錄在了每個標(biāo)記對象的lexpos屬性中镣煮，這樣姐霍，就有可能來計算列信息了。例如：每當(dāng)遇到新行的時候就重置列值：
# Compute column.
# input is the input text string
# token is a token instance
def find_column(input,token):
last_cr = input.rfind('\n',0,token.lexpos)
if last_cr < 0:
last_cr = 0
column = (token.lexpos - last_cr) + 1
return column
通常，計算列的信息是為了指示上下文的錯誤位置镊折，所以只在必要時有用胯府。
4.7 忽略字符
t_ignore規(guī)則比較特殊，是lex.py所保留用來忽略字符的恨胚，通常用來跳過空白或者不需要的字符骂因。雖然可以通過定義像t_newline()這樣的規(guī)則來完成相同的事情，不過使用t_ignore能夠提供較好的詞法分析性能赃泡，因為相比普通的正則式寒波，它被特殊化處理了。
4.8 字面字符
字面字符可以通過在詞法模塊中定義一個literals變量做到升熊，例如：
literals = [ '+','-','*','/' ]
或者
literals = "+-*/"
字面字符是指單個字符俄烁，表示把字符本身作為標(biāo)記，標(biāo)記的type和value都是字符本身僚碎。不過猴娩，字面字符是在其他正則式之后被檢查的，因此如果有規(guī)則是以這些字符開頭的勺阐，那么這些規(guī)則的優(yōu)先級較高卷中。
4.9 錯誤處理
最后，在詞法分析中遇到非法字符時渊抽，t_error()用來處理這類錯誤蟆豫。這種情況下，t.value包含了余下還未被處理的輸入字串懒闷，在之前的例子中十减，錯誤處理方法是這樣的：
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
這個例子中，我們只是簡單的輸出不合法的字符愤估，并且通過調(diào)用t.lexer.skip(1)跳過一個字符帮辟。
4.10 構(gòu)建和使用lexer
函數(shù)lex.lex()使用Python的反射機(jī)制讀取調(diào)用上下文中的正則表達(dá)式，來創(chuàng)建lexer玩焰。lexer一旦創(chuàng)建好由驹，有兩個方法可以用來控制lexer對象：
- lexer.input(data) 重置lexer和輸入字串
- lexer.token() 返回下一個LexToken類型的標(biāo)記實例，如果進(jìn)行到輸入字串的尾部時將返回
None
推薦直接在lex()函數(shù)返回的lexer對象上調(diào)用上述接口昔园，盡管也可以向下面這樣用模塊級別的lex.input()和lex.token()：
lex.lex()
lex.input(sometext)
while 1:
tok = lex.token()
if not tok: break
print tok
在這個例子中蔓榄，lex.input()和lex.token()是模塊級別的方法，在lex模塊中默刚，input()和token()方法綁定到最新創(chuàng)建的lexer對象的對應(yīng)方法上甥郑。最好不要這樣用，因為這種接口可能不知道在什么時候就失效（譯者注：垃圾回收荤西？）
4.11 @TOKEN裝飾器
在一些應(yīng)用中澜搅，你可能需要定義一系列輔助的記號來構(gòu)建復(fù)雜的正則表達(dá)式伍俘，例如：
digit = r'([0-9])'
nondigit = r'([_A-Za-z])'
identifier = r'(' + nondigit + r'(' + digit + r'|' + nondigit + r')*)'
def t_ID(t):
# want docstring to be identifier above. ?????
...
在這個例子中，我們希望ID的規(guī)則引用上面的已有的變量店展。然而养篓，使用文檔字符串無法做到，為了解決這個問題赂蕴，你可以使用@TOKEN裝飾器：
from ply.lex import TOKEN
@TOKEN(identifier)
def t_ID(t):
...
裝飾器可以將identifier關(guān)聯(lián)到t_ID()的文檔字符串上以使lex.py正常工作，一種等價的做法是直接給文檔字符串賦值：
def t_ID(t):
...
t_ID.__doc__ = identifier
注意：@TOKEN裝飾器需要Python-2.4以上的版本舶胀。如果你在意老版本Python的兼容性問題概说，使用上面的等價辦法。
4.12 優(yōu)化模式
為了提高性能嚣伐，你可能希望使用Python的優(yōu)化模式（比如糖赔，使用-o選項執(zhí)行Python）。然而轩端，這樣的話放典，Python會忽略文檔字串，這是lex.py的特殊問題基茵，可以通過在創(chuàng)建lexer的時候使用optimize選項：
lexer = lex.lex(optimize=1)
接著奋构，用Python常規(guī)的模式運行，這樣拱层，lex.py會在當(dāng)前目錄下創(chuàng)建一個lextab.py文件，這個文件會包含所有的正則表達(dá)式規(guī)則和詞法分析階段的分析表根灯。然后径缅，lextab.py可以被導(dǎo)入用來構(gòu)建lexer行您。這種方法大大改善了詞法分析程序的啟動時間，而且可以在Python的優(yōu)化模式下工作娃循。
想要更改生成的文件名炕檩，使用如下參數(shù)：
lexer = lex.lex(optimize=1,lextab="footab")
在優(yōu)化模式下執(zhí)行，需要注意的是lex會被禁用大多數(shù)的錯誤檢查捌斧。因此笛质，建議只在確保萬事俱備準(zhǔn)備發(fā)布最終代碼時使用。
4.13 調(diào)試
如果想要調(diào)試捞蚂，可以使lex()運行在調(diào)試模式：
lexer = lex.lex(debug=1)
這將打出一些調(diào)試信息妇押，包括添加的規(guī)則、最終的正則表達(dá)式和詞法分析過程中得到的標(biāo)記姓迅。
除此之外敲霍，lex.py有一個簡單的主函數(shù)，不但支持對命令行參數(shù)輸入的字串進(jìn)行掃描丁存，還支持命令行參數(shù)指定的文件名：
if __name__ == '__main__':
lex.runmain()
想要了解高級調(diào)試的詳情肩杈，請移步至最后的高級調(diào)試部分。
4.14 其他方式定義詞法規(guī)則
上面的例子柱嫌，詞法分析器都是在單個的Python模塊中指定的锋恬。如果你想將標(biāo)記的規(guī)則放到不同的模塊，使用module關(guān)鍵字參數(shù)编丘。例如与学，你可能有一個專有的模塊，包含了標(biāo)記的規(guī)則：
# module: tokrules.py
# This module just contains the lexing rules
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
現(xiàn)在嘉抓，如果你想要從不同的模塊中構(gòu)建分析器索守，應(yīng)該這樣（在交互模式下）：
>>> import tokrules
>>> lexer = lex.lex(module=tokrules)
>>> lexer.input("3 + 4")
>>> lexer.token()
LexToken(NUMBER,3,1,1,0)
>>> lexer.token()
LexToken(PLUS,'+',1,2)
>>> lexer.token()
LexToken(NUMBER,4,1,4)
>>> lexer.token()
None
module選項也可以指定類型的實例，例如：
import ply.lex as lex
class MyLexer:
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
# Note addition of self parameter since we're in a class
def t_NUMBER(self,t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(self,t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(self,t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
# Build the lexer
def build(self,**kwargs):
self.lexer = lex.lex(module=self, **kwargs)
# Test it output
def test(self,data):
self.lexer.input(data)
while True:
tok = lexer.token()
if not tok: break
print tok
# Build the lexer and try it out
m = MyLexer()
m.build() # Build the lexer
m.test("3 + 4") # Test it
當(dāng)從類中定義lexer抑片，你需要創(chuàng)建類的實例卵佛，而不是類本身。這是因為敞斋，lexer的方法只有被綁定（bound-methods）對象后才能使PLY正常工作截汪。
當(dāng)給lex()方法使用module選項時，PLY使用dir()方法植捎，從對象中獲取符號信息衙解，因為不能直接訪問對象的__dict__屬性。（譯者注：可能是因為兼容性原因焰枢，__dict__這個方法可能不存在）
最后蚓峦，如果你希望保持較好的封裝性舌剂，但不希望什么東西都寫在類里面，lexers可以在閉包中定義暑椰，例如：
import ply.lex as lex
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
def MyLexer():
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
# Build the lexer from my environment and return it
return lex.lex()
4.15 額外狀態(tài)維護(hù)
在你的詞法分析器中霍转，你可能想要維護(hù)一些狀態(tài)。這可能包括模式設(shè)置一汽，符號表和其他細(xì)節(jié)避消。例如，假設(shè)你想要跟蹤NUMBER標(biāo)記的出現(xiàn)個數(shù)角虫。
一種方法是維護(hù)一個全局變量：
num_count = 0
def t_NUMBER(t):
r'\d+'
global num_count
num_count += 1
t.value = int(t.value)
return t
如果你不喜歡全局變量沾谓，另一個記錄信息的地方是lexer對象內(nèi)部〈炼欤可以通過當(dāng)前標(biāo)記的lexer屬性訪問：
def t_NUMBER(t):
r'\d+'
t.lexer.num_count += 1 # Note use of lexer attribute
t.value = int(t.value)
return t
lexer = lex.lex()
lexer.num_count = 0 # Set the initial count
上面這樣做的優(yōu)點是當(dāng)同時存在多個lexer實例的情況下，簡單易行昏兆。不過這看上去似乎是嚴(yán)重違反了面向?qū)ο蟮姆庋b原則枫虏。lexer的內(nèi)部屬性（除了lineno）都是以lex開頭命名的（lexdata、lexpos）爬虱。因此隶债，只要不以lex開頭來命名屬性就很安全的。
如果你不喜歡給lexer對象賦值跑筝，你可以自定義你的lexer類型死讹，就像前面看到的那樣：
class MyLexer:
...
def t_NUMBER(self,t):
r'\d+'
self.num_count += 1
t.value = int(t.value)
return t
def build(self, **kwargs):
self.lexer = lex.lex(object=self,**kwargs)
def __init__(self):
self.num_count = 0
如果你的應(yīng)用會創(chuàng)建很多l(xiāng)exer的實例，并且需要維護(hù)很多狀態(tài)曲梗，上面的類可能是最容易管理的赞警。
狀態(tài)也可以用閉包來管理，比如虏两，在Python3中：
def MyLexer():
num_count = 0
...
def t_NUMBER(t):
r'\d+'
nonlocal num_count
num_count += 1
t.value = int(t.value)
return t
...
4.16 Lexer克隆
如果有必要的話愧旦，lexer對象可以通過clone()方法來復(fù)制：
lexer = lex.lex()
...
newlexer = lexer.clone()
當(dāng)lexer被克隆后，復(fù)制品能夠精確的保留輸入串和內(nèi)部狀態(tài)定罢，不過笤虫，新的lexer可以接受一個不同的輸出字串，并獨立運作起來祖凫。這在幾種情況下也許有用：當(dāng)你在編寫的解析器或編譯器涉及到遞歸或者回退處理時琼蚯，你需要掃描先前的部分，你可以clone并使用復(fù)制品惠况，或者你在實現(xiàn)某種預(yù)編譯處理遭庶，可以clone一些lexer來處理不同的輸入文件。
創(chuàng)建克隆跟重新調(diào)用lex.lex()的不同點在于售滤，PLY不會重新構(gòu)建任何的內(nèi)部分析表或者正則式罚拟。當(dāng)lexer是用類或者閉包創(chuàng)建的台诗，需要注意類或閉包本身的的狀態(tài)。換句話說你要注意新創(chuàng)建的lexer會共享原始lexer的這些狀態(tài)赐俗，比如：
m = MyLexer()
a = lex.lex(object=m) # Create a lexer
b = a.clone() # Clone the lexer
4.17 Lexer的內(nèi)部狀態(tài)
lexer有一些內(nèi)部屬性在特定情況下有用：
-
lexer.lexpos拉队。這是一個表示當(dāng)前分析點的位置的整型值。如果你修改這個值的話阻逮，這會改變下一個token()的調(diào)用行為粱快。在標(biāo)記的規(guī)則方法里面，這個值表示緊跟匹配字串后面的第一個字符的位置叔扼，如果這個值在規(guī)則中修改事哭，下一個返回的標(biāo)記將從新的位置開始匹配 -
lexer.lineno。表示當(dāng)前行號瓜富。PLY只是聲明這個屬性的存在鳍咱，卻永遠(yuǎn)不更新這個值。如果你想要跟蹤行號的話与柑，你需要自己添加代碼（ 4.6 行號和位置信息） -
lexer.lexdata谤辜。當(dāng)前l(fā)exer的輸入字串，這個字符串就是input()方法的輸入字串价捧，更改它可能是個糟糕的做法丑念，除非你知道自己在干什么。 -
lexer.lexmatch结蟋。PLY內(nèi)部調(diào)用Python的re.match()方法得到的當(dāng)前標(biāo)記的原始的Match對象脯倚，該對象被保存在這個屬性中。如果你的正則式中包含分組的話嵌屎，你可以通過這個對象獲得這些分組的值推正。注意：這個屬性只在有標(biāo)記規(guī)則定義的方法中才有效。
4.18 基于條件的掃描和啟動條件
在高級的分析器應(yīng)用程序中编整，使用狀態(tài)化的詞法掃描是很有用的舔稀。比如，你想在出現(xiàn)特定標(biāo)記或句子結(jié)構(gòu)的時候觸發(fā)開始一個不同的詞法分析邏輯掌测。PLY允許lexer在不同的狀態(tài)之間轉(zhuǎn)換内贮。每個狀態(tài)可以包含一些自己獨特的標(biāo)記和規(guī)則等。這是基于GNU flex的“啟動條件”來實現(xiàn)的汞斧，關(guān)于flex詳見http://flex.sourceforge.net/manual/Start-Conditions.html#Start-Conditions
要使用lex的狀態(tài)夜郁，你必須首先聲明。通過在lex模塊中聲明”states”來做到：
states = (
('foo','exclusive'),
('bar','inclusive'),
)
這個聲明中包含有兩個狀態(tài)：’foo’和’bar’粘勒。狀態(tài)可以有兩種類型：’排他型’和’包容型’竞端。排他型的狀態(tài)會使得lexer的行為發(fā)生完全的改變：只有能夠匹配在這個狀態(tài)下定義的規(guī)則的標(biāo)記才會返回；包容型狀態(tài)會將定義在這個狀態(tài)下的規(guī)則添加到默認(rèn)的規(guī)則集中庙睡，進(jìn)而事富，只要能匹配這個規(guī)則集的標(biāo)記都會返回技俐。
一旦聲明好之后，標(biāo)記規(guī)則的命名需要包含狀態(tài)名：
t_foo_NUMBER = r'\d+' # Token 'NUMBER' in state 'foo'
t_bar_ID = r'[a-zA-Z_][a-zA-Z0-9_]*' # Token 'ID' in state 'bar'
def t_foo_newline(t):
r'\n'
t.lexer.lineno += 1
一個標(biāo)記可以用在多個狀態(tài)中统台，只要將多個狀態(tài)名包含在聲明中：
t_foo_bar_NUMBER = r'\d+' # Defines token 'NUMBER' in both state 'foo' and 'bar'
同樣的雕擂，在任何狀態(tài)下都生效的聲明可以在命名中使用ANY：
t_ANY_NUMBER = r'\d+' # Defines a token 'NUMBER' in all states
不包含狀態(tài)名的情況下，標(biāo)記被關(guān)聯(lián)到一個特殊的狀態(tài)INITIAL贱勃，比如井赌，下面兩個聲明是等價的：
t_NUMBER = r'\d+'
t_INITIAL_NUMBER = r'\d+'
特殊的t_ignore()和t_error()也可以用狀態(tài)關(guān)聯(lián)：
t_foo_ignore = " \t\n" # Ignored characters for state 'foo'
def t_bar_error(t): # Special error handler for state 'bar'
pass
詞法分析默認(rèn)在INITIAL狀態(tài)下工作，這個狀態(tài)下包含了所有默認(rèn)的標(biāo)記規(guī)則定義贵扰。對于不希望使用“狀態(tài)”的用戶來說仇穗，這是完全透明的。在分析過程中戚绕，如果你想要改變詞法分析器的這種的狀態(tài)纹坐，使用begin()方法：
def t_begin_foo(t):
r'start_foo'
t.lexer.begin('foo') # Starts 'foo' state
使用begin()切換回初始狀態(tài)：
def t_foo_end(t):
r'end_foo'
t.lexer.begin('INITIAL') # Back to the initial state
狀態(tài)的切換可以使用棧：
def t_begin_foo(t):
r'start_foo'
t.lexer.push_state('foo') # Starts 'foo' state
def t_foo_end(t):
r'end_foo'
t.lexer.pop_state() # Back to the previous state
當(dāng)你在面臨很多狀態(tài)可以選擇進(jìn)入，而又僅僅想要回到之前的狀態(tài)時舞丛，狀態(tài)棧比較有用恰画。
舉個例子會更清晰。假設(shè)你在寫一個分析器想要從一堆C代碼中獲取任意匹配的閉合的大括號里面的部分：這意味著瓷马，當(dāng)遇到起始括號’{‘，你需要讀取與之匹配的’}’以上的所有部分跨晴。并返回字符串欧聘。使用通常的正則表達(dá)式幾乎不可能，這是因為大括號可以嵌套端盆，而且可以有注釋怀骤，字符串等干擾。因此焕妙，試圖簡單的匹配第一個出現(xiàn)的’}’是不行的蒋伦。這里你可以用lex的狀態(tài)來做到：
# Declare the state
states = (
('ccode','exclusive'),
)
# Match the first {. Enter ccode state.
def t_ccode(t):
r'\{'
t.lexer.code_start = t.lexer.lexpos # Record the starting position
t.lexer.level = 1 # Initial brace level
t.lexer.begin('ccode') # Enter 'ccode' state
# Rules for the ccode state
def t_ccode_lbrace(t):
r'\{'
t.lexer.level +=1
def t_ccode_rbrace(t):
r'\}'
t.lexer.level -=1
# If closing brace, return the code fragment
if t.lexer.level == 0:
t.value = t.lexer.lexdata[t.lexer.code_start:t.lexer.lexpos+1]
t.type = "CCODE"
t.lexer.lineno += t.value.count('\n')
t.lexer.begin('INITIAL')
return t
# C or C++ comment (ignore)
def t_ccode_comment(t):
r'(/\*(.|\n)*?*/)|(//.*)'
pass
# C string
def t_ccode_string(t):
r'\"([^\\\n]|(\\.))*?\"'
# C character literal
def t_ccode_char(t):
r'\'([^\\\n]|(\\.))*?\''
# Any sequence of non-whitespace characters (not braces, strings)
def t_ccode_nonspace(t):
r'[^\s\{\}\'\"]+'
# Ignored characters (whitespace)
t_ccode_ignore = " \t\n"
# For bad characters, we just skip over it
def t_ccode_error(t):
t.lexer.skip(1)
這個例子中，第一個’{‘使得lexer記錄了起始位置焚鹊，并且進(jìn)入新的狀態(tài)’ccode’痕届。一系列規(guī)則用來匹配接下來的輸入，這些規(guī)則只是丟棄掉標(biāo)記（不返回值）末患，如果遇到閉合右括號研叫，t_ccode_rbrace規(guī)則收集其中所有的代碼（利用先前記錄的開始位置），并保存璧针，返回的標(biāo)記類型為’CCODE’嚷炉，與此同時，詞法分析的狀態(tài)退回到初始狀態(tài)探橱。
4.19 其他問題
- lexer需要輸入的是一個字符串申屹。好在大多數(shù)機(jī)器都有足夠的內(nèi)存绘证，這很少導(dǎo)致性能的問題。這意味著哗讥，lexer現(xiàn)在還不能用來處理文件流或者socket流嚷那。這主要是受到
re模塊的限制。 - lexer支持用Unicode字符描述標(biāo)記的匹配規(guī)則忌栅，也支持輸入字串包含Unicode
- 如果你想要向
re.compile()方法提供flag车酣，使用reflags選項：lex.lex(reflags=re.UNICODE) - 由于lexer是全部用Python寫的，性能很大程度上取決于Python的
re模塊索绪，即使已經(jīng)盡可能的高效了湖员。當(dāng)接收極其大量的輸入文件時表現(xiàn)并不盡人意。如果擔(dān)憂性能瑞驱，你可以升級到最新的Python娘摔，或者手工創(chuàng)建分析器，或者用C語言寫lexer并做成擴(kuò)展模塊唤反。
如果你要創(chuàng)建一個手寫的詞法分析器并計劃用在yacc.py中凳寺，只需要滿足下面的要求：
- 需要提供一個
token()方法來返回下一個標(biāo)記，如果沒有可用的標(biāo)記了彤侍，則返回None肠缨。 -
token()方法必須返回一個tok對象，具有type和value屬性盏阶。如果行號需要跟蹤的話晒奕，標(biāo)記還需要定義lineno屬性。
5 語法分析基礎(chǔ)
yacc.py用來對語言進(jìn)行語法分析名斟。在給出例子之前脑慧，必須提一些重要的背景知識。首先砰盐，‘語法’通常用BNF范式來表達(dá)闷袒。例如，如果想要分析簡單的算術(shù)表達(dá)式岩梳，你應(yīng)該首先寫下無二義的文法：
expression : expression + term
| expression - term
| term
term : term * factor
| term / factor
| factor
factor : NUMBER
| ( expression )
在這個文法中囊骤，像NUMBER,+,-,*,/的符號被稱為終結(jié)符，對應(yīng)原始的輸入蒋腮。類似term淘捡，factor等稱為非終結(jié)符，它們由一系列終結(jié)符或其他規(guī)則的符號組成池摧，用來指代語法規(guī)則焦除。
通常使用一種叫語法制導(dǎo)翻譯的技術(shù)來指定某種語言的語義。在語法制導(dǎo)翻譯中作彤，符號及其屬性出現(xiàn)在每個語法規(guī)則后面的動作中膘魄。每當(dāng)一個語法被識別乌逐，動作就能夠描述需要做什么。比如创葡，對于上面給定的文法浙踢，想要實現(xiàn)一個簡單的計算器，應(yīng)該寫成下面這樣：
Grammar Action
-------------------------------- --------------------------------------------
expression0 : expression1 + term expression0.val = expression1.val + term.val
| expression1 - term expression0.val = expression1.val - term.val
| term expression0.val = term.val
term0 : term1 * factor term0.val = term1.val * factor.val
| term1 / factor term0.val = term1.val / factor.val
| factor term0.val = factor.val
factor : NUMBER factor.val = int(NUMBER.lexval)
| ( expression ) factor.val = expression.val
一種理解語法指導(dǎo)翻譯的好方法是將符號看成對象灿渴。與符號相關(guān)的值代表了符號的“狀態(tài)”（比如上面的val屬性）洛波，語義行為用一組操作符號及符號值的函數(shù)或者方法來表達(dá)。
Yacc用的分析技術(shù)是著名的LR分析法或者叫移進(jìn)-歸約分析法骚露。LR分析法是一種自下而上的技術(shù)：首先嘗試識別右部的語法規(guī)則蹬挤，每當(dāng)右部得到滿足，相應(yīng)的行為代碼將被觸發(fā)執(zhí)行棘幸，當(dāng)前右邊的語法符號將被替換為左邊的語法符號焰扳。（歸約）
LR分析法一般這樣實現(xiàn)：將下一個符號進(jìn)棧，然后結(jié)合棧頂?shù)姆柡秃罄^符號（譯者注：下一個將要輸入符號）误续，與文法中的某種規(guī)則相比較吨悍。具體的算法可以在編譯器的手冊中查到，下面的例子展現(xiàn)了如果通過上面定義的文法蹋嵌，來分析3 + 5 * ( 10 - 20 )這個表達(dá)式育瓜，$用來表示輸入結(jié)束
Step Symbol Stack Input Tokens Action
---- --------------------- --------------------- -------------------------------
1 3 + 5 * ( 10 - 20 )$ Shift 3
2 3 + 5 * ( 10 - 20 )$ Reduce factor : NUMBER
3 factor + 5 * ( 10 - 20 )$ Reduce term : factor
4 term + 5 * ( 10 - 20 )$ Reduce expr : term
5 expr + 5 * ( 10 - 20 )$ Shift +
6 expr + 5 * ( 10 - 20 )$ Shift 5
7 expr + 5 * ( 10 - 20 )$ Reduce factor : NUMBER
8 expr + factor * ( 10 - 20 )$ Reduce term : factor
9 expr + term * ( 10 - 20 )$ Shift *
10 expr + term * ( 10 - 20 )$ Shift (
11 expr + term * ( 10 - 20 )$ Shift 10
12 expr + term * ( 10 - 20 )$ Reduce factor : NUMBER
13 expr + term * ( factor - 20 )$ Reduce term : factor
14 expr + term * ( term - 20 )$ Reduce expr : term
15 expr + term * ( expr - 20 )$ Shift -
16 expr + term * ( expr - 20 )$ Shift 20
17 expr + term * ( expr - 20 )$ Reduce factor : NUMBER
18 expr + term * ( expr - factor )$ Reduce term : factor
19 expr + term * ( expr - term )$ Reduce expr : expr - term
20 expr + term * ( expr )$ Shift )
21 expr + term * ( expr ) $ Reduce factor : (expr)
22 expr + term * factor $ Reduce term : term * factor
23 expr + term $ Reduce expr : expr + term
24 expr $ Reduce expr
25 $ Success!
（譯者注：action里面的Shift就是進(jìn)棧動作，簡稱移進(jìn)栽烂；Reduce是歸約）
在分析表達(dá)式的過程中爆雹，一個相關(guān)的自動狀態(tài)機(jī)和后繼符號決定了下一步應(yīng)該做什么乒躺。如果下一個標(biāo)記看起來是一個有效語法（產(chǎn)生式）的一部分（通過棧上的其他項判斷這一點）爸吮，那么這個標(biāo)記應(yīng)該進(jìn)棧代态。如果棧頂?shù)捻椏梢越M成一個完整的右部語法規(guī)則，一般就可以進(jìn)行“歸約”菇晃，用產(chǎn)生式左邊的符號代替這一組符號。當(dāng)歸約發(fā)生時蚓挤，相應(yīng)的行為動作就會執(zhí)行磺送。如果輸入標(biāo)記既不能移進(jìn)也不能歸約的話，就會發(fā)生語法錯誤灿意，分析器必須進(jìn)行相應(yīng)的錯誤恢復(fù)估灿。分析器直到棧空并且沒有另外的輸入標(biāo)記時缤剧，才算成功馅袁。 需要注意的是，這是基于一個有限自動機(jī)實現(xiàn)的荒辕，有限自動器被轉(zhuǎn)化成分析表汗销。分析表的構(gòu)建比較復(fù)雜犹褒，超出了本文的討論范圍。不過弛针，這構(gòu)建過程的微妙細(xì)節(jié)能夠解釋為什么在上面的例子中叠骑，解析器選擇在步驟9將標(biāo)記轉(zhuǎn)移到堆棧中，而不是按照規(guī)則expr : expr + term做歸約削茁。
6 Yacc
ply.yacc模塊實現(xiàn)了PLY的分析功能宙枷，‘yacc’是‘Yet Another Compiler Compiler’的縮寫并保留了其作為Unix工具的名字。
6.1 一個例子
假設(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)文法厌衔，方法的語句實現(xiàn)了對應(yīng)規(guī)則的語義行為璧帝。每個方法接受一個單獨的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的簡單類型恤左、元組或者類的實例。在這個例子中搀绣，我們依賴這樣一個事實：NUMBER標(biāo)記的值保存的是整型值飞袋，所有規(guī)則的行為都是得到這些整型值的算術(shù)運算結(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ù)就能運行分析器。它將運行所有的語法規(guī)則卧晓，并返回整個分析的結(jié)果芬首，這個結(jié)果就是在起始規(guī)則中賦給p[0]的值。
6.2 將語法規(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)生式的項數(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ī)則里面用很多條件來處理。因為纳像，每次檢查當(dāng)前究竟匹配的是哪個語法規(guī)則的時候荆烈，實際上重復(fù)做了分析器已經(jīng)做過的事（分析器已經(jīng)準(zhǔn)確的知道哪個規(guī)則被匹配了）。為每個規(guī)則定義單獨的方法，可以消除這點開銷憔购。
6.3 字面字符
如果愿意宫峦，可以在語法規(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’==’)。
6.4 空產(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á)意圖唱凯，并有較好的可讀性羡忘。
6.5 改變起始符號
默認(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')
