Community Learn Tools Library Leisure
search
English
Home > List of blog posts > 使用 Python 开发一个 Python 解释器
Blogger Information
Blog 11
fans 0
comment 0
visits 7672
Special Recommendation
More>
Related recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
使用 Python 开发一个 Python 解释器
P粉934491362
Original
693 people have browsed it

计算机只能理解机器码。归根结底，编程语言只是一串文字，目的是为了让人类更容易编写他们想让计算机做的事情。真正的魔法是由编译器和解释器完成，它们弥合了两者之间的差距。解释器逐行读取代码并将其转换为机器码。

在本文中，我们将设计一个可以执行算术运算的解释器。

我们不会重新造轮子。文章将使用由 David M. Beazley 开发的词法解析器 —— PLY（Python Lex-Yacc。

PLY 可以通过以下方式下载：

  1. $ pip install ply

我们将粗略地浏览一下创建解释器所需的基础知识。

标记（Token）

标记是为解释器提供有意义信息的最小字符单位。标记包含一对名称和属性值。

让我们从创建标记名称列表开始。这是一个必要的步骤。

  1. tokens = (
  2.     # 数据类型
  3.     "NUM",
  4.     "FLOAT",
  5.     # 算术运算
  6.     "PLUS",
  7.     "MINUS",
  8.     "MUL",
  9.     "DIV",
  10.     # 括号
  11.     "LPAREN",
  12.     "RPAREN",
  13. )

词法分析器（Lexer）

将语句转换为标记的过程称为标记化或词法分析。执行词法分析的程序是词法分析器。

  1. # 标记的正则表达
  2. t_PLUS   = r"+"
  3. t_MINUS  = r"-"
  4. t_MUL    = r"*"
  5. t_DIV    = r"/"
  6. t_LPAREN = r"("
  7. t_RPAREN = r")"
  8. t_POW    = r"^"
  9. # 忽略空格和制表符
  10. t_ignore = " \t"
  13. # 为每个规则添加动作
  14. def t_FLOAT(t):
  15.     r"""\d+.\d+"""
  16.     t.value = float(t.value)
  17.     return t
  20. def t_NUM(t):
  21.     r"""\d+"""
  22.     t.value = int(t.value)
  23.     return t
  26. # 未定义规则字符的错误处理
  27. def t_error(t):
  28.     # 此处的 t.value 包含未标记的其余输入
  29.     print(f"keyword not found: {t.value[0]}\nline {t.lineno}")
  30.     t.lexer.skip(1)
  33. # 如果遇到 \n 则将其设为新的一行
  34. def t_newline(t):
  35.     r"""\n+"""
  36.     t.lexer.lineno += t.value.count("\n")

为导入词法分析器，我们将使用：

import ply.lex as lex

t_ 是一个特殊的前缀，表示定义标记的规则。每条词法规则都是用正则表达式制作的，与 Python 中的 re 模块兼容。正则表达式能够根据规则扫描输入并搜索符合的符号串。正则表达式定义的文法称为正则文法。正则文法定义的语言则称为正则语言。

定义好了规则，我们将构建词法分析器。

  1. data = 'a = 2 +(10 -8)/1.0'
  3. lexer = lex.lex()
  4. lexer.input(data)
  6. while tok := lexer.token():
  7.     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或…… 等等）。对于我们的这个算术解释器，语法规格如下：

  1. expression : expression '+' expression
  2.            | expression '-' expression
  3.            | expression '/' expression
  4.            | expression '*' expression
  5.            | expression '^' expression
  6.            | +expression
  7.            | -expression
  8.            | ( expression )
  9.            | NUM
  10.            | FLOAT

输入的标记是诸如 NUM、FLOAT、+、-、*、/ 之类的符号，称作终端（无法继续分解或产生其他符号的字符）。一个表达式由终端和规则集组成，例如 expression 则称为非终端。

解析器（Parser）

我们将使用 YACC（Yet Another Compiler Compiler） 作为解析器生成器。导入模块：import ply.yacc as yacc。

  1. from operator import (add, sub, mul, truediv, pow)
  3. # 我们的解释器支持的运算符列表
  4. ops = {
  5.     "+": add,
  6.     "-": sub,
  7.     "*": mul,
  8.     "/": truediv,
  9.     "^": pow,
  10. }
  12. def p_expression(p):
  13.     """expression : expression PLUS expression
  14.                   | expression MINUS expression
  15.                   | expression DIV expression
  16.                   | expression MUL expression
  17.                   | expression POW expression"""
  18.     if (p[2], p[3]) == ("/", 0):
  19.         # 如果除以 0，则将“INF”（无限）作为值
  20.         p[0] = float("INF")
  21.     else:
  22.         p[0] = ops[p[2]](p[1], p[3])
  25. def p_expression_uplus_or_expr(p):
  26.     """expression : PLUS expression %prec UPLUS
  27.                   | LPAREN expression RPAREN"""
  28.     p[0] = p[2]
  31. def p_expression_uminus(p):
  32.     """expression : MINUS expression %prec UMINUS"""
  33.     p[0] = -p[2]
  36. def p_expression_num(p):
  37.     """expression : NUM
  38.                   | FLOAT"""
  39.     p[0] = p[1]
  42. # 语法错误时的规则
  43. def p_error(p):
  44.     print(f"Syntax error in {p.value}")

在文档字符串中，我们将添加适当的语法规范。p 列表中的的元素与语法符号一一对应，如下所示：

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

