自己手动编写一个简单的解释器 Part 4

接之前的 Part 1，Part 2 和 Part 3：

• 自己手动编写一个简单的解释器 Part 1 

• 自己手动编写一个简单的解释器 Part 2

• 自己手动编写一个简单的解释器 Part 3

你是只被动学习这篇文章中的材料还是主动练习它？我真的希望你能够主动练习它：

记得孔子所说的吗？

在之前的文章中你已经学习到了怎样利用算术表达式中的加减操作符进行解析（识别）并且翻译它们，比方”7-3+2-1“。你还学会了语法图并且知道它们是怎样被使用辨别一个编程语言中的语法的。

今天你将要学习怎样利用在算术表达式中的任何数量的乘除操作符进行解析和翻译，比方”7*4、2*3“。这篇文章中的中的除操作符指的是整除，因此如果表达式是”9/4“之类的，那么结果将会是整数：2。

今天我将谈论相当多的另一个广泛使用的符号，这些是用来规定一个编程语言的语法的。它叫做上下文无关语法（简称语法）或者 BNF（巴科斯范式形式)。这篇文章的目的是我将不是使用纯粹的 BNF 符号而是更多的使用像 EBNF 这样的修饰了的符号。

这里是使用语法的几个原因：

1.一种语法以简明的方式规定了其语法规则。不像语法图那样，语法本身是很浓缩的。你将看到我在之后的文章会更多地使用语法。

2.一种语法能充当大量的文档。

3.一种语法是一个好的起点即使是你手动从你的手稿中写语法分析器。通常是你只要将语法通过一组简单的规则转换成代码。

4.这里有一组工具，称为语法分析产生器，它能够接受语法作为输入并且基于此语法自动产生语法分析器。我将在接下来的系列中谈谈这些工具。

现在，让我们谈谈语法机制方面的问题吧？

这是一种语法描述的算术表达式像“7*4/2*3”这样（这只是可由语法产生的众多表达式中的一种）：

一种语法包含一系列的规则，也称作产品。以下是我们的语法的两个规则：

一个规则包含一个非终端，称为产品的 head(头) 或者 left-hand side(左手端)，一个冒号和一系列的终端和/或者非终端，称为产品的 body(体) 或者 right-hand side(右手端)：

在上面我所展示的语法中，像 MUL，DIV 和 INTEHER 这样的标记称作终端，像 expr 和 facto 这样的变量称作非终端。通常，非终端包含一系列的终端和/或者非终端：

第一条规则的左手端的非终端符号称之为起始符。我们的语法中的情况是，起始符是个表达式。

你可以视这一规则中的表达式为如下定义：“一个表达式可以是随意跟随着一个乘法运算符或者除法运算符的一个因子，同时这跟随着的乘法或除法运算符又可以是随意跟随着另外一个这样因子的运算符，反过来这另外一个因子又可以是随意跟随着一个乘法或者除法运算符的一个因子，同时这跟随着的乘法或除法运算符又可以跟随着另外一个因子，如此反复。”

什么是因子？这篇文章的目的是一个因子仅是一个整数。

我们先快速浏览一下语法中的所有符号及它们的意义。

• | -替代选择。一杠表示“或”的意思。因此（MUL|DIV）表示即可以是 MUL 也可以是DIV。

• (...)  -一个开放和关闭的圆括号表示在(MUL|DIV)中的一组终端和/或者非终端。

• (...)*  -以零次或者多次在组内进行内容匹配。

如果你之前与正则表达式打过交道，那么这些符号 |，()，和 (...)* 对于你来说应该是相当熟悉的。

一个语言的语法定义了这个语言可以支持多少种的语句。下面，我们将具体说明如何通过上面定义的语法来产生这个语法支持的语句集合：说起来这个过程也很简单，就是从起始符号 expr 开始，不断地将非终结符号使用一个规则的主题进行替换，直到整个表达式中只包含终结符号。通过不断重复这样的过程得到的语句集合就形成了这个语法定义的语言。

对于一个具体的算术表达式，如果无法通过语法定义推到出来，那么就意味着这个语法定义不支持这种算术表达式，那么对应的语法分析器在看到这个算术表达式的时候就会产生一个语法错误的提示。

让我们举一些具体的日子，来看看我们前面定义的语法可以产生哪些语句。

