02 四则运算解释器 | 《Let’s Build A Simple Interpreter》
本文最后更新于:2021年8月26日
这篇文章将给出一个针对合法的任意长度的四则运算的解释器。
概念与术语
token
token 是一个有类型的值的对象。例如对于字符串“3 + 4”来说,“3”是类型为 INTEGER 值为 3 的 token,“+”是类型为 PLUS 值为 + 的 token。
lexer
把输入字符串拆分成 token 的过程被称为词法分析(lexical analysis)。解释器中读取输入的字符串并把他转化成 token 流的部分被称为词法分析器(lexical analyzer),简称 lexer。有时候也会被叫做别的名字,如 scanner 或 tokenizer。它们的含义是一样的:表示解释器或编译器中将输入的字符串转化为 token 流的部分。
lexeme
lexeme 是组成 token 的一个字符序列。在下面的图片中是一些 token 和 lexeme 的例子:
lexeme 是组成编程语言的最小的有意义的单元实体。
parser
从 token 流中查找结构,或者说从 token 流中识别组合,的过程叫做 parsing。解释器或编译器中执行这部分任务的叫 parser。
interpreter
这里区分下 parser 和 interpreter:前者识别出来 “3”、“+”、“4” 这个组合,后者则将这个组合翻译成具体的算数表达式。
总结一下:lexer 获取输入并把它转化为 token 流(词法分析器完成词法分析),parser 从 lexer 提供的 token 流中识别结构(句法分析器完成句法分析),interpreter 在 parser 成功识别到一个合法的算术表达式之后求得其结果(解释器完成解释)。
语法
首先介绍表示编程语言句法的广泛使用的表示法:上下文无关语法(context-free grammars)或 BNF(Backus-Naur Form)。这篇文章不会使用纯 BNF 记法,而是一个修改过的 EBNF 记法。有一套工具,叫解析器生成器(parser generator),可以把语法做为输入并自动根据它生成一个解析器。
语法是由一系列规则组成的,也被称为生成式(production)。在这个语法中目前有两条规则:
expr : factor ((MUL|DIV) factor)*
factor : INTEGER
一条规则由一个非终结符(叫做 head 或生成式的左边),一个冒号,和一系列终结符和/或非终结符(叫做 body 或生成式的右边)。在这个例子中,像 MUL、DIV、INTEGER 这样的 token 被称为终结符,expr、factor 这样的被称为非终结符。
这个语法有点像正则表达式,是用来从 token 流中匹配表达式的。每个符号的意义如下:
|
:多选一,符号表示“或”。所以 (MUL | DIV) 表示 MUL 或 DIV(...)
:被括号包围表示把终结符和/或非终结符组成一组,就像 (MUL | DIV)(...)*
:分组中的内容被匹配 0 或多次
阅读这个语法时,需要从下到上阅读:
- factor 是一个整数(INTEGER)
- expr 是一个 factor 后面可选地跟一个乘或除运算符再跟另一个 factor,后面也相应可选地跟一个乘或除运算符再跟另一个 factor,如此重复
前面展示了一个基础的语法,下面我们来看一个可以完整表达四则运算的语法:
expr : term ((PLUS | MINUS) term)*
term : factor ((MUL | DIV) factor)*
factor : INTEGER | LPAREN expr RPAREN
同样从下到上阅读这个语法:
- factor 是一个整数,或者是用括号括起来的 expr
- term 是一个 factor 后面可选地跟一个乘或除运算符再跟另一个 factor,后面也相应可选地跟一个乘或除运算符再跟另一个 factor,如此重复
- expr 是一个 term 后面可选地跟一个加或减运算符再跟另一个 term,后面也相应可选地跟一个加或减运算符再跟另一个 term,如此重复
这个语法中有一个有趣的特点──它是递归的。如果你尝试派生表达式 2 * (7 + 3), 会 由开始符号 expr 开始并在某一时刻递归地使用规则 expr 来派生原始算术表达式中的 “(7 + 3)” 部分。现在尝试根据语法来分解表达式 2 * (7 + 3), 来看看它是如何工作的:
完整代码
# Token types
#
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis
INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = (
'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'
)
class Token(object):
def __init__(self, type, value):
self.type = type
self.value = value
def __str__(self):
"""String representation of the class instance.
Examples:
Token(INTEGER, 3)
Token(PLUS, '+')
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. "4 + 2 * 3 - 6 / 2"
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(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()
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):
"""factor : INTEGER | LPAREN expr RPAREN"""
token = self.current_token
if token.type == INTEGER:
self.eat(INTEGER)
return token.value
elif token.type == LPAREN:
self.eat(LPAREN)
result = self.expr()
self.eat(RPAREN)
return result
def term(self):
"""term : factor ((MUL | DIV) factor)*"""
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 result
def expr(self):
"""Arithmetic expression parser / interpreter.
calc> 7 + 3 * (10 / (12 / (3 + 1) - 1))
22
expr : term ((PLUS | MINUS) term)*
term : factor ((MUL | DIV) factor)*
factor : INTEGER | LPAREN expr RPAREN
"""
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
def main():
while True:
try:
text = input('calc> ')
except EOFError:
break
if not text:
continue
lexer = Lexer(text)
interpreter = Interpreter(lexer)
result = interpreter.expr()
print(result)
if __name__ == '__main__':
main()
评论系统采用 utterances ,加载有延迟,请稍等片刻。