ANTLR 解析与 C++，第二部分：构建 Python 解析器

• 下载 Python3_gnu - 851.4 KB
• 下载 Python3_vs - 1.1 MB
• 下载 Python3_grammar - 9.5 KB

1 引言

上一篇文章解释了如何在 C++ 应用程序中访问 ANTLR 生成的代码。该语法非常简单，因此生成的代码不适合演示 ANTLR 的高级功能。本文将从 Python 语法生成解析代码，并提供一个使用该代码分析 Python 脚本的应用程序。

本文介绍了一些与 ANTLR 语法相关的高级功能。然后，它将解释如何使用监听器和访问者来分析解析树。

2 解析 Python

您可以在 ANTLR 的 Github 页面 上找到多个语法文件。在 Python 文件夹中，您会找到与 Python 编程语言相关的不同语法。本文关注的是 python/python3-cpp 文件夹中的语法文件 Python3.g4。该文件包含在本文的 Python3_grammar.zip 文件中，您可以通过输入以下命令来生成代码

java -jar antlr-4.9.2-complete.jar -Dlanguage=Cpp -visitor Python3.g4

-visitor 标志是新的，它告诉 ANTLR 为访问者类生成代码。我将在本文稍后解释访问者类是什么。

现在，我想概述一下 Python 的语法。然后，我将解释如何构建本文的示例应用程序，该应用程序使用监听器和访问者分析简短程序的解析树。

2.1 基本解析规则

Python 已经变得非常流行，其很大一部分原因是 简单性。Python 易于阅读、易于编写和易于调试。它也易于解析，这使其非常适合 ANTLR 的高级开发。本讨论重点关注解析 test.py 文件中的代码，该文件在清单 1 中给出。

清单 1：test.py

letters = ["a", "b", "c"]
for letter in letters:
    print(letter)
print("Done")

当解析器分析这段文本时，它会形成一个解析树，其节点代表语法规则。图 1 显示了解析树的上半部分的样子。

图 1：Python 解析树示例（已缩减）

要理解该树的节点，您需要熟悉 Python 语法的规则。输入文件由语句和换行符组成。语句可以是简单的或复合的，简单的语句由一个或多个小语句后跟换行符组成。Python3.g4 以以下方式表达这些关系

file_input: (NEWLINE | stmt)* EOF;

stmt: simple_stmt | compound_stmt;

simple_stmt: small_stmt (';' small_stmt)* (';')? NEWLINE;

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |
             import_stmt | global_stmt | nonlocal_stmt | assert_stmt);

test.py 代码有三个语句：两个简单语句和一个复合语句。以下讨论将介绍简单语句的规则，然后介绍复合语句的规则。

2.1.1 简单语句

test.py 的第一行是一个简单语句。具体来说，它是一个由 expr_stmt 规则表示的表达式

expr_stmt: testlist_star_expr (annassign | augassign (yield_expr|testlist) | 
    ('=' (yield_expr|testlist_star_expr))*);

在 test.py 的第一行中，letters 变量名和分配的数组都由 testlist_star_expr 规则标识

testlist_star_expr: (test|star_expr) (',' (test|star_expr))* (',')?;

test 规则识别任何通用表达式，其定义如下

test: or_test ('if' or_test 'else' test)? | lambdef;

test_nocond: or_test | lambdef_nocond;

or_test: and_test ('or' and_test)*;

and_test: not_test ('and' not_test)*;

not_test: 'not' not_test | comparison;

comparison: expr (comp_op expr)*;

如果 test 节点不包含 if、and、or 或 not，它就归结为 expr。expr 规则如下

expr: xor_expr ('|' xor_expr)*;

xor_expr: and_expr ('^' and_expr)*;

and_expr: shift_expr ('&' shift_expr)*;

shift_expr: arith_expr (('<<'|'>>') arith_expr)*;

arith_expr: term (('+'|'-') term)*;

term: factor (('*'|'@'|'/'|'%'|'//') factor)*;

factor: ('+'|'-'|'~') factor | power;

power: atom_expr ('**' factor)?;

atom_expr: (AWAIT)? atom trailer*;

如果 expr 不包含逻辑或数学运算符，它就归结为 atom，其定义如下规则