• 下图显示了根据语法定义如何产生表达式 3 :

• 下图显示了根据语法定义如何产生表达式 3 * 7 :



• 下图显示了根据语法定义如何产生表达式 3 * 7 / 2 :



看到这里，大家可能会大声说，这也太理论了吧！

但我第一次接触到语法以及相关术语的时候，我就想下面途中所画的那样，觉得头晕眼花，无所适从:

从我的经验来看，现在的你应该也是一头雾水，而不会像下面图中的人一样说我全部都搞懂了:

我着实花了一段时间才搞清楚这些标记，他们是如何用来描述语法的，以及在分析器和文法分析其中是如何使用它们的，但是我要说从长远来说，你现在所花的时间是觉得值得的，因为它们是如此广泛地应用在编译器实践中（类似的分析工具也可以应用在编译器外的其他地方）。所以为什么不在现在就搞清楚这些东西呢？:）

下面，让我们一起看看如何从语法图产生正确的代码。

下面我们列出了将一个语法表示翻译成代码的基本步骤，根据这些步骤，你可以方便地将一个语法表示翻译解释器代码:

1. 将语法表示中定义的每一条规则 R， 翻译成一个方法, 而对这个规则的应用则翻译成一个方法调用: R() . 根据相似的方法，将规则的定义翻译成方法的实现。

2. 将 (a1 | a2 | aN) 翻译成一个  if-elif-else 语句

3. 将 (…)* 翻译成一个可以执行0次或者多次的 while 语句

4. 将每个对token T 的应用变成一个对  eat  方法的调用： eat(T) 。在  eat  方法中，如果当前的 token 和传入的 token 一致，那么  eat  方法将消费掉这个 token，并且将下一个分析出的 token 赋值给  current_token  变量。

根据上面的步骤，对于我们前面定义的语法表示，我们可以得到下面的这张图所示的翻译过程:

下面就让我们来真正实现我们的分析器吧。

在我们当前定义的文法中有 2 个规则定义: 一个规则叫 expr， 另外一个规则叫  factor 。让我们从最简单的规则  factor  开始. 根据我们上面讲的翻译规则，我们需要创建一个方法叫做  factor （规则1），同时根据规则 4，这个方法只有一个对  eat  方法的调用（ eat(INTEGER) ):

def factor(self):     self.eat(INTEGER)

看到了吧，根据翻译规则，把这条语法规则翻译成代码就是这么简单

继续！

规则 expr  根据规则 1 被翻译成一个叫做  expr  的方法。根据翻译规则 1，2 和 3，这个方法的执行将包括：1）调用  factor  方法；2）(...)*被翻译成一个 while 循环；3） (MUL | DIV) 这个被翻译成一个 if..else 语句。把这些东西合在一起就变成了下面的代码:

def expr(self): self.factor() while self.current_token.type in (MUL, DIV):  token = self.current_token  if token.type == MUL:   self.eat(MUL)   self.factor()  elif token.type == DIV:   self.eat(DIV)   self.factor() 

现在请花一点时间阅读上面的翻译过程，确保你完全理解了这部分的内容。

我把以上的代码放在一个叫做 parser.py  的文件中 （ 你可以直接从  GitHub 下载这个文件），这个文件包含了词法分析器代码，但是没有包含解释器（因此不会得到最终的计算结果）。但你运行这个程序的时候，程序将会显示一个"calc>"提示，你可以在这个提示之后输入算术表达式，程序将告诉你这个表达式是否合法。

下图显示的是我在我自己的机器上运行这个程序的情况：

$ python parser.py calc> 3 calc> 3 * 7 calc> 3 * 7 / 2 calc> 3 * Traceback (most recent call last):   File "parser.py", line 155, in <module>     main()   File "parser.py", line 151, in main     parser.parse()   File "parser.py", line 136, in parse     self.expr()   File "parser.py", line 130, in expr     self.factor()   File "parser.py", line 114, in factor     self.eat(INTEGER)   File "parser.py", line 107, in eat     self.error()   File "parser.py", line 97, in error     raise Exception('Invalid syntax')Exception: Invalid syntax

（强烈建议读者在本地尝试一下这个代码）

这里我忍不住要再强调一次我们的语法图，下面是我们的 expr  规则的语法图：

