PyPy 解析器

概述

PyPy 解析器包含一个词法分析器和一个递归下降解析器。

词法分析器

目前，词法分析器实现为单个函数（generate_tokens 在 pypy/interpreter/pyparser/pytokenizer.py 中），该函数构建一个令牌列表。然后将这些令牌馈送到解析器。

解析器

解析器是一个简单的 LL(1) 解析器，类似于 CPython 的解析器。

构建 Python 语法

Python 语法在启动时从原始的 CPython 语法文件构建（参见 pypy/interpreter/pyparser/metaparser.py）。语法构建器首先将语法表示为对应于一组非确定性有限自动机 (NFA) 的规则。然后将其转换为一组确定性有限自动机 (DFA)。NFA 和 DFA 之间的区别在于，对于任何给定的输入，NFA 可能有多个可能的下一个状态，而 DFA 只能有一个。因此，DFA 更加限制，但在解析中效率更高。最后，语法构建器为每个 DFA 状态分配一个数字，并将它们打包到一个列表中供解析器使用。最终产品是 pypy/interpreter/pyparser/parser.py 中 Grammar 类的实例。

解析器实现

解析器的核心是 Parser 类的 add_token 方法。它尝试根据作为参数接收的令牌，从当前状态找到到另一个状态的转换。如果找不到转换，它会检查当前状态是否为接受状态。如果不是，则会引发 ParseError。当解析在没有错误的情况下完成时，解析器会构建一个 Node 树。

解析 Python

词法分析器和解析器之间的粘合代码以及额外的 Python 特定代码位于 pypy/interpreter/pyparser/pyparse.py 中。 parse_source 方法接受 Python 代码字符串并返回解析树。它还会检测编码 cookie（如果有）并解码源代码。请注意，__future__ 导入在解析器被调用之前通过在 pypy/interpreter/pyparser/future.py 中手动解析源代码来处理。

编译器

生成 Python 字节码的下一步是将解析树转换为抽象语法树 (AST)。

构建 AST

Python 的 AST 在 pypy/interpreter/astcompiler/tools/Python.asdl 中描述。从这个定义中，pypy/interpreter/astcompiler/tools/asdl_py.py 生成 pypy/interpreter/astcompiler/ast.py，它为编译器提供 RPython 类，以及与 AST 的应用程序级代码的绑定。AST 类的某些自定义扩展位于 pypy/interpreter/astcompiler/asthelpers.py 中。

pypy/interpreter/astcompiler/astbuilder.py 负责将解析树转换为 AST。它遍历解析树，在遍历过程中构建节点。结果是一个顶级的 mod 节点。

AST 优化

pypy/interpreter/astcompiler/optimize.py 包含 AST 优化器。它对表达式进行常量折叠，以及其他简单的转换，例如将对名称“None”的加载转换为常量。

符号分析

在编写字节码之前，符号表在 pypy/interpreter/astcompiler/symtable.py 中构建。它确定源代码中的每个名称是局部变量、隐式全局变量（没有全局声明）、显式全局变量（在作用域中存在该名称的全局声明）、单元格（该名称在嵌套作用域中使用）还是自由变量（它在嵌套函数中使用）。

字节码生成

字节码在 pypy/interpreter/astcompiler/codegen.py 中发出。每个字节码暂时由 pypy/interpreter/astcompiler/assemble.py 中的 Instruction 类表示。在所有字节码发出后，就该构建代码对象了。计算跳转偏移量和字节码信息，例如行号表和堆栈深度。最后，所有内容都传递给一个全新的 PyCode 对象。