使用 Python 開發(fā)一個(gè) Python 解釋器
計(jì)算機(jī)只能理解機(jī)器碼。歸根結(jié)底，編程語言只是一串文字，目的是為了讓人類更容易編寫他們想讓計(jì)算機(jī)做的事情。真正的魔法是由編譯器和解釋器完成，它們彌合了兩者之間的差距。解釋器逐行讀取代碼并將其轉(zhuǎn)換為機(jī)器碼。
在本文中，我們將設(shè)計(jì)一個(gè)可以執(zhí)行算術(shù)運(yùn)算的解釋器。
我們不會(huì)重新造輪子。文章將使用由 David M. Beazley 開發(fā)的詞法解析器 —— PLY（Python Lex-Yacc(https://github.com/dabeaz/ply)）。
PLY 可以通過以下方式下載：
- $ pip install ply
我們將粗略地瀏覽一下創(chuàng)建解釋器所需的基礎(chǔ)知識(shí)。欲了解更多，請(qǐng)參閱這個(gè) GitHub 倉(cāng)庫(https://github.com/dabeaz/ply)。
標(biāo)記（Token）
標(biāo)記是為解釋器提供有意義信息的最小字符單位。標(biāo)記包含一對(duì)名稱和屬性值。
讓我們從創(chuàng)建標(biāo)記名稱列表開始。這是一個(gè)必要的步驟。
- tokens = (
- # 數(shù)據(jù)類型
- "NUM",
- "FLOAT",
- # 算術(shù)運(yùn)算
- "PLUS",
- "MINUS",
- "MUL",
- "DIV",
- # 括號(hào)
- "LPAREN",
- "RPAREN",
- )
詞法分析器（Lexer）
將語句轉(zhuǎn)換為標(biāo)記的過程稱為標(biāo)記化或詞法分析。執(zhí)行詞法分析的程序是詞法分析器。
- # 標(biāo)記的正則表達(dá)
- t_PLUS = r"\+"
- t_MINUS = r"\-"
- t_MUL = r"\*"
- t_DIV = r"/"
- t_LPAREN = r"\("
- t_RPAREN = r"\)"
- t_POW = r"\^"
- # 忽略空格和制表符
- t_ignore = " \t"
- # 為每個(gè)規(guī)則添加動(dòng)作
- def t_FLOAT(t):
- r"""\d+\.\d+"""
- t.value = float(t.value)
- return t
- def t_NUM(t):
- r"""\d+"""
- t.value = int(t.value)
- return t
- # 未定義規(guī)則字符的錯(cuò)誤處理
- def t_error(t):
- # 此處的 t.value 包含未標(biāo)記的其余輸入
- print(f"keyword not found: {t.value[0]}\nline {t.lineno}")
- t.lexer.skip(1)
- # 如果遇到 \n 則將其設(shè)為新的一行
- def t_newline(t):
- r"""\n+"""
- t.lexer.lineno += t.value.count("\n")
為導(dǎo)入詞法分析器，我們將使用：
import ply.lex as lex
t_ 是一個(gè)特殊的前綴，表示定義標(biāo)記的規(guī)則。每條詞法規(guī)則都是用正則表達(dá)式制作的，與 Python 中的 re 模塊兼容。正則表達(dá)式能夠根據(jù)規(guī)則掃描輸入并搜索符合的符號(hào)串。正則表達(dá)式定義的文法稱為正則文法。正則文法定義的語言則稱為正則語言。
定義好了規(guī)則，我們將構(gòu)建詞法分析器。
- data = 'a = 2 +(10 -8)/1.0'
- lexlexer = lex.lex()
- lexer.input(data)
- while tok := lexer.token():
- print(tok)
為了傳遞輸入字符串，我們使用 lexer.input(data)。lexer.token() 將返回下一個(gè) LexToken 實(shí)例，最后返回 None。根據(jù)上述規(guī)則，代碼 2 + ( 10 -8)/1.0 的標(biāo)記將是：
紫色字符代表的是標(biāo)記的名稱，其后是標(biāo)記的具體內(nèi)容。
巴科斯-諾爾范式（Backus-Naur Form，BNF）
大多數(shù)編程語言都可以用上下文無關(guān)文法來編寫。它比常規(guī)語言更復(fù)雜。對(duì)于上下文無關(guān)文法，我們用上下文無關(guān)語法，它是描述語言中所有可能語法的規(guī)則集。BNF 是一種定義語法的方式，它描述了編程語言的語法。讓我們看看例子：
symbol : alternative1 | alternative2 …
根據(jù)產(chǎn)生式，: 的左側(cè)被替換為右側(cè)的其中一個(gè)值替換。右側(cè)的值由 | 分隔（可理解為 symbol 定義為 alternative1 或 alternative2或…… 等等）。對(duì)于我們的這個(gè)算術(shù)解釋器，語法規(guī)格如下：
- expression : expression '+' expression
- | expression '-' expression
- | expression '/' expression
- | expression '*' expression
- | expression '^' expression
- | +expression
- | -expression
- | ( expression )
- | NUM
- | FLOAT
輸入的標(biāo)記是諸如 NUM、FLOAT、+、-、*、/ 之類的符號(hào)，稱作終端（無法繼續(xù)分解或產(chǎn)生其他符號(hào)的字符）。一個(gè)表達(dá)式由終端和規(guī)則集組成，例如 expression 則稱為非終端。
解析器（Parser）
我們將使用 YACC（Yet Another Compiler Compiler） 作為解析器生成器。導(dǎo)入模塊：import ply.yacc as yacc。
- from operator import (add, sub, mul, truediv, pow)
- # 我們的解釋器支持的運(yùn)算符列表
- ops = {
- "+": add,
- "-": sub,
- "*": mul,
- "/": truediv,
- "^": pow,
- }
- def p_expression(p):
- """expression : expression PLUS expression
- | expression MINUS expression
- | expression DIV expression
- | expression MUL expression
- | expression POW expression"""
- if (p[2], p[3]) == ("/", 0):
- # 如果除以 0，則將“INF”（無限）作為值
- p[0] = float("INF")
- else:
- p[0] = ops[p[2]](p[1], p[3])
- def p_expression_uplus_or_expr(p):
- """expression : PLUS expression %prec UPLUS
- | LPAREN expression RPAREN"""
- p[0] = p[2]
- def p_expression_uminus(p):
- """expression : MINUS expression %prec UMINUS"""
- p[0] = -p[2]
- def p_expression_num(p):
- """expression : NUM
- | FLOAT"""
- p[0] = p[1]
- # 語法錯(cuò)誤時(shí)的規(guī)則
- def p_error(p):
- print(f"Syntax error in {p.value}")
在文檔字符串中，我們將添加適當(dāng)?shù)恼Z法規(guī)范。p 列表中的的元素與語法符號(hào)一一對(duì)應(yīng)，如下所示：
- expression : expression PLUS expression
- p[0] p[1] p[2] p[3]
在上文中，%prec UPLUS 和 %prec UMINUS 是用來表示自定義運(yùn)算的。%prec 即是 precedence 的縮寫。在符號(hào)中本來沒有 UPLUS 和 UMINUS 這個(gè)說法（在本文中這兩個(gè)自定義運(yùn)算表示一元正號(hào)和符號(hào)，其實(shí) UPLUS 和 UMINUS 只是個(gè)名字，想取什么就取什么）。之后，我們可以添加基于表達(dá)式的規(guī)則。YACC 允許為每個(gè)令牌分配優(yōu)先級(jí)。我們可以使用以下方法設(shè)置它：
- precedence = (
- ("left", "PLUS", "MINUS"),
- ("left", "MUL", "DIV"),
- ("left", "POW"),
- ("right", "UPLUS", "UMINUS")
- )
在優(yōu)先級(jí)聲明中，標(biāo)記按優(yōu)先級(jí)從低到高的順序排列。PLUS 和 MINUS 優(yōu)先級(jí)相同并且具有左結(jié)合性（運(yùn)算從左至右執(zhí)行）。MUL 和 DIV 的優(yōu)先級(jí)高于 PLUS 和 MINUS，也具有左結(jié)合性。POW 亦是如此，不過優(yōu)先級(jí)更高。UPLUS 和 UMINUS 則是具有右結(jié)合性（運(yùn)算從右至左執(zhí)行）。
要解析輸入我們將使用：
- parser = yacc.yacc()
- result = parser.parse(data)
- print(result)
完整代碼如下：
- #####################################
- # 引入模塊 #
- #####################################
- from logging import (basicConfig, INFO, getLogger)
- from operator import (add, sub, mul, truediv, pow)
- import ply.lex as lex
- import ply.yacc as yacc
- # 我們的解釋器支持的運(yùn)算符列表
- ops = {
- "+": add,
- "-": sub,
- "*": mul,
- "/": truediv,
- "^": pow,
- }
- #####################################
- # 標(biāo)記集 #
- #####################################
- tokens = (
- # 數(shù)據(jù)類型
- "NUM",
- "FLOAT",
- # 算術(shù)運(yùn)算
- "PLUS",
- "MINUS",
- "MUL",
- "DIV",
- "POW",
- # 括號(hào)
- "LPAREN",
- "RPAREN",
- )
- #####################################
- # 標(biāo)記的正則表達(dá)式 #
- #####################################
- t_PLUS = r"\+"
- t_MINUS = r"\-"
- t_MUL = r"\*"
- t_DIV = r"/"
- t_LPAREN = r"\("
- t_RPAREN = r"\)"
- t_POW = r"\^"
- # 忽略空格和制表符
- t_ignore = " \t"
- # 為每個(gè)規(guī)則添加動(dòng)作
- def t_FLOAT(t):
- r"""\d+\.\d+"""
- t.value = float(t.value)
- return t
- def t_NUM(t):
- r"""\d+"""
- t.value = int(t.value)
- return t
- # 未定義規(guī)則字符的錯(cuò)誤處理
- def t_error(t):
- # 此處的 t.value 包含未標(biāo)記的其余輸入
- print(f"keyword not found: {t.value[0]}\nline {t.lineno}")
- t.lexer.skip(1)
- # 如果看到 \n 則將其設(shè)為新的一行
- def t_newline(t):
- r"""\n+"""
- t.lexer.lineno += t.value.count("\n")
- #####################################
- # 設(shè)置符號(hào)優(yōu)先級(jí) #
- #####################################
- precedence = (
- ("left", "PLUS", "MINUS"),
- ("left", "MUL", "DIV"),
- ("left", "POW"),
- ("right", "UPLUS", "UMINUS")
- )
- #####################################
- # 書寫 BNF 規(guī)則 #
- #####################################
- def p_expression(p):
- """expression : expression PLUS expression
- | expression MINUS expression
- | expression DIV expression
- | expression MUL expression
- | expression POW expression"""
- if (p[2], p[3]) == ("/", 0):
- # 如果除以 0，則將“INF”（無限）作為值
- p[0] = float("INF")
- else:
- p[0] = ops[p[2]](p[1], p[3])
- def p_expression_uplus_or_expr(p):
- """expression : PLUS expression %prec UPLUS
- | LPAREN expression RPAREN"""
- p[0] = p[2]
- def p_expression_uminus(p):
- """expression : MINUS expression %prec UMINUS"""
- p[0] = -p[2]
- def p_expression_num(p):
- """expression : NUM
- | FLOAT"""
- p[0] = p[1]
- # 語法錯(cuò)誤時(shí)的規(guī)則
- def p_error(p):
- print(f"Syntax error in {p.value}")
- #####################################
- # 主程式 #
- #####################################
- if __name__ == "__main__":
- basicConfig(level=INFO, filename="logs.txt")
- lexlexer = lex.lex()
- parser = yacc.yacc()
- while True:
- try:
- result = parser.parse(
- input(">>>"),
- debug=getLogger())
- print(result)
- except AttributeError:
- print("invalid syntax")
結(jié)論
由于這個(gè)話題的體積龐大，這篇文章并不能將事物完全的解釋清楚，但我希望你能很好地理解文中涵蓋的表層知識(shí)。
