python - Python的语法是LL(1)吗？

Question

this question 可能重复但是对我来说还不够具体。

python语法是claimed to be LL(1) , 但我注意到 Python grammar 中的一些表达式这真的让我感到困惑，例如，以下函数调用中的参数:

foo(a)
foo(a=a)

对应如下语法:

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

test 在语法的第一个位置出现了两次。这意味着仅通过查看 test Python 无法确定它是 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

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

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

实际上，Python 解析器将语法转换为可执行的解析器，而不是上下文无关的语法。出于 Python 的实用目的，能够构建一个仅具有前瞻性标记的预测解析器就足够了。因为预测解析器可以使用像条件语句和循环这样的控制结构，所以完全转换为上下文无关文法是不必要的。因此，可以使用 EBNF 产生式——与记录的语法一样——它们不是完全左因式分解的，甚至可以使用 EBNF 产生式，其到 LL(1) 的转换是非常重要的:

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

在上面的产生式中，(';' small_stmt)* 的重复后面可能跟着一个';'，这意味着一个简单的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)。 (我知道这不是原来的问题，所以我不会再追问了。)