譯自：https://ruslanspivak.com/lsbasi-part1/
（已獲作者授權）
“如果你不知道編譯器的作業方式，那么你將不知道計算機的作業方式，如果你不能100％確定是否知道編譯器的作業方式，那么你將不知道它們的作業方式，”
——史蒂夫·耶格
無論你是新手還是經驗豐富的軟體開發人員，如果你不知道編譯器和解釋器的作業方式，那么你也不知道計算機的作業方式，就是這么簡單，
那么，你知道編譯器和解釋器如何作業嗎？ 你是否100％確定知道它們的作業原理？ 如果沒有的話：
或者，如果你確實不知道，并且你為此感到不安的話：
別擔心，如果你堅持不懈地學習本系列文章，并與我一起實作解釋器和編譯器，你將最終了解它們是如何作業的，
你為什么要學習解釋器和編譯器？我會給你三個理由，
1、要撰寫解釋器或編譯器，你必須具有很多需要結合使用的技能，撰寫解釋器或編譯器將幫助你提高這些技能，并成為更好的軟體開發人員，同樣，你學到的技能對于撰寫任何軟體（不僅僅是解釋器或編譯器）都很有用，
2、你想知道計算機如何作業，通常解釋器和編譯器看起來像魔術，你不應該對這種魔術感到滿意，你想揭露實作解釋器和編譯器的程序的神秘性，了解它們的作業方式并控制一切，
3、你要創建自己的編程語言或特定于某一領域的語言(domain specific language)，如果創建一個，則你還需要為其創建解釋器或編譯器，最近，人們對新的編程語言重新產生了興趣，你幾乎可以每天看到一種新的編程語言：Elixir，Go和Rust等，
好的，但是解釋器和編譯器是什么？
解釋器或編譯器的目標是將某種高級語言的源程式轉換為其他形式，很模糊，不是嗎？請耐心等待，在本系列的后面部分，你將確切地了解源程式被翻譯成什么，
此時，你可能還想知道解釋器和編譯器之間的區別是什么，就本系列而言，如果我們將源程式翻譯成機器語言，則它是編譯器，如果我們在不先將其翻譯成機器語言的情況下處理和執行源程式，則它就是解釋器，看起來像這樣：
我希望到現在為止，你已經確信要學習并實作解釋器和編譯器，
你和我將為Pascal這門編程語言的大部分子集實作一個簡單的解釋器，在本系列的最后，你將擁有一個可運行的Pascal解釋器和一個源代碼除錯器，例如Python的pdb，
你可能會問，為什么是Pascal？一方面，這不是我在本系列中提出的一種組合語言：它是一種真正的編程語言，具有許多重要的語言構造(language constructs)，還有一些古老但有用的CS書籍在其示例中使用Pascal編程語言（我了解，這不是選擇我們選擇實作Pascal解釋器的主要理由，但我認為學習一門非主流(non-mainstream)的編程語言也是很好的:)
這是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.
我們這里將使用Python來實作Pascal解釋器，你也可以使用任何所需的語言，因為實作解釋器的思路并不局限于任何特定的編程語言，
好吧，讓我們開始吧，預備，準備，開始！
我們的首次嘗試是撰寫簡單的算術運算式(arithmetic expressions)解釋器（也稱為計算器），今天的目標很容易：使你的計算器能夠處理個位數字的加法，比如3+5， 這是你的解釋器的源代碼：
# Token types
#
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis
INTEGER, PLUS, EOF = 'INTEGER', 'PLUS', 'EOF'
class Token(object):
def __init__(self, type, value):
# token type: INTEGER, PLUS, or EOF
self.type = type
# token value: 0, 1, 2. 3, 4, 5, 6, 7, 8, 9, '+', or None
self.value = https://www.cnblogs.com/Xlgd/p/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=https://www.cnblogs.com/Xlgd/p/repr(self.value)
)
def __repr__(self):
return self.__str__()
class Interpreter(object):
def __init__(self, text):
# client string input, e.g. "3+5"
self.text = text
# self.pos is an index into self.text
self.pos = 0
# current token instance
self.current_token = None
def error(self):
raise Exception('Error parsing input')
def get_next_token(self):
"""Lexical analyzer (also known as scanner or tokenizer)
This method is responsible for breaking a sentence
apart into tokens. One token at a time.
"""
text = self.text
# is self.pos index past the end of the self.text ?
# if so, then return EOF token because there is no more
# input left to convert into tokens
if self.pos > len(text) - 1:
return Token(EOF, None)
# get a character at the position self.pos and decide
# what token to create based on the single character
current_char = text[self.pos]
# if the character is a digit then convert it to
# integer, create an INTEGER token, increment self.pos
# index to point to the next character after the digit,
# and return the INTEGER token
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):
# compare the current token type with the passed token
# type and if they match then "eat" the current token
# and assign the next token to the self.current_token,
# otherwise raise an exception.
if self.current_token.type == token_type:
self.current_token = self.get_next_token()
else:
self.error()
def expr(self):
"""expr -> INTEGER PLUS INTEGER"""
# set current token to the first token taken from the input
self.current_token = self.get_next_token()
# we expect the current token to be a single-digit integer
left = self.current_token
self.eat(INTEGER)
# we expect the current token to be a '+' token
op = self.current_token
self.eat(PLUS)
# we expect the current token to be a single-digit integer
right = self.current_token
self.eat(INTEGER)
# after the above call the self.current_token is set to
# EOF token
# at this point INTEGER PLUS INTEGER sequence of tokens
# has been successfully found and the method can just
# return the result of adding two integers, thus
# effectively interpreting client input
result = left.value + right.value
return result
def main():
while True:
try:
# To run under Python3 replace 'raw_input' call
# with '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，則需要用input來替換raw_input）：
$ python calc1.py
calc> 3+4
7
calc> 3+5
8
calc> 3+9
12
calc>
為了使你的簡單計算器正常作業而不會引發例外，你的輸入需要遵循某些規則：
1、輸入中僅允許一位數(single digit)的整數
2、目前唯一支持的算術運算是加法
3、輸入中的任何地方都不允許有空格
這些限制是使計算器簡單化所必需的，不用擔心，你很快就會使它變得非常復雜，
好的，現在讓我們深入了解一下解釋器的作業原理以及它如何計算算術運算式，
在命令列上輸入運算式3+5時，解釋器將獲得字串"3+5"，為了使解釋器真正理解如何處理該字串，首先需要將輸入"3+5"分解為Token，Token是具有型別(type)和值(value)的物件(object)，例如，對于字符"3"，Token的型別將是INTEGER，而對應的值將是整數3，
將輸入字串分解為Token的程序稱為詞法分析(lexical analysis)，因此，你的解釋器需要做的第一步是讀取字輸入字符并將其轉換為Token流，解釋器執行此操作的部分稱為詞法分析器(lexical analyzer)，簡稱lexer，你可能還會遇到其他的名稱，例如 scanner或者tokenizer，它們的含義都一樣：解釋器或編譯器中將字符輸入轉換為Token流的部分，
Interpreter類的get_next_token函式是詞法分析器，每次呼叫它時，都會從字符輸入中獲得下一個Token，讓我們仔細看看這個函式，看看它如何完成將字符轉換為Token，字符輸入存盤在text變數中，pos變數是該字符輸入的索引(index)（將字串視為字符陣列）， pos最初設定為0，并指向字符"3"，函式首先檢查字符是否為數字，如果是數字，則遞增pos并回傳型別為INTEGER、值為整數3的Token：
pos現在指向文本中的"+"字符，下次呼叫該函式時，它將測驗pos所指的字符是否為數字，然后測驗該字符是否為加號，然后該函式遞增pos并回傳一個新創建的Token，其型別為PLUS，值為"+"：
pos現在指向字符"5"，當再次呼叫get_next_token函式時，將檢查它是否為數字，以便遞增pos并回傳一個新的Token，其型別為INTEGER，值為5：
現在pos索引已超過字串"3+5"的末尾，如果再呼叫get_next_token函式的話，將回傳一個型別為EOF的Token：
試試看，親自看看計算器的詞法分析器如何作業：
>>> 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)
>>>
因此，既然解釋器現在可以訪問由輸入字符組成的Token流，那么解釋器就需要對其進行處理：它需要在從Token流中查找結構(structure)，解釋器希望在Token流中找到以下結構：
INTEGER-> PLUS-> INTEGER
也就是說，它嘗試查找Token序列：先是一個整數，后面跟加號，最后再跟一個整數，
負責查找和解釋該結構的函式為expr，它驗證Token序列是否與預期的Token序列相對應，即INTEGER-> PLUS-> INTEGER，成功確認結構后，它會通過將PLUS左右兩側的Token的值相加來生成結果，從而成功解釋了傳遞給解釋器的算術運算式，
expr函式本身使用輔助函式(helper method)eat來驗證傳遞給eat函式的Token型別是否與當前正在處理的Token型別一致(match)，在確保型別一致后，eat函式將獲取下一個Token并將其分配給current_token變數，從而有效地“消耗”已經驗證過的Token并在Token流中推進pos向前，如果Token流中的結構與預期的INTEGER PLUS INTEGER 序列不對應，那么eat函式將引發例外，
讓我們來回顧一下解釋器為決議算術運算式所做的事情：
1、解釋器接受輸入字串，例如"3+5"
2、解釋器呼叫expr函式以在詞法分析器get_next_token回傳的Token流中找到預期的結構，它嘗試查找的結構的形式為INTEGER PLUS INTEGER，查找到結構后，它就將輸入字符解釋為把兩個型別為INTEGER的Token的值加起來，也就是將兩個整數3和5相加，
恭喜你！剛剛學習了如何構實作你的第一個解釋器！
現在該做練習了：
1、修改代碼以允許輸入中包含多位數(multiple-digit)的整數，例如"12+3"
2、添加一種跳過空格的方法，以便計算器可以處理帶有"12 + 3"之類帶有空格的字符輸入
3、修改代碼，使計算器能夠處理減法，例如"7-5"
最后再來復習回憶一下：
1、什么是解釋器？
2、什么是編譯器？
3、解釋器和編譯器有什么區別？
4、什么是Token？
5、將輸入分解為Token的程序的名稱是什么？
6、解釋器中進行詞法分析的部分是什么？
今天到這就結束了，在下一篇文章中，我們將擴展計算器以處理更多的算術運算式，敬請關注，
PS：
這也是我第一次翻譯技術文章，如有錯誤和不恰當的地方，希望大家能及時批評指正，謝謝！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2084.html
標籤：其他
上一篇：論文翻譯：2000_wideband extension of telephone speech using a hidden Markov model
下一篇：實作一個簡單的解釋器（2）