引言

最近剛剛用python寫(xiě)完了一個(gè)解析protobuf文件的簡(jiǎn)單編譯器，深感ply實(shí)現(xiàn)詞法分析和語(yǔ)法分析的簡(jiǎn)潔方便。乘著余熱未過(guò)，頭腦清醒，記下一點(diǎn)總結(jié)和心得，方便各位pythoner參考使用。

ply使用

簡(jiǎn)介

如果你不是從事編譯器或者解析器的開(kāi)發(fā)工作，你可能從未聽(tīng)說(shuō)過(guò)ply。ply是基于python的lex和yacc，而它的作者就是大名鼎鼎Python Cookbook, 3rd Edition的作者。可能有些朋友就納悶了，我一個(gè)業(yè)務(wù)開(kāi)發(fā)怎么需要自己寫(xiě)編譯器呢，各位編程大牛說(shuō)過(guò)，中央決定了，要多嘗試新的東西。而且了解一些語(yǔ)法解析的姿勢(shì)，以后自己解析格式復(fù)雜的日志或者數(shù)學(xué)公式，也是非常有幫助的。

針對(duì)沒(méi)有編譯基礎(chǔ)的童鞋，強(qiáng)烈建議了解一些文法相關(guān)的基本概念。輪子哥強(qiáng)烈推薦的parsing techniques以及編譯龍虎鯨書(shū)，個(gè)人感覺(jué)都不適合入門(mén)學(xué)習(xí)，在此推薦胡倫俊的編譯原理（電子工業(yè)出版社），針對(duì)概念的例子講解很多，很適合入門(mén)學(xué)習(xí)。當(dāng)然也不需要特別深入研究，知道詞法分析和語(yǔ)法分析的相關(guān)概念和方法就可以愉快的使用ply了。文檔鏈接： http://www.pchou.info/open-source/2014/01/18/52da47204d4cb.html

為了方便大家上手，以求解多元一次方程組為例，講解一下ply的使用。

例子說(shuō)明

輸入是多個(gè)格式為x + 4y - 3.2z = 7的一次方程，為了讓例子盡可能簡(jiǎn)單，做如下限制：

每個(gè)方程含有變量的部分在等號(hào)左邊，常數(shù)在等號(hào)右邊 每個(gè)方程不限制變量的個(gè)數(shù)以及變量的順序，但每個(gè)方程每個(gè)變量只允許出現(xiàn)一次 變量的命令規(guī)則為小寫(xiě)字母串（x y xx yy abc 均為合法變量名） 變量的系數(shù)限制為整數(shù)和浮點(diǎn)數(shù)，浮點(diǎn)數(shù)不允許1.4e8的格式，系數(shù)和變量緊鄰，且系數(shù)不能為0 方程組和方程組之間用, ;隔開(kāi)

學(xué)過(guò)線性代數(shù)的童鞋肯定知道，只需要將方程組抽象為矩陣，按照線性代數(shù)的方法就可以解決。因此只需要將輸入方程組解析成右邊的矩陣和變量列表即可，剩下的求解過(guò)程就可以交給線性代數(shù)相關(guān)的工具解決。

詞法解析

ply中的lex來(lái)做詞法解析，詞法解析的理論有一大堆，但是lex用起來(lái)卻非常直觀，就是用正則表達(dá)式的方式將文本字符串解析為一個(gè)一個(gè)的token，下面的代碼就是用lex實(shí)現(xiàn)詞法解析。

