几年前，有人问我将Python转换为PEG解析器（或PEG语法；我不记得确切的名称和时间）是否有意义。 然后我稍微看了一下他，但没有得出任何结论，因此我放弃了这个话题。 我最近了解了更多关于PEG（解析表达式语法，解析表达式语法）的知识，现在我认为这是30年前刚开始使用Python时开发的自写解析器生成器的有趣替代。 我称它为“ pgen”，这可能是我为Python编写的第一段代码。
我目前对PEG解析器感兴趣的原因是因为pgen的局限性使我有些恼火。 它基于自己的LL（1）实现而构建，该实现具有许多假设。 例如，我不喜欢会产生空行的语法规则，所以我禁止使用它们。 从而简化了用于创建解析表的算法。 我还发明了我自己仍然很喜欢的类似于EBNF的语法符号。
这是pgen惹恼我的一些问题。 名称LL（1）中的“ 1”表示仅分析下一个标记，这限制了我们创建良好语法规则的能力。 例如，Python语句可以是表达式或赋值（或其他形式，但它们都以突出显示的关键字开头，例如if或def ）。 我想用pgen表示法描述语法。 请注意，这只是一个简化的示例，它是Python的一个子集，通常在描述语言设计时会这样做。 这将是一种玩具语法，将在以后的演示中派上用场。
statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement
关于符号的几句话： NAME和NUMBER是记号，并且在语法之外进行了预定义。 带引号的字符串'+'或'if'也是标记。 （下次让我们推迟讨论它们。）语法规则以规则名称开头，后跟: ，然后是一个或多个替代项，并用|分隔| 。
问题是，如果您以这种方式描述语法，则pgen将不起作用。 这是由于以下事实：一些规则（ expr和term ）是递归的，并且他不够聪明，无法正确处理此类情况。 通常，仅重写这些规则即可解决此问题，而其他规则则保持不变。 例如：
expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)*
这揭示了pgen中EBNF的几种可能性：您可以将替代方案嵌套在括号中，并通过在元素后放置*创建重复项。 因此，表达式expr的规则在这里表示“这是一个术语，后跟序列<term正负的零个或多个重复，然后是term>”。 该语法采用与第一个版本相同的语言，但再次没有反映该语言的设计意图。 特别是，它并不表示运算符位于左侧，这在您尝试生成代码时很重要。
但是这个示例（还有Python）中还有一个烦人的问题。 由于仅解析一个令牌，因此分析器无法确定它在看什么-表达式或赋值的开始。 在运算符处理的最开始，解析器应仅决定第一个令牌，然后解析第一个令牌。 （为什么？这是pgen中解析的实现方式。）假设我们的程序如下：
answer = 42
该程序由三个标记表示： NAME （具有answer值）， =和NUMBER （具有值42 ）。 在解析的开始我们唯一了解的就是第一个NAME令牌。 我们现阶段试图解析的规则是statement （语法的初始字符）。 为此定义了三个备选方案： expr ， assignment和if_statement 。 我们可以立即排除if_statement ，因为先前的标记不是if 。 但是expr和assignment都可以以NAME标记开头，因此，pgen拒绝了我们的语法模棱两可。
这并不是完全正确的，因为从技术上讲语法本身不是正确的。 我找不到更准确的表述，所以让我们继续讲下去。 pgen如何解决这个问题？ 它为每个语法规则计算一个称为FIRST集的内容，如果它们相交，则将引发异常。
因此，我们不能通过为解析器提供更大的查看缓冲区来解决此问题吗？ 对于我们的示例，第二个预览令牌就足够了，因为在此语法中，第二个分配令牌应为= 。 但是在更现实的语言（如Python）中，您可能需要无限制的缓冲区，因为=标记=左侧的内容可以任意复杂，例如：
table[index + 1].name.first = 'Steven'
在这种情况下，您必须先解析十个令牌，然后才能满足= 。 但我向您保证，表达式可能会更长。 为了解决pgen中的此问题，我们更改了语法分析器以接受一些不正确的表达式，并在后续步骤中添加了额外的检查。 如果左侧和右侧不匹配，则会抛出SyntaxError错误。 对于我们的玩具语言，归结为编写以下内容：
statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr]
方括号表示可选部分。 然后，在编译器的下一个阶段（例如，生成字节码时），我们检查是否= ，如果是，则检查左侧是否与target语法匹配。
函数调用参数也有类似的问题。 我们想写这样的东西（同样，在Python语法的简化版本中）：
call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr
但是仅考虑下一个标记的解析算法无法告诉解析器，参数开头的NAME是posarg的开头（因为expr可以以NAME开头）还是kwarg的开头。 同样，当前的Python解析器通过确定以下内容来解决此问题：
arg: expr ['=' expr]
然后在后续的编译器遍历中完成替换。 （我们甚至犯了一个小错误，就像foo(a = 1)一样解析foo((a) = 1) foo(a = 1) 。仅在Python 3.8中已修复）
那么PEG解析器如何解决这些问题呢？ 使用无限的备份缓冲区！ 它的典型实现使用所谓的packrat解析器，该解析器不仅可以在解析程序之前将整个程序加载到内存中，还可以将分析器回滚到任意数量的令牌上。 尽管术语PEG主要是指语法符号，但从PEG语法生成的解析器通常是具有递归下降和无限制返回的解析器。 packrat解析器通过记住已针对特定位置进行解析的规则来提高自我效率。
这简化了算法，但是当然要付出代价：内存。 30年前，我有充分的理由使用LL（1）：内存很昂贵。 他（与YACC闻名的LALR（1）等其他技术一样）使用状态机和堆栈来高效地构建解析树。
幸运的是，运行CPython的计算机比30年前拥有更多的内存，并且将整个文件存储在内存中不再是问题。 例如，我可以在stdlib中找到最大的非测试文件是_pydecimal.py ，它大约需要223kb。 在千兆字节的世界中，这基本上什么都没有，这使我对解析器有了不同的了解。
但是当前的CPython解析器中还有一件事令我感到困扰。 编译器是很复杂的事情，CPython的实现也不例外。 尽管pgen解析器的结果是一棵解析树，但它没有直接用作字节码生成器的输入：它首先转换为抽象语法树（AST），然后才将此AST编译为字节码。 （实际上，它在那里更加复杂，但是目前我们不再赘述）
为什么不立即从解析树进行编译？ 确实如此，但是大约15年前，我们发现编译器过于复杂。 因此我们分别从解析树中分离出AST和AST的转换阶段。 随着Python的发展，AST仍比解析稳定，这降低了编译器中发生错误的可能性。
AST与想要测试Python代码的第三方库一起使用也更容易。 可以使用流行的ast模块获得。 它还允许您从头开始创建节点并修改现有节点，并将部分编译为字节码。 后者允许创建Python语言扩展的整个行业。 （Python用户也可以通过解析模块访问解析树，但是使用解析树要困难得多；因此，它并不那么受欢迎）
现在，我想结合这些内容，看看是否可以为CPython创建一个新的解析器，该解析器在解析期间使用PEG和packrat直接创建AST。 因此，有可能省略中间分析树的生成，即使为令牌使用了无限的缓冲区，也可以节省我们的内存。 我仍在实施过程中，但是我已经有了一个原型，该原型可以以与当前CPython解析器大致相同的速度将Python子集编译为AST。 但是，它使用更多的内存，在我看来，将子集扩展为完整语言会降低PEG分析器的速度。 但是到目前为止，我还没有考虑任何优化，因此我将继续工作。
切换到PEG的最后一个优势是，它为语言的进一步发展提供了更大的灵活性。 过去，有人说pgen中的LL（1）约束使Python语法简单。 这很可能是正确的，但是我们还有许多其他过程可以防止语言不受控制地增长（主要是PEP流程，这得益于非常严格的向后兼容性要求和新的管理结构）。 所以我不用担心。
我想介绍更多关于PEG及其实现的信息，但是在我清理代码后的下一篇文章中。
本文和引用代码的许可： CC BY-NC-SA 4.0