用Python编写个解释器实现方法接受
作者:宋宋讲编程 发布时间:2023-01-11 15:50:08
前言
在本文中,我们将设计一个可以执行算术运算的解释器。
我们不会重新造轮子。文章将使用由 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")
为导入词法分析器,我们将使用:
importply.lexaslex
t_ 是一个特殊的前缀,表示定义标记的规则。每条词法规则都是用正则表达式制作的,与 Python 中的 re 模块兼容。正则表达式能够根据规则扫描输入并搜索符合的符号串。正则表达式定义的文法称为正则文法。正则文法定义的语言则称为正则语言。
定义好了规则,我们将构建词法分析器。
data = 'a = 2 +(10 -8)/1.0'
lexer = 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")
lexer = lex.lex()
parser = yacc.yacc()
while True:
try:
result = parser.parse(
input(">>>"),
debug=getLogger())
print(result)
except AttributeError:
print("invalid syntax")
结论
由于这个话题的体积庞大,这篇文章并不能将事物完全的解释清楚,但我希望你能很好地理解文中涵盖的表层知识。
来源:https://blog.csdn.net/qiqi1220/article/details/128298338
猜你喜欢
- 最近项目遇到一个坑爹的事情,一个源码必须使用PHP5.3,但是现在Ubuntu上自带的版本是5.4,降级之后会出各种奇怪的问题,最后没办法,
- 大家做网站,特别是自己写的代码,常常担心被一些黑客入侵服务器,从而导致网站代码被盗,给自己带来一些损失。那么我们怎么样做,就算黑客盗了你的代
- <?php //设置我们将要使用的文件 $srcurl = "http://localhost/index.php"
- 从大的发展来看,网站就是一块试验田,一块在错误中成长、在错误中变强变大的试验田。这决定了互联网产品的成长路线,一定是一个反复修正和迭代的曲线
- 引言 亚马逊网站相较于国内的购物网站,可以直接使用python的最基本的request
- 前言Python是C语言实现的,因此Python对象在C语言层面应该是一个结构体 ,组织对象占用的内存。 不同类型的对象,数据及行为均可能不
- 字符串索引示意图字符串切片也就是截取字符串,取子串Python中字符串切片方法字符串[开始索引:结束索引:步长]切取字符串为开始索引到结束索
- 1、time模块(※※※※)import time #导入时间模块print(time.time()) #返回当前时间的时间戳,可用于计算程
- 本文实例讲解了php表单验证的实现方法,分享给大家供大家参考,具体内容如下1.PHP表单处理welcome.html<html>
- /* 功能: 通用分页存储过程 参数: @PK varchar(50), 主键,用来排序的单一字段,空的话,
- 第一种import win32clipboardimport time#速度快 容易出错class niubi(): def l
- 首先得抛出个重要的前提观点,大屏幕、宽屏幕根本不是为方便“扫视”准备的。所以说以内容为基础的网站设计不用考虑超宽、超大的场景,甚至包括服务类
- 神经网络框架使用方法及设计思想在框自己手写架上基本模仿pytorch,用以学习神经网络的基本算法,如前向传播、反向传播、各种层、各种激活函数
- 很多开发者说自从有了 Python/Pandas,Excel 都不怎么用了,用它来处理与可视化表格非常快速。下面我来举几个例子。1. 删除重
- 1.func Copy(dst Writer, src Reader) (written int64, err error)这个函数是从一个
- 本文实例讲述了Python实现获取邮箱内容并解析的方法。分享给大家供大家参考,具体如下:# -*- coding: utf-8 -*-fro
- <%@LANGUAGE="VBSCRIPT" CODEPAGE="936"%> &nbs
- 下面这段代码是兼容IE的图片切换代码,请问各位老鸟如何兼容FF,或者有相类似无按钮无数字兼容FF的图片切换代码?<!DOCTYPE h
- 在你自己安装了一个新的MySQL服务器后,你需要为MySQL的root用户指定一个目录(缺省无口令),否则如果你忘记这点,你将你的MySQL
- 在工作实践和学习中,如何开启 MySQL 数据库的远程登陆帐号算是一个难点的问题,以下内容便是在工作和实践中总结出来的两大步骤,能帮助DBA