from ply import lex# 空格 制表符 回車(chē)這些不可見(jiàn)符號(hào)都忽略t_ignore = ’ tr’# 解析錯(cuò)誤的時(shí)候直接拋出異常def t_error(t): raise Exception(’error {} at line {}’.format(t.value[0], t.lineno))# 記錄行號(hào)，方便出錯(cuò)定位def t_newline(t): r’n+’ t.lexer.lineno += len(t.value)# 支持c++風(fēng)格的注釋def t_ignore_COMMENT(t): r’//[^n]*’# 變量的命令規(guī)則def t_VARIABLE(t): r’[a-z]+’ return t# 常數(shù)命令規(guī)則def t_CONSTANT(t): r’d+(.d+)?’ t.value = float(t.value) return t# 輸入中支持的符號(hào)頭token，當(dāng)然也支持t_PLUS = r’+’的方式將加號(hào)定義為tokenliterals = ’+-,;=’tokens = (’VARIABLE’, ’CONSTANT’)if __name__ == ’__main__’: data = ’’’ -x + 2.4y + z = 0; //this is a comment 9y - z + 7.2x = -1; y - z + x = 8 ’’’ lexer = lex.lex() lexer.input(data) while True: tok = lexer.token() if not tok: break print tok

直接運(yùn)行文件就可以將解析的token串打印出來(lái)，如下所示，詳細(xì)的使用文檔可以參考ply文檔。