在上文中，%prec UPLUS 和 %prec UMINUS 是用来表示自定义运算的。%prec 即是 precedence 的缩写。在符号中本来没有 UPLUS 和 UMINUS 这个说法（在本文中这两个自定义运算表示一元正号和符号，其实 UPLUS 和 UMINUS 只是个名字，想取什么就取什么）。之后，我们可以添加基于表达式的规则。YACC 允许为每个令牌分配优先级。我们可以使用以下方法设置它：

  1. precedence = (
  2.     ("left", "PLUS", "MINUS"),
  3.     ("left", "MUL", "DIV"),
  4.     ("left", "POW"),
  5.     ("right", "UPLUS", "UMINUS")
  6. )

在优先级声明中，标记按优先级从低到高的顺序排列。PLUS 和 MINUS 优先级相同并且具有左结合性（运算从左至右执行）。MUL 和 DIV 的优先级高于 PLUS 和 MINUS，也具有左结合性。POW 亦是如此，不过优先级更高。UPLUS 和 UMINUS 则是具有右结合性（运算从右至左执行）。

要解析输入我们将使用：

  1. parser = yacc.yacc()
  2. result = parser.parse(data)
  3. print(result)

完整代码如下：

  1. #####################################
  2. # 引入模块                           #
  3. #####################################
  4. from logging import (basicConfig, INFO, getLogger)
  5. from operator import (add, sub, mul, truediv, pow)
  7. import ply.lex as lex
  8. import ply.yacc as yacc
  10. # 我们的解释器支持的运算符列表
  11. ops = {
  12.     "+": add,
  13.     "-": sub,
  14.     "*": mul,
  15.     "/": truediv,
  16.     "^": pow,
  17. }
  19. #####################################
  20. # 标记集                             #
  21. #####################################
  22. tokens = (
  23.     # 数据类型
  24.     "NUM",
  25.     "FLOAT",
  26.     # 算术运算
  27.     "PLUS",
  28.     "MINUS",
  29.     "MUL",
  30.     "DIV",
  31.     "POW",
  32.     # 括号
  33.     "LPAREN",
  34.     "RPAREN",
  35. )
  37. #####################################
  38. # 标记的正则表达式                    #
  39. #####################################
  40. t_PLUS   = r"+"
  41. t_MINUS  = r"-"
  42. t_MUL    = r"*"
  43. t_DIV    = r"/"
  44. t_LPAREN = r"("
  45. t_RPAREN = r")"
  46. t_POW    = r"^"
  47. # 忽略空格和制表符
  48. t_ignore = " \t"
  51. # 为每个规则添加动作
  52. def t_FLOAT(t):
  53.     r"""\d+.\d+"""
  54.     t.value = float(t.value)
  55.     return t
  58. def t_NUM(t):
  59.     r"""\d+"""
  60.     t.value = int(t.value)
  61.     return t
  64. # 未定义规则字符的错误处理
  65. def t_error(t):
  66.     # 此处的 t.value 包含未标记的其余输入
  67.     print(f"keyword not found: {t.value[0]}\nline {t.lineno}")
  68.     t.lexer.skip(1)
  71. # 如果看到 \n 则将其设为新的一行
  72. def t_newline(t):
  73.     r"""\n+"""
  74.     t.lexer.lineno += t.value.count("\n")
  77. #####################################
  78. # 设置符号优先级                      #
  79. #####################################
  80. precedence = (
  81.     ("left", "PLUS", "MINUS"),
  82.     ("left", "MUL", "DIV"),
  83.     ("left", "POW"),
  84.     ("right", "UPLUS", "UMINUS")
  85. )
  88. #####################################
  89. # 书写 BNF 规则                      #
  90. #####################################
  91. def p_expression(p):
  92.     """expression : expression PLUS expression
  93.                   | expression MINUS expression
  94.                   | expression DIV expression
  95.                   | expression MUL expression
  96.                   | expression POW expression"""
  97.     if (p[2], p[3]) == ("/", 0):
  98.         # 如果除以 0，则将“INF”（无限）作为值
  99.         p[0] = float("INF")
  100.     else:
  101.         p[0] = ops[p[2]](p[1], p[3])
  104. def p_expression_uplus_or_expr(p):
  105.     """expression : PLUS expression %prec UPLUS
  106.                   | LPAREN expression RPAREN"""
  107.     p[0] = p[2]
  110. def p_expression_uminus(p):
  111.     """expression : MINUS expression %prec UMINUS"""
  112.     p[0] = -p[2]
  115. def p_expression_num(p):
  116.     """expression : NUM
  117.                   | FLOAT"""
  118.     p[0] = p[1]
  121. # 语法错误时的规则
  122. def p_error(p):
  123.     print(f"Syntax error in {p.value}")
  126. #####################################
  127. # 主程式                             #
  128. #####################################
  129. if __name__ == "__main__":
  130.     basicConfig(level=INFO, filename="logs.txt")
  132.     lexer = lex.lex()
  133.     parser = yacc.yacc()
  135.     while True:
  136.         try:
  137.             result = parser.parse(
  138.                 input(">>>"),
  139.                 debug=getLogger())
  140.             print(result)
  141.         except AttributeError:
  142.             print("invalid syntax")

结论

由于这个话题的体积庞大，这篇文章并不能将事物完全的解释清楚，但我希望你能很好地理解文中涵盖的表层知识。我很快会发布关于这个话题的其他文章。谢谢你，祝你有个美好的一天。

以上就是本次分享的所有内容，如果你觉得文章还不错，欢迎关注点赞一下，在此感谢你们的支持，

Statement of this Website
The copyright of this blog article belongs to the blogger. Please specify the address when reprinting! If there is any infringement or violation of the law, please contact admin@php.cn Report processing!
All comments Speak rationally on civilized internet, please comply with News Comment Service Agreement
0 comments
Author's latest blog post