Python 的语法是 LL(1) 吗？

Question

这个问题可能有重复，但对我来说还不够具体。

python 语法声称是 LL(1)，但我注意到Python 语法中的一些表达式确实让我感到困惑，例如，以下函数调用中的参数：

foo(a)
foo(a=a)

对应于以下语法：

argument: ( test [comp_for] |
            test '=' test |
            '**' test |
            '*' test )

test在语法的第一个位置出现两次。这意味着仅通过查看testPython 无法确定它是test [comp_for]或test '=' test.

更多例子：

comp_op: '<'|'>'|'=='|'>='|'<='|'<>'|'!='|'in'|'not' 'in'|'is'|'is' 'not'

注意'is'和'is' 'not'

subscript: test | [test] ':' [test] [sliceop]

test 也出现了两次。

我对 LL(1) 的理解是错误的吗？Python 是否在词法分析或解析期间对语法进行了一些变通，以使其 LL(1) 可处理？谢谢大家。

Answer 1

Python 文档中提供的语法（并用于生成 Python 解析器）以扩展 BNF 的形式编写，其中包括“操作符”，例如可选性 ( [a]) 和 Kleene 闭包 ( (a b c)*)。然而，LL(1) 是一个仅适用于简单的上下文无关文法的类别，它没有这样的运算符。因此，询问该特定语法是否为 LL(1) 是一个类别错误。

为了使问题有意义，必须将语法转换为简单的上下文无关语法。这当然是可能的，但没有规范转换，Python 文档也没有解释所使用的精确转换。一些转换可能会产生 LL(1) 文法，而另一些则可能不会。（实际上，对 Kleene 星的简单翻译很容易导致歧义，根据定义，对于任何 k，这都不是 LL(k)。）

实际上，Python 解析装置将语法转换为可执行的解析器，而不是上下文无关的语法。就 Python 的实用目的而言，能够构建一个预测解析器，仅预测一个标记就足够了。由于预测解析器可以使用条件语句和循环等控制结构，因此不需要完全转换为上下文无关文法。因此，可以使用 EBNF 产生式——就像文档化的语法一样——它们不是完全左因式的，甚至可以使用转换为 LL(1) 的 EBNF 产生式：

simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE

在上面的产生式中， 的重复(';' small_stmt)*后面可能跟着 a ';'，这意味着简单的while循环不会正确地表示产生式。我不知道 Python 解析器生成器如何处理这个产生式，但是可以在扩展重复后通过左因子分解将其转换为 CFG：

simple_stmt: small_stmt rest_A
rest_A     : ';' rest_B
           | NEWLINE
rest_B     : small_stmt rest_A
           | NEWLINE

类似地，整个 EBNF 可以转换为 LL(1) 文法。之所以没有这样做，是因为该练习对于解析或解释语法既无用处。读起来很费劲，EBNF 可以直接转化为解析器。

这与 Python 是否为 LL(1) 的问题略微无关，因为如果该语言存在 LL(1) 语法，则该语言正是 LL(1)。一种语言总是有无限可能的文法，包括对于任何 k 不是 LL(k) 的文法，甚至不是上下文无关的文法，但这与语言是否是 LL(1)的问题无关)：如果存在一种 LL(1) 文法，则语言为 LL(1)。（我知道这不是最初的问题，所以我不会再继续下去了。）