python - 如何将具有多个非终端产生的 EBNF 转换为函数调用

Question

我正在学习编译器构造，并且已经设法创建可以解释简单代码行的小型 Python 脚本。但是，我正在努力实现提供非终端产品选择的 EBNF 语句的正确方法。我们以这个 EBNF 为例：

expression ::= term
               | expression '+' term
               | expression '-' term

term       ::= factor
               | term '*' factor
               | term '/' factor

factor     ::= NUMBER
               | '(' expression ')'

这是一个 EBNF，用于解释简单的数学表达式，例如 5 * (3 + 4)。

从编译器文献中，我了解了用if语句识别终端符号（令牌）的基本方法，对于非终端产品，我们称之为子函数。有了这些知识，我就可以编写解释的函数factor：

def factor():
    if token.type == 'NUMBER':
        number = token.value
        eat('NUM')
        return number
    elif token.type == '(':
        eat('(')
        expr = self.expression()
        eat(')')
        return expr

expression实现终端和term非终端的推荐方法是什么？我使用了一个peek()函数来查看一个标记：

def expression():
    next_token = peek()
    if token.type in ['NUMBER', '('] and next_token.type == '+':
        expression = expression(token)
        eat('+')
        term = term()
        return (expression, '+', term)
    elif token.type in ['NUMBER', '('] and next_token.type == '-':
        expression = expression(token)
        eat('-')
        term = term()
        return (expression, '-', term)
    elif token.type in ['NUMBER', '(']:
        term = term()
        return term

我觉得很奇怪，我必须通过两个级别的 EBNF (term和factor) 来找到我可以用来决定做出哪些选择的终端符号expression（如if token.type in ['NUMBER', '('] and next_token.type == '+':）。我不确定的另一件事是，上述方法term需要最后进行测试。这意味着在 EBNF 中测试非终端产品的顺序变得很重要。这是这样做的正确方法吗？

标签： pythoncompiler-constructionebnf