atom: ('(' (yield_expr|testlist_comp)? ')' |
       '[' (testlist_comp)? ']' |
       '{' (dictorsetmaker)? '}' |
       NAME | NUMBER | STRING+ | '...' | 'None' | 'True' | 'False');

此时，我们可以看到解析器将如何分析 test.py 的第一行。letters 变量由 NAME 标记表示。

NAME: ID_START ID_CONTINUE*;

在此词法分析器规则中，ID_START 是一个片段，用于标识 Python 变量名可以使用的所有字符。ID_CONTINUE 用于标识可以构成名称其余部分的字符。

在赋值的右侧，三个项目的列表由 testlist_comp 表示。

testlist_comp: (test|star_expr) ( comp_for | (',' (test|star_expr))* (',')? );

这表明 testlist_comp 本质上是一组由逗号分隔的 test 节点。我们之前已经看过 test 规则。

2.1.2 复合语句

在 test.py 脚本中，第二行代码包含一个复合语句。根据 Python 语法，复合语句可以有九种形式之一

compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | 
    classdef | decorated | async_stmt;

for_stmt 规则表示 for 循环。其定义如下

for_stmt: 'for' exprlist 'in' testlist ':' suite ('else' ':' suite)?;

exprlist 和 testlist 规则都很简单。

exprlist: (expr|star_expr) (',' (expr|star_expr))* (',')?;

testlist: test (',' test)* (',')?;

在 for 循环的第一行之后，接下来的行由 suite 规则表示

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT;

这表明 for 循环后面必须跟着一个简单语句或一个或多个缩进/反缩进的语句。INDENT 和 DEDENT 标记尤其有趣，我将在稍后讨论它们。

您可以以类似的方式查看其他复合语句。您不需要成为 Python 或其语法的专家也能理解本文，但您对语法的理解越深，对解析树的理解就越好。

2.2 构建示例项目

为了演示 C++ 中的 Python 解析，本文提供了两个包含项目代码的 zip 文件。第一个 zip 文件 Python3_vs.zip 包含 Visual Studio 的项目代码。第二个 Python3_gnu.zip 包含 GNU 构建系统的代码。

与上一篇文章中的项目一样，这些项目通过 main.cpp 源文件访问 ANTLR 生成的代码。清单 2 展示了其代码。

清单 2：main.cpp

int main(int argc, const char* argv[]) {
    
    // Create an input file stream
    std::ifstream infile("test.py");

    // Create an ANTLR stream from the file stream
    antlr4::ANTLRInputStream input(infile);

    // Create a lexer from the ANTLR stream
    Python3Lexer lexer(&input);

    // Create a token stream from the lexer
    antlr4::CommonTokenStream tokens(&lexer);

    // Create a parser from the token stream
    Python3Parser parser(&tokens);    

    // Associate a visitor with the Suite context
    Python3BaseVisitor visitor;
    std::string str = visitor.visitSuite(parser.suite()).as<std::string>();
    std::cout << "Visitor output: " << str << std::endl;

    // Associate a listener with the file_input context
    std::cout << "Listener output" << std::endl;
    antlr4::tree::ParseTreeWalker walker;
    antlr4::ParserRuleContext* fileInput = parser.file_input();
    Python3BaseListener* listener = new Python3BaseListener();
    walker.walk(listener, fileInput);

    return 0;
}

与上一篇文章一样，main 函数创建一个包含输入文本的 ANTLRInputStream。然后它创建一个词法分析器 (Python3Lexer) 和一个解析器 (Python3Parser)。创建解析器后，该函数使用访问者 (Python3BaseVisitor) 和监听器 (Python3BaseListener) 来分析解析树。

本文稍后将介绍监听器和访问者。首先，了解 Python3.g4 语法文件中使用的一些高级功能很重要。

3 高级语法功能

Python3.g4 语法文件比上一篇文章中介绍的 Expression.g4 语法文件复杂得多。除了规则和语法标识之外，它还包含三个新功能

• 一个 tokens 部分，用于识别词法分析器规则之外的标记
• 位于 @lexer::header 和 @lexer::members 等名称之后的代码块
• 位于规则定义之后的代码块

本节将介绍这些功能中的每一个，并解释它们的使用方法。

3.1 tokens 部分

在语法标识之后，Python3.g4 语法具有以下行