现在是时候来实现我们的算术表达式解释器了。下面是完整的源代码，它实现了一个可以运行合法算术表达式的计算器。如果你认真阅读了代码，你会发现现在我把词法分析器变成了一个单独的类 --- Lexer 类，而且解释器也修改成接受 Lexer 实例来进行词法分析。:

# Token types## EOF (end-of-file) token is used to indicate that# there is no more input left for lexical analysisINTEGER, MUL, DIV, EOF = 'INTEGER', 'MUL', 'DIV', 'EOF' class Token(object):  def __init__(self, type, value):   # token type: INTEGER, MUL, DIV, 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(MUL, '*')  """   return 'Token({type}, {value})'.format(    type=self.type,    value=repr(self.value)   )  def __repr__(self):   return self.__str__() class Lexer(object):  def __init__(self, text):   # client string input, e.g. "3 * 5", "12 / 3 * 4", etc   self.text = text   # self.pos is an index into self.text   self.pos = 0   self.current_char = self.text[self.pos]  def error(self):   raise Exception('Invalid character')  def advance(self):   """Advance the `pos` pointer and set the `current_char` variable."""   self.pos += 1   if self.pos > len(self.text) - 1:    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):   """Return a (multidigit) integer consumed from the input."""   result = ''   while self.current_char is not None and self.current_char.isdigit():    result += self.current_char    self.advance()   return int(result)  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.skip_whitespace()     continue    if self.current_char.isdigit():     return Token(INTEGER, self.integer())    if self.current_char == '*':     self.advance()     return Token(MUL, '*')    if self.current_char == '/':     self.advance()     return Token(DIV, '/')    self.error()   return Token(EOF, None) class Interpreter(object):  def __init__(self, lexer):   self.lexer = lexer   # set current token to the first token taken from the input   self.current_token = self.lexer.get_next_token()  def error(self):   raise Exception('Invalid syntax')  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.lexer.get_next_token()   else:    self.error()  def factor(self):   """Return an INTEGER token value.  factor : INTEGER  """   token = self.current_token   self.eat(INTEGER)   return token.value  def expr(self):   """Arithmetic expression parser / interpreter.  expr   : factor ((MUL | DIV) factor)*  factor : INTEGER  """   result = self.factor()   while self.current_token.type in (MUL, DIV):    token = self.current_token    if token.type == MUL:     self.eat(MUL)     result = result * self.factor()    elif token.type == DIV:     self.eat(DIV)     result = result / self.factor()   return resultdef  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   lexer = Lexer(text)   interpreter = Interpreter(lexer)   result = interpreter.expr()   print(result)if __name__ == '__main__': main() 

你可以从 GitHub 直接下载这个文件，然后在你自己的机器上进行测试。

这是在我的笔记本上运行的示例：

$ python calc4.py calc> 7 * 4 / 2 14 calc> 7 * 4 / 2 * 3 42 calc> 10 * 4  * 2 * 3 / 8 30

我知道你迫不及待了:)下面是今天新的练习：

• 写一个语法，描述包含任意数量的+，- ，*，或/操作。语法起源于表达式，如“2 +7* 4”，“7 - 8/4”，“14 +2 * 3 - 6/2”，等等。

• 使用语法，写一个解释器，可以计算包含任意数量的+，- ，*，或/操作。你的解释器应该能够处理诸如“2 +7* 4”，“7 - 8/4”，“14 +2 * 3 - 6/2”，等等。

• 如果你已经完成了上述练习，放松和享受吧:)

课后练习

请尝试回答下面的问题来测试你对今天的内容理解了多少，下图是今天的课程所使用的语法图，在你回到下面的问题的时候，可以参考下图获得语法信息：

1. 什么叫做上下文无关文法?

2. 本文中的文法包含多少规则定义，以及这些规则可以产生多少语句？

3. 什么叫终结符? (请找出上图中所有的终结符)

4. 什么叫非终结符? (请找出上图中所有的非终结符)

5. 什么叫规则头? (找出上图所有的规则头)

6. 什么叫规则体? (找出上图所有的规则体)

7. 那个符号是上图所示文法的起始符号?

这篇文章包含了大量的理论知识，再次 恭喜你通读了这篇文章，对此 我深深以你为荣。

过段时间我会再发布一些关于解释器的新的文章，请保持你的求知欲，并且尝试完成本站所留的作业，这些作业能够让你更好地掌握本章所学的内容。