Pomian语言处理器研发笔记（三）：使用组合子构建抽象语法树

本文介绍了使用组合子构建抽象语法树(AST)的方法，重点讲解了三种基本组合子(Sequence、Or、Repeat)的实现原理及其在语法分析中的应用。通过组合子技术，可以将简单解析器组合成复杂语法规则，有效处理编程语言的语法结构。文章详细展示了组合子类的C++实现代码，包括Sequence的顺序解析、Or的选择性解析和Repeat的重复解析机制，并介绍了Grammar类作为语法规则管理器的设计思路

郝学胜-神的一滴

1489人浏览 · 2025-09-01 07:34:20

郝学胜-神的一滴 · 2025-09-01 07:34:20 发布

引言

在前两篇博客中，我们已经介绍了如何使用C++的正则表达式构建词法分析器【1†source】，以及如何使用组合模式定义表示程序结构的语法树【2†source】。在本篇博客中，我们将深入探讨如何使用组合子（Combinators）来构建抽象语法树（AST），从而实现对输入代码的语法分析和结构化处理。

组合子是一种函数式编程中的概念，用于组合简单的函数来形成更复杂的函数。在语法解析中，组合子用于组合简单的解析器来形成更复杂的解析逻辑。通过组合子，我们可以将复杂的语法分解为简单的构建块，并通过组合这些构建块来定义整个语言的语法。

组合子的基本概念

在现代编译器和解释器的设计中，组合子是一种强大的工具，用于描述和构造语言的语法结构。常见的组合子包括：

Sequence（顺序） ：按顺序应用多个解析器，只有当所有解析器都成功匹配时，整个组合才成功。
Or（或） ：尝试多个解析器中的一个，返回第一个成功匹配的解析结果。
Repeat（重复） ：重复应用某个解析器，直到无法再匹配。

通过这些组合子，我们可以灵活地定义各种语法规则，从而构建出复杂的语法结构。

组合子的实现

在Pomian语言处理器中，我们实现了三种基本的组合子：Sequence、Or和Repeat。下面将分别介绍它们的实现细节。

1. Sequence组合子

Sequence组合子用于按顺序应用多个解析器。只有当所有解析器都成功匹配时，整个组合才成功。其parse方法的实现如下：

class Sequence : public IParser 
{
private:
    std::list<IParser*> m_parsers;
    std::function<AstNode* (const std::vector<AstNode*>&)> m_combine;

public:
    Sequence(const std::list<IParser*>& parsers, const std::function<AstNode*(const std::vector<AstNode*>&)>& combine)
        : m_parsers(parsers), m_combine(combine)
    {
    }

    AstNode* parse(Tokenizer* tokenizer) override
    {
        std::vector<AstNode*> nodes;
        for (auto parser : m_parsers)
        {
            AstNode* node = parser->parse(tokenizer);
            if (!node)
            {
                // 回溯到初始状态
                tokenizer->undo();
                return nullptr;
            }
            nodes.push_back(node);
        }
        return m_combine(nodes);
    }

    ~Sequence()
    {
        for (auto parser : m_parsers)
        {
            delete parser;
        }
    }
};

2. Or组合子

Or组合子用于尝试多个解析器中的一个，返回第一个成功匹配的解析结果。其parse方法的实现如下：

class Or : public IParser
{
private:
    std::list<IParser*> m_parsers;

public:
    Or(const std::list<IParser*>& parsers) : m_parsers(parsers)
    {
    }

    AstNode* parse(Tokenizer* tokenizer) override
    {
        for (auto parser : m_parsers)
        {
            tokenizer->saveState(); // 保存当前状态
            AstNode* node = parser->parse(tokenizer);
            if (node)
            {
                return node;
            }
            tokenizer->restoreState(); // 回溯到保存的状态
        }
        return nullptr;
    }

    ~Or()
    {
        for (auto parser : m_parsers)
        {
            delete parser;
        }
    }
};

3. Repeat组合子

Repeat组合子用于重复应用某个解析器，直到无法再匹配。其parse方法的实现如下：

