基于 antlr4 的 Python 解释器

该项目是上海交通大学 ACM 班程序设计课程的大作业, 笔者通过助教的讲解与同学的帮助, 完成了 Python 解释器的核心代码. 大作业地址: https://github.com/ACMClassCourse-2022/Python-Interpreter-2022 实现方案: https://github.com/Conless/Python-Interpreter

简介

Antlr (ANother Tool for Language Recognition) 是一个强大的跨语言语法解析器,可以用来读取, 处理, 执行或翻译结构化文本或二进制文件. 它被广泛用来构建语言, 工具和框架. Antlr 可以从语法上来生成一个可以构建和遍历解析树的解析器. 通过使用 antlr 对一个简单的 Python 程序进行句法语法分析, 可以得到一棵代码语法树, 如下图所示

该语法树对应的核心规则在 Python3.g4 中给出. 随后需要完成的就是在 Evalvisitor.h/.cpp 中完成对树上每一个节点的访问.

Any 类型是 Python 解释器中十分关键的一环. 众所周知, Python 里面进行变量定义与赋值的时候并不需要指定类型, 函数的返回参数也并非给定的类型. 因此, 为了在 C++ 中进行实现, 我们有必要引入这个类以完成任意类型的判断. 在该项目使用的 antlr 4.11 中,使用的 any 类型为自定义的 antlrcpp::Any 而非 C++17 中的 std::any, 其两个最重要的接口为:

template <class U> bool is();

template<class U> const StorageType<U>& as();

前者可用于判断一个变量是否为某一类型的数据, 后者用于将变量转化为某一类型的数据. 其实现的基本原理是使用 dynamic_cast<>() 来对指针进行类型转化. 接口

以下内容是 Evalvisitor.h 中给出的, 需要逐一实现的接口

class EvalVisitor : public Python3BaseVisitor {

  public:
    virtual antlrcpp::Any visitFuncdef(Python3Parser::FuncdefContext *ctx) override;

    virtual antlrcpp::Any visitParameters(Python3Parser::ParametersContext *ctx) override;

    virtual antlrcpp::Any visitExpr_stmt(Python3Parser::Expr_stmtContext *ctx) override;

    virtual antlrcpp::Any visitFlow_stmt(Python3Parser::Flow_stmtContext *ctx) override;

    virtual antlrcpp::Any visitIf_stmt(Python3Parser::If_stmtContext *ctx) override;

    virtual antlrcpp::Any visitWhile_stmt(Python3Parser::While_stmtContext *ctx)
    override;

    virtual antlrcpp::Any visitSuite(Python3Parser::SuiteContext *ctx) override;

    virtual antlrcpp::Any visitOr_test(Python3Parser::Or_testContext *ctx) override;

    virtual antlrcpp::Any visitAnd_test(Python3Parser::And_testContext *ctx) override;

    virtual antlrcpp::Any visitNot_test(Python3Parser::Not_testContext *ctx) override;

    virtual antlrcpp::Any visitComparison(Python3Parser::ComparisonContext *ctx) override;

    virtual antlrcpp::Any visitArith_expr(Python3Parser::Arith_exprContext *ctx) override;

    virtual antlrcpp::Any visitTerm(Python3Parser::TermContext *ctx) override;

    virtual antlrcpp::Any visitFactor(Python3Parser::FactorContext *ctx) override;

    virtual antlrcpp::Any visitAtom_expr(Python3Parser::Atom_exprContext *ctx) override;

    virtual antlrcpp::Any visitTrailer(Python3Parser::TrailerContext *ctx) override;

    virtual antlrcpp::Any visitAtom(Python3Parser::AtomContext *ctx) override;

    virtual antlrcpp::Any visitTestlist(Python3Parser::TestlistContext *ctx) override;

    virtual antlrcpp::Any visitArglist(Python3Parser::ArglistContext *ctx) override;

    virtual antlrcpp::Any visitArgument(Python3Parser::ArgumentContext *ctx) override;
};

实现

基础功能: 赋值, 变量与基础运算

对变量赋值, 以及进行自算术运算的语句属于 expr_stmt, 在 Python3.g4 中的定如下:

expr_stmt: testlist ( (augassign testlist) | ('=' testlist)*);
augassign: ('+=' | '-=' | '*=' | '/=' | '//=' | '%=' );
testlist: test (',' test)* (',')?; // 算式 eg: a,b a a+b

首先考虑对变量赋值. 在 Python 中, 对变量的定义是可以直接在赋值时完成的, 因此在此之前需要首先实现变量的操作. 如果只考虑全局变量的情况, 实现是简单的:

class Scope {
  private:
    std::unordered_map<std::string, antlrcpp::Any> data_table;
  public:
    std::pair<bool, antlrcpp::Any> VarQuery(std::string var_name);
    void VarRegister(std::string var_name, antlrcpp::Any var_data);
};

