【百度云搜索，搜各種資料:http://bdy.lqkweb.com】
【搜網(wǎng)盤，搜各種資料:http://www.swpan.cn】
原博客地址為：http://www.pchou.info/open-source/2014/01/18/52da47204d4cb.html,已經(jīng)不能訪問，但是覺得文檔不錯(cuò)，就保存了下了，以供后來者學(xué)習(xí)。
我寫的SQLflow機(jī)器學(xué)習(xí)平臺(tái)開源項(xiàng)目就是用到這篇文章的詞法分析語法解析。SQLflow開源git地址：https://github.com/lqkweb/sqlflow
本文是PLY (Python Lex-Yacc)的中文翻譯版。轉(zhuǎn)載請(qǐng)注明出處。
如果你從事編譯器或解析器的開發(fā)工作，你可能對(duì)lex和yacc不會(huì)陌生，PLY是David Beazley實(shí)現(xiàn)的基于Python的lex和yacc。作者最著名的成就可能是其撰寫的Python Cookbook, 3rd Edition。我因?yàn)榕既坏脑蚪佑|了PLY，覺得是個(gè)好東西，但是似乎國內(nèi)沒有相關(guān)的資料。于是萌生了翻譯的想法，雖然內(nèi)容不算多，但是由于能力有限，很多概念不了解，還專門補(bǔ)習(xí)了編譯原理，這對(duì)我有很大幫助。為了完成翻譯，經(jīng)過初譯，復(fù)審，排版等，花費(fèi)我很多時(shí)間，最終還是堅(jiān)持下來了，希望對(duì)需要的人有所幫助。另外，第一次大規(guī)模翻譯英文，由于水平有限，如果錯(cuò)誤或者不妥的地方還請(qǐng)指正，非常感謝。
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)行詞法分析和語法解析的，鑒于解析本身是個(gè)復(fù)雜性的事情，在你使用PLY投入大規(guī)模的開發(fā)前，我強(qiáng)烈建議你完整地閱讀或者瀏覽本文檔。
PLY-3.0能同時(shí)兼容Python2和Python3。需要注意的是，對(duì)于Python3的支持是新加入的，還沒有廣泛的測(cè)試（盡管所有的例子和單元測(cè)試都能夠在Pythone3下通過）。如果你使用的是Python2，應(yīng)該使用Python2.4以上版本，雖然，PLY最低能夠支持到Python2.2，不過一些可選的功能需要新版本模塊的支持。
2 介紹
PLY是純粹由Python實(shí)現(xiàn)的Lex和yacc（流行的編譯器構(gòu)建工具）。PLY的設(shè)計(jì)目標(biāo)是盡可能的沿襲傳統(tǒng)lex和yacc工具的工作方式，包括支持LALR(1)分析法、提供豐富的輸入驗(yàn)證、錯(cuò)誤報(bào)告和診斷。因此，如果你曾經(jīng)在其他編程語言下使用過yacc，你應(yīng)該能夠很容易的遷移到PLY上。
2001年，我在芝加哥大學(xué)教授“編譯器簡(jiǎn)介”課程時(shí)開發(fā)了的早期的PLY。學(xué)生們使用Python和PLY構(gòu)建了一個(gè)類似Pascal的語言的完整編譯器，其中的語言特性包括：詞法分析、語法分析、類型檢查、類型推斷、嵌套作用域，并針對(duì)SPARC處理器生成目標(biāo)代碼等。最終他們大約實(shí)現(xiàn)了30種不同的編譯器！PLY在接口設(shè)計(jì)上影響使用的問題也被學(xué)生們所提出。從2001年以來，PLY繼續(xù)從用戶的反饋中不斷改進(jìn)。為了適應(yīng)對(duì)未來的改進(jìn)需求，PLY3.0在原來基礎(chǔ)上進(jìn)行了重大的重構(gòu)。
由于PLY是作為教學(xué)工具來開發(fā)的，你會(huì)發(fā)現(xiàn)它對(duì)于標(biāo)記和語法規(guī)則是相當(dāng)嚴(yán)謹(jǐn)?shù)?，這一定程度上是為了幫助新手用戶找出常見的編程錯(cuò)誤。不過，高級(jí)用戶也會(huì)發(fā)現(xiàn)這有助于處理真實(shí)編程語言的復(fù)雜語法。還需要注意的是，PLY沒有提供太多花哨的東西（例如，自動(dòng)構(gòu)建抽象語法樹和遍歷樹），我也不認(rèn)為它是個(gè)分析框架。相反，你會(huì)發(fā)現(xiàn)它是一個(gè)用Python實(shí)現(xiàn)的，基本的，但能夠完全勝任的lex/yacc。
本文的假設(shè)你多少熟悉分析理論、語法制導(dǎo)的翻譯、基于其他編程語言使用過類似lex和yacc的編譯器構(gòu)建工具。如果你對(duì)這些東西不熟悉，你可能需要先去一些書籍中學(xué)習(xí)一些基礎(chǔ)，比如：Aho, Sethi和Ullman的《Compilers: Principles, Techniques, and Tools》（《編譯原理》），和O’Reilly’出版的John Levine的《lex and yacc》。事實(shí)上，《lex and yacc》和PLY使用的概念幾乎相同。
3 PLY概要
PLY包含兩個(gè)獨(dú)立的模塊：lex.py和yacc.py，都定義在ply包下。lex.py模塊用來將輸入字符通過一系列的正則表達(dá)式分解成標(biāo)記序列，yacc.py通過一些上下文無關(guān)的文法來識(shí)別編程語言語法。yacc.py使用LR解析法，并使用LALR(1)算法（默認(rèn)）或者SLR算法生成分析表。
這兩個(gè)工具是為了一起工作的。lex.py通過向外部提供token()方法作為接口，方法每次會(huì)從輸入中返回下一個(gè)有效的標(biāo)記。yacc.py將會(huì)不斷的調(diào)用這個(gè)方法來獲取標(biāo)記并匹配語法規(guī)則。yacc.py的的功能通常是生成抽象語法樹(AST)，不過，這完全取決于用戶，如果需要，yacc.py可以直接用來完成簡(jiǎn)單的翻譯。
就像相應(yīng)的unix工具，yacc.py提供了大多數(shù)你期望的特性，其中包括：豐富的錯(cuò)誤檢查、語法驗(yàn)證、支持空產(chǎn)生式、錯(cuò)誤的標(biāo)記、通過優(yōu)先級(jí)規(guī)則解決二義性。事實(shí)上，傳統(tǒng)yacc能夠做到的PLY都應(yīng)該支持。
yacc.py與Unix下的yacc的主要不同之處在于，yacc.py沒有包含一個(gè)獨(dú)立的代碼生成器，而是在PLY中依賴反射來構(gòu)建詞法分析器和語法解析器。不像傳統(tǒng)的lex/yacc工具需要一個(gè)獨(dú)立的輸入文件，并將之轉(zhuǎn)化成一個(gè)源文件，Python程序必須是一個(gè)可直接可用的程序，這意味著不能有額外的源文件和特殊的創(chuàng)建步驟（像是那種執(zhí)行yacc命令來生成Python代碼）。又由于生成分析表開銷較大，PLY會(huì)緩存生成的分析表，并將它們保存在獨(dú)立的文件中，除非源文件有變化，會(huì)重新生成分析表，否則將從緩存中直接讀取。
4 Lex
lex.py是用來將輸入字符串標(biāo)記化。例如，假設(shè)你正在設(shè)計(jì)一個(gè)編程語言，用戶的輸入字符串如下：
x = 3 + 42 * (s - t)
標(biāo)記器將字符串分割成獨(dú)立的標(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實(shí)現(xiàn)。
4.1 Lex的例子
下面的例子展示了如何使用lex.py對(duì)輸入進(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工作，你需要給定一個(gè)輸入，并傳遞給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也同時(shí)支持迭代，你可以把上面的循環(huán)寫成這樣：
for tok in lexer:
print tok
由lexer.token()方法返回的標(biāo)記是LexToken類型的實(shí)例，擁有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)記相對(duì)于輸入串起始位置的偏移。
4.2 標(biāo)記列表
詞法分析器必須提供一個(gè)標(biāo)記的列表，這個(gè)列表將所有可能的標(biāo)記告訴分析器，用來執(zhí)行各種驗(yàn)證，同時(shí)也提供給yacc.py作為終結(jié)符。
在上面的例子中，是這樣給定標(biāo)記列表的：
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
4.3 標(biāo)記的規(guī)則
每種標(biāo)記用一個(gè)正則表達(dá)式規(guī)則來表示，每個(gè)規(guī)則需要以”t_“開頭聲明，表示該聲明是對(duì)標(biāo)記的規(guī)則定義。對(duì)于簡(jiǎn)單的標(biāo)記，可以定義成這樣（在Python中使用raw string能比較方便的書寫正則表達(dá)式）：
t_PLUS = r'\+'
這里，緊跟在t_后面的單詞，必須跟標(biāo)記列表中的某個(gè)標(biāo)記名稱對(duì)應(yīng)。如果需要執(zhí)行動(dòng)作的話，規(guī)則可以寫成一個(gè)方法。例如，下面的規(guī)則匹配數(shù)字字串，并且將匹配的字符串轉(zhuǎn)化成Python的整型：
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
如果使用方法的話，正則表達(dá)式寫成方法的文檔字符串。方法總是需要接受一個(gè)LexToken實(shí)例的參數(shù)，該實(shí)例有一個(gè)t.type的屬性（字符串表示）來表示標(biāo)記的類型名稱，t.value是標(biāo)記值（匹配的實(shí)際的字符串），t.lineno表示當(dāng)前在源輸入串中的作業(yè)行，t.lexpos表示標(biāo)記相對(duì)于輸入串起始位置的偏移。默認(rèn)情況下，t.type是以t_開頭的變量或方法的后面部分。方法可以在方法體里面修改這些屬性。但是，如果這樣做，應(yīng)該返回結(jié)果token，否則，標(biāo)記將被丟棄。
在lex內(nèi)部，lex.py用re模塊處理模式匹配，在構(gòu)造最終的完整的正則式的時(shí)候，用戶提供的規(guī)則按照下面的順序加入：
- 所有由方法定義的標(biāo)記規(guī)則，按照他們的出現(xiàn)順序依次加入
- 由字符串變量定義的標(biāo)記規(guī)則按照其正則式長(zhǎng)度倒序后，依次加入（長(zhǎng)的先入）
- 順序的約定對(duì)于精確匹配是必要的。比如，如果你想?yún)^(qū)分‘=’和‘==’，你需要確?！?=’優(yōu)先檢查。如果用字符串來定義這樣的表達(dá)式的話，通過將較長(zhǎng)的正則式先加入，可以幫助解決這個(gè)問題。用方法定義標(biāo)記，可以顯示地控制哪個(gè)規(guī)則優(yōu)先檢查。
為了處理保留字，你應(yīng)該寫一個(gè)單一的規(guī)則來匹配這些標(biāo)識(shí)，并在方法里面作特殊的查詢：
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
這樣做可以大大減少正則式的個(gè)數(shù)，并稍稍加快處理速度。注意：你應(yīng)該避免為保留字編寫單獨(dú)的規(guī)則，例如，如果你像下面這樣寫：
t_FOR = r'for'
t_PRINT = r'print'
但是，這些規(guī)則照樣也能夠匹配以這些字符開頭的單詞，比如’forget’或者’printed’，這通常不是你想要的。
4.4 標(biāo)記的值
標(biāo)記被lex返回后，它們的值被保存在value屬性中。正常情況下，value是匹配的實(shí)際文本。事實(shí)上，value可以被賦為任何Python支持的類型。例如，當(dāng)掃描到標(biāo)識(shí)符的時(shí)候，你可能不僅需要返回標(biāo)識(shí)符的名字，還需要返回其在符號(hào)表中的位置，可以像下面這樣寫：
def t_ID(t):
...
# Look up symbol table information and return a tuple
t.value = (t.value, symbol_lookup(t.value))
...
return t
需要注意的是，不推薦用其他屬性來保存值，因?yàn)閥acc.py模塊只會(huì)暴露出標(biāo)記的value屬性，訪問其他屬性會(huì)變得不自然。如果想保存多種屬性，可以將元組、字典、或者對(duì)象實(shí)例賦給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àn)榉椒軌蛱峁└_的匹配優(yōu)先級(jí)控制（方法根據(jù)出現(xiàn)的順序，而字符串的正則表達(dá)式依據(jù)正則表達(dá)式的長(zhǎng)度）
4.6 行號(hào)和位置信息
默認(rèn)情況下，lex.py對(duì)行號(hào)一無所知。因?yàn)閘ex.py根本不知道何為”行”的概念（換行符本身也作為文本的一部分）。不過，可以通過寫一個(gè)特殊的規(guī)則來記錄行號(hào)：
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
在這個(gè)規(guī)則中，當(dāng)前l(fā)exer對(duì)象t.lexer的lineno屬性被修改了，而且空行被簡(jiǎn)單的丟棄了，因?yàn)闆]有任何的返回。
lex.py也不自動(dòng)做列跟蹤。但是，位置信息被記錄在了每個(gè)標(biāo)記對(duì)象的lexpos屬性中，這樣，就有可能來計(jì)算列信息了。例如：每當(dāng)遇到新行的時(shí)候就重置列值：
# 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
通常，計(jì)算列的信息是為了指示上下文的錯(cuò)誤位置，所以只在必要時(shí)有用。
4.7 忽略字符
t_ignore規(guī)則比較特殊，是lex.py所保留用來忽略字符的，通常用來跳過空白或者不需要的字符。雖然可以通過定義像t_newline()這樣的規(guī)則來完成相同的事情，不過使用t_ignore能夠提供較好的詞法分析性能，因?yàn)橄啾绕胀ǖ恼齽t式，它被特殊化處理了。
4.8 字面字符
字面字符可以通過在詞法模塊中定義一個(gè)literals變量做到，例如：
literals = [ '+','-','*','/' ]
或者
literals = "+-*/"
字面字符是指單個(gè)字符，表示把字符本身作為標(biāo)記，標(biāo)記的type和value都是字符本身。不過，字面字符是在其他正則式之后被檢查的，因此如果有規(guī)則是以這些字符開頭的，那么這些規(guī)則的優(yōu)先級(jí)較高。
4.9 錯(cuò)誤處理
最后，在詞法分析中遇到非法字符時(shí)，t_error()用來處理這類錯(cuò)誤。這種情況下，t.value包含了余下還未被處理的輸入字串，在之前的例子中，錯(cuò)誤處理方法是這樣的：
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
這個(gè)例子中，我們只是簡(jiǎn)單的輸出不合法的字符，并且通過調(diào)用t.lexer.skip(1)跳過一個(gè)字符。
4.10 構(gòu)建和使用lexer
函數(shù)lex.lex()使用Python的反射機(jī)制讀取調(diào)用上下文中的正則表達(dá)式，來創(chuàng)建lexer。lexer一旦創(chuàng)建好，有兩個(gè)方法可以用來控制lexer對(duì)象：
- lexer.input(data) 重置lexer和輸入字串
- lexer.token() 返回下一個(gè)LexToken類型的標(biāo)記實(shí)例，如果進(jìn)行到輸入字串的尾部時(shí)將返回
None
推薦直接在lex()函數(shù)返回的lexer對(duì)象上調(diào)用上述接口，盡管也可以向下面這樣用模塊級(jí)別的lex.input()和lex.token()：
lex.lex()
lex.input(sometext)
while 1:
tok = lex.token()
if not tok: break
print tok
在這個(gè)例子中，lex.input()和lex.token()是模塊級(jí)別的方法，在lex模塊中，input()和token()方法綁定到最新創(chuàng)建的lexer對(duì)象的對(duì)應(yīng)方法上。最好不要這樣用，因?yàn)檫@種接口可能不知道在什么時(shí)候就失效（譯者注：垃圾回收？）
4.11 @TOKEN裝飾器
在一些應(yīng)用中，你可能需要定義一系列輔助的記號(hào)來構(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. ?????
...
在這個(gè)例子中，我們希望ID的規(guī)則引用上面的已有的變量。然而，使用文檔字符串無法做到，為了解決這個(gè)問題，你可以使用@TOKEN裝飾器：
from ply.lex import TOKEN
@TOKEN(identifier)
def t_ID(t):
...
裝飾器可以將identifier關(guān)聯(lián)到t_ID()的文檔字符串上以使lex.py正常工作，一種等價(jià)的做法是直接給文檔字符串賦值：
def t_ID(t):
...
t_ID.__doc__ = identifier
注意：@TOKEN裝飾器需要Python-2.4以上的版本。如果你在意老版本Python的兼容性問題，使用上面的等價(jià)辦法。
4.12 優(yōu)化模式
為了提高性能，你可能希望使用Python的優(yōu)化模式（比如，使用-o選項(xiàng)執(zhí)行Python）。然而，這樣的話，Python會(huì)忽略文檔字串，這是lex.py的特殊問題，可以通過在創(chuàng)建lexer的時(shí)候使用optimize選項(xiàng)：
lexer = lex.lex(optimize=1)
接著，用Python常規(guī)的模式運(yùn)行，這樣，lex.py會(huì)在當(dāng)前目錄下創(chuàng)建一個(gè)lextab.py文件，這個(gè)文件會(huì)包含所有的正則表達(dá)式規(guī)則和詞法分析階段的分析表。然后，lextab.py可以被導(dǎo)入用來構(gòu)建lexer。這種方法大大改善了詞法分析程序的啟動(dòng)時(shí)間，而且可以在Python的優(yōu)化模式下工作。
想要更改生成的文件名，使用如下參數(shù)：
lexer = lex.lex(optimize=1,lextab="footab")
在優(yōu)化模式下執(zhí)行，需要注意的是lex會(huì)被禁用大多數(shù)的錯(cuò)誤檢查。因此，建議只在確保萬事俱備準(zhǔn)備發(fā)布最終代碼時(shí)使用。
4.13 調(diào)試
如果想要調(diào)試，可以使lex()運(yùn)行在調(diào)試模式：
lexer = lex.lex(debug=1)
這將打出一些調(diào)試信息，包括添加的規(guī)則、最終的正則表達(dá)式和詞法分析過程中得到的標(biāo)記。
除此之外，lex.py有一個(gè)簡(jiǎn)單的主函數(shù)，不但支持對(duì)命令行參數(shù)輸入的字串進(jìn)行掃描，還支持命令行參數(shù)指定的文件名：
if __name__ == '__main__':
lex.runmain()
想要了解高級(jí)調(diào)試的詳情，請(qǐng)移步至最后的高級(jí)調(diào)試部分。
4.14 其他方式定義詞法規(guī)則
上面的例子，詞法分析器都是在單個(gè)的Python模塊中指定的。如果你想將標(biāo)記的規(guī)則放到不同的模塊，使用module關(guān)鍵字參數(shù)。例如，你可能有一個(gè)專有的模塊，包含了標(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選項(xiàng)也可以指定類型的實(shí)例，例如：
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，你需要?jiǎng)?chuàng)建類的實(shí)例，而不是類本身。這是因?yàn)椋琹exer的方法只有被綁定（bound-methods）對(duì)象后才能使PLY正常工作。
當(dāng)給lex()方法使用module選項(xiàng)時(shí)，PLY使用dir()方法，從對(duì)象中獲取符號(hào)信息，因?yàn)椴荒苤苯釉L問對(duì)象的__dict__屬性。（譯者注：可能是因?yàn)榧嫒菪栽颍?code>__dict__這個(gè)方法可能不存在）
最后，如果你希望保持較好的封裝性，但不希望什么東西都寫在類里面，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è)置，符號(hào)表和其他細(xì)節(jié)。例如，假設(shè)你想要跟蹤NUMBER標(biāo)記的出現(xiàn)個(gè)數(shù)。
一種方法是維護(hù)一個(gè)全局變量：
num_count = 0
def t_NUMBER(t):
r'\d+'
global num_count
num_count += 1
t.value = int(t.value)
return t
如果你不喜歡全局變量，另一個(gè)記錄信息的地方是lexer對(duì)象內(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)點(diǎn)是當(dāng)同時(shí)存在多個(gè)lexer實(shí)例的情況下，簡(jiǎn)單易行。不過這看上去似乎是嚴(yán)重違反了面向?qū)ο蟮姆庋b原則。lexer的內(nèi)部屬性（除了lineno）都是以lex開頭命名的（lexdata、lexpos）。因此，只要不以lex開頭來命名屬性就很安全的。
如果你不喜歡給lexer對(duì)象賦值，你可以自定義你的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)用會(huì)創(chuàng)建很多l(xiāng)exer的實(shí)例，并且需要維護(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對(duì)象可以通過clone()方法來復(fù)制：
lexer = lex.lex()
...
newlexer = lexer.clone()
當(dāng)lexer被克隆后，復(fù)制品能夠精確的保留輸入串和內(nèi)部狀態(tài)，不過，新的lexer可以接受一個(gè)不同的輸出字串，并獨(dú)立運(yùn)作起來。這在幾種情況下也許有用：當(dāng)你在編寫的解析器或編譯器涉及到遞歸或者回退處理時(shí)，你需要掃描先前的部分，你可以clone并使用復(fù)制品，或者你在實(shí)現(xiàn)某種預(yù)編譯處理，可以clone一些lexer來處理不同的輸入文件。
創(chuàng)建克隆跟重新調(diào)用lex.lex()的不同點(diǎn)在于，PLY不會(huì)重新構(gòu)建任何的內(nèi)部分析表或者正則式。當(dāng)lexer是用類或者閉包創(chuàng)建的，需要注意類或閉包本身的的狀態(tài)。換句話說你要注意新創(chuàng)建的lexer會(huì)共享原始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。這是一個(gè)表示當(dāng)前分析點(diǎn)的位置的整型值。如果你修改這個(gè)值的話，這會(huì)改變下一個(gè)token()的調(diào)用行為。在標(biāo)記的規(guī)則方法里面，這個(gè)值表示緊跟匹配字串后面的第一個(gè)字符的位置，如果這個(gè)值在規(guī)則中修改，下一個(gè)返回的標(biāo)記將從新的位置開始匹配 -
lexer.lineno。表示當(dāng)前行號(hào)。PLY只是聲明這個(gè)屬性的存在，卻永遠(yuǎn)不更新這個(gè)值。如果你想要跟蹤行號(hào)的話，你需要自己添加代碼（ 4.6 行號(hào)和位置信息） -
lexer.lexdata。當(dāng)前l(fā)exer的輸入字串，這個(gè)字符串就是input()方法的輸入字串，更改它可能是個(gè)糟糕的做法，除非你知道自己在干什么。 -
lexer.lexmatch。PLY內(nèi)部調(diào)用Python的re.match()方法得到的當(dāng)前標(biāo)記的原始的Match對(duì)象，該對(duì)象被保存在這個(gè)屬性中。如果你的正則式中包含分組的話，你可以通過這個(gè)對(duì)象獲得這些分組的值。注意：這個(gè)屬性只在有標(biāo)記規(guī)則定義的方法中才有效。
4.18 基于條件的掃描和啟動(dòng)條件
在高級(jí)的分析器應(yīng)用程序中，使用狀態(tài)化的詞法掃描是很有用的。比如，你想在出現(xiàn)特定標(biāo)記或句子結(jié)構(gòu)的時(shí)候觸發(fā)開始一個(gè)不同的詞法分析邏輯。PLY允許lexer在不同的狀態(tài)之間轉(zhuǎn)換。每個(gè)狀態(tài)可以包含一些自己獨(dú)特的標(biāo)記和規(guī)則等。這是基于GNU flex的“啟動(dòng)條件”來實(shí)現(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'),
)
這個(gè)聲明中包含有兩個(gè)狀態(tài)：’foo’和’bar’。狀態(tài)可以有兩種類型：’排他型’和’包容型’。排他型的狀態(tài)會(huì)使得lexer的行為發(fā)生完全的改變：只有能夠匹配在這個(gè)狀態(tài)下定義的規(guī)則的標(biāo)記才會(huì)返回；包容型狀態(tài)會(huì)將定義在這個(gè)狀態(tài)下的規(guī)則添加到默認(rèn)的規(guī)則集中，進(jìn)而，只要能匹配這個(gè)規(guī)則集的標(biāo)記都會(huì)返回。
一旦聲明好之后，標(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
一個(gè)標(biāo)記可以用在多個(gè)狀態(tài)中，只要將多個(gè)狀態(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)到一個(gè)特殊的狀態(tài)INITIAL，比如，下面兩個(gè)聲明是等價(jià)的：
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)下工作，這個(gè)狀態(tài)下包含了所有默認(rèn)的標(biāo)記規(guī)則定義。對(duì)于不希望使用“狀態(tài)”的用戶來說，這是完全透明的。在分析過程中，如果你想要改變?cè)~法分析器的這種的狀態(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)時(shí)，狀態(tài)棧比較有用。
舉個(gè)例子會(huì)更清晰。假設(shè)你在寫一個(gè)分析器想要從一堆C代碼中獲取任意匹配的閉合的大括號(hào)里面的部分：這意味著，當(dāng)遇到起始括號(hào)’{‘，你需要讀取與之匹配的’}’以上的所有部分。并返回字符串。使用通常的正則表達(dá)式幾乎不可能，這是因?yàn)榇罄ㄌ?hào)可以嵌套，而且可以有注釋，字符串等干擾。因此，試圖簡(jiǎn)單的匹配第一個(gè)出現(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)
這個(gè)例子中，第一個(gè)’{‘使得lexer記錄了起始位置，并且進(jìn)入新的狀態(tài)’ccode’。一系列規(guī)則用來匹配接下來的輸入，這些規(guī)則只是丟棄掉標(biāo)記（不返回值），如果遇到閉合右括號(hào)，t_ccode_rbrace規(guī)則收集其中所有的代碼（利用先前記錄的開始位置），并保存，返回的標(biāo)記類型為’CCODE’，與此同時(shí)，詞法分析的狀態(tài)退回到初始狀態(tài)。
4.19 其他問題
- lexer需要輸入的是一個(gè)字符串。好在大多數(shù)機(jī)器都有足夠的內(nèi)存，這很少導(dǎo)致性能的問題。這意味著，lexer現(xiàn)在還不能用來處理文件流或者socket流。這主要是受到
re模塊的限制。 - lexer支持用Unicode字符描述標(biāo)記的匹配規(guī)則，也支持輸入字串包含Unicode
- 如果你想要向
re.compile()方法提供flag，使用reflags選項(xiàng)：lex.lex(reflags=re.UNICODE) - 由于lexer是全部用Python寫的，性能很大程度上取決于Python的
re模塊，即使已經(jīng)盡可能的高效了。當(dāng)接收極其大量的輸入文件時(shí)表現(xiàn)并不盡人意。如果擔(dān)憂性能，你可以升級(jí)到最新的Python，或者手工創(chuàng)建分析器，或者用C語言寫lexer并做成擴(kuò)展模塊。
如果你要?jiǎng)?chuàng)建一個(gè)手寫的詞法分析器并計(jì)劃用在yacc.py中，只需要滿足下面的要求：
- 需要提供一個(gè)
token()方法來返回下一個(gè)標(biāo)記，如果沒有可用的標(biāo)記了，則返回None。 -
token()方法必須返回一個(gè)tok對(duì)象，具有type和value屬性。如果行號(hào)需要跟蹤的話，標(biāo)記還需要定義lineno屬性。
5 語法分析基礎(chǔ)
yacc.py用來對(duì)語言進(jìn)行語法分析。在給出例子之前，必須提一些重要的背景知識(shí)。首先，‘語法’通常用BNF范式來表達(dá)。例如，如果想要分析簡(jiǎn)單的算術(shù)表達(dá)式，你應(yīng)該首先寫下無二義的文法：
expression : expression + term
| expression - term
| term
term : term * factor
| term / factor
| factor
factor : NUMBER
| ( expression )
在這個(gè)文法中，像NUMBER,+,-,*,/的符號(hào)被稱為終結(jié)符，對(duì)應(yīng)原始的輸入。類似term，factor等稱為非終結(jié)符，它們由一系列終結(jié)符或其他規(guī)則的符號(hào)組成，用來指代語法規(guī)則。
通常使用一種叫語法制導(dǎo)翻譯的技術(shù)來指定某種語言的語義。在語法制導(dǎo)翻譯中，符號(hào)及其屬性出現(xiàn)在每個(gè)語法規(guī)則后面的動(dòng)作中。每當(dāng)一個(gè)語法被識(shí)別，動(dòng)作就能夠描述需要做什么。比如，對(duì)于上面給定的文法，想要實(shí)現(xiàn)一個(gè)簡(jiǎn)單的計(jì)算器，應(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)翻譯的好方法是將符號(hào)看成對(duì)象。與符號(hào)相關(guān)的值代表了符號(hào)的“狀態(tài)”（比如上面的val屬性），語義行為用一組操作符號(hào)及符號(hào)值的函數(shù)或者方法來表達(dá)。
Yacc用的分析技術(shù)是著名的LR分析法或者叫移進(jìn)-歸約分析法。LR分析法是一種自下而上的技術(shù)：首先嘗試識(shí)別右部的語法規(guī)則，每當(dāng)右部得到滿足，相應(yīng)的行為代碼將被觸發(fā)執(zhí)行，當(dāng)前右邊的語法符號(hào)將被替換為左邊的語法符號(hào)。（歸約）
LR分析法一般這樣實(shí)現(xiàn)：將下一個(gè)符號(hào)進(jìn)棧，然后結(jié)合棧頂?shù)姆?hào)和后繼符號(hào)（譯者注：下一個(gè)將要輸入符號(hào)），與文法中的某種規(guī)則相比較。具體的算法可以在編譯器的手冊(cè)中查到，下面的例子展現(xiàn)了如果通過上面定義的文法，來分析3 + 5 * ( 10 - 20 )這個(gè)表達(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)棧動(dòng)作，簡(jiǎn)稱移進(jìn)；Reduce是歸約）
在分析表達(dá)式的過程中，一個(gè)相關(guān)的自動(dòng)狀態(tài)機(jī)和后繼符號(hào)決定了下一步應(yīng)該做什么。如果下一個(gè)標(biāo)記看起來是一個(gè)有效語法（產(chǎn)生式）的一部分（通過棧上的其他項(xiàng)判斷這一點(diǎn)），那么這個(gè)標(biāo)記應(yīng)該進(jìn)棧。如果棧頂?shù)捻?xiàng)可以組成一個(gè)完整的右部語法規(guī)則，一般就可以進(jìn)行“歸約”，用產(chǎn)生式左邊的符號(hào)代替這一組符號(hào)。當(dāng)歸約發(fā)生時(shí)，相應(yīng)的行為動(dòng)作就會(huì)執(zhí)行。如果輸入標(biāo)記既不能移進(jìn)也不能歸約的話，就會(huì)發(fā)生語法錯(cuò)誤，分析器必須進(jìn)行相應(yīng)的錯(cuò)誤恢復(fù)。分析器直到?？詹⑶覜]有另外的輸入標(biāo)記時(shí)，才算成功。 需要注意的是，這是基于一個(gè)有限自動(dòng)機(jī)實(shí)現(xiàn)的，有限自動(dòng)器被轉(zhuǎn)化成分析表。分析表的構(gòu)建比較復(fù)雜，超出了本文的討論范圍。不過，這構(gòu)建過程的微妙細(xì)節(jié)能夠解釋為什么在上面的例子中，解析器選擇在步驟9將標(biāo)記轉(zhuǎn)移到堆棧中，而不是按照規(guī)則expr : expr + term做歸約。
6 Yacc
ply.yacc模塊實(shí)現(xiàn)了PLY的分析功能，‘yacc’是‘Yet Another Compiler Compiler’的縮寫并保留了其作為Unix工具的名字。
6.1 一個(gè)例子
假設(shè)你希望實(shí)現(xiàn)上面的簡(jiǎ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
在這個(gè)例子中，每個(gè)語法規(guī)則被定義成一個(gè)Python的方法，方法的文檔字符串描述了相應(yīng)的上下文無關(guān)文法，方法的語句實(shí)現(xiàn)了對(duì)應(yīng)規(guī)則的語義行為。每個(gè)方法接受一個(gè)單獨(dú)的p參數(shù)，p是一個(gè)包含有當(dāng)前匹配語法的符號(hào)的序列，p[i]與語法符號(hào)的對(duì)應(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)于詞法分析模塊中對(duì)p.value屬性賦的值，對(duì)于非終結(jié)符的值，將在歸約時(shí)由p[0]的賦值決定，這里的值可以是任何類型，當(dāng)然，大多數(shù)情況下只是Python的簡(jiǎn)單類型、元組或者類的實(shí)例。在這個(gè)例子中，我們依賴這樣一個(gè)事實(shí)：NUMBER標(biāo)記的值保存的是整型值，所有規(guī)則的行為都是得到這些整型值的算術(shù)運(yùn)算結(jié)果，并傳遞結(jié)果。
注意：在這里負(fù)數(shù)的下標(biāo)有特殊意義–這里的p[-1]不等同于p[3]。詳見下面的嵌入式動(dòng)作部分
在yacc中定義的第一個(gè)語法規(guī)則被默認(rèn)為起始規(guī)則（這個(gè)例子中的第一個(gè)出現(xiàn)的expression規(guī)則）。一旦起始規(guī)則被分析器歸約，而且再無其他輸入，分析器終止，最后的值將返回（這個(gè)值將是起始規(guī)則的p[0]）。注意：也可以通過在yacc()中使用start關(guān)鍵字參數(shù)來指定起始規(guī)則
p_error(p)規(guī)則用于捕獲語法錯(cuò)誤。詳見處理語法錯(cuò)誤部分
為了構(gòu)建分析器，需要調(diào)用yacc.yacc()方法。這個(gè)方法查看整個(gè)當(dāng)前模塊，然后試圖根據(jù)你提供的文法構(gòu)建LR分析表。第一次執(zhí)行yacc.yacc()，你會(huì)得到如下輸出：
$ python calcparse.py
Generating LALR tables
calc >
由于分析表的得出相對(duì)開銷較大（尤其包含大量的語法的情況下），分析表被寫入當(dāng)前目錄的一個(gè)叫parsetab.py的文件中。除此之外，會(huì)生成一個(gè)調(diào)試文件parser.out。在接下來的執(zhí)行中，yacc直到發(fā)現(xiàn)文法發(fā)生變化，才會(huì)重新生成分析表和parsetab.py文件，否則yacc會(huì)從parsetab.py中加載分析表。注：如果有必要的話這里輸出的文件名是可以改的。
如果在你的文法中有任何錯(cuò)誤的話，yacc.py會(huì)產(chǎn)生調(diào)試信息，而且可能拋出異常。一些可以被檢測(cè)到的錯(cuò)誤如下：
- 方法重復(fù)定義（在語法文件中具有相同名字的方法）
- 二義文法產(chǎn)生的移進(jìn)-歸約和歸約-歸約沖突
- 指定了錯(cuò)誤的文法
- 不可終止的遞歸（規(guī)則永遠(yuǎn)無法終結(jié)）
- 未使用的規(guī)則或標(biāo)記
- 未定義的規(guī)則或標(biāo)記
下面幾個(gè)部分將更詳細(xì)的討論語法規(guī)則
這個(gè)例子的最后部分展示了如何執(zhí)行由yacc()方法創(chuàng)建的分析器。你只需要簡(jiǎn)單的調(diào)用parse()，并將輸入字符串作為參數(shù)就能運(yùn)行分析器。它將運(yùn)行所有的語法規(guī)則，并返回整個(gè)分析的結(jié)果，這個(gè)結(jié)果就是在起始規(guī)則中賦給p[0]的值。
6.2 將語法規(guī)則合并
如果語法規(guī)則類似的話，可以合并到一個(gè)方法中。例如，考慮前面例子中的兩個(gè)規(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]
比起寫兩個(gè)方法，你可以像下面這樣寫在一個(gè)方法里面：
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]
總之，方法的文檔字符串可以包含多個(gè)語法規(guī)則。所以，像這樣寫也是合法的（盡管可能會(huì)引起困惑）：
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ī)則合并才是個(gè)不錯(cuò)的注意（比如，產(chǎn)生式的項(xiàng)數(shù)相同）。不然，語義動(dòng)作可能會(huì)變得復(fù)雜。不過，簡(jiǎn)單情況下，可以使用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)該避免像這些例子一樣在一個(gè)語法規(guī)則里面用很多條件來處理。因?yàn)?，每次檢查當(dāng)前究竟匹配的是哪個(gè)語法規(guī)則的時(shí)候，實(shí)際上重復(fù)做了分析器已經(jīng)做過的事（分析器已經(jīng)準(zhǔn)確的知道哪個(gè)規(guī)則被匹配了）。為每個(gè)規(guī)則定義單獨(dú)的方法，可以消除這點(diǎn)開銷。
6.3 字面字符
如果愿意，可以在語法規(guī)則里面使用單個(gè)的字面字符，例如：
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]
字符必須像’+’那樣使用單引號(hào)。除此之外，需要將用到的字符定義單獨(dú)定義在lex文件的literals列表里：
# Literals. Should be placed in module given to lex()
literals = ['+','-','*','/' ]
字面的字符只能是單個(gè)字符。因此，像’<=’或者’==’都是不合法的，只能使用一般的詞法規(guī)則（例如t_EQ = r’==’)。
6.4 空產(chǎn)生式
yacc.py可以處理空產(chǎn)生式，像下面這樣做：
def p_empty(p):
'empty :'
pass
現(xiàn)在可以使用空匹配，只要將’empty’當(dāng)成一個(gè)符號(hào)使用：
def p_optitem(p):
'optitem : item'
' | empty'
...
注意：你可以將產(chǎn)生式保持’空’，來表示空匹配。然而，我發(fā)現(xiàn)用一個(gè)’empty’規(guī)則并用其來替代’空’，更容易表達(dá)意圖，并有較好的可讀性。
6.5 改變起始符號(hào)
默認(rèn)情況下，在yacc中的第一條規(guī)則是起始語法規(guī)則（頂層規(guī)則）?？梢杂?code>start標(biāo)識(shí)來改變這種行為：
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)識(shí)有助于在調(diào)試的時(shí)候?qū)⒋笮偷恼Z法規(guī)則分成小部分來分析。也可把start符號(hào)作為yacc的參數(shù)：
yacc.yacc(start='foo')
