让我们写一个简单的解释器

大约 12 分钟compiler编译原理interpre

让我们写一个简单的解释器

“如果你不知道编译器是如何工作的，那么你就不知道计算机是如何工作的。如果你不确定自己是否100％了解编译器的工作原理，那么你就不知道它们的工作原理。” —— Steve Yegge

就是这样。想想看。无论你是新手还是经验丰富的软件开发人员：如果你不知道编译器和解释器如何工作，那么你就不知道计算机是如何工作的。就那么简单。

那么，你知道编译器和解释器如何工作吗？我是说，你是否100％确定自己知道它们的工作原理？如果不知道，请学习。

或者如果你不这样做而且你真的很焦虑。

不要担心。如果你坚持下去，跟我一起完成这个系列，构建一个解释器和编译器，最终你会知道它们是如何工作的。你也会变成一个自信的快乐营员。至少我希望如此。

为什么要学习解释器和编译器？以下是三个理由：

  1. 要编写解释器或编译器，你需要掌握很多技术技能并将它们合理运用。编写解释器或编译器将帮助你提高这些技能，成为更好的软件开发人员。此外，这些技能在编写任何软件时都很有用，不仅仅是在解释器或编译器方面。
  2. 你真的想知道计算机是如何工作的。通常，解释器和编译器看起来就像魔法。但你不应该对这种魔法感到舒适。你想揭开编写解释器和编译器的过程之谜，理解它们的工作原理，并掌握它们。
  3. 你想创建自己的编程语言或领域特定语言。如果你创建了一个编程语言，你也需要为它创建解释器或编译器。最近，新编程语言的兴趣再次高涨。你几乎可以每天看到一个新的编程语言出现：Elixir、Go、Rust等。

好的，但解释器和编译器是什么？

解释器或编译器的目的是将某种高级语言的源程序翻译成其他形式。听起来很模糊，对吧？请跟我一起坚持，本系列的后续内容将准确介绍源程序翻译成的内容。

此时，你可能还想知道解释器和编译器之间的区别。为了本系列的目的，我们先约定：如果一个翻译器将源程序翻译成机器语言，那么它是一个编译器。如果一个翻译器在未将源程序翻译成机器语言之前处理并执行源程序，那么它是一个解释器。从视觉上看，它大致是这样的：

我希望现在您已经确定自己真的想学习和构建解释器和编译器。您可以从这个关于解释器的系列中期待什么？

我们将为大型子集的Pascalopen in new window语言创建一个简单的解释器。在本系列结束时，您将拥有一个可工作的Pascal解释器和一个源级调试器，类似于Python的pdbopen in new window。

您可能会问，为什么是Pascal？首先，它不是我为这个系列而想出的虚构语言：它是一个真正的编程语言，具有许多重要的语言结构。一些古老但有用的计算机科学书籍在其中的示例中使用了Pascal编程语言（我知道选择一种语言来构建解释器的原因不是特别令人信服，但我认为学习非主流语言也是一种很好的改变：）

以下是一个Pascal阶乘函数的示例，您将能够使用自己的解释器解释它，并使用您沿途创建的交互式源级调试器进行调试：

program factorial;

function factorial(n: integer): longint;
begin
	if n = 0 then
		factorial := 1
	else
		factorial := n * factorial(n - 1);
end;

var
	n: integer;

begin
	for n := 0 to 16 do
		writeln(n, '! = ', factorial(n));
end.

Pascal解释器的实现语言将是Python，但您可以使用任何语言，因为所提出的想法不依赖于任何特定的实现语言。好的，让我们开始吧。准备，开始！

您将通过编写一个算术表达式的简单解释器（也称为计算器）开始您的第一次探索解释器和编译器。今天的目标相当简单：使您的计算器能够处理两个一位数整数的加法，例如3+5。以下是您的计算器，抱歉，解释器的源代码：

# Token types
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis

INTEGER, PLUS, EOF = 'INTEGER', 'PLUS', 'EOF'

class Token(object):
	def **init**(self, type, value):
		# token type: INTEGER, PLUS, or EOF
		self.type = type
		# token value: 0, 1, 2. 3, 4, 5, 6, 7, 8, 9, '+', or None
		self.value = value

	def __str__(self):
    """String representation of the class instance.

    Examples:
        Token(INTEGER, 3)
        Token(PLUS '+')
    """
    return 'Token({type}, {value})'.format(
        type=self.type,
        value=repr(self.value)
    )

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

