实现一个简单的解释器（6）
Xlgd 人气:0
译自：https://ruslanspivak.com/lsbasi-part6/
（已获得作者授权）
今天，我们通过将带括号的表达式添加到语法，并实现一个能够计算任意深度嵌套表达式的解释器来结束对算术表达式的讨论。
让我们开始吧！
首先，让我们修改语法以支持括号内的表达式，正如在第5部分中所记得的那样，factor规则用于表达式中的基本单位，在那篇文章中，我们仅有的基本单位是整数，今天我们添加了另外一个基本单位，也就是带括号的表达式。
这是我们更新的语法：
expr和term与第5部分完全相同，唯一的变化是factor的产生式，其中LPAREN表示左括号'('，RPAREN表示右括号')'，而括号之间的非终结符expr表示expr规则。
这是factor的更新语法图：
因为expr和term的语法规则没有改变，所以它们的语法图看起来与[第5部分](https://www.cnblogs.com/Xlgd/p/12402997.html)中的相同：
这是我们新语法的一个有趣功能：递归，如果尝试推导表达式2 * (7 + 3)，则将从expr起始符开始，之后将递归地再次使用expr规则来推导表达式(7 + 3)这一部分。
让我们根据语法分解表达式2 *(7 + 3)：
好的，让我们开始将新的更新语法转换为代码。
以下是对上一篇文章代码的主要更改：
1、对Lexer进行修改，以返回另外两个标记：LPAREN用于左括号，而RPAREN用于右括号。
2、对解释器的factor函数进行修改，可以解析(parse)除整数以外的带括号的表达式。
这是计算器的完整代码，可以计算任意数量的加，减，乘和除整数运算以及带有任意深度嵌套的带括号的表达式：
```pascal
# 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:
# 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()
```
将上面的代码保存到calc6.py文件中，体验一下新解释器是否正确计算了具有不同运算符和括号的算术表达式。
这是运行效果：
```
$ python calc6.py
calc> 3
3
calc> 2 + 7 * 4
30
calc> 7 - 8 / 4
5
calc> 14 + 2 * 3 - 6 / 2
17
calc> 7 + 3 * (10 / (12 / (3 + 1) - 1))
22
calc> 7 + 3 * (10 / (12 / (3 + 1) - 1)) / (2 + 3) - 5 - 3 + (8)
10
calc> 7 + (((3 + 2)))
12
```
这是今天的练习：
1、如本文所述，编写你自己的算术表达式解释器版本，记住：重复是所有学习的源泉。
嘿，你一直阅读到最后！ 恭喜你已经学会了如何实现一个基本的递归下降解析器/解释器，它可以评估非常复杂的算术表达式。
在下一篇文章中，我将详细讨论递归下降解析器。 我还将在解释器和编译器的构造中介绍一个重要且广泛使用的数据结构，我们将在整个系列中使用。
请继续关注，很快再见。在此之前请你继续实现自己的解释器，最重要的是：尽情享受这一过程！
加载全部内容