是Python的语法LL(1)吗? [英] Is the Python's grammar LL(1)?

问题描述

这个问题的可能重复，但对我而言，它不够具体.

Possible duplicate for this question however for me it's not specific enough.

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

The python grammar is claimed to be LL(1), but I've noticed some expressions in the Python grammar that really confuse me, for example, the arguments in the following function call:

foo(a)
foo(a=a)

对应于以下语法:

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

test在语法的第一位置出现两次.这意味着仅查看test，Python无法确定它是test [comp_for]还是test '=' test.

test appears twice in the first position of the grammar. It means that by only looking at test Python cannot determine it's test [comp_for] or test '=' test.

更多示例:

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

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

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

test也会出现两次.

我对LL(1)的理解是否错误? Python在词法分析或语法分析期间是否为语法做一些变通办法，以使其LL(1)可处理?谢谢大家.

Is my understanding of LL(1) wrong? Does Python do some workaround for the grammar during lexing or parsing to make it LL(1) processable? Thank you all in advance.

推荐答案

呈现的语法在Python文档中(并用于生成Python解析器)以扩展BNF的形式编写，其中包括运算符"，例如可选性([a])和Kleene闭包((a b c)*).但是，LL(1)是仅适用于不具有此类运算符的简单上下文无关文法的类别.因此，询问该特定语法是否为LL(1)是一个类别错误.

The grammar presented in the Python documentation (and used to generate the Python parser) is written in a form of Extended BNF which includes "operators" such as optionality ([a]) and Kleene closure ((a b c)*). LL(1), however, is a category which appies only to simple context-free grammars, which do not have such operators. So asking whether that particular grammar is LL(1) or not is a category error.

为了使问题有意义，必须将语法转换为简单的无上下文语法.当然，这是可能的，但是没有规范的转换，Python文档也没有解释所使用的精确转换.某些转换可能会产生LL(1)语法，而其他转换可能不会. (实际上，对Kleene星的幼稚翻译很容易导致模棱两可，根据定义，这对任何k都不是LL(k).)

In order to make the question meaningful, the grammar would have to be transformed into a simple context-free grammar. This is, of course, possible but there is no canonical transformation and the Python documentation does not explain the precise transformation used. Some transformations may produce LL(1) grammars and other ones might not. (Indeed, naive translation of the Kleene star can easily lead to ambiguity, which is by definition not LL(k) for any k.)

在实践中，Python解析设备将语法转换为可执行的解析器，而不是上下文无关的语法.出于Python的务实目的，能够仅使用一个令牌的前瞻性就可以构建一个预测性解析器就足够了.由于预测解析器可以使用条件语句和循环之类的控制结构，因此无需完全转换为无上下文语法.因此，可以使用未完全左分解的EBNF生成物(如已记录的语法)，甚至可以使用向LL(1)转换不平凡的EBNF生成物:

In practice, the Python parsing apparatus transforms the grammar into an executable parser, not into a context-free grammar. For Python's pragmatic purposes, it is sufficient to be able to build a predictive parser with a lookahead of just one token. Because a predictive parser can use control structures like conditional statements and loops, a complete transformation into a context-free grammar is unnecessary. Thus, it is possible to use EBNF productions -- as with the documented grammar -- which are not fully left-factored, and even EBNF productions whose transformation to LL(1) is non-trivial:

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

在上面的生产中，(';' small_stmt)*的重复后面可能是';'，这意味着简单的while循环将无法正确表示生产.我不知道Python解析器生成器如何处理此生成，但是可以在扩展重复之后通过左分解将其转换为CFG:

In the above production, the repetition of (';' small_stmt)* may be followed by a ';', which means that a simple while loop will not correctly represent the production. I don't know how this production is handled by the Python parser generator, but it is possible to transform it into CFG by left-factoring after expanding the repetition:

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

类似地，可以将整个EBNF转换为LL(1)语法.之所以没有这样做，是因为该练习对于解析或解释语法都没有用.它将很难阅读，并且EBNF可以直接转换为解析器.

Similarly, the entire EBNF can be transformed into an LL(1) grammar. That is not done because the exercise is neither useful for parsing or for explaining the syntax. It would be hard to read, and the EBNF can be directly transformed into a parser.

这一点与Python是否为LL(1)的问题无关，因为如果该语言存在LL(1)语法，那么该语言就是LL(1).语言的语法永远都是无限的，包括对于任何k而言不是LL(k)的语法，甚至不是与上下文无关的语法，但这与 language 为LL(1):即使存在一个LL(1)语法，语言也为LL(1). (我知道这不是最初的问题，因此我将不再进一步探讨这个问题.)

This is slightly independent of the question of whether Python is LL(1), because a language is LL(1) precisely if an LL(1) grammar exists for the language. There will always be an infinitude of possible grammars for a language, including grammars which are not LL(k) for any k and even grammars which are not context-free, but that is irrelevant to the question of whether the language is LL(1): the language is LL(1) if even one LL(1) grammar exists. (I'm aware that this is not the original question, so I won't pursue this any further.)

这篇关于是Python的语法LL(1)吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！