Python 的语法是 LL(1) 吗？

Question

可能与重复，但对我来说还不够具体。

python语法是claimed to be LL(1), but I've noticed some expressions in the Python grammar，这让我很困惑，例如，以下函数调用中的参数：

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

你是对的，像 'is' | 'is' 'not' 这样的结构不是 LL(1)。它们可以很容易地通过将其更改为 'is' notOpt 其中 notOpt: 'not' | ϵ 或者，如果您允许 EBNF 语法，只需 'is' 'not'? （或 'is' ['not'] 取决于关于 EBNF 的味道）。

所以语言是 LL(1)，但语法在技术上不是。我假设 Python 设计者认为这没问题，因为左因子版本会更难阅读而没有太多好处，并且当前版本仍然可以毫无困难地用作 LL(1) 解析器的基础.

Answer 2

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

为了使问题有意义，必须将语法转换为简单的上下文无关语法。这当然是可能的，但没有规范转换，Python 文档也没有解释所使用的精确转换。某些转换可能会产生 LL(1) 文法，而其他转换可能不会。（事实上，Kleene 星的天真翻译很容易导致歧义，根据定义，对于任何 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) 的文法，甚至是非上下文无关的文法，但这与 是否存在的问题无关language is LL(1)：如果存在一个 LL(1) 文法，则该语言就是 LL(1)。（我知道这不是原来的问题，所以我不会再追究了。）

Python 的语法是 LL(1) 吗？

Is the Python's grammar LL(1)?

python

compiler-construction

grammar

parsing