华夏猫鱼：GuidovanRossum是Python的创造者。虽然他现在已经放弃了“终身仁政”的位置，但成为了指导委员会的五名成员之一，他的一举一动都备受瞩目。最近，他开通了一个Medium账号，发表了第一篇文章，透露了更换Python核心组件（解析器）的想法。本文分析了目前pgen解析器的诸多不足，同时介绍了PEG解析器的优点，令人期待。这个改造工作还在进行中，Guido表示他会写更多相关的文章，我们拭目以待。本文首发于公众号【蟒猫】，未经授权请勿转载。原文地址：https://mp.weixin.qq.com/s/yq...原标题|PEG解析器的作者|GuidovanRossum（Python之父）译者|作者)原文|https://medium.com/@gvanrossum_83706/peg-parsers-7ed72462f97c声明|转载仅供交流学习，欢迎转载，但请保留本文出处，请勿用于商业或非法用途。几年前，有人问Python是否会改用PEG解析器（或PEG语法，我记不清了，谁说的，什么时候说的）。我稍微看了看这个话题，但没有头绪并放弃了。最近，我学习了很多关于PEG（ParsingExpressionGrammars）的知识，现在我认为它是我30年前开始使用Python的自制解析器生成器（parsergenerator）的有趣替代品（那个解析器生成器，叫做“pgen"，是我为Python编写的第一段代码）。我现在对PEG很感兴趣，因为我对pgen的局限性感到有点恼火。它使用我自己编写的LL(1)解析变体——我不喜欢生成空字符串的语法规则，所以我禁用它以稍微简化生成解析表的算法。同时，我还发明了一套类似于EBNF的语法表示法（译注：ExtendedBackus-NaurForm，BNF的扩展，是一种形式化的表示法，用于描述给定语言的文法），我还是很喜欢的很多。以下是pgen的一些问题，这让我很恼火。LL(1)名称中的“1”表示它仅使用单个标记前瞻，这限制了我们编写良好语法规则的能力。例如，Python语句既可以是表达式也可以是赋值（或其他东西，但它们以专门的关键字开头，如if或def）。我们希望使用pgen表示法来编写如下语法。（请注意，这个例子描述了一种玩具语言，它是Python的一个微小子集，就像在传统语言设计中一样。）语句：assignment|表达式|if_statementexpr:expr'+'项|expr'-'术语|termterm：术语“*”原子|术语“/”原子|原子：名称|编号|'('expr')'assignment:target'='exprtarget:NAMEif_statement:'if'expr':'statement解释一下这些符号：NAME和NUMBER是记号，在语法之外预定义。括在引号中的字符串，例如“+”或“if”也是标记。（稍后我将讨论标记。）语法规则以其名称开头，后跟一个:符号，然后是一个或多个由|分隔的备选方案。符号。但问题是，如果你这样写语法，解析器将无法工作，pgen将罢工。原因之一是某些规则（例如expr和term）是左递归的，而pgen不够智能，无法解析它们。这通常需要通过重写规则来解决，例如（同时保持其他规则不变）：expr:term('+'term|'-'term)*term:atom('*'atom|'/'atom)*这揭示了pgen的EBNF功能的一部分：您可以在括号内嵌套可选值，并且可以在括号后放置*以创建重复，因此这里的expr规则意味着：它是一个术语(term)，后跟零个或多个由a组成的语句块加号后跟术语，或减号后跟术语。此语法与该语言的第一个版本兼容，但它并不反映语言设计者的意图——特别是它不表示运算符是左绑定的，这在您尝试生成代码时很重要。但是在这种玩具语言（以及Python中）中，还有另一个烦人的问题。由于前向单个标记，解析器无法确定它是在查看表达式的开头还是赋值。在语句的开头，解析器需要根据它看到的第一个标记来决定它应该查看语句的哪些可选内容。（为什么？pgen的自动解析器就是这样工作的。）假设我们的程序是这样的：answer=42这个程序将被解析成三个标记：NAME（值为answer）、'='和NUMBER（值为42）.在程序开始时，我们拥有的唯一前向标记是NAME。此时，我们要满足的规则是语句（此语法的开始标志）。该规则有三个可选内容：expr、assignment和if_statement。我们可以排除if_statement，因为前向标记不是“if”。但是expr和assignment都可以以NAME标签开头，所以会产生歧义，pgen会拒绝我们的语法。（这也不完全正确，因为语法在技术上不会导致歧义；但让我们别管它，因为我想不出更好的词。那么pgen是如何做出这个决定的？它为每个语法规则做这个计算称为第一组的东西，如果在给定点，第一组有重叠的选项，它会抱怨）。那么，我们能否为解析器提供更大的前向缓冲区来解决这个烦恼呢？对于我们的玩具语言来说，第二个前向标记就足够了，因为在这个语法中，赋值的第二个标记必须是“=”。但是在像Python这样更现实的语言中，你可能需要一个无限的前向缓冲区，因为“=”标记左边的东西可能非常复杂，例如：table[index+1].name.first='Steven'有在“=”标记之前使用了10个标记，如果您想挑战一下，我可以举一个任意长的示例。为了在pgen中解决它，我们的方法是修改语法并添加一个额外的检查，以确保它接受一些非法程序，但如果检查检测到对左侧的赋值无效，则会抛出SyntaxError。对于我们的玩具语言，这归结为写作：statement:assignment_or_expr|if_statementassignment_or_expr:expr['='expr]（方括号表示可选部分。）然后在后续编译期间（例如，段代码），我们检查是否存在“=”，如果是，我们检查目标语法在左侧。关键字参数在调用函数时也有类似的问题。我们想这样写（同样，这是Python调用语法的简化版本）：kwargposarg:exprkwarg:NAME'='expr但前向单个标记无法告诉解析器参数开头的NAME是posarg的开头（因为expr可能以NAME开头）还是kwarg的开头。同样，Python当前的解析器在解决这个问题时，专门声明：arg:expr['='expr]，然后在后续的编译过程中解决这个问题。（我们甚至犯了一个小错误，允许foo((a)=1)之类的东西，赋予它与foo(a=1)相同的含义，直到Python3.8才修复。)那么，PEG解析器是如何解决这些烦恼的呢？通过使用无限前向缓冲！PEG解析器的经典实现使用一种称为“packrat解析”的东西，它不仅在解析前将整个程序加载到内存中，而且还允许解析器任意回溯。尽管术语PEG主要是指语法符号，但PEG语法生成的解析器是一个可以无限返回的递归下降解析器。“packrat解析”有效。这使一切变得更容易，但是当然有一个成本：内存。三十年前，我有充分的理由使用单前向令牌解析技术：内存很昂贵。LL(1)解析（以及其他技术，如LALR(1)，因YACC而出名）使用状态机和堆栈（“下推自动机”）来有效地构造解析树。幸运的是，运行CPython的计算机比30年前拥有更多的内存，将整个文件保存在内存中真的不再是一种负担。例如，我在标准库中能找到的最大的非测试文件是_pydecimal.py，大约223KB。在千兆字节的世界中，这几乎算不了什么。这就是让我再次研究解析技术的原因。然而，目前CPython中的解析器还有另一个让我烦恼的错误。编译器很复杂，CPython也不例外：虽然pgen驱动的解析器的输出是一个解析树，但这个解析树并不直接用作代码生成器的输入：它首先被转换成抽象语法树(AST)，然后编译成字节码。（还有更多的细节，但我不会在这里重点。）为什么不直接从解析树编译呢？这实际上是它最初的工作方式，但大约15年前，我们发现编译器因解析树的结构而变得复杂，因此我们引入了一个单独的AST，并引入了一种将解析树转换为AST链接的方法。随着Python的发展，AST比解析树更稳定，这使得编译器出错的可能性更小。AST对于想要检查Python代码的第三方代码也更容易，它也通过流行的ast模块公开。该模块还允许您从头开始构建AST节点，或修改现有的AST节点，然后您可以将新节点编译为字节码。后一种能力支撑了整个家庭手工业向Python语言添加扩展。（借助parser模块也向Python用户开放了一个parsetree，但是使用起来很麻烦，相对于ast模块已经过时了。）话虽如此，我现在的想法是看看我是否可以创建一个新的CPython的parser，使用PEG和packrat解析，解析时直接构造AST，跳过中间解析树结构，尽可能节省内存，虽然会使用无限前向缓冲。我还没有到达那里，但是有一个原型可以以与当前CPython解析器大致相同的速度将Python的一个子集编译成AST。只是它更占用内存，所以我希望它在将PEG解析器扩展到整个语言时会减慢PEG解析器的速度。但是，我还没有优化它，所以它很有希望。转换为PEG的最后一个好处是它为语言的未来发展提供了更大的灵活性。过去有人说pgen的LL(1)缺陷有助于Python保持语法简单。这很有意义，但我们也有很多流程来防止语言不受控制的膨胀（主要是PEP流程，在非常严格的向后兼容性要求和新的治理结构的帮助下）。所以我不担心。关于PEG分析和我的具体实现，我还有很多东西要写，但是我会在整理代码后写在后续的文章中。公众号【Python猫】，本号连载系列精品文章，包括喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐与翻译等，欢迎收看注意。
