手把手教你实现C语言LR解析器（从零开始构建LR(1)语法分析器）

什么是LR解析器？

LR 是 “Left-to-right scan, Rightmost derivation in reverse” 的缩写，意思是：从左到右扫描输入，按最右推导的逆序进行归约。LR解析器属于自底向上语法分析方法，它通过不断将输入符号移进（shift）栈中，并在识别出某个产生式右部时进行归约（reduce）。

常见的 LR 解析器有 LR(0)、SLR(1)、LALR(1) 和 LR(1)。其中 LR(1) 功能最强，能处理最广泛的文法，但状态数也最多。我们本教程以 LR(1) 为例进行讲解。

LR(1) 项目与闭包

LR(1) 项目的形式为：[A → α • β, a]，其中：

• A → αβ 是一个产生式
• “•” 表示当前解析位置
• a 是向前看符号（lookahead），用于指导归约决策

要构造 LR(1) 自动机，我们需要计算每个项目的闭包（Closure）。闭包规则如下：

1. 将项目本身加入闭包
2. 若存在项目 [A → α • B β, a]，则对每个产生式 B → γ，将 [B → • γ, b] 加入闭包，其中 b ∈ FIRST(βa)

构造 LR(1) 分析表

LR(1) 分析表包含 ACTION 表和 GOTO 表：

• ACTION[s, a]：决定在状态 s 遇到终结符 a 时执行 shift、reduce、accept 或报错
• GOTO[s, X]：表示从状态 s 经非终结符 X 转移到的新状态

下面是一个简化版的 C 语言表达式文法示例：

E → E + TE → TT → T * FT → FF → ( E )F → id

LR 解析器核心算法（伪代码）

一旦构建好分析表，解析过程就非常机械。以下是 LR 解析器的主循环逻辑：

初始化栈 stack = [0]输入 token 流 tokens = [id, '+', id, '$']i = 0while true:    s = stack.top()    a = tokens[i]    action = ACTION[s][a]    if action == 'shift s1':        stack.push(a)        stack.push(s1)        i += 1    elif action == 'reduce A → β':        pop 2*|β| 个元素（符号和状态）        t = stack.top()        stack.push(A)        stack.push(GOTO[t][A])        执行语义动作（如构建AST）    elif action == 'accept':        return 成功    else:        报错

用 C 语言实现简易 LR(1) 解析器

虽然完整实现 LR(1) 构造器较为复杂，但我们可以借助工具（如 Bison）或手动构建小型文法的分析表。以下是一个极简的 C 语言 LR 解析器框架：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_STACK 100// 简化版 ACTION 表（仅支持 id + id）// 状态0: 初始状态// 状态1: 接受 F → id// 状态2: 接受 T → F// 状态3: 接受 E → T// 状态4: 移进 '+' 后的状态// 状态5: '+' 后接 idint ACTION[6][3] = {    //   id    +    $    { 1,  -1,  -1 }, // 状态0    { -1,  4,  -1 }, // 状态1（F→id）    { -1,  4,  -2 }, // 状态2（T→F），-2 表示 reduce E→T    { -1, -1,   0 }, // 状态3（accept）    { 5,  -1,  -1 }, // 状态4    { -1, -1,  -3 }  // 状态5，-3 表示 reduce E→E+T};int GOTO[6][3] = {    //   E   T   F    { 3,  2,  1 },    { -1, -1, -1 },    { -1, -1, -1 },    { -1, -1, -1 },    { -1, 2, 1 },    { -1, -1, -1 }};int main() {    char input[] = {'i', '+', 'i', '$'}; // 简化：'i' 代表 id    int stack[MAX_STACK];    int top = 0;    stack[top] = 0; // 初始状态    int i = 0;    while (1) {        int state = stack[top];        char token = input[i];        int col = (token == 'i') ? 0 : (token == '+') ? 1 : 2;        int action = ACTION[state][col];        if (action > 0) { // shift            stack[++top] = token;            stack[++top] = action;            i++;        } else if (action == 0) { // accept            printf("Parse successful!\n");            break;        } else if (action < 0) { // reduce            // 此处简化处理，实际需根据产生式长度弹栈            if (action == -2) { // E → T                top -= 2; // 弹出 T 和其状态                int g = GOTO[stack[top]][0]; // GOTO to E                stack[++top] = 'E';                stack[++top] = g;            } else if (action == -3) { // E → E + T                top -= 6; // 弹出 E + T（共3个符号，6个栈元素）                int g = GOTO[stack[top]][0];                stack[++top] = 'E';                stack[++top] = g;            }        } else {            printf("Syntax error at position %d\n", i);            return 1;        }    }    return 0;}

注意：上述代码仅为教学演示，真实项目应使用更健壮的数据结构和错误处理机制。对于复杂的 C 语言文法，建议使用 bison 工具自动生成 LR 解析器。

总结

通过本教程，你已经了解了 C语言LR解析器 的基本原理、LR(1) 项目的构造方法、分析表的作用以及如何用 C 语言实现一个简易的解析器。掌握 自底向上语法分析 技术，是深入理解编译器设计的关键一步。后续可进一步学习 LALR(1) 优化、语义动作集成、抽象语法树（AST）构建等内容。

记住，实践是最好的老师。尝试为更复杂的文法（如 if 语句、函数定义）编写 LR(1) 分析表，将极大提升你的 LR(1)语法分析 能力！