class Interpreter(object):
	def **init**(self, text):
		# client string input, e.g. "3+5"
		self.text = text
		# self.pos is an index into self.text
		self.pos = 0
		# current token instance
		self.current_token = None

	def error(self):
    raise Exception('Error parsing input')

	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.
    """
    text = self.text

    # is self.pos index past the end of the self.text ?
    # if so, then return EOF token because there is no more
    # input left to convert into tokens
    if self.pos > len(text) - 1:
        return Token(EOF, None)

    # get a character at the position self.pos and decide
    # what token to create based on the single character
    current_char = text[self.pos]

    # if the character is a digit then convert it to
    # integer, create an INTEGER token, increment self.pos
    # index to point to the next character after the digit,
    # and return the INTEGER token
    if current_char.isdigit():
        token = Token(INTEGER, int(current_char))
        self.pos += 1
        return token

    if current_char == '+':
        token = Token(PLUS, current_char)
        self.pos += 1
        return token

    self.error()

	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 expr(self):
    """expr -> INTEGER PLUS INTEGER"""
    # set current token to the first token taken from the input
    self.current_token = self.get_next_token()

    # we expect the current token to be a single-digit integer
    left = self.current_token
    self.eat(INTEGER)

    # we expect the current token to be a '+' token
    op = self.current_token
    self.eat(PLUS)

    # we expect the current token to be a single-digit integer
    right = self.current_token
    self.eat(INTEGER)
    # after the above call the self.current_token is set to
    # EOF token

    # at this point INTEGER PLUS INTEGER sequence of tokens
    # has been successfully found and the method can just
    # return the result of adding two integers, thus
    # effectively interpreting client input
    result = left.value + right.value
    return result

	def main():
		while True:
			try:
				# To run under Python3 replace 'raw_input' call
				# with 'input'
				text = raw_input('calc> ')
			except EOFError:
				break
			if not text:
				continue
			interpreter = Interpreter(text)
			result = interpreter.expr()
			print(result)

if __name__ == '__main__':
	main()

将上述代码保存到*calc1.pyopen in new window文件中，或直接从GitHubopen in new window下载它。在您深入了解代码之前，在命令行上运行计算器并看到它在工作。与它一起玩！以下是我笔记本电脑上的一个示例会话（如果您想在Python3下运行计算器，则需要使用input替换raw_input*）：

$ python calc1.py
calc> 3+4
7
calc> 3+5
8
calc> 3+9
12
calc>

为了使您的简单计算器正常工作而不抛出异常，您的输入需要遵循以下规则：

  • 仅允许单个数字整数输入
  • 目前仅支持加法运算
  • 输入中不允许出现任何空格字符

这些限制是为了使计算器简单。别担心，您很快就会使它变得相当复杂。

好的，现在让我们深入了解一下您的解释器是如何工作以及如何评估算术表达式的。

当您在命令行上输入表达式3+5时，您的解释器会收到一个字符串*“3+5”。为了让解释器真正理解该字符串该如何处理，它首先需要将输入“3+5”拆分成称为标记的组件。标记是具有类型和值的对象。例如，对于字符串“3”*，标记的类型将是INTEGER，相应的值将是整数3。

将输入字符串拆分为标记的过程称为词法分析。因此，您的解释器首先需要读取字符输入并将其转换为标记流。执行此操作的解释器部分称为词法分析器，或简称词法分析器。您可能还会遇到相同组件的其他名称，例如扫描仪或标记生成器。它们都意味着相同的功能：将字符输入转换为标记流的解释器或编译器的部分。

Interpreter类的get_next_token方法是您的词法分析器。每次调用它时，您都会获得从传递给解释器的字符输入创建的下一个标记。让我们更仔细地查看该方法本身，并了解它如何实际执行将字符转换为标记的工作。输入存储在变量text中，该变量保存输入字符串，pos是该字符串中的索引（将字符串视为字符数组）。pos最初设置为0，指向字符“3”。该方法首先检查字符是否为数字，如果是，则将pos增加1并返回一个标记实例，其类型为INTEGER，值设置为字符串“3”的整数值，即整数3：

现在，pos指向text中的*‘+’字符。下一次调用该方法时，它会测试在位置pos处的字符是否为数字，然后测试该字符是否为加号，这是真的。结果，该方法会增加pos并返回一个具有类型PLUS和值‘+’*的新标记：

现在，pos指向字符*‘5’。当你再次调用get_next_token方法时，该方法会检查它是否为数字，是的，所以它会增加pos并返回一个值为整数5的新的INTEGER*令牌：

因为 pos 索引现在已经超过了字符串“3+5”的末尾，所以每次调用 get_next_token 方法时它都会返回 EOF 标记：

试一下，看看您的计算器的词法分析器组件如何工作：

>>> from calc1 import Interpreter
>>>
>>> interpreter = Interpreter('3+5')
>>> interpreter.get_next_token()
Token(INTEGER, 3)
>>>
>>> interpreter.get_next_token()
Token(PLUS, '+')
>>> interpreter.get_next_token()
Token(INTEGER, 5)
>>> interpreter.get_next_token()
Token(EOF, None)

现在，您的解释器可以访问由输入字符生成的令牌流，解释器需要做某些事情：它需要在从词法分析器 get_next_token 得到的扁平令牌流中找到结构。您的解释器期望在该流中找到以下结构：INTEGER -> PLUS -> INTEGER。也就是说，它试图找到一系列令牌：整数，后跟加号，后跟整数。

负责查找和解释该结构的方法是 expr。该方法验证令牌序列确实对应于所期望的令牌序列，即 INTEGER -> PLUS -> INTEGER。在成功确认结构之后，它通过将 PLUS 左侧令牌的值和右侧令牌的值相加来生成结果，从而成功解释您传递给解释器的算术表达式。

expr 方法本身使用辅助方法 eat 来验证传递给 eat 方法的标记类型是否与当前标记类型匹配。匹配传递的标记类型后，eat 方法获取下一个标记并将其分配给 current_token 变量，从而有效地“吃掉”当前匹配的标记并在标记流中推进虚拟指针。如果标记流中的结构不符合预期的 INTEGER PLUS INTEGER 标记序列，则 eat 方法会抛出异常。

让我们回顾一下解释器如何评估算术表达式：

  • 解释器接受一个输入字符串，比如说 “3+5”
  • 解释器调用 expr 方法来查找词法分析器 get_next_token 返回的标记流中的结构。它试图找到的结构是 INTEGER PLUS INTEGER 的形式。确认了结构后，它通过添加两个 INTEGER 标记的值来解释输入，因为此时解释器清楚它需要做的是将两个整数3和5相加。

恭喜你。你刚刚学会了如何构建你自己的解释器！

现在是练习的时间。

你没有想过仅仅阅读这篇文章就足够了吧？好的，动手做以下练习吧：

  1. 修改代码以允许输入多位整数，例如“12+3”。
  2. 添加一个跳过空格字符的方法，以便你的计算器可以处理带有空格字符的输入，例如“12 + 3”。
  3. 修改代码，而不是处理“+”，而是处理“-”，以计算减法，例如“7-5”。

检查你的理解

  1. 什么是解释器？
  2. 什么是编译器？
  3. 解释器和编译器之间有什么区别？
  4. 什么是标记？
  5. 将输入拆分为标记的过程的名称是什么？
  6. 做词法分析的解释器的部分称为什么？
  7. 解释器或编译器的这一部分的其他常用名称是什么？

在我完成这篇文章之前，我真的希望你承诺学习解释器和编译器。我希望你现在就开始学习。不要把它放在后面。不要等待。如果你只是浏览了文章，请重新开始。如果你仔细阅读了它但没有做练习，请现在做。如果你只做了一些，请完成剩下的。你明白了。而且你知道吗？签署承诺书，从今天开始学习解释器和编译器！

我，____，身心健康，特此承诺从今天开始致力于学习解释器和编译器，并达到100％了解它们的工作原理的水平！

签名:

日期：

签署它，日期，把它放在你每天都能看到的地方，以确保你坚守自己的承诺。并记住“承诺”的定义：

“承诺是在你说出它的心情已经消失后长时间坚持去做你说过的事情。”-达伦·哈迪

好的，今天就到这里。在这个迷你系列的下一篇文章中，您将扩展您的计算器以处理更多的算术表达式。敬请关注。

上次编辑于:
贡献者: Shen Yuan
默认页脚