LexToken(-,’-’,2,5)LexToken(VARIABLE,’x’,2,6)LexToken(+,’+’,2,8)LexToken(CONSTANT,2.4,2,10)LexToken(VARIABLE,’y’,2,13)LexToken(+,’+’,2,15)LexToken(VARIABLE,’z’,2,17)LexToken(=,’=’,2,19)LexToken(CONSTANT,0.0,2,21)LexToken(;,’;’,2,22)```### 語(yǔ)法解析ply中的yacc用作語(yǔ)法分析，雖然復(fù)雜的詞法分析可以代替簡(jiǎn)單的語(yǔ)法分析，但類似于編程語(yǔ)言的解析再?gòu)?fù)雜的詞法分析也勝任不了。在使用yacc之前，需要了解上下文無(wú)關(guān)文法，這部分內(nèi)容太多太雜，我也只了解部分簡(jiǎn)單的概念，有興趣的可以看一看編譯原理深入了解。目前語(yǔ)法分析的方法有兩大類，即自下向上的分析方法和自上而下的分析方法。所謂自上而下的分下法就是從文法的開(kāi)始符號(hào)出發(fā)，根據(jù)文法規(guī)則正向推到出給定句子的一種方法，或者說(shuō)，從樹(shù)根開(kāi)始，往下構(gòu)造語(yǔ)法樹(shù)，直到建立每個(gè)樹(shù)葉的分析方法。代表算法是LL(1)，此算法文法解析能力不強(qiáng)，對(duì)文法定義要求比較高，主流的編譯器都沒(méi)有使用。自下而上的分析法是從給定的輸入串開(kāi)始，根據(jù)文法規(guī)則逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)，或者說(shuō)從語(yǔ)法書(shū)的末端開(kāi)始，步步向上歸約，直至歸約到根節(jié)點(diǎn)的分析方法。代表算法有SLR、LRLR，ply使用的就是LRLR。因此我們只需要定義文法和規(guī)約動(dòng)作即可，以下就是完整的代碼。```python# -*- coding=utf8 -*-from ply import ( lex, yacc)# 空格 制表符 回車(chē)這些不可見(jiàn)符號(hào)都忽略t_ignore = ’ tr’# 解析錯(cuò)誤的時(shí)候直接拋出異常def t_error(t): raise Exception(’error {} at line {}’.format(t.value[0], t.lineno))# 記錄行號(hào)，方便出錯(cuò)定位def t_newline(t): r’n+’ t.lexer.lineno += len(t.value)# 支持c++風(fēng)格的注釋def t_ignore_COMMENT(t): r’//[^n]*’# 變量的命令規(guī)則def t_VARIABLE(t): r’[a-z]+’ return t# 常數(shù)命令規(guī)則def t_CONSTANT(t): r’d+(.d+)?’ t.value = float(t.value) return t# 輸入中支持的符號(hào)頭token，當(dāng)然也支持t_PLUS = r’+’的方式將加號(hào)定義為tokenliterals = ’+-,;=’tokens = (’VARIABLE’, ’CONSTANT’)# 頂層文法，規(guī)約的時(shí)候equations對(duì)應(yīng)的p[1]是一個(gè)列表，包含了方程左邊各個(gè)變量與系數(shù)還有方程左邊的常數(shù)def p_start(p): '''start : equations''' var_count, var_list = 0, [] for left, _ in p[1]: for con, var_name in left: if var_name in var_list:continue var_list.append(var_name) var_count += 1 matrix = [[0] * (var_count + 1) for _ in xrange(len(p[1]))] for counter, eq in enumerate(p[1]): left, right = eq for con, var_name in left: matrix[counter][var_list.index(var_name)] = con matrix[counter][-1] = -right var_list.append(1) p[0] = matrix, var_list# 方程組對(duì)應(yīng)的文法，每個(gè)方程用，或者；做分隔def p_equations(p): '''equations : equation ’,’ equations | equation ’;’ equations | equation''' if len(p) == 2: p[0] = [p[1]] else: p[0] = [p[1]] + p[3]# 單個(gè)方程對(duì)應(yīng)的文法def p_equation(p): '''equation : eq_left ’=’ eq_right''' p[0] = (p[1], p[3])# 方程等式左邊對(duì)應(yīng)的文法def p_eq_left(p): '''eq_left : var_unit eq_left|''' if len(p) == 1: p[0] = [] else: p[0] = [p[1]] + p[2]# 六種文法對(duì)應(yīng)例子： x, 5x, +x, -x, +4x, -4y# 歸約的形式是一個(gè)元組，例： (5, ’x’)def p_var_unit(p): '''var_unit : VARIABLE| CONSTANT VARIABLE| ’+’ VARIABLE| ’-’ VARIABLE| ’+’ CONSTANT VARIABLE| ’-’ CONSTANT VARIABLE''' len_p = len(p) if len_p == 2: p[0] = (1.0, p[1]) elif len_p == 3: if p[1] == ’+’: p[0] = (1.0, p[2]) elif p[1] == ’-’: p[0] = (-1.0, p[2]) else: p[0] = (p[1], p[2]) else: if p[1] == ’+’: p[0] = (p[2], p[3]) else: p[0] = (-p[2], p[3])# 方程等式右邊對(duì)應(yīng)的常數(shù)，對(duì)應(yīng)的例子：1.2， +1.2， -1.2def p_eq_right(p): '''eq_right : CONSTANT| ’+’ CONSTANT| ’-’ CONSTANT''' if len(p) == 3: if p[1] == ’-’: p[0] = -p[2] else: p[0] = p[2] else: p[0] = p[1]if __name__ == ’__main__’: data = ’’’ -x + 2.4y + z = 0; //this is a comment 9y - z + 7.2x = -1; y - z + x = 8 ’’’ lexer = lex.lex() parser = yacc.yacc(debug=True) lexer.lineno = 1 s = parser.parse(data) print s

直接運(yùn)行文件即可，得到的輸出如下，之后就可以根據(jù)線性代數(shù)的方法求解各個(gè)變量的值

([[-1.0, 2.4, 1.0, -0.0], [7.2, 9.0, -1.0, 1.0], [1.0, 1.0, -1.0, -8.0]], [’x’, ’y’, ’z’, 1])

總結(jié)

依托于python簡(jiǎn)潔的語(yǔ)法，ply為我們提供了一個(gè)強(qiáng)大的語(yǔ)法分析工具，更復(fù)雜的例子可以參考https://github.com/LiuRoy/proto_parser，這是我用ply實(shí)現(xiàn)的一個(gè)簡(jiǎn)單的protobuf解析器，用于減少頻繁的中間文件生成。有這種神器，一顆賽艇！

以上就是python開(kāi)發(fā)一個(gè)解析protobuf文件的簡(jiǎn)單編譯器的詳細(xì)內(nèi)容，更多關(guān)于python開(kāi)發(fā)編譯器的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！