替换CPython的解析器

2020-05-10 13:41:18

从一开始,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仍然必须得到批准,新的规范需要最后的审查。这项提议没有遭到反对;事实上,观众中的几个人询问它是否可以更早成为违约。