tokens { INDENT, DEDENT }

这创建了两个没有关联词法分析器规则的标记。它们没有规则，因为它们需要特殊处理。这种处理是通过 操作 来定义的，我将在下一节讨论。

3.2 命名操作

在 Python 中，代码块由缩进而不是标点符号表示。如果连续行的缩进相同，解释器会假定它们属于同一个代码块。缩进的空格数并不重要，但块中的每一行都必须缩进相同的空格数。

tokens 部分创建了 INDENT 标记来表示文本向右移动，并创建了 DEDENT 标记来表示文本向左移动。由于 Python 的特殊要求，这些标记不能用词法分析器规则来定义。相反，语法需要提供特殊代码来创建这些标记。此代码包含在 @lexer::members 之后的花括号中。

@lexer::members {
  private:
  std::vector<std::unique_ptr<antlr4::Token>> m_tokens;
  std::stack<int> m_indents;
  ...
  
  public:
  ...
}

此代码负责处理 INDENT 和 DEDENT 标记。它被花括号包围，因此它标识了一个 操作，并将被插入到 ANTLR 生成的代码中。此操作跟在 @lexer::members 之后，因此它将被添加到词法分析器的属性和函数中。操作也可以跟在 @lexer::header、@parser::header 和 @parser::members 等名称之后。

如果操作跟在 @header 之后，它将被添加到生成的词法分析器和解析器的头区域。如果操作跟在 @members 之后，它将被添加到生成的词法分析器类和生成的解析器类的成员中。

3.3 匿名操作

Python3.g4 中的大多数操作都不跟在 @parser::header 或 @lexer::members 之类名称后面。相反，它们位于规则内部或之后。例如，NEWLINE 规则如下

NEWLINE: ( {atStartOfInput()}? SPACES | ( '\r'? '\n' | '\r' | '\f' ) SPACES?) { ,,, }

此规则有两个操作。第一个在规则处理期间调用词法分析器的 atStartOfInput() 函数。第二个是由规则末尾的代码块提供的。由于第二个操作位于末尾，因此在词法分析器找到有效的 NEWLINE 标记后会被调用。

如果一个操作与词法分析器规则相关联，其代码可以通过在标记名称前加上 $，然后在后面加上点和属性来访问该规则标记的属性。例如，如果一个操作与 ID 标记的规则相关联，它可以通过 $ID.line 访问标记的行，通过 $ID.text 访问标记的文本。

4 分析解析树

许多应用程序会监视解析器的分析，并在遇到特定规则时执行操作。这被称为遍历解析树。ANTLR 提供了两种遍历解析树的机制：监听器和访问者。监听器更容易使用，但访问者提供更多控制。

4.1 监听器

当 ANTLR 从语法生成代码时，它会创建两个监听器类：一个以 -Listener 结尾，一个以 -BaseListener 结尾。图 2 说明了从 Python3 语法生成的监听器的类层次结构。

图 2：监听器类层次结构

如果您查看 Python3Listener 和 Python3BaseListener 类的头文件，您会发现它们都有相同的函数集：每个解析器规则有两个函数。例如，Python3 语法有一个名为 if_stmt 的规则，因此监听器类具有名为 enterIf_stmt 和 exitIf_stmt 的函数。enter 函数在规则处理之前调用，exit 函数在规则处理之后调用。

在 Python3Listener 类中，enter/exit 函数是纯虚函数。在 Python3BaseListener 类中，函数具有空的函数体。因此，如果您想编写自己的监听器类，应该将其子类化自 Python3Listener。如果您只想为少数 enter/exit 函数提供代码，应该修改 Python3BaseListener 代码。

一个例子将阐明这一点。在本例的代码中，Python3BaseListener 包含一个函数，该函数在解析器进入 for_stmt 规则时被调用

void Python3BaseListener::enterFor_stmt(Python3Parser::For_stmtContext* forCtx) {

    // Display text of for statement context
    std::cout << "For statement text: " << forCtx->getText() << std::endl;

    // Display text of expr context
    Python3Parser::ExprContext* exprCtx = forCtx->testlist()->test()[0]->or_test()[0]->
                                and_test()[0]->not_test()[0]->comparison()->expr()[0];
    std::cout << "Expr text: " << exprCtx->getText() << std::endl;

    // Display text of atom context
    Python3Parser::AtomContext* atomCtx = exprCtx->xor_expr()[0]->and_expr()[0]->
    shift_expr()[0]->arith_expr()[0]->term()[0]->factor()[0]->power()->atom_expr()->atom();
    std::cout << "Atom text: " << atomCtx->getText() << std::endl;
}

