[译]Let’s Build A Simple Interpreter. Part 3.

Posted on | Comments:

原文地址：Let’s Build A Simple Interpreter. Part 3.

今天早上我醒来时想到：“为什么学习一项新技能这么困难呢？”

我不认为只是因为需要努力工作。我认为原因之一可能是我们花费了很多时间和精力通过阅 读和观察来获取知识，但没有花费足够的时间来通过练习把知识转化为技能。以游泳为例， 你可以花费很多时间阅读上百本关于游泳的书，跟有经验的游泳者和教练谈上数小时，观看 所有能找到的训练视频，但你第一次跃进泳池时仍然会像块石头一样沉下去。

关键是：你认为你对这个问题有多了解并不重要 ── 你必须把这些练习付诸实践才能把它变 成一项技能。为了帮助你练习，我在本系列的第一部分和第二部分中加入了练习。是的，你 在今天还有将来的文章中还会看到更多的练习，我保证:)

好了，让我们开始今天的学习，好吗？

目前为止，你已经学习了如何解释整数相加或相减的算术表达式如“7+3”或“12-9”。今天我 会聊一聊怎样解析（识别）并解释包含多位整数的加减法的算术表达式，如“7 - 3 + 2 - 1”。

本文中的算术表达式可以用如下的句法图(syntax diagram)表示：

Figure 1: syntax diagram

什么是句法图？ 句法图 就是程序语言句法规则的图形表示。基本上，句法图从视觉上向 你展示了在你的程序语言中哪些语句是允许的哪些是不允许的。

句法图很容易阅读：只需跟随箭头所指示的路径即可。一些路径表示选择，一些路径表示循环。

你可以这样阅读上面的句法图：一个 term 后面可以跟一个加号或减号，后面又跟另一个 term， 相应地它后面又可以跟一个加号或减号，后面又跟另一个 term，如此循环。你已经读懂了 这幅图片，真的。你可能会疑惑什么是“term”。在这篇文章中“term”就是一个整数。

句法图主要有两个用途：

  • 从图形上表示一个编程语言的标准（语法）。
  • 用来帮助你编写 parser - 你可以通过下面简单的规则将图映射到代码。

你已经学过了从 token 流中识别组合的过程叫 parsing. 且解释器或编译器中执行这部 分任务的部分叫 parser. parsing 也被称为 句法分析 (syntax analysis)，parser 也相应地被称为 句法分析器 (syntax analyzer)，你应该也猜到这点了。

根据上面的句法图，下面所有的算术表达式都是合法的：

  • 3
  • 3 + 4
  • 7 - 3 + 2 - 1

因为在不同的程序语言中算术表达式的句法规则都相似，我们可以使用 Python shell 来 “测试”我们的句法图。启动 Python shell 自己试一下： 

>>> 3
3
>>> 3 + 4
7
>>> 7 - 3 + 2 - 1
5

一切正常。

但表达式“3+”就不是合法的算术表达式，因为根据句法图加号后面必须跟一个 term（整数）， 否则就是句法错误。两次启动 Python shell 自己查看结果： 

>>> 3 +
  File "<stdin>", line 1
    3 +
      ^
SyntaxError: invalid syntax

使用 Python shell 来做测试是挺不错的，不过我们还是把上面的句法图映射到代码，用我 们自己的解释器来测试，是吧？

从前面的文章（第一部分和第二部分）你知道了 parser 和 interpreter 都在 expr 方 法中。再重复一下，parser 只是识别出结构并保证它符合某些规范，interpreter 在 parser 成功识别后对表达式进行求值。

下面的代码片段展示了与句法图相对应的 parser 的代码。句法图中的矩形盒子变成了解析 一个整数的 term 方法， expr 方法则只是跟随了句法图的指示： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def term(self):
    self.eat(INTEGER)

def expr(self):
    # set current token to the first token taken from the input
    self.current_token = self.get_next_token()

    self.term()
    while self.current_token.type in (PLUS, MINUS):
	token = self.current_token
	if token.type == PLUS:
	    self.eat(PLUS)
	    self.term()
	elif token.type == MINUS:
	    self.eat(MINUS)
	    self.term()

可以看到 expr 方法首先调用了 term 方法。然后是一个可能执行 0 或多次的循环。 在循环中，parser 根据 token （是加号还是减号）来做选择。花些时间确认上面的代码确 实体现了算术表达式的句法图。

Parser 本身并不解释任何事：如果识别到一个表达式它就沉默，否则就抛出一个句法错误。 让我们修改 expr 方法来添加 interpreter 代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def term(self):
    """Return an INTEGER token value"""
    token = self.current_token
    self.eat(INTEGER)
    return token.value

def expr(self):
    """Parser / Interpreter"""
    # set current token to the first token taken from the input
    self.current_token = self.get_next_token()

    result = self.term()
    while self.current_token.type in (PLUS, MINUS):
	token = self.current_token
	if token.type == PLUS:
	    self.eat(PLUS)
	    result = result += self.term()
	elif token.type == MINUS:
	    self.eat(MINUS)
	    result = result - self.term()

    return result

因为 interpreter 需要对表达式进行求值，所以 term 方法被修改为返回一个整数值， expr 方法被修改为在适当的地方执行加减法并返回解释的结果。尽管代码很直接，但我 还是建议你花点时间研究它。

让我们继续前进，来看一下现在解释器的完整代码怎么样？

下面是你新版计算器的源代码，它可以处理包含任意多个整数的加减操作的合法算术表达式： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
# Token types
#
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis
INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'

class Token():
    def __init__(self, type, value):
	# token type: INTEGER, PLUS, MINUX, or EOF
	self.type  = type
	# token value: non-negative integer value, '+', '-', or None
	self.value = value

    def __str__(self):
	"""String representation of the class instance.
	Examples:
	    Token(INTEGER, 3)
	    Token(PLUS, '+')
	"""
	return f'Token({self.type}, {repr(self.value)})'

    def __repr__(self):
	return self.__str__()

