Let's Build A Simple Interpreter 学习笔记（Part 1 ~ Part 6）
概述
原教程地址：Let's Build A Simple Interpreter（构建一个简单的解释器）
前六部分主要在做一个计算器，重点在于 Lexer 与 Parser 的构建。
Token 对象
Token 对象只有两个属性，类型和值，同时实现了 __str__ 函数，便于调试。
词法分析部分
Lexer 用途为处理源程序，将其转换为 Token 序列，便于后续处理。
Lexer 对外暴露的接口只有 get_next_token()，其返回值为下一个 token 对象，get_next_token() 函数内部逻辑主要为一个循环体，其一个接一个地读取源程序中的字符，并根据这些字符产生出相应的 Token 对象。
对于单字符的 Token，例如 +，- 等运算符，只取出一个字符即可；然而对于数字类型的 Token，我们需要一个工具函数 integer() 协助处理。
class Lexer(object):
def __init__(self, text):
self.text = text # 存储源程序
self.pos = 0 # 记录当前已经处理到的位置
self.current_char = self.text[self.pos] # 当前正在处理的字符
def error(self):
raise Exception('Invalid character')
def advance(self): # 该函数用于加载下一个字符（维护 pos 和 current_char 变量）
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): # 将数字字符拼接成数字
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): # 供外界调用，按照顺序每次生成一个 Token 提高给调用者
while self.current_char is not None: # 内部的主循环，循环自然结束意味着源文件读取完毕，返回 EOF
if self.current_char.isspace():
self.skip_whitespace()
continue
if self.current_char.isdigit(): # 根据当前字符判断出要生成的 token 类型
return Token(INTEGER, self.integer())
if self.current_char == '+':
self.advance()
return Token(PLUS, '+')
if self.current_char == '-':
self.advance()
return Token(MINUS, '-')
if self.current_char == '*':
self.advance()
return Token(MUL, '*')
if self.current_char == '/':
self.advance()
return Token(DIV, '/')
if self.current_char == '(':
self.advance()
return Token(LPAREN, '(')
if self.current_char == ')':
self.advance()
return Token(RPAREN, ')')
self.error() # 程序执行到这里意味着出现了 unexpected character
return Token(EOF, None) # 源文件读取完毕，返回 EOF
语法分析部分
该部分以之前词法分析产生的 Token 流为输入，输出即算术表达式的值。
具体实现上即 Interpreter 对象，其内置一个 lexer 对象用以提供输入，此外有一个 eat(token_type) 的工具函数，其用于检测当前 token 的类型是否满足期望，若满足则更新 current_token，否则报 unexpected token 的错误。
之后我们根据上下文无关文法构造相应的函数即可。在这个计算器的例子中，文法为：
factor -> INTEGER | LPAREN expr RPAREN
term -> factor ((MUL | DIV) factor)*
expr -> term ((PLUS | MINUS) term)
具体要怎么构建函数呢？以第二行为例：
def term(self):
"""term -> factor ((MUL | DIV) factor)*"""
result = self.factor() # 箭头右边的第一个元素为一个 factor，我们就调用之前写的 factor 函数
while self.current_token.type in (MUL, DIV): # 随后是 (pattern)*，因此我们需要一个循环
token = self.current_token
if token.type == MUL:
self.eat(MUL) # 更新当前 token
result = result * self.factor() # 下一个 token 为一个 factor，因此我们调用之前写的 factor 函数
elif token.type == DIV:
self.eat(DIV)
result = result // self.factor()
return result