随后, 对于简单的赋值语句, 即 a = b 或类似操作, 我们只需要首先访问右值, 然后强制 VarRegister 即可:

if (testlist_array.size() == 2) {
    std::string var_name = testlist_array[0]->getText();
    antlrcpp::Any num = visitTestlist(testlist_array[1]);
    // TODO
    var_table.VarRegister(var_name, num);
}

对于自算术运算同理:

if (ctx->augassign()) {
    std::string opt = ctx->augassign()->getText();
    std::string var_name = testlist_array[0]->getText();
    auto var = var_table.VarQuery(var_name);
    auto num = visitTestlist(testlist_array[1]);
    if (!var.exist)
        throw Exception("", UNDEFINED);
    if (opt == "+=") {
        var_table.VarRegister(var_name, var.data + num);
    } else if (opt == "-=") {
        var_table.VarRegister(var_name, var.data - num);
    } else if (opt == "*=") {
        var_table.VarRegister(var_name, var.data * num);
    } else if (opt == "/=") {
        var_table.VarRegister(var_name, var.data / num);
    } else if (opt == "//=") {
        var_table.VarRegister(var_name, divide(var.data, num));
    }
    return var_table.VarQuery(var_name).data;
}

对变量进行算术运算的操作则在 arith_expr (+,-) 与 term (*,/,//,%) 中实现 (显然地, 后者是前者的子节点, 因为先乘除后加减), 在 Python3.g4 中可以找到对应的语法规范:

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

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

与上述实现方式类同, 在此不再赘述. 简单功能: 判断, 循环, 逻辑语句

Python3.g4 中, 可以找到判断语句的基本组成结构:

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ('else' ':' suite)?;

其中 test 是一个判断语句, suite 是一串操作语句. 这里的难点在于处理好 if-else 之间的关系, 注意到他们可以更加清晰地表示为

if (test1)
    suite1
elif (test2)
    suite2
else
    suite3

也即, 在最后一个 else 存在的情况下, 会且仅会执行一段 suite 语句, 其进入条件直接由对应编号相等的 test 语句进行控制, 这样一来, 就能写出相关内容的处理:

auto test_array = ctx->test();              // The test array for if statement
auto suite_array = ctx->suite();            // The suite array
for (int i = 0; i < test_array.size(); i++) {
    if (Convert<bool>()(visitTest(test_array[i])))
        return visitSuite(suite_array[i]);
}
if (test_array.size() < suite_array.size()) // Else statement
    return visitSuite(suite_array.back());
return {};

对于 while 语句的处理也是同理, 这里需要特判的是循环语句的提前中断标志, 例如, continue, breakreturn, 可以考虑采用枚举类型 enum FlowType { kFlowContinue, kFlowBreak, kFlowReturn};. 于是对于 while 语句类型 while_stmt: 'while' test ':' suite;, 就可以直接使用 C++ 的 while 逻辑进行实现.

auto test_expr = ctx->test();
auto suite_expr = ctx->suite();
while (Convert<bool>()(visitTest(test_expr))) {
    antlrcpp::Any ret = visitSuite(suite_expr);
    if (ret.is<FlowType>() && ret.as<FlowType>() == kFlowBreak)
        break;
    if (ret.is<std::pair<FlowType, antlrcpp::Any>>() && ret.as<std::pair<FlowType, antlrcpp::Any>>().first == kFlowReturn)
        return ret;
}
return {};

紧接着就是逻辑运算的实现 (当然, 这个也是上面的判断循环语句的前提), 语法结构按照 Python 中的操作顺序进行:

or_test: and_test ('or' and_test)*;
and_test: not_test ('and' not_test)*;
not_test: 'not' not_test | comparison;

这里需要注意的是 and not 语句需要及时终端, 也即 and 逻辑中一错皆错, or 逻辑中一对皆对:

// void visitOr_test(ctx)
for (int i = 0; i < or_array.size(); i++) {
    if (Convert<bool>()(visitAnd_test(or_array[i])))
        return true;
}
return false;
// void visitAnd_test(ctx):
for (int i = 0; i < not_array.size(); i++) {
    if (!Convert<bool>()(visitNot_test(not_array[i])))
        return false;
}
return true;
// void visitNot_test(ctx)
if (ctx->NOT())
    return !(Convert<bool>()(visitNot_test(ctx->not_test())));

至此就完成了一个极简 Python 代码 (无函数, 无列表, 无复杂类型) 的解释器. 进阶功能: 函数与局部变量

函数的实现和调试是笔者完成这一项目过程中耗时较多的一部分, 其难点在于递归调用与局部变量的处理, 在这里, 前面实现的 class Scope 就有必要更改了:

class Scope {
    // std::unordered_map<std::string, antlrcpp::Any> data_table;
    std::vector<std::unordered_map<std::string, antlrcpp::Any>> data_table;
};

每进入一层函数, 就需要在 vector 中新建一维 unordered_map, 而在函数内进行参数访问的时候, 有可能出现: 访问局部变量, 访问全局变量, 局部变量和全局变量重名 这几种情况, 因此, 在 VarQuery 中需要实现访问优先级的判断:

QueryResult Scope::VarQuery(const std::string &var_name) const {
    auto it = data_table.back().find(var_name);
    if (it == data_table.back().end()) {
        it = data_table.front().find(var_name);
        if (it == data_table.front().end())
            return QueryResult(false, 0);
    }
    return QueryResult(true, it->second);
}

于是就可以进行函数的定义, 根据 Python3.g4:

funcdef: 'def' NAME parameters ':' suite;
parameters: '(' typedargslist? ')';

函数的定义由参数定义和语句定义两部分组成, 在定义环节, 首先注册函数的参数, 注意直接访问默认传参的右值

int fir_init = tfpdef_array.size() - test_array.size();
for (int i = 0; i < tfpdef_array.size(); i++) {
    std::string var_name = tfpdef_array[i]->NAME()->getText();
    antlrcpp::Any var_data;
    if (i < fir_init)
        var_data = {};                                  // Default parameter as null
    else
        var_data = visitTest(test_array[i - fir_init]); // Visit Default test
    para_array_init.push_back(make_pair(var_name, var_data));
}
return para_array_init;

然后直接进行函数的定义, 不需要进行语句访问

std::string func_name = ctx->NAME()->getText();
Function func_data({visitParameters(ctx->parameters()).as<std::vector<std::pair<std::string, antlrcpp::Any>>>(), ctx->suite()});
func_table.VarRegister(func_name, func_data);
return {};

函数的调用则是在 atom_expr 中进行的, 在每一次调用过程中, 对于基本的函数访问, 分为三个阶段进行:

  • 往栈中新压入一个哈希表, 注册函数参数.
  • 访问函数.
  • 注销函数参数与函数局部变量, 将栈顶弹出.
  • 注册函数参数过程中, 则可以给每一个参数先赋予临时变量, 然后再用传入的数值对参数值进行 override.
Function func_now = func_query.data;
var_table.push();
stk++;
for (int i = 0; i < func_now.para_array.size(); i++)
    var_table.VarRegister(func_now.para_array[i].first, func_now.para_array[i].second);
// TODO
for (int i = 0; i < argsArray.size(); i++)
    var_table.VarRegister(func_now.para_array[i].first, argsArray[i]);
antlrcpp::Any ret_value = visitSuite(func_now.suite_array);
stk--;
var_table.pop();

Python 特性: Arglist, Keyword positioning

Arglist

在 Python 解释器的实现过程中, 也学到了一些 Python 中很难实现独具的特性, 在这里挑两个进行简单介绍: 首先是稍微容易实现的 Arglist, 参考 Python3.g4 的定义:

arglist: argument (',' argument)*  (',')?;

也就是说, 会有类似

a, b = 1, 2
a, b = func()

于是需要注意在赋值语句, 函数返回语句等处注意遇到 arglist 时需要用 vector 传参.

Keyword positioning

这是一个令人实现起来非常头大的功能, 举个栗子: 对于函数 def func(a, b, c = f(1), d = g(1)), 我们可以考虑调用方式

func(1, 2, 3)
func(a = 1, 2)
func(c = 1, 2, a = 3)

也即, 可以在调用时单独对参数进行赋值. 但是因为在笔者的实现方式中, 访问一个 test 的返回值是原始数据, 而非像 hastin 等巨佬一样早早发现应该返回 std::pair<std::string(var_name), antlrcpp::Any(var_data)>

导致在处理这个的时候做的非常麻烦, 在此不做展开.

一些总结

该项目的实现最大难点在于正确使用每个第三方库接口, 以及看懂 Python3.g4 里面给出的语法规则. 后面在调试的时候遇到的问题有: 没有搞懂有些语法细节, 比如 keyword positioningdefault value 的混合使用. 在类型转化的时候出现了不少问题, 最后改为使用模板类特化的方式进行了实现.

template <class T> class Convert {
  public:
    T operator()(const antlrcpp::Any &num);
};
template <> class Convert<ll>;
template <> class Convert<double>;
template <> class Convert<bool>;
template <> class Convert<std::string>;



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 2022 届湖北省二十一所重点中学高三第三次联考数学参考答案与评分细则
  • 2022 届湖北省二十一所重点中学高三第三次联考数学试题
  • OI 退役日记 (fake)
  • QOI 格式的图像压缩工具
  • 寒假特训营数学研究报告