python - 创建 LL(1) 语法时出现问题

Question

我正在通过创建一个简单的递归下降解析器来学习解析器的工作原理。然而，我在将语法定义为 LL(1) 时遇到问题。我希望能够解析以下两个语句:

a = 1
a + 1

为此，我创建了以下语法规则:

statement:  assignent | expression
assignment: NAME EQUALS expression
expression: term [(PLUS|MINUS) term]
term:       NAME | NUMBER

但是，当使用 LL(1) 解析器时，这会导致歧义，因为当在 statement 规则中遇到 NAME 标记时，它不知道它是否是一个赋值 或不带前瞻的表达式。

Python 的语法是 LL(1)，所以我知道这是可以做到的，但我不知道如何做到。我查看了此处找到的 Python 语法规则 ( https://docs.python.org/3/reference/grammar.html )，但我仍然不确定它们是如何实现的。

任何帮助将不胜感激:)

Answer 1

只需将 = 视为优先级非常低的运算符。但是(除非您想要像 C 这样的语言，其中 = 实际上是一个优先级非常低的运算符)，您需要将其从内部(例如括号)表达式中排除。

如果您只有乘法和加法，您可以使用:

expression: factor ['+' factor]
factor:     term ['*' term]
term:       ID | NUMBER | '(' expression ')'

这是运算符优先级指南: 具有更高的优先级，因为 + 的参数可以包含 s，但反之则不然。所以我们可以添加分配:

statement: expression ['=' expression]

不幸的是，这将允许，例如:

(a + 1) = b

这是不可取的。所以它需要被消除，但是当产生式被接受时(通过检查第一个表达式的形式)，而不是在语法本身中，可以消除它。据我了解，这就是 Python 解析器的作用；请参阅有关 test 和关键字的长评论。

如果您使用 LR(1) 解析器，则不会出现此问题。