計算機只能理解機器碼。歸根結底，編程語言只是一串文字，目的是為了讓人類更容易編寫他們想讓計算機做的事情。真正的魔法是由編譯器和解釋器完成，它們彌合了兩者之間的差距。解釋器逐行讀取代碼并將其轉換為機器碼。

在本文中，我們將設計一個可以執行算術運算的解釋器。

我們不會重新造輪子。文章將使用由 David M. Beazley 開發的詞法解析器 —— PLY（Python Lex-Yacc(https://github.com/dabeaz/ply)）。

PLY 可以通過以下方式下載：

$ pip install ply 

我們將粗略地瀏覽一下創建解釋器所需的基礎知識。欲了解更多，請參閱這個 GitHub 倉庫(https://github.com/dabeaz/ply)。

標記（Token）

標記是為解釋器提供有意義信息的最小字符單位。標記包含一對名稱和屬性值。

讓我們從創建標記名稱列表開始。這是一個必要的步驟。 

tokens = (  
    # 數據類型  
    "NUM",  
    "FLOAT",  
    # 算術運算  
    "PLUS",  
    "MINUS",  
    "MUL",  
    "DIV",  
    # 括號  
    "LPAREN",  
    "RPAREN",  
) 

詞法分析器（Lexer）

將語句轉換為標記的過程稱為標記化或詞法分析。執行詞法分析的程序是詞法分析器。 

# 標記的正則表達  
t_PLUS   = r"\+"  
t_MINUS  = r"\-"  
t_MUL    = r"\*"  
t_DIV    = r"/"  
t_LPAREN = r"\("  
t_RPAREN = r"\)"  
t_POW    = r"\^"  
# 忽略空格和制表符  
t_ignore = " \t"  
# 為每個規則添加動作  
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  
# 未定義規則字符的錯誤處理  
def t_error(t):  
    # 此處的 t.value 包含未標記的其余輸入  
    print(f"keyword not found: {t.value[0]}\nline {t.lineno}")  
    t.lexer.skip(1)  
# 如果遇到 \n 則將其設為新的一行  
def t_newline(t):  
    r"""\n+"""  
    t.lexer.lineno += t.value.count("\n") 

為導入詞法分析器，我們將使用：

import ply.lex as lex

t_ 是一個特殊的前綴，表示定義標記的規則。每條詞法規則都是用正則表達式制作的，與 Python 中的 re 模塊兼容。正則表達式能夠根據規則掃描輸入并搜索符合的符號串。正則表達式定義的文法稱為正則文法。正則文法定義的語言則稱為正則語言。

定義好了規則，我們將構建詞法分析器。 

data = 'a = 2 +(10 -8)/1.0'  
lexlexer = lex.lex()  
lexer.input(data)  
while tok := lexer.token():  
    print(tok) 

為了傳遞輸入字符串，我們使用 lexer.input(data)。lexer.token() 將返回下一個 LexToken 實例，最后返回 None。根據上述規則，代碼 2 + ( 10 -8)/1.0 的標記將是：

紫色字符代表的是標記的名稱，其后是標記的具體內容。

巴科斯-諾爾范式（Backus-Naur Form，BNF）

大多數編程語言都可以用上下文無關文法來編寫。它比常規語言更復雜。對于上下文無關文法，我們用上下文無關語法，它是描述語言中所有可能語法的規則集。BNF 是一種定義語法的方式，它描述了編程語言的語法。讓我們看看例子：

symbol : alternative1 | alternative2 …

根據產生式，: 的左側被替換為右側的其中一個值替換。右側的值由 | 分隔（可理解為 symbol 定義為 alternative1 或 alternative2或…… 等等）。對于我們的這個算術解釋器，語法規格如下： 

expression : expression '+' expression  
           | expression '-' expression  
           | expression '/' expression  
           | expression '*' expression  
           | expression '^' expression  
           | +expression  
           | -expression  
           | ( expression )  
           | NUM  
           | FLOAT 

輸入的標記是諸如 NUM、FLOAT、+、-、*、/ 之類的符號，稱作終端（無法繼續分解或產生其他符號的字符）。一個表達式由終端和規則集組成，例如 expression 則稱為非終端。

解析器（Parser）

我們將使用 YACC（Yet Another Compiler Compiler） 作為解析器生成器。導入模塊：import ply.yacc as yacc。 

from operator import (add, sub, mul, truediv, pow)  
# 我們的解釋器支持的運算符列表  
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]  
# 語法錯誤時的規則  
def p_error(p):  
    print(f"Syntax error in {p.value}") 

在文檔字符串中，我們將添加適當的語法規范。p 列表中的的元素與語法符號一一對應，如下所示： 

expression : expression PLUS expression  
p[0]         p[1]       p[2] p[3] 

在上文中，%prec UPLUS 和 %prec UMINUS 是用來表示自定義運算的。%prec 即是 precedence 的縮寫。在符號中本來沒有 UPLUS 和 UMINUS 這個說法（在本文中這兩個自定義運算表示一元正號和符號，其實 UPLUS 和 UMINUS 只是個名字，想取什么就取什么）。之后，我們可以添加基于表達式的規則。YACC 允許為每個令牌分配優先級。我們可以使用以下方法設置它： 

precedence = (  
    ("left", "PLUS", "MINUS"),  
    ("left", "MUL", "DIV"),  
    ("left", "POW"),  
    ("right", "UPLUS", "UMINUS")  
) 

在優先級聲明中，標記按優先級從低到高的順序排列。PLUS 和 MINUS 優先級相同并且具有左結合性（運算從左至右執行）。MUL 和 DIV 的優先級高于 PLUS 和 MINUS，也具有左結合性。POW 亦是如此，不過優先級更高。UPLUS 和 UMINUS 則是具有右結合性（運算從右至左執行）。

要解析輸入我們將使用： 

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  
# 我們的解釋器支持的運算符列表  
ops = {  
    "+": add,  
    "-": sub,  
    "*": mul,  
    "/": truediv,  
    "^": pow,  
}  
#####################################  
# 標記集                             #  
#####################################  
tokens = (  
    # 數據類型  
    "NUM",  
    "FLOAT",  
    # 算術運算  
    "PLUS",  
    "MINUS",  
    "MUL",  
    "DIV",  
    "POW",  
    # 括號  
    "LPAREN",  
    "RPAREN",  
)  
#####################################  
# 標記的正則表達式                    #  
#####################################  
t_PLUS   = r"\+"  
t_MINUS  = r"\-"  
t_MUL    = r"\*"  
t_DIV    = r"/"  
t_LPAREN = r"\("  
t_RPAREN = r"\)"  
t_POW    = r"\^"  
# 忽略空格和制表符  
t_ignore = " \t"  
# 為每個規則添加動作  
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  
# 未定義規則字符的錯誤處理  
def t_error(t):  
    # 此處的 t.value 包含未標記的其余輸入  
    print(f"keyword not found: {t.value[0]}\nline {t.lineno}")  
    t.lexer.skip(1)  
# 如果看到 \n 則將其設為新的一行 
 def t_newline(t):  
    r"""\n+"""  
    t.lexer.lineno += t.value.count("\n")  
#####################################  
# 設置符號優先級                      #  
#####################################  
precedence = (  
    ("left", "PLUS", "MINUS"),  
    ("left", "MUL", "DIV"),  
    ("left", "POW"),  
    ("right", "UPLUS", "UMINUS")  
)  
#####################################  
# 書寫 BNF 規則                      #  
#####################################  
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]  
# 語法錯誤時的規則  
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") 

結論

由于這個話題的體積龐大，這篇文章并不能將事物完全的解釋清楚，但我希望你能很好地理解文中涵蓋的表層知識。