再谈递归下降解析器：构建一个简单的算术表达式解析器
引言
在编译原理中，解析是将源代码转换为抽象语法树(AST)的过程。这一过程对于任何编程语言的实现都是至关重要的一步。递归下降解析是一种自顶向下的解析策略，它直接从文法开始构建解析函数。每个非终结符都有对应的解析函数，这些函数按照文法规则调用其他函数（包括自身），从而形成递归结构。本文将介绍如何使用Python实现一个简单的递归下降解析器，用于解析和计算基本的算术表达式。
什么是递归下降解析？
递归下降解析是一种自顶向下的解析方法，它通过为文法中的每个非终结符编写一个对应的解析函数来实现。这些函数根据文法规则递归地调用其他函数，从而逐步解析输入字符串。递归下降解析特别适合于LL(k)类型的文法，其中k表示向前查看的符号数目。
特点
- 易于理解和实现：因为其结构直观地反映了文法定义。
- 支持左递归：通过一些技巧可以处理大多数形式的左递归问题。
- 灵活性高：可以根据需要调整错误处理机制或添加额外的功能。
构建一个简单的算术表达式解析器
接下来，我们将使用Python语言来实现一个能够解析简单算术表达式的递归下降解析器。这里考虑的算术表达式仅包含加减乘除运算以及括号。
文法定义
首先定义我们的文法如下：
expr -> term ((PLUS | MINUS) term)*term -> factor ((MUL | DIV) factor)*factor -> NUMBER | (expr)
这里的PLUS, MINUS, MUL, DIV分别代表加、减、乘、除操作；NUMBER代表数字。
Python 实现
1. 定义正则表达式和Token
我们首先定义正则表达式来匹配各种符号，并使用collections.namedtuple来创建Token对象。
import re
import collections
NUM = r'(?P<NUM>\d+)'
PLUS = r'(?P<PLUS>\+)'
MINUS = r'(?P<MINUS>-)'
TIMES = r'(?P<TIMES>\*)'
DIVIDE = r'(?P<DIVIDE>/)'
LPAREN = r'(?P<LPAREN>\()'
RPAREN = r'(?P<RPAREN>\))'
WS = r'(?P<WS>\s+)'
master_pat = re.compile('|'.join([NUM, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, WS]))
# Tokenizer
Token = collections.namedtuple('Token', ['type', 'value'])
def generate_tokens(text):
scanner = master_pat.scanner(text)
for m in iter(scanner.match, None):
tok = Token(m.lastgroup, m.group())
if tok.type != 'WS':
yield tok
2. 解析器类
接下来，我们定义一个解析器类ExpressionEvaluator，该类实现了递归下降解析的方法。
class ExpressionEvaluator:
'''
Implementation of a recursive descent parser. Each method implements a single grammar rule.
Use the ._accept() method to test and accept the current lookahead token. Use the ._expect()
method to exactly match and discard the next token on on the input or raise a SyntaxError if it doesn't match.
'''
def parse(self, text):
self.tokens = generate_tokens(text)
self.tok = None
self.nexttok = None
self._advance()
return self.expr()
def _advance(self):
'Advance one token ahead'
self.tok, self.nexttok = self.nexttok, next(self.tokens, None)
def _accept(self, toktype):
'Test and consume the next token if it matches toktype'
if self.nexttok and self.nexttok.type == toktype:
self._advance()
return True
else:
return False
def _expect(self, toktype):
'Consume next token if it matches toktype or raise SyntaxError'
if not self._accept(toktype):
raise SyntaxError('Expected ' + toktype)
# Grammar rules follow
def expr(self):
"expression ::= term { ('+'|'-') term }*"
exprval = self.term()
while self._accept('PLUS') or self._accept('MINUS'):
op = self.tok.type
right = self.term()
if op == 'PLUS':
exprval += right
elif op == 'MINUS':
exprval -= right
return exprval
def term(self):
"term ::= factor { ('*'|'/') factor }*"
termval = self.factor()
while self._accept('TIMES') or self._accept('DIVIDE'):
op = self.tok.type
right = self.factor()
if op == 'TIMES':
termval *= right
elif op == 'DIVIDE':
termval /= right
return termval
def factor(self):
"factor ::= NUM | (expr)"
if self._accept('NUM'):
return int(self.tok.value)
elif self._accept('LPAREN'):
exprval = self.expr()
self._expect('RPAREN')
return exprval
else:
raise SyntaxError('Expected NUMBER or LPAREN')
使用示例
最后，我们可以使用这个解析器来解析和计算一些简单的算术表达式。
e = ExpressionEvaluator()
print(e.parse('2')) # 输出: 2
print(e.parse('2 + 3')) # 输出: 5
print(e.parse('2 + (3 + 4) * 5')) # 输出: 37
try:
print(e.parse('2 + (3 + * 4)')) # 应该抛出SyntaxError
except SyntaxError as e:
print(f"Syntax Error: {e}")
结论
递归下降解析提供了一种非常直观的方式来实现解析器，尤其适用于教育目的和小型项目。虽然它的效率可能不如某些专门设计的解析算法如LALR(1)，但对于许多应用场景来说已经足够强大了。通过本文提供的示例代码，你可以轻松地理解并实现一个简单的递归下降解析器，用于解析和计算基本的算术表达式。希望本文能帮助你掌握这项技术！
欢迎点赞、关注、转发、收藏！！！