此函数访问与 for_stmt 关联的各种规则上下文。然后它调用 getText() 来打印与三个规则上下文关联的字符串。

编写完监听器函数后，需要将监听器与解析器关联起来。创建此关联需要四个步骤

1. 创建 antl4::tree::ParseTreeWalker 类的实例。
2. 获取指向您希望监听器处理的解析器规则上下文的指针。
3. 创建您的监听器实例。
4. 调用 ParseTreeWalker 的 walk 函数，传入监听器和解析器规则上下文。

以下代码取自 main.cpp，展示了如何执行这四个操作。

antlr4::tree::ParseTreeWalker walker;
antlr4::ParserRuleContext* fileInput = parser.file_input();
Python3BaseListener* listener = new Python3BaseListener();
walker.walk(listener, fileInput);

监听器易于使用和理解，但它们有两个限制。首先，应用程序无法控制哪些节点被处理。例如，前面的监听器代码会为每个 for_stmt 规则运行，而应用程序无法更改此行为。此外，监听器函数始终返回 void，因此没有简单的方法可以将信息传递给其他类和函数。为了弥补这些缺点，ANTLR 提供了访问者。

4.2 访问者

默认情况下，ANTLR 不为访问者类生成代码。但是，如果将 -visitor 标志添加到生成命令中，ANTLR 将生成四个额外的源文件。对于 Python3.g4 语法，这些文件是 Python3Visitor.h、Python3Visitor.cpp、Python3BaseVisitor.h 和 Python3BaseVisitor.cpp。

Python3Visitor.h 文件声明了一个名为 Python3Visitor 的类以及一系列 纯虚 函数。Python3BaseVisitor.h 文件声明了 Python3Visitor 的一个子类，名为 Python3BaseVisitor。这个子类具有与 Python3Visitor 相同的函数，但这些函数有代码。如果您想创建一个新的访问者类，最好对其进行子类化以创建自定义的 Python3Visitor。如果您宁愿为单个访问者函数编写代码，请将函数添加到 Python3BaseVisitor.cpp。

访问者函数的所有名称都以 visit 开头，以解析器规则的名称结尾。每个访问者函数都提供指向相应规则上下文的指针。例如，调用 visitSuite 函数来访问与语法 suite 规则相对应的上下文。它为每个处理的规则提供 SuiteContext 的指针。以下代码展示了 Python3BaseVisitor.h 中 visitSuite 的定义。

virtual antlrcpp::Any visitSuite(Python3Parser::SuiteContext *ctx) override {
    return visitChildren(ctx);
}

默认情况下，每个访问者函数都调用 visitChildren 来访问规则上下文的子项。此外，每个访问者函数都返回一个 antlrcpp::Any。Any struct 基于 Boost 的 Any 类，它可以设置为任何值。要访问 Any 实例的值，需要使用所需的数据类型调用其 as 函数。例如，以下代码调用 visitSuite 并将其返回值作为 string 访问。

std::string res = visitSuite(ctx).as<std::string>();

要理解访问者函数，看看一个例子会很有帮助。Python3BaseVisitor.cpp 中的以下函数返回与 SuiteContext 对应的文本。

antlrcpp::Any Python3BaseVisitor::visitSuite(Python3Parser::SuiteContext* ctx) {
    return ctx->getText();
}

为了将此访问者与解析器关联起来，main 函数创建了访问者的实例，并调用其 visitSuite 函数，传入解析器的 SuiteContext。然后，它将结果转换为 string 并将其打印到标准输出。

Python3BaseVisitor visitor;
std::string str = visitor.visitSuite(parser.suite()).as<std::string>();
std::cout << "Visitor output: " << str << std::endl;

这个例子并不太有趣，但它演示了访问者的两个重要特性。首先，应用程序可以控制哪些规则被访问者访问。其次，它展示了如何设置和访问访问者函数的返回值。

历史

• 2021 年 8 月 1 日：文章首次提交