从正则表达式到算符优先：手把手教你用C语言写语法分析器

从正则表达式到算符优先：用C语言构建语法分析器的工程实践

在当今软件开发领域，处理自定义表达式和领域特定语言(DSL)的需求日益增长。无论是配置文件解析、公式计算引擎，还是业务规则处理，都需要高效可靠的语法分析能力。本文将带您深入探索语法分析的核心技术，从广为人知的正则表达式出发，逐步深入到更强大的算符优先分析法，最终用C语言实现一个完整的语法分析器。

1. 语法分析技术演进：从正则到算符优先

正则表达式无疑是文本处理中最广为人知的工具，它通过有限状态自动机实现高效的词法分析。典型的正则引擎可以处理如下的模式匹配：

// 简单的整数匹配正则表达式 const char* int_regex = "^[+-]?[0-9]+$";

然而，正则表达式存在本质局限：

• 无法处理嵌套结构：如括号匹配的算术表达式
• 缺乏优先级概念：无法正确处理运算符优先级
• 不能表示递归规则：难以描述复杂的语法结构

这些限制促使我们转向更强大的语法分析技术。算符优先分析法(Operator Precedence Parsing)作为自底向上分析方法的一种，特别适合处理表达式解析。它与正则表达式的主要区别如下表所示：

2. 算符优先分析法的核心原理

算符优先分析法的核心在于建立运算符之间的优先级关系。这些关系包括：

1. a < b：a的优先级低于b，应继续移进
2. a > b：a的优先级高于b，应进行归约
3. a = b：优先级相等，通常出现在配对符号中

2.1 关键数据结构实现

在C语言中，我们可以用以下结构表示文法符号：

// 非终结符结构体 typedef struct noterminal { char symbol; char* firstvt; // FirstVT集合 char* lastvt; // LastVT集合 char** productions; // 产生式数组 int prod_count; struct noterminal* next; } NonTerminal; // 终结符结构体 typedef struct terminal { char symbol; char* precedence_table; // 优先关系表 struct terminal* next; } Terminal;

2.2 FirstVT和LastVT集合计算

FirstVT和LastVT集合是构建优先关系表的基础。它们的计算遵循以下规则：

FirstVT集合计算算法：

1. 若有产生式 A → a... 或 A → Ba...，则 a ∈ FirstVT(A)
2. 若有产生式 A → B...，则 FirstVT(B) ⊆ FirstVT(A)

void compute_firstvt(NonTerminal* grammar) { bool changed; do { changed = false; NonTerminal* nt = grammar; while (nt != NULL) { for (int i = 0; i < nt->prod_count; i++) { char* prod = nt->productions[i]; // 规则1应用 if (is_terminal(prod[0])) { changed |= add_to_set(&nt->firstvt, prod[0]); } // 规则2应用 else if (is_nonterminal(prod[0])) { NonTerminal* b = find_nt(grammar, prod[0]); changed |= merge_sets(&nt->firstvt, b->firstvt); if (strlen(prod) > 1 && is_terminal(prod[1])) { changed |= add_to_set(&nt->firstvt, prod[1]); } } } nt = nt->next; } } while (changed); }

3. 构建完整的语法分析器

3.1 优先关系表的构造

基于FirstVT和LastVT集合，我们可以构建完整的优先关系表：

void build_precedence_table(NonTerminal* grammar, Terminal* terms) { // 初始化所有关系为UNKNOWN init_table(terms); NonTerminal* nt = grammar; while (nt != NULL) { for (int i = 0; i < nt->prod_count; i++) { char* prod = nt->productions[i]; int len = strlen(prod); for (int j = 0; j < len - 1; j++) { // 处理相邻终结符情况 if (is_terminal(prod[j]) && is_terminal(prod[j+1])) { set_relation(terms, prod[j], prod[j+1], EQUAL); } // 处理终结符-非终结符情况 if (is_terminal(prod[j]) && is_nonterminal(prod[j+1])) { NonTerminal* next_nt = find_nt(grammar, prod[j+1]); for (int k = 0; k < strlen(next_nt->firstvt); k++) { set_relation(terms, prod[j], next_nt->firstvt[k], LESS); } } // 处理非终结符-终结符情况 if (is_nonterminal(prod[j]) && is_terminal(prod[j+1])) { NonTerminal* prev_nt = find_nt(grammar, prod[j]); for (int k = 0; k < strlen(prev_nt->lastvt); k++) { set_relation(terms, prev_nt->lastvt[k], prod[j+1], GREATER); } } } } nt = nt->next; } }

3.2 分析算法的实现

算符优先分析的核心算法采用移进-归约策略：

bool op_precedence_parse(const char* input, NonTerminal* grammar, Terminal* terms) { char stack[STACK_SIZE] = {'#'}; int top = 0; int input_pos = 0; while (true) { // 寻找栈顶终结符 int k = top; while (k >= 0 && !is_terminal(stack[k])) k--; Relation rel = get_relation(terms, stack[k], input[input_pos]); switch (rel) { case LESS: case EQUAL: // 移进操作 stack[++top] = input[input_pos++]; break; case GREATER: { // 归约操作 char handle[STACK_SIZE] = {0}; int handle_len = find_handle(stack, top, terms, handle); char nt = find_matching_production(grammar, handle); if (nt == '\0') return false; // 归约失败 top -= handle_len; stack[++top] = nt; break; } case ACCEPT: return true; default: return false; } } }

4. 工程实践中的优化技巧

在实际项目中应用算符优先分析法时，以下几个优化技巧可以显著提升性能：

4.1 内存管理优化

// 使用内存池管理频繁分配释放的临时字符串 typedef struct { char* buffer; size_t size; size_t used; } StringPool; StringPool* create_pool(size_t initial_size) { StringPool* pool = malloc(sizeof(StringPool)); pool->buffer = malloc(initial_size); pool->size = initial_size; pool->used = 0; return pool; } char* pool_alloc(StringPool* pool, size_t size) { if (pool->used + size > pool->size) { pool->size *= 2; pool->buffer = realloc(pool->buffer, pool->size); } char* ptr = pool->buffer + pool->used; pool->used += size; return ptr; }

4.2 错误处理与恢复

良好的错误处理机制能极大提升开发体验：

typedef enum { ERR_UNKNOWN_SYMBOL, ERR_PRECEDENCE_CONFLICT, ERR_MISSING_OPERAND, ERR_UNMATCHED_PAREN } ParseError; void report_error(ParseError err, int position, const char* context) { const char* messages[] = { [ERR_UNKNOWN_SYMBOL] = "未知符号", [ERR_PRECEDENCE_CONFLICT] = "优先级冲突", [ERR_MISSING_OPERAND] = "缺少操作数", [ERR_UNMATCHED_PAREN] = "括号不匹配" }; fprintf(stderr, "错误[%d]: %s\n位置: %d\n上下文: %s\n", err, messages[err], position, context); // 提供错误恢复建议 if (err == ERR_UNMATCHED_PAREN) { fprintf(stderr, "建议: 检查括号是否成对出现\n"); } }

4.3 性能优化策略

对于大型表达式，可以采用以下优化：

// 使用哈希表加速符号查找 typedef struct { char symbol; void* data; UT_hash_handle hh; } SymbolEntry; SymbolEntry* symbol_table = NULL; void* lookup_symbol(char sym) { SymbolEntry* entry; HASH_FIND(hh, symbol_table, &sym, sizeof(char), entry); return entry ? entry->data : NULL; } void add_symbol(char sym, void* data) { SymbolEntry* entry = malloc(sizeof(SymbolEntry)); entry->symbol = sym; entry->data = data; HASH_ADD(hh, symbol_table, symbol, sizeof(char), entry); }

5. 实际应用案例：数学表达式解析器

让我们通过一个具体案例展示如何实现数学表达式解析器：

5.1 文法定义

E → E + T | E - T | T T → T * F | T / F | F F → ( E ) | num

5.2 优先级关系表

构造的优先关系表如下：

5.3 表达式分析示例

分析表达式3 + 4 * (5 - 2)的过程：

步骤 栈 关系 输入 动作 1 # < 3 + 4 * (5 - 2 )# 移进3 2 #3 < + 4 * (5 - 2 )# 归约 F→num 3 #F < + 4 * (5 - 2 )# 归约 T→F 4 #T < + 4 * (5 - 2 )# 归约 E→T 5 #E < + 4 * (5 - 2 )# 移进+ 6 #E+ < 4 * (5 - 2 )# 移进4 7 #E+4 < * (5 - 2 )# 归约 F→num 8 #E+F < * (5 - 2 )# 归约 T→F 9 #E+T < * (5 - 2 )# 移进* 10 #E+T* < (5 - 2 )# 移进( 11 #E+T*( < 5 - 2 )# 移进5 12 #E+T*(5 < - 2 )# 归约 F→num 13 #E+T*(F < - 2 )# 归约 T→F 14 #E+T*(T < - 2 )# 归约 E→T 15 #E+T*(E < - 2 )# 移进- 16 #E+T*(E- < 2 )# 移进2 17 #E+T*(E-2 < )# 归约 F→num 18 #E+T*(E-F < )# 归约 T→F 19 #E+T*(E-T < )# 归约 E→E-T 20 #E+T*(E = )# 移进) 21 #E+T*(E) > # 归约 F→(E) 22 #E+T*F > # 归约 T→T*F 23 #E+T > # 归约 E→E+T 24 #E = # 接受