替换CPython的解析器

从一开始，Python的语法就是LL(1)：它只需要一个从左到右的解析器，向前看一个标记来解决歧义。标准CPython解析器是由一个简单的自定义解析器生成器生成的。然而，这种简单性是有代价的。首先，官方的Python语法文件没有准确捕获语言。语法允许无效的构造，例如，这个赋值表达式(使用new walrus运算符)：这个表达式是非法的，因为walrus运算符的左侧必须是一个名称，而不是像[x for x in y]这样的任意子表达式。不过，Python的LL(1)解析器的功能不足以强制执行此规则，因此必须在通过特殊情况逻辑(在将解析树转换为抽象语法树(AST)时运行的特殊情况逻辑)进行解析后才能强制执行该规则。更糟糕的是，有一些Python代码是我们想要编写但无法编写的，因为它不能被解析。用-语句括起来看起来很合理，但目前是禁止的：阅读更多2020年Python语言峰会的报道。Guido van Rossum、Pablo Galindo和Lysandros Nikolaou编写了一个新的Python解析器来去除这些缺点，并建议PEP617在CPython中采用它。新的解析器是以更强大的风格编写的，称为解析表达式语法(PEG)，因此该项目被命名为“PEGEN”。当PEG解析器读取可能匹配多个语法规则的令牌序列的开头时，解析器会从左到右尝试每条规则，直到其中一条成功。例如，给定一组规则：解析器首先尝试将规则A应用于其输入序列。如果A成功，解析器将忽略B和C。否则，解析器继续并尝试应用规则B，依此类推。与LL(1)解析器不同，PEG解析器可以根据需要向前看，以消除序列的歧义。语法是确定性的：在多个规则匹配的情况下，最左边的规则获胜。有些序列需要指数级的时间才能找到匹配规则；为了避免这种情况，大多数PEG解析器(包括新的Python解析器)实现了“Packrat”方法来缓存中间结果。PackRAT解析器可以在线性时间内处理任何输入，但会在其缓存上花费一些内存。PEGEN的语法比旧的要清晰得多，并且语法与所有合法的Python程序完全匹配。CPython的旧解析器分阶段进行：记号赋值器向LL(1)解析器提供数据，该解析器生成具体的语法树(CST)，并将其转换为AST。cst阶段是必需的，因为解析器不支持左递归。考虑一下这个表达式：旧解析器的CST太扁平了，正如本幻灯片中的演示者所展示的那样：在现实生活中，表达式将在运行时通过首先将a加到b，然后添加c来计算。不幸的是，CST不对此嵌套计算进行编码，因此LL(1)解析器必须第二次转换程序以将CST转换为适当嵌套形式的AST，然后可以生成字节码。另一方面，PEGEN直接生成AST。根据程序的不同，PEGEN可能会使用更多或更少的内存：它在PackRat方法上花费的钱，可以通过跳过CST来节省。Emily Morehouse针对旧解析器测试了PEGEN，方法是验证它们为标准库中的每个模块和前3800个PyPI包生成相同的AST。(PEGEN解析标准库的速度略快于旧解析器，但使用的内存多10%。)。一旦Python有了非LL(1)解析器，其语法可能会变得更加复杂；Victor Stner询问第三方Python解析器(如linters和IDE)是否会有困难。van Rossum确信，如果有必要，他们自己可以采用更强大的解析器。作者计划谨慎地将CPython切换到新的解析器。在Python3.9alpha6中，新的解析器将选择加入；它将成为Beta1和官方3.9版本中的默认解析器，旧的解析器仍然可以通过命令行开关使用。一旦启用了新的解析器，将允许使用带括号的-语句！在Python3.10中，旧的解析器将被删除。然而，PEP617仍然必须得到批准，新的规范需要最后的审查。这项提议没有遭到反对；事实上，观众中的几个人询问它是否可以更早成为违约。