class Repeat : public IParser
{
private:
    IParser* m_parser;

public:
    Repeat(IParser* parser) : m_parser(parser)
    {
    }

    AstNode* parse(Tokenizer* tokenizer) override
    {
        std::vector<AstNode*> nodes;
        while (true)
        {
            tokenizer->saveState();
            AstNode* node = m_parser->parse(tokenizer);
            if (node)
            {
                nodes.push_back(node);
            }
            else
            {
                tokenizer->restoreState();
                break;
            }
        }
        if (nodes.empty())
        {
            return nullptr;
        }
        // 默认返回第一个节点，可以根据需要返回组合后的节点
        return nodes[0];
    }

    ~Repeat()
    {
        delete m_parser;
    }
};

Grammar类的设计

Grammar类用于定义和管理一系列的解析器，可以组合成复杂的语法结构。通过Grammar类，我们可以方便地定义各种语法规则，并生成相应的AST节点。

class GRAMMAR_EXPORT Grammar : public IParser
{
private:
    std::list<IParser*> m_parsers;

public:
    static Grammar* grammar();

    AstNode* parse(Tokenizer* tokenizer) override;

    Grammar* o_r(const std::list<IParser*>& parsers);

    Grammar* sequence(const std::list<IParser*>& parsers, const std::function<AstNode* (const std::vector<AstNode*>&)>& combine);

    ~Grammar();
};

1. 静态方法grammar()

静态方法grammar()用于获取Grammar实例。

Grammar* Grammar::grammar()
{
    Grammar* grammar = new Grammar();
    return grammar;
}

2. 解析方法parse()

parse()方法用于解析输入的Token流，并生成AST节点。

AstNode* Grammar::parse(Tokenizer* tokenizer)
{
    for (IParser* parser : m_parsers)
    {
        parser->parse(tokenizer);
    }
    return nullptr;
}

3. 添加或逻辑o_r()

o_r()方法用于添加或逻辑，尝试多个解析器中的一个。

Grammar* Grammar::o_r(const std::list<IParser*>& parsers)
{
    m_parsers.push_back(new Or(parsers));
    return this;
}

4. 添加顺序逻辑sequence()

sequence()方法用于添加顺序逻辑，按顺序应用多个解析器，并组合结果。

Grammar* Grammar::sequence(const std::list<IParser*>& parsers, const std::function<AstNode* (const std::vector<AstNode*>&)>& combine)
{
    m_parsers.push_back(new Sequence(parsers, combine));
    return this;
}

5. 析构函数

析构函数用于释放资源。

Grammar::~Grammar()
{
    for (IParser* parser : m_parsers)
    {
        delete parser;
    }
    m_parsers.clear();
}

示例代码解析

下面是一个具体的代码示例，展示了如何使用组合子构建AST，解析输入的表达式。

Tokenizer *tokenizer = new Tokenizer(
	{
		//"if(YongYong == 250)", 
		    "250 + 188; "
	});

Grammar* grammar = createPomian();
grammar->parse(tokenizer);

1. 创建Tokenizer

Tokenizer负责将输入字符串分解为Token。在本例中，输入字符串为“250 + 188;”，Tokenizer将其分解为数字Token、操作符Token和分号Token。

2. 创建Grammar实例

通过createPomian()函数创建Grammar实例，并定义具体的语法规则。

Grammar* createPomian()
{
    Grammar* grammar = Grammar::grammar();
    grammar->sequence({ createNumber(), createOperator({"+", "-"}), createNumber()}, [](const std::vector<AstNode*>& nodes)->AstNode* {

        OperatorNode* operatorNode = dynamic_cast<OperatorNode*>(nodes.at(1));
        BinaryExpr* binaryExpr = new BinaryExpr(
            operatorNode->getOperatorToken(), 
            nodes.at(0), 
            nodes.at(2)
        );
        operatorNode->setOperatorToken(nullptr);
        delete operatorNode;
        return binaryExpr;
    });
    return grammar;
}