讓我們做個簡單的解釋器(一)
就是這樣。想一想。你是萌新還是一個資深的軟體開發者實際上都無關緊要:如果你不知道 編譯器 和 解釋器 是怎麼工作的,那麼你就不知道電腦是怎麼工作的。就這麼簡單。
所以,你知道編譯器和解釋器是怎麼工作的嗎?我是說,你百分百確定自己知道他們怎麼工作嗎?如果不知道。
或者如果你不知道但你非常想要了解它。
不用擔心。如果你能堅持跟著這個系列做下去,和我一起構建一個解釋器和編譯器,最後你將會知道他們是怎麼工作的。並且你會變成一個自信滿滿的快樂的人。至少我希望如此。
為什麼要學習編譯器和解釋器?有三點理由。
- 要寫出一個解釋器或編譯器,你需要有很多的專業知識,並能融會貫通。寫一個解釋器或編譯器能幫你加強這些能力,成為一個更厲害的軟體開發者。而且,你要學的技能對編寫軟體非常有用,而不是僅僅局限於解釋器或編譯器。
- 你確實想要了解電腦是怎麼工作的。通常解釋器和編譯器看上去很魔幻。你或許不習慣這種魔力。你會想去揭開構建解釋器和編譯器那層神秘的面紗,了解它們的原理,把事情做好。
- 你想要創建自己的編程語言或者特定領域的語言。如果你創建了一個,你還要為它創建一個解釋器或者編譯器。最近,興起了對新的編程語言的興趣。你能看到幾乎每天都有一門新的編程語言橫空出世:Elixir,Go,Rust,還有很多。
好,但什麼是解釋器和編譯器?
解釋器 和 編譯器 的任務是把用高級語言寫的源程序翻譯成其他的格式。很奇怪,是不是?忍一忍,稍後你會在這個系列學到到底把源程序翻譯成什麼東西。
這時你可能會奇怪解釋器和編譯器之間有什麼區別。為了實現這個系列的目的,我們規定一下,如果有個翻譯器把源程序翻譯成機器語言,那它就是 編譯器。如果一個翻譯器可以處理並執行源程序,卻不用把它翻譯器機器語言,那它就是 解釋器。直觀上它看起來像這樣:
我希望你現在確信你很想學習構建一個編譯器和解釋器。你期望在這個教程里學習解釋器的哪些知識呢?
你看這樣如何。你和我一起為 Pascal 語言的一個大子集做一個簡單的解釋器。在這個系列結束的時候你能做出一個可以運行的 Pascal 解釋器和一個像 Python 的 pdb 那樣的源代碼級別的調試器。
你或許會問,為什麼是 Pascal?一方面,它不是我為了這個系列而提出的一個虛構的語言:它是真實存在的一門編程語言,有很多重要的語言結構。有些陳舊但有用的計算機書籍使用 Pascal 編程語言作為示例(我知道對於選擇一門語言來構建解釋器,這個理由並不令人信服,但我認為學一門非主流的語言也不錯 :))。
這有個 Pascal 中的階乘函數示例,你將能用自己的解釋器解釋代碼,還能夠用可交互的源碼級調試器進行調試,你可以這樣創造:
program factorial;
function factorial(n: integer): longint;
begin
if n = 0 then
factorial := 1
else
factorial := n * factorial(n - 1);
end;
var
n: integer;
begin
for n := 0 to 16 do
writeln(n, '! = ', factorial(n));
end.
這個 Pascal 解釋器的實現語言會使用 Python,但你也可以用其他任何語言,因為這裡展示的思想不依賴任何特殊的實現語言。好,讓我們開始幹活。準備好了,出發!
你會從編寫一個簡單的算術表達式解析器,也就是常說的計算器,開始學習解釋器和編譯器。今天的目標非常簡單:讓你的計算器能處理兩個個位數相加,比如 3+5
。下面是你的計算器的源代碼——不好意思,是解釋器:
# 標記類型
#
# EOF (end-of-file 文件末尾)標記是用來表示所有輸入都解析完成
INTEGER, PLUS, EOF = 'INTEGER', 'PLUS', 'EOF'
class Token(object):
def __init__(self, type, value):
# token 類型: INTEGER, PLUS, MINUS, or EOF
self.type = type
# token 值: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, '+', 或 None
self.value = value
def __str__(self):
"""String representation of the class instance.
Examples:
Token(INTEGER, 3)
Token(PLUS '+')
"""
return 'Token({type}, {value})'.format(
type=self.type,
value=repr(self.value)
)
def __repr__(self):
return self.__str__()
class Interpreter(object):
def __init__(self, text):
# 用戶輸入字元串, 例如 "3+5"
self.text = text
# self.pos 是 self.text 的索引
self.pos = 0
# 當前標記實例
self.current_token = None
def error(self):
raise Exception('Error parsing input')
def get_next_token(self):
"""詞法分析器(也說成掃描器或者標記器)
該方法負責把一個句子分成若干個標記。每次處理一個標記
"""
text = self.text
# self.pos 索引到達了 self.text 的末尾嗎?
# 如果到了,就返回 EOF 標記,因為沒有更多的
# 能轉換成標記的輸入了
if self.pos > len(text) - 1:
return Token(EOF, None)
# 從 self.pos 位置獲取當前的字元,
# 基於單個字元判斷要生成哪種標記
current_char = text[self.pos]
# 如果字元是一個數字,就把他轉換成一個整數,生成一個 INTEGER # 標記,累加 self.pos 索引,指向數字後面的下一個字元,
# 並返回 INTEGER 標記
if current_char.isdigit():
token = Token(INTEGER, int(current_char))
self.pos += 1
return token
if current_char == '+':
token = Token(PLUS, current_char)
self.pos += 1
return token
self.error()
def eat(self, token_type):
# 將當前的標記類型與傳入的標記類型作比較,如果他們相匹配,就
# 「eat」 掉當前的標記並將下一個標記賦給 self.current_token,
# 否則拋出一個異常
if self.current_token.type == token_type:
self.current_token = self.get_next_token()
else:
self.error()
def expr(self):
"""expr -> INTEGER PLUS INTEGER"""
# 將輸入中的第一個標記設置成當前標記
self.current_token = self.get_next_token()
# 我們期望當前標記是個位數。
left = self.current_token
self.eat(INTEGER)
# 期望當前標記是 『+』 號
op = self.current_token
self.eat(PLUS)
# 我們期望當前標記是個位數。
right = self.current_token
self.eat(INTEGER)
# 上述操作完成後,self.current_token 被設成 EOF 標記
# 這時成功找到 INTEGER PLUS INTEGER 標記序列
# 這個方法就可以返回兩個整數相加的結果了,
# 即高效的解釋了用戶輸入
result = left.value + right.value
return result
def main():
while True:
try:
# 要在 Python3 下運行,請把 『raw_input』 換成 『input』
text = raw_input('calc> ')
except EOFError:
break
if not text:
continue
interpreter = Interpreter(text)
result = interpreter.expr()
print(result)
if __name__ == '__main__':
main()
把上面的代碼保存到 calc1.py
文件,或者直接從 GitHub 上下載。在你深入研究代碼前,在命令行裡面運行它看看效果。試一試!這是我筆記本上的示例會話(如果你想在 Python3 下運行,你要把 raw_input
換成 input
):
$ python calc1.py
calc> 3+4
7
calc> 3+5
8
calc> 3+9
12
calc>
要讓你的簡易計算器正常工作,不拋出異常,你的輸入要遵守以下幾個規則:
- 只允許輸入個位數
- 此時支持的唯一一個運算符是加法
- 輸入中不允許有任何的空格符號
要讓計算器變得簡單,這些限制非常必要。不用擔心,你很快就會讓它變得很複雜。
好,現在讓我們深入它,看看解釋器是怎麼工作,它是怎麼評估出算術表達式的。
當你在命令行中輸入一個表達式 3+5
,解釋器就獲得了字元串 「3+5」。為了讓解釋器能夠真正理解要用這個字元串做什麼,它首先要把輸入 「3+5」 分到叫做 token
(標記)的容器里。 標記 是一個擁有類型和值的對象。比如說,對字元 「3」 而言,標記的類型是 INTEGER 整數,對應的值是 3。
把輸入字元串分成標記的過程叫 詞法分析 。因此解釋器的需要做的第一步是讀取輸入字元,並將其轉換成標記流。解釋器中的這一部分叫做 詞法分析器 ,或者簡短點叫 lexer。你也可以給它起別的名字,諸如 掃描器 或者 標記器 。它們指的都是同一個東西:解釋器或編譯器中將輸入字元轉換成標記流的那部分。
Interpreter
類中的 get_next_token
方法就是詞法分析器。每次調用它的時候,你都能從傳入解釋器的輸入字元中獲得創建的下一個標記。仔細看看這個方法,看看它是如何完成把字元轉換成標記的任務的。輸入被存在可變文本中,它保存了輸入的字元串和關於該字元串的索引(把字元串想像成字元數組)。pos
開始時設為 0,指向字元 『3』。這個方法一開始檢查字元是不是數字,如果是,就將 pos
加 1,並返回一個 INTEGER 類型的標記實例,並把字元 『3』 的值設為整數,也就是整數 3:
現在 pos
指向文本中的 『+』 號。下次調用這個方法的時候,它會測試 pos
位置的字元是不是個數字,然後檢測下一個字元是不是個加號,就是這樣。結果這個方法把 pos
加 1,返回一個新創建的標記,類型是 PLUS,值為 『+』。
pos
現在指向字元 『5』。當你再調用 get_next_token
方法時,該方法會檢查這是不是個數字,就是這樣,然後它把 pos
加 1,返回一個新的 INTEGER 標記,該標記的值被設為整數 5:
因為 pos
索引現在到了字元串 「3+5」 的末尾,你每次調用 get_next_token
方法時,它將會返回 EOF 標記:
自己試一試,看看計算器里的詞法分析器的運行:
>>> from calc1 import Interpreter
>>>
>>> interpreter = Interpreter('3+5')
>>> interpreter.get_next_token()
Token(INTEGER, 3)
>>>
>>> interpreter.get_next_token()
Token(PLUS, '+')
>>>
>>> interpreter.get_next_token()
Token(INTEGER, 5)
>>>
>>> interpreter.get_next_token()
Token(EOF, None)
>>>
既然你的解釋器能夠從輸入字元中獲取標記流,解釋器需要對它做點什麼:它需要在詞法分析器 get_next_token
中獲取的標記流中找出相應的結構。你的解釋器應該能夠找到流中的結構:INTEGER -> PLUS -> INTEGER。就是這樣,它嘗試找出標記的序列:整數後面要跟著加號,加號後面要跟著整數。
負責找出並解釋結構的方法就是 expr
。該方法檢驗標記序列確實與期望的標記序列是對應的,比如 INTEGER -> PLUS -> INTEGER。成功確認了這個結構後,就會生成加號左右兩邊的標記的值相加的結果,這樣就成功解釋你輸入到解釋器中的算術表達式了。
expr
方法用了一個助手方法 eat
來檢驗傳入的標記類型是否與當前的標記類型相匹配。在匹配到傳入的標記類型後,eat
方法會獲取下一個標記,並將其賦給 current_token
變數,然後高效地 「吃掉」 當前匹配的標記,並將標記流的虛擬指針向後移動。如果標記流的結構與期望的 INTEGER -> PLUS -> INTEGER 標記序列不對應,eat
方法就拋出一個異常。
讓我們回顧下解釋器做了什麼來對算術表達式進行評估的:
- 解釋器接受輸入字元串,比如說 「3+5」
- 解釋器調用
expr
方法,在詞法分析器get_next_token
返回的標記流中找出結構。這個結構就是 INTEGER -> PLUS -> INTEGER 這樣的格式。在確認了格式後,它就通過把兩個整型標記相加來解釋輸入,因為此時對於解釋器來說很清楚,它要做的就是把兩個整數 3 和 5 進行相加。
恭喜。你剛剛學習了怎麼構建自己的第一個解釋器!
現在是時候做練習了。
看了這篇文章,你肯定覺得不夠,是嗎?好,準備好做這些練習:
- 修改代碼,允許輸入多位數,比如 「12+3」
- 添加一個方法忽略空格符,讓你的計算器能夠處理帶有空白的輸入,比如 「12 + 3」
- 修改代碼,用 『-』 號而非 『+』 號去執行減法比如 「7-5」
檢驗你的理解
- 什麼是解釋器?
- 什麼是編譯器
- 解釋器和編譯器有什麼差別?
- 什麼是標記?
- 將輸入分隔成若干個標記的過程叫什麼?
- 解釋器中進行詞法分析的部分叫什麼?
- 解釋器或編譯器中進行詞法分析的部分有哪些其他的常見名字?
在結束本文前,我衷心希望你能留下學習解釋器和編譯器的承諾。並且現在就開始做。不要把它留到以後。不要拖延。如果你已經看完了本文,就開始吧。如果已經仔細看完了但是還沒做什麼練習 —— 現在就開始做吧。如果已經開始做練習了,那就把剩下的做完。你懂得。而且你知道嗎?簽下承諾書,今天就開始學習解釋器和編譯器!
本人, __,身體健全,思想正常,在此承諾從今天開始學習解釋器和編譯器,直到我百分百了解它們是怎麼工作的!
簽字人:
日期:
簽字,寫上日期,把它放在你每天都能看到的地方,確保你能堅守承諾。謹記你的承諾:
「承諾就是,你說自己會去做的事,在你說完就一直陪著你的東西。」 —— Darren Hardy
好,今天的就結束了。這個系列的下一篇文章里,你將會擴展自己的計算器,讓它能夠處理更複雜的算術表達式。敬請期待。
via: https://ruslanspivak.com/lsbasi-part1/
作者:Ruslan Spivak 譯者:BriFuture 校對:wxy
本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive