手把手教你用C++实现一个简易的表达式语法分析器（附完整源码）

手把手教你用C++实现一个简易的表达式语法分析器（附完整源码）

在编译原理的学习中，语法分析器是一个承上启下的关键环节。它接收词法分析器生成的单词序列，检查其是否符合语法规则，并构建语法树为后续的语义分析和代码生成做准备。对于初学者来说，如何将抽象的First/Follow集、递归下降等概念转化为可运行的代码，往往是最具挑战性的部分。

本文将聚焦于表达式语法分析器的实现，采用C++语言和递归下降分析法，带你从零开始构建一个可实际运行的语法分析器。我们不会过多纠缠于理论推导，而是通过代码实例和逐行注释，让你快速掌握语法分析器的核心实现逻辑。无论你是正在完成编译原理实验作业的学生，还是对编译器实现感兴趣的开发者，这篇文章都能为你提供实用的参考。

1. 准备工作：理解表达式文法

在开始编码之前，我们需要明确要分析的表达式文法规则。以PL/0语言的表达式部分为例，其BNF定义如下：

<表达式> ::= [+|-]<项>{<加法运算符> <项>} <项> ::= <因子>{<乘法运算符> <因子>} <因子> ::= <标识符>|<无符号整数>| '(' <表达式> ')' <加法运算符> ::= +|- <乘法运算符> ::= *|/

这个文法定义了表达式的组成结构：

• 表达式由可选的加减符号和一项或多项通过加减运算符连接的项组成
• 项由一个或多个通过乘除运算符连接的因子组成
• 因子可以是标识符、无符号整数或用括号括起来的表达式

关键点：这是一个典型的LL(1)文法，适合使用递归下降分析法实现。递归下降分析法的核心思想是为每个非终结符编写一个解析函数，函数内部按照产生式规则递归调用其他非终结符的解析函数。

2. 项目结构与基础代码

我们先搭建项目的基本框架。创建一个C++项目，包含以下主要文件：

// analyzer.h - 头文件声明 #pragma once #include <vector> #include <string> enum class TokenType { IDENT, NUMBER, PLUS, MINUS, TIMES, SLASH, LPAREN, RPAREN, END }; struct Token { TokenType type; std::string value; }; class SyntaxAnalyzer { public: SyntaxAnalyzer(const std::vector<Token>& tokens); bool analyze(); private: void expression(); void term(); void factor(); void match(TokenType expected); const std::vector<Token>& tokens_; size_t current_ = 0; };

对应的实现文件开始部分：

// analyzer.cpp #include "analyzer.h" #include <iostream> #include <stdexcept> SyntaxAnalyzer::SyntaxAnalyzer(const std::vector<Token>& tokens) : tokens_(tokens) {} bool SyntaxAnalyzer::analyze() { try { expression(); match(TokenType::END); return true; } catch (const std::runtime_error& e) { std::cerr << "Syntax error: " << e.what() << std::endl; return false; } }

这个基础结构定义了：

• TokenType枚举：表示不同类型的词法单元
• Token结构体：存储词法单元的类型和值
• SyntaxAnalyzer类：核心语法分析器类，包含主要的分析方法

3. 核心分析函数实现

递归下降分析法的核心是为每个非终结符编写解析函数。我们按照文法规则逐步实现这些函数。

3.1 表达式分析

表达式由可选的加减号和一项或多项组成：

void SyntaxAnalyzer::expression() { // 处理可选的+/-符号 if (matchCurrent(TokenType::PLUS) || matchCurrent(TokenType::MINUS)) { advance(); } // 分析第一项 term(); // 分析后续的加减项 while (matchCurrent(TokenType::PLUS) || matchCurrent(TokenType::MINUS)) { advance(); term(); } }

3.2 项分析

项由一个或多个通过乘除运算符连接的因子组成：

void SyntaxAnalyzer::term() { factor(); // 分析后续的乘除因子 while (matchCurrent(TokenType::TIMES) || matchCurrent(TokenType::SLASH)) { advance(); factor(); } }

3.3 因子分析

因子可以是标识符、数字或括号表达式：

void SyntaxAnalyzer::factor() { if (matchCurrent(TokenType::IDENT) || matchCurrent(TokenType::NUMBER)) { advance(); } else if (matchCurrent(TokenType::LPAREN)) { advance(); expression(); match(TokenType::RPAREN); } else { throw std::runtime_error("Expected identifier, number or '('"); } }

3.4 辅助函数

实现几个关键的辅助函数：

bool SyntaxAnalyzer::matchCurrent(TokenType type) const { if (current_ >= tokens_.size()) return false; return tokens_[current_].type == type; } void SyntaxAnalyzer::advance() { if (current_ < tokens_.size()) { current_++; } } void SyntaxAnalyzer::match(TokenType expected) { if (matchCurrent(expected)) { advance(); } else { throw std::runtime_error("Unexpected token"); } }

4. 词法分析与语法分析的集成

为了让语法分析器更实用，我们需要将词法分析和语法分析结合起来。下面是一个简单的词法分析器实现：

std::vector<Token> lex(const std::string& input) { std::vector<Token> tokens; size_t pos = 0; while (pos < input.size()) { char c = input[pos]; if (isspace(c)) { pos++; continue; } if (isalpha(c)) { // 标识符 std::string value; while (pos < input.size() && isalnum(input[pos])) { value += input[pos++]; } tokens.push_back({TokenType::IDENT, value}); } else if (isdigit(c)) { // 数字 std::string value; while (pos < input.size() && isdigit(input[pos])) { value += input[pos++]; } tokens.push_back({TokenType::NUMBER, value}); } else { // 运算符和括号 switch (c) { case '+': tokens.push_back({TokenType::PLUS, "+"}); break; case '-': tokens.push_back({TokenType::MINUS, "-"}); break; case '*': tokens.push_back({TokenType::TIMES, "*"}); break; case '/': tokens.push_back({TokenType::SLASH, "/"}); break; case '(': tokens.push_back({TokenType::LPAREN, "("}); break; case ')': tokens.push_back({TokenType::RPAREN, ")"}); break; default: throw std::runtime_error("Invalid character"); } pos++; } } tokens.push_back({TokenType::END, ""}); return tokens; }

5. 完整示例与测试

现在我们可以将各个部分组合起来，创建一个完整的语法分析示例：

#include "analyzer.h" #include <iostream> int main() { std::string input; std::cout << "Enter an expression: "; std::getline(std::cin, input); try { auto tokens = lex(input); SyntaxAnalyzer analyzer(tokens); if (analyzer.analyze()) { std::cout << "Syntax is correct!" << std::endl; } } catch (const std::runtime_error& e) { std::cerr << "Error: " << e.what() << std::endl; } return 0; }

测试一些表达式：

Enter an expression: a + 20 * (b - 3) Syntax is correct! Enter an expression: 5 + * 3 Syntax error: Expected identifier, number or '('

6. 错误处理与调试技巧

在实际开发中，良好的错误处理机制至关重要。我们的语法分析器已经包含基本的错误检测，但还可以进一步改进：

1. 更详细的错误信息：记录错误发生的位置和上下文
2. 错误恢复：尝试从错误中恢复，继续分析后面的代码
3. 测试用例：构建全面的测试用例集合

常见问题排查表：

7. 性能优化与扩展

虽然我们的实现已经可以正确分析表达式，但还有优化和扩展的空间：

1. 抽象语法树(AST)生成：修改分析器，使其构建AST而不仅仅是验证语法
2. 运算符优先级处理：更优雅地处理运算符优先级和结合性
3. 更丰富的表达式：支持函数调用、数组索引等复杂表达式

AST节点示例：

struct ASTNode { enum class Type { BINARY_OP, UNARY_OP, IDENT, NUMBER }; Type type; std::string value; std::unique_ptr<ASTNode> left; std::unique_ptr<ASTNode> right; // 构造函数等... };

修改后的factor函数可以返回AST节点：

std::unique_ptr<ASTNode> SyntaxAnalyzer::factor() { if (matchCurrent(TokenType::IDENT)) { auto node = std::make_unique<ASTNode>(ASTNode::Type::IDENT, tokens_[current_].value); advance(); return node; } // 其他情况处理... }

实现这些扩展后，我们的语法分析器将更加强大和实用，为后续的语义分析和代码生成打下坚实基础。