class Interpreter():
    def __init__(self, text):
	# client string input, e.g. "3 + 5", "12 - 5 + 3", etc
	self.text = text
	# self.pos is an index into self.text
	self.pos = 0
	# current token instance
	self.current_token = None
	self.current_char  = self.text[self.pos]

    ##########################################################
    # Lexer code                                             #
    ##########################################################
    def error(self):
	raise Exception('Invalid syntax')

    def advance(self):
	"""Advance the 'pos' pointer and set the 'current_char' variable."""
	self.pos += 1
	if self.pos >= len(self.text):
	    self.current_char = None  # Indicates end of input
	else:
	    self.current_char = self.text[self.pos]

    def skip_whitespace(self):
	while self.current_char is not None and self.current_char.isspace():
	    self.advance()

    def integer(self):
	value = ''
	while self.current_char is not None and self.current_char.isdigit():
	    value += self.current_char
	    self.advance()
	return int(value)

    def get_next_token(self):
	"""Lexical analyzer (also known as scanner or tokenizer)

	This method is responsible for breaking a sentence
	apart into tokens. One token at a time.
	"""
	while self.current_char is not None:
	    if self.current_char.isspace():
		self.advance()
		continue
	    elif self.current_char.isdigit():
		return Token(INTEGER, self.integer())
	    elif self.current_char == '+':
		self.advance()
		return Token(PLUS, '+')
	    elif self.current_char == '-':
		self.advance()
		return Token(MINUS, '-')
	    else:
		self.error()

	return Token(EOF, None)

    ##########################################################
    # Parser / Interpreter code                              #
    ##########################################################
    def eat(self, token_type):
	# compare the current token type with the passed token
	# type and if they match then "eat" the current token
	# and assign the next token to the self.current_token,
	# otherwise raise an exception.
	if self.current_token.type == token_type:
	    self.current_token = self.get_next_token()
	else:
	    self.error()

    def term(self):
	"""Return an INTEGER token value."""
	token = self.current_token
	self.eat(INTEGER)
	return token.value

    def expr(self):
	"""Arithmetic expression parser / interpreter."""
	# set current token to the first token taken from the input
	self.current_token = self.get_next_token()

	result = self.term()
	while self.current_token.type in (PLUS, MINUS):
	    token = self.current_token
	    if token.type == PLUS:
		self.eat(PLUS)
		result += self.term()
	    elif token.type == MINUS:
		self.eat(MINUS)
		result -= self.term()
	    else:
		self.error()

	return result

def main():
    while True:
	try:
	    text = input('calc> ')
	except EOFError:
	    print()
	    break

	if not text:
	    continue
	interpreter = Interpreter(text)
	result = interpreter.expr()
	print(result)

if __name__ == '__main__':
    main()

将以上代码保存到名为 calc3.py 中，或者直接从 GitHub 上下载。试一试。亲眼看一下 它可以处理之前展示给你的句法图中包含的算术表达式规则。

下面是在我笔记本上的一次尝试： 

$ python calc3.py
calc> 3
3
calc> 7 - 4
3
calc> 10 + 5
15
calc> 7 - 3 + 2 - 1
5
calc> 10 + 1 + 2 - 3 + 4 + 6 - 15
5
calc> 3 +
Traceback (most recent call last):
  File "calc3.py", line 147, in <module>
    main()
  File "calc3.py", line 142, in main
    result = interpreter.expr()
  File "calc3.py", line 123, in expr
    result = result + self.term()
  File "calc3.py", line 110, in term
    self.eat(INTEGER)
  File "calc3.py", line 105, in eat
    self.error()
  File "calc3.py", line 45, in error
    raise Exception('Invalid syntax')
Exception: Invalid syntax

记得我在开头提到的练习吧：在这儿，说到做到:)

Figure 2: exercises

  • 画一张只包含乘除法的算术表达式句法图，例如“7 * 4 / 2 * 3”。不开玩笑，拿只钢笔 或铅笔试试。
  • 修改计算器的源代码使它解释只包含乘除法的算术表达式，如“7 * 4 / 2 * 3”。
  • 从头写一个可以处理如“7 - 3 + 2 - 1”这样算术表达式的解释器。使用任何你喜欢的语 言都可以，只靠自己，不要参考例子。做这件事时，想想都需要包含的组件：lexer 获取 输入并把它转化为 token 流，parser 从 lexer 提供的 token 流中识别结构， interpreter 在 parser 成功识别到一个合法的算术表达式之后求得其结果。把这些连起 来。花点时间把你学到的知识转化为一个可以运行的算术表达式解释器。

检查你的理解。

  1. 什么是句法图？
  2. 什么是句法分析？
  3. 什么是句法分析器？

看呐！你读完了整篇文章。谢谢你今天在这浏览，别忘了做练习。:) 等我下次回来就会有 一篇新文章了 ── 敬请关注。

下面是我推荐的帮助你学习解释器和编译器的一些书：

  1. Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)
  2. Writing Compilers and Interpreters: A Software Engineering Approach
  3. Modern Compiler Implementation in Java
  4. Modern Compiler Design
  5. Compilers: Principles, Techniques, and Tools (2nd Edition)

顺便说一下，我还在写一本书“et’s Build A Web Server: First Steps”，解释了怎么从头 写一个基本的 Web 服务器。你可以从这里， 这里 和 这里 来感受一下这本书。

本系列的所有文章：

Last Updated 2018-05-26 Sat 14:12.
Render by hexo-renderer-org with Emacs 25.2.2 (Org mode 9.1.13)
0%