用Python編寫(xiě)個(gè)解釋器實(shí)現(xiàn)方法接受
前言
在本文中,我們將設(shè)計(jì)一個(gè)可以執(zhí)行算術(shù)運(yùn)算的解釋器。
我們不會(huì)重新造輪子。文章將使用由 David M. Beazley 開(kāi)發(fā)的詞法解析器 —— PLY(Python Lex-Yacc(https://github.com/dabeaz/ply))。
PLY 可以通過(guò)以下方式下載:
$ pip install ply
我們將粗略地瀏覽一下創(chuàng)建解釋器所需的基礎(chǔ)知識(shí)。欲了解更多,請(qǐng)參閱這個(gè) GitHub 倉(cāng)庫(kù)(https://github.com/dabeaz/ply)。
標(biāo)記(Token)
標(biāo)記是為解釋器提供有意義信息的最小字符單位。標(biāo)記包含一對(duì)名稱(chēng)和屬性值。
讓我們從創(chuàng)建標(biāo)記名稱(chēng)列表開(kāi)始。這是一個(gè)必要的步驟。
tokens = ( # 數(shù)據(jù)類(lèi)型 "NUM", "FLOAT", # 算術(shù)運(yùn)算 "PLUS", "MINUS", "MUL", "DIV", # 括號(hào) "LPAREN", "RPAREN", )
詞法分析器(Lexer)
將語(yǔ)句轉(zhuǎn)換為標(biāo)記的過(guò)程稱(chēng)為標(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)入詞法分析器,我們將使用:
importply.lexaslex
t_ 是一個(gè)特殊的前綴,表示定義標(biāo)記的規(guī)則。每條詞法規(guī)則都是用正則表達(dá)式制作的,與 Python 中的 re 模塊兼容。正則表達(dá)式能夠根據(jù)規(guī)則掃描輸入并搜索符合的符號(hào)串。正則表達(dá)式定義的文法稱(chēng)為正則文法。正則文法定義的語(yǔ)言則稱(chēng)為正則語(yǔ)言。
定義好了規(guī)則,我們將構(gòu)建詞法分析器。
data = 'a = 2 +(10 -8)/1.0' lexer = 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)記的名稱(chēng),其后是標(biāo)記的具體內(nèi)容。
巴科斯-諾爾范式(Backus-Naur Form,BNF)
大多數(shù)編程語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)編寫(xiě)。它比常規(guī)語(yǔ)言更復(fù)雜。對(duì)于上下文無(wú)關(guān)文法,我們用上下文無(wú)關(guān)語(yǔ)法,它是描述語(yǔ)言中所有可能語(yǔ)法的規(guī)則集。BNF 是一種定義語(yǔ)法的方式,它描述了編程語(yǔ)言的語(yǔ)法。讓我們看看例子:
symbol : alternative1 | alternative2 …
根據(jù)產(chǎn)生式,: 的左側(cè)被替換為右側(cè)的其中一個(gè)值替換。右側(cè)的值由 | 分隔(可理解為 symbol 定義為 alternative1 或 alternative2或…… 等等)。對(duì)于我們的這個(gè)算術(shù)解釋器,語(yǔ)法規(guī)格如下:
expression : expression '+' expression
| expression '-' expression
| expression '/' expression
| expression '*' expression
| expression '^' expression
| +expression
| -expression
| ( expression )
| NUM
| FLOAT
輸入的標(biāo)記是諸如 NUM、FLOAT、+、-、*、/ 之類(lèi)的符號(hào),稱(chēng)作終端(無(wú)法繼續(xù)分解或產(chǎn)生其他符號(hào)的字符)。一個(gè)表達(dá)式由終端和規(guī)則集組成,例如 expression 則稱(chēng)為非終端。
解析器(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”(無(wú)限)作為值 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] # 語(yǔ)法錯(cuò)誤時(shí)的規(guī)則 def p_error(p): print(f"Syntax error in {p.value}")
在文檔字符串中,我們將添加適當(dāng)?shù)恼Z(yǔ)法規(guī)范。p 列表中的的元素與語(yǔ)法符號(hào)一一對(duì)應(yīng),如下所示:
expression : expression PLUS expression
p[0] p[1] p[2] p[3]
在上文中,%prec UPLUS 和 %prec UMINUS 是用來(lái)表示自定義運(yùn)算的。%prec 即是 precedence 的縮寫(xiě)。在符號(hào)中本來(lái)沒(méi)有 UPLUS 和 UMINUS 這個(gè)說(shuō)法(在本文中這兩個(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 亦是如此,不過(guò)優(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ù)類(lèi)型 "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") ) ##################################### # 書(shū)寫(xiě) 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”(無(wú)限)作為值 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] # 語(yǔ)法錯(cuò)誤時(shí)的規(guī)則 def p_error(p): print(f"Syntax error in {p.value}") ##################################### # 主程式 # ##################################### if __name__ == "__main__": basicConfig(level=INFO, filename="logs.txt") lexer = lex.lex() parser = yacc.yacc() while True: try: result = parser.parse( input(">>>"), debug=getLogger()) print(result) except AttributeError: print("invalid syntax")
結(jié)論
由于這個(gè)話(huà)題的體積龐大,這篇文章并不能將事物完全的解釋清楚,但我希望你能很好地理解文中涵蓋的表層知識(shí)。
到此這篇關(guān)于用Python編寫(xiě)個(gè)解釋器實(shí)現(xiàn)方法接受的文章就介紹到這了,更多相關(guān)Python解釋器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python應(yīng)用案例之利用opencv實(shí)現(xiàn)圖像匹配
OpenCV 是一個(gè)的跨平臺(tái)計(jì)算機(jī)視覺(jué)庫(kù),可以運(yùn)行在 Linux、Windows 和 Mac OS 操作系統(tǒng)上,這篇文章主要給大家介紹了關(guān)于Python應(yīng)用案例之利用opencv實(shí)現(xiàn)圖像匹配的相關(guān)資料,需要的朋友可以參考下2024-08-08python3.5 + PyQt5 +Eric6 實(shí)現(xiàn)的一個(gè)計(jì)算器代碼
這篇文章主要介紹了python3.5 + PyQt5 +Eric6 實(shí)現(xiàn)的一個(gè)計(jì)算器代碼,在windows7 32位系統(tǒng)可以完美運(yùn)行 計(jì)算器,有興趣的可以了解一下。2017-03-03Python中用memcached來(lái)減少數(shù)據(jù)庫(kù)查詢(xún)次數(shù)的教程
這篇文章主要介紹了Python中用memcached來(lái)減少數(shù)據(jù)庫(kù)查詢(xún)次數(shù)的教程,memcached是一種分布式的內(nèi)存緩存工具,使用后可以減少對(duì)硬盤(pán)的I/O次數(shù),需要的朋友可以參考下2015-04-04Python爬取qq空間說(shuō)說(shuō)的實(shí)例代碼
這篇文章主要介紹了Python爬取qq空間說(shuō)說(shuō)的實(shí)例代碼,代碼簡(jiǎn)單易懂,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2018-08-08python向企業(yè)微信發(fā)送文字和圖片消息的示例
這篇文章主要介紹了python向企業(yè)微信發(fā)送文字和圖片消息的示例,幫助大家更好的理解和使用python,感興趣的朋友可以了解下2020-09-09Python多進(jìn)程方式抓取基金網(wǎng)站內(nèi)容的方法分析
這篇文章主要介紹了Python多進(jìn)程方式抓取基金網(wǎng)站內(nèi)容的方法,結(jié)合實(shí)例形式分析了Python多進(jìn)程抓取網(wǎng)站內(nèi)容相關(guān)實(shí)現(xiàn)技巧與操作注意事項(xiàng),需要的朋友可以參考下2019-06-06Python進(jìn)階教程之創(chuàng)建本地PyPI倉(cāng)庫(kù)
pypi是一個(gè)python包的倉(cāng)庫(kù),里面有很多別人寫(xiě)好的python庫(kù),你可以通過(guò)easy_install或者pip進(jìn)行安裝,下面這篇文章主要給大家介紹了關(guān)于Python進(jìn)階教程之創(chuàng)建本地PyPI倉(cāng)庫(kù)的相關(guān)資料,需要的朋友可以參考下2021-10-10基于Python的PIL庫(kù)學(xué)習(xí)詳解
這篇文章主要介紹了基于Python的PIL庫(kù)學(xué)習(xí)詳解,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-05-05