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

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

我们不会重新造轮子。文章将使用由 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")

结论

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

更多相关文章

  1. adb logcat命令查看并过滤android输出log
  2. Android(安卓)PlayGame
  3. Android(安卓)图文混排spannableStringBuilder简单使用
  4. Xamarin开发Android时Visual Studio 2012没有智能提示解决办法
  5. Android(安卓)4.4 KitKat 支持 u 盘功能
  6. Android(安卓)GoogleMap Overlay （图层标记）
  7. android 关于InputDispatcher出现Consumer异常的解决方法
  8. Android(安卓)初始化Setup Wizard——Provision
  9. Android(安卓)初始化Setup Wizard——Provision

随机推荐

  1. Linux下非root用户能创建新文件，却不能拷
  2. Linux用户和组的操作（一） 用户文件/etc/pas
  3. Linux命令应用大词典-第21章 LVM和RAID管
  4. Linux网络状态工具ss命令使用详解
  5. [置顶] Linux C编程--string.h函
  6. Ubuntu12挂载扩充/home
  7. Linux文件映射的反思
  8. [转帖]linux文件描述符文件/etc/security
  9. 重装linux，从ubuntu到centos
  10. 双插槽与单插槽内存模型？