使用Python編寫一個最基礎的代碼解釋器的要點解析
一直以來都對編譯器和解析器有著很大的興趣，也很清楚一個編譯器的概念和整體的框架，但是對于細節(jié)部分卻不是很了解。我們編寫的程序源代碼實際上就是一串字符序列，編譯器或者解釋器可以直接理解并執(zhí)行這個字符序列，這看起來實在是太奇妙了。本文會用Python實現(xiàn)一個簡單的解析器，用于解釋一種小的列表操作語言（類似于python的list）。其實編譯器、解釋器并不神秘，只要對基本的理論理解之后，實現(xiàn)起來也比較簡單（當然，一個產(chǎn)品級的編譯器或解釋器還是很復雜的）。
這種列表語言支持的操作：
veca = [1, 2, 3] # 列表聲明 vecb = [4, 5, 6] print 'veca:', veca # 打印字符串、列表，print expr+ print 'veca * 2:', veca * 2 # 列表與整數(shù)乘法 print 'veca + 2:', veca + 2 # 列表與整數(shù)加法 print 'veca + vecb:', veca + vecb # 列表加法 print 'veca + [11, 12]:', veca + [11, 12] print 'veca * vecb:', veca * vecb # 列表乘法 print 'veca:', veca print 'vecb:', vecb
對應輸出：
veca: [1, 2, 3] veca * 2: [2, 4, 6] veca + 2: [1, 2, 3, 2] veca + vecb: [1, 2, 3, 2, 4, 5, 6] veca + [11, 12]: [1, 2, 3, 2, 11, 12] veca * vecb: [4, 5, 6, 8, 10, 12, 12, 15, 18, 8, 10, 12] veca: [1, 2, 3, 2] vecb: [4, 5, 6]
編譯器和解釋器在處理輸入字符流時，基本上和人理解句子的方式是一致的。比如：
I love you.
如果初學英語，首先需要知道各個單詞的意思，然后分析各個單詞的詞性，符合主-謂-賓的結構，這樣才能理解這句話的意思。這句話就是一個字符序列，按照詞法劃分就得到了一個詞法單元流，實際上這就是詞法分析，完成從字符流到詞法單元流的轉(zhuǎn)化。分析詞性，確定主謂賓結構，是按照英語的語法識別出這個結構，這就是語法分析，根據(jù)輸入的詞法單元流識別出語法解析樹。最后，再結合單詞的意思和語法結構最后得出這句話的意思，這就是語義分析。編譯器和解釋器處理過程類似，但是要略微復雜一些，這里只關注解釋器：
我們只是實現(xiàn)一個很簡單的小語言，所以不涉及到語法樹的生成，以及后續(xù)復雜的語義分析。下面我就來看看詞法分析和語法分析。
詞法分析和語法分析分別由詞法解析器和語法解析器完成。這兩種解析器具有類似的結構和功能，它們都是以一個輸入序列為輸入，然后識別出特定的結構。詞法解析器從源代碼字符流中解析出一個一個的token（詞法單元），而語法解析器識別出子結構和詞法單元，然后進行一些處理。可以通過LL(1)遞歸下降解析器實現(xiàn)這兩種解析器，這類解析器完成的步驟是：預測子句的類型，調(diào)用解析函數(shù)匹配該子結構、匹配詞法單元，然后按照需要插入代碼，執(zhí)行自定義操作。
這里對LL(1)做簡要介紹，語句的結構通常用樹型結構表示，稱為解析樹，LL(1)做語法解析就依賴于解析樹。比如：x = x +2;
在這棵樹中，像x、=和2這樣的葉節(jié)點，稱為終結節(jié)點，其他的叫做非終結節(jié)點。LL(1)解析時，不需要創(chuàng)建具體的樹型數(shù)據(jù)結構，可以為每個非終結節(jié)點編寫解析函數(shù)，在遇到相應節(jié)點時進行調(diào)用，這樣就可以通過解析函數(shù)的調(diào)用序列中（相當于樹的遍歷）獲得解析樹的信息。在LL(1)解析時，是按照從根節(jié)點到葉節(jié)點的順序執(zhí)行的，所以這是一個“下降”的過程，而解析函數(shù)又可以調(diào)用自身，所以是“遞歸”的，因此LL(1)又叫做遞歸下降解析器。
LL(1)中兩個L都是left-to-right的意思，第一個L表示解析器按從左到右的順序解析輸入內(nèi)容，第二個L表示在下降過程中，也是按照從左到右的順序遍歷子節(jié)點，而1表示根據(jù)1個向前看單元做預測。
下面看一下列表小語言的實現(xiàn)，首先是語言的文法，文法用于描述一個語言，算是解析器的設計說明書。
statlist: stat+
stat: ID '=' expr
| 'print' expr (, expr)*
expr: multipart ('+' multipart)*
| STR
multipart: primary ('*' primary)*
primary: INT
| ID
| '[' expr (',', expr)* ']'
INT: (1..9)(0..9)*
ID: (a..z | A..Z)*
STR: (\".*\") | (\'.*\')
這是用DSL描述的文法，其中大部分概念和正則表達式類似。"a|b"表示a或者b，所有以單引號括起的字符串是關鍵字，比如：print，=等。大寫的單詞是詞法單元?？梢钥吹竭@個小語言的文法還是很簡單的。有很多解析器生成器可以自動根據(jù)文法生成對應的解析器，比如：ANTRL，flex，yacc等，這里采用手寫解析器主要是為了理解解析器的原理。下面看一下這個小語言的解釋器是如何實現(xiàn)的。
首先是詞法解析器，完成字符流到token流的轉(zhuǎn)換。采用LL(1)實現(xiàn)，所以使用1個向前看字符預測匹配的token。對于像INT、ID這樣由多個字符組成的詞法規(guī)則，解析器有一個與之對應的方法。由于語法解析器并不關心空白字符，所以詞法解析器在遇到空白字符時直接忽略掉。每個token都有兩個屬性類型和值，比如整型、標識符類型等，對于整型類型它的值就是該整數(shù)。語法解析器需要根據(jù)token的類型進行預測，所以詞法解析必須返回類型信息。語法解析器以iterator的方式獲取token，所以詞法解析器實現(xiàn)了next_token方法，以元組方式(type, value)返回下一個token，在沒有token的情況時返回EOF。
'''''
A simple lexer of a small vector language.
statlist: stat+
stat: ID '=' expr
| 'print' expr (, expr)*
expr: multipart ('+' multipart)*
| STR
multipart: primary ('*' primary)*
primary: INT
| ID
| '[' expr (',', expr)* ']'
INT: (1..9)(0..9)*
ID: (a..z | A..Z)*
STR: (\".*\") | (\'.*\')
Created on 2012-9-26
@author: bjzllou
'''
EOF = -1
# token type
COMMA = 'COMMA'
EQUAL = 'EQUAL'
LBRACK = 'LBRACK'
RBRACK = 'RBRACK'
TIMES = 'TIMES'
ADD = 'ADD'
PRINT = 'print'
ID = 'ID'
INT = 'INT'
STR = 'STR'
class Veclexer:
'''''
LL(1) lexer.
It uses only one lookahead char to determine which is next token.
For each non-terminal token, it has a rule to handle it.
LL(1) is a quit weak parser, it isn't appropriate for the grammar which is
left-recursive or ambiguity. For example, the rule 'T: T r' is left recursive.
However, it's rather simple and has high performance, and fits simple grammar.
'''
def __init__(self, input):
self.input = input
# current index of the input stream.
self.idx = 1
# lookahead char.
self.cur_c = input[0]
def next_token(self):
while self.cur_c != EOF:
c = self.cur_c
if c.isspace():
self.consume()
elif c == '[':
self.consume()
return (LBRACK, c)
elif c == ']':
self.consume()
return (RBRACK, c)
elif c == ',':
self.consume()
return (COMMA, c)
elif c == '=':
self.consume()
return (EQUAL, c)
elif c == '*':
self.consume()
return (TIMES, c)
elif c == '+':
self.consume()
return (ADD, c)
elif c == '\'' or c == '"':
return self._string()
elif c.isdigit():
return self._int()
elif c.isalpha():
t = self._print()
return t if t else self._id()
else:
raise Exception('not support token')
return (EOF, 'EOF')
def has_next(self):
return self.cur_c != EOF
def _id(self):
n = self.cur_c
self.consume()
while self.cur_c.isalpha():
n += self.cur_c
self.consume()
return (ID, n)
def _int(self):
n = self.cur_c
self.consume()
while self.cur_c.isdigit():
n += self.cur_c
self.consume()
return (INT, int(n))
def _print(self):
n = self.input[self.idx - 1 : self.idx + 4]
if n == 'print':
self.idx += 4
self.cur_c = self.input[self.idx]
return (PRINT, n)
return None
def _string(self):
quotes_type = self.cur_c
self.consume()
s = ''
while self.cur_c != '\n' and self.cur_c != quotes_type:
s += self.cur_c
self.consume()
if self.cur_c != quotes_type:
raise Exception('string quotes is not matched. excepted %s' % quotes_type)
self.consume()
return (STR, s)
def consume(self):
if self.idx >= len(self.input):
self.cur_c = EOF
return
self.cur_c = self.input[self.idx]
self.idx += 1
if __name__ == '__main__':
exp = '''''
veca = [1, 2, 3]
print 'veca:', veca
print 'veca * 2:', veca * 2
print 'veca + 2:', veca + 2
'''
lex = Veclexer(exp)
t = lex.next_token()
while t[0] != EOF:
print t
t = lex.next_token()
運行這個程序，可以得到源代碼：
veca = [1, 2, 3] print 'veca:', veca print 'veca * 2:', veca * 2 print 'veca + 2:', veca + 2
對應的token序列：
('ID', 'veca')
('EQUAL', '=')
('LBRACK', '[')
('INT', 1)
('COMMA', ',')
('INT', 2)
('COMMA', ',')
('INT', 3)
('RBRACK', ']')
('print', 'print')
('STR', 'veca:')
('COMMA', ',')
('ID', 'veca')
('print', 'print')
('STR', 'veca * 2:')
('COMMA', ',')
('ID', 'veca')
('TIMES', '*')
('INT', 2)
('print', 'print')
('STR', 'veca + 2:')
('COMMA', ',')
('ID', 'veca')
('ADD', '+')
('INT', 2)
接下來看一下語法解析器的實現(xiàn)。語法解析器的的輸入是token流，根據(jù)一個向前看詞法單元預測匹配的規(guī)則。對于每個遇到的非終結符調(diào)用對應的解析函數(shù)，而終結符（token）則match掉，如果不匹配則表示有語法錯誤。由于都是使用的LL(1)，所以和詞法解析器類似， 這里不再贅述。
'''''
A simple parser of a small vector language.
statlist: stat+
stat: ID '=' expr
| 'print' expr (, expr)*
expr: multipart ('+' multipart)*
| STR
multipart: primary ('*' primary)*
primary: INT
| ID
| '[' expr (',', expr)* ']'
INT: (1..9)(0..9)*
ID: (a..z | A..Z)*
STR: (\".*\") | (\'.*\')
example:
veca = [1, 2, 3]
vecb = veca + 4 # vecb: [1, 2, 3, 4]
vecc = veca * 3 # vecc:
Created on 2012-9-26
@author: bjzllou
'''
import veclexer
class Vecparser:
'''''
LL(1) parser.
'''
def __init__(self, lexer):
self.lexer = lexer
# lookahead token. Based on the lookahead token to choose the parse option.
self.cur_token = lexer.next_token()
# similar to symbol table, here it's only used to store variables' value
self.symtab = {}
def statlist(self):
while self.lexer.has_next():
self.stat()
def stat(self):
token_type, token_val = self.cur_token
# Asignment
if token_type == veclexer.ID:
self.consume()
# For the terminal token, it only needs to match and consume.
# If it's not matched, it means that is a syntax error.
self.match(veclexer.EQUAL)
# Store the value to symbol table.
self.symtab[token_val] = self.expr()
# print statement
elif token_type == veclexer.PRINT:
self.consume()
v = str(self.expr())
while self.cur_token[0] == veclexer.COMMA:
self.match(veclexer.COMMA)
v += ' ' + str(self.expr())
print v
else:
raise Exception('not support token %s', token_type)
def expr(self):
token_type, token_val = self.cur_token
if token_type == veclexer.STR:
self.consume()
return token_val
else:
v = self.multipart()
while self.cur_token[0] == veclexer.ADD:
self.consume()
v1 = self.multipart()
if type(v1) == int:
v.append(v1)
elif type(v1) == list:
v = v + v1
return v
def multipart(self):
v = self.primary()
while self.cur_token[0] == veclexer.TIMES:
self.consume()
v1 = self.primary()
if type(v1) == int:
v = [x*v1 for x in v]
elif type(v1) == list:
v = [x*y for x in v for y in v1]
return v
def primary(self):
token_type = self.cur_token[0]
token_val = self.cur_token[1]
# int
if token_type == veclexer.INT:
self.consume()
return token_val
# variables reference
elif token_type == veclexer.ID:
self.consume()
if token_val in self.symtab:
return self.symtab[token_val]
else:
raise Exception('undefined variable %s' % token_val)
# parse list
elif token_type == veclexer.LBRACK:
self.match(veclexer.LBRACK)
v = [self.expr()]
while self.cur_token[0] == veclexer.COMMA:
self.match(veclexer.COMMA)
v.append(self.expr())
self.match(veclexer.RBRACK)
return v
def consume(self):
self.cur_token = self.lexer.next_token()
def match(self, token_type):
if self.cur_token[0] == token_type:
self.consume()
return True
raise Exception('expecting %s; found %s' % (token_type, self.cur_token[0]))
if __name__ == '__main__':
prog = '''''
veca = [1, 2, 3]
vecb = [4, 5, 6]
print 'veca:', veca
print 'veca * 2:', veca * 2
print 'veca + 2:', veca + 2
print 'veca + vecb:', veca + vecb
print 'veca + [11, 12]:', veca + [11, 12]
print 'veca * vecb:', veca * vecb
print 'veca:', veca
print 'vecb:', vecb
'''
lex = veclexer.Veclexer(prog)
parser = Vecparser(lex)
parser.statlist()
運行代碼便會得到之前介紹中的輸出內(nèi)容。這個解釋器極其簡陋，只實現(xiàn)了基本的表達式操作，所以不需要構建語法樹。如果要為列表語言添加控制結構，就必須實現(xiàn)語法樹，在語法樹的基礎上去解釋執(zhí)行。
相關文章
這篇文章主要介紹了淺談django channels 路由誤導，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
這篇文章主要介紹了pytorch_detach 切斷網(wǎng)絡反傳方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-05-05
python Web開發(fā)你要理解的WSGI & uwsgi詳解
這篇文章主要給大家介紹了關于python Web開發(fā)你一定要理解的WSGI & uwsgi的相關資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面隨著小編來一起學習學習吧2018-08-08
本篇文章主要介紹了Python爬蟲中urllib庫的進階學習內(nèi)容，對此有興趣的朋友趕緊學習分享下。2018-01-01
python標準庫壓縮包模塊zipfile和tarfile詳解(常用標準庫)
在我們常用的系統(tǒng)windows和Linux系統(tǒng)中有很多支持的壓縮包格式，包括但不限于以下種類：rar、zip、tar，這篇文章主要介紹了python標準庫壓縮包模塊zipfile和tarfile詳解(常用標準庫),需要的朋友可以參考下2022-06-06
這篇文章主要介紹了Python 流媒體播放器的實現(xiàn)(基于VLC),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
解析Mac OS下部署Pyhton的Django框架項目的過程
這篇文章主要介紹了Mac OS下部署Pyhton的Django框架項目的過程,還附帶將了一個gunicorn結合Nginx來部署Django應用的方法,需要的朋友可以參考下2016-05-05
python雙向鏈表和單鏈表類似，只不過是增加了一個指向前面一個元素的指針,下面的代碼實例了python雙向鏈表的方法2013-11-11
這篇文章主要為大家詳細介紹了python微信好友數(shù)據(jù)分析，實現(xiàn)對微信好友的獲取，并對省份、性別等數(shù)據(jù)分析，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-11-11
這篇文章主要為大家介紹了加速Python代碼執(zhí)行的利器使用實例探究,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2024-01-01