当前位置：首页 > ds >正文

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

ds 2025/9/2 5:35:04

引言

在前两篇博客中，我们已经介绍了如何使用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;
}