企业官网建设流程全解析

简介：面向编译原理课程实验的语法分析程序设计与实现文档，适合正在完成词法分析后续实验、需要理解LL(1)预测分析流程的高校学生与自学者参考，也适用于互联网自学场景。内容围绕算术表达式简化文法展开，从实验目的、BNF定义与LL(1)文法改写，到预测分析表构造、C++源程序结构及分析栈、剩余串输出均有涉及，并给出符合语法与典型错例的测试要求，可用于对照检查“RIGHT/ERROR”判定与中间过程展示。资源包含1个doc文件，压缩包约127KB，体量轻便，便于直接查阅实验报告与代码片段。目前已有145人学习下载。对需要梳理语法分析流程图、数据结构、预测分析表填充和排错思路的读者，这份文档可作为课程实验的参考范本与复盘材料。

1. 从一份能跑通的实验报告说起：语法分析程序设计与实现真正要交的是什么

语法分析程序设计与实现这个题目，绝大多数人第一版都能跑出结果：把实验一扫描器输出的UCON,PL,UCON,MU,ID手工翻译成i+i*i，套一张 LL(1) 预测分析表，屏幕上刷出 RIGHT，截图一贴就完事。真正卡人的是第二周——换成(i+i)*i#就报错，输入i+#时程序直接退出、什么都不打印，导师问一句“你的分析栈在第 4 步长什么样”，答不上来。这套方案要解决的不是“能不能跑”，而是把文法改造、预测分析表构造、分析栈驱动、出错中间结果输出、词法语法合并这几件事做成一条能自证正确的链路：每一步都有栈、剩余串、所用产生式可查，正确串输出 RIGHT 并附完整过程，错误串输出 ERROR 并保留出错瞬间的现场。它适合正在做编译原理课设、毕设前期原型，或者需要交一份完整语法分析模块方案的人，照着改文法就能迁移到赋值语句、条件语句的分析上。

2. 文法改造与预测分析表：从 G2[E] 到 5×8 的 LL(1) 表

2.1 五种方法里为什么落到 LL(1)

题目给的候选是算符优先、递归下降、LL(1)、SLR(1)、LR(1)。这几个不是难度递增的排列，而是四种不同代价的取舍，选错方向后面全是返工。

我一般建议课设场景选 LL(1)，理由很实在：它的中间状态就是“一个栈 + 一个剩余串 + 一条产生式”，三样东西都能直接打印成表，答辩时指着表格讲，评委跟得上；而 SLR(1) 的项目集规范族在纸上画到第 9 个状态就开始乱，一旦算错一个闭包，后面全崩，调起来是典型的黑匣子。代价是文法必须改写成 LL(1) 形式，这一步反而是最值得写进报告的干货。

2.2 消除左递归与提取左公因子：G2 改写前后的对照

原始文法 G2[E] 是这样的：

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

E → E+T是直接左递归，T → T*F同理。如果不改写就直接建表，M[E][i]会填上E→E+T，分析栈把 E 弹出又压回 E，栈长度不减，程序进入死循环——这是最常见的第一类事故。

改写的标准动作是引入新非终结符吸收左递归的“尾巴”。E → T | E+T | E-T的右部都以 T 开头，提取出来得到E → T G，G → +T G | -T G | ε。T 层同样处理，得到T → F S，S → *F S | /F S | ε。F 没有左递归，但要注意F → i | (E)两条右部首符号不同，不需要提左公因子。最终文法：

E → T G G → + T G | - T G | ε T → F S S → * F S | / F S | ε F → i | ( E )

改写前后的语言是等价的，但结合性从“左递归隐含的左结合”变成了“由 G、S 的递归展开顺序保证的左结合”，这一点在报告中要写一句，否则评委会追问“你改了文法，i-i-i还是左结合吗”。答案是：E → TG，G 展开为-TG再展开为-TG，栈里先处理左边的减法，语义仍是(i-i)-i。

提示：ε 在代码里不要用空字符表示，用一个可见占位符（比如^）存进产生式右部，否则strcpy之后长度和内容对不上，逆序入栈时会读到脏字符。

2.3 FIRST、FOLLOW 与 5×8 预测分析表的填法

改写完文法，先算两个集合，再填表。终结符集是{ i, +, -, *, /, (, ), # }共 8 个，非终结符集是{ E, G, T, S, F }共 5 个，所以预测分析表是一个 5 行 8 列的二维结构。集合结果如下：

填表规则两条：对每个产生式A → α，若终结符a ∈ FIRST(α)，则M[A][a] = A → α；若ε ∈ FIRST(α)，则对所有b ∈ FOLLOW(A)，M[A][b] = A → ε。按这个规则填出来的表，任何一个格子最多只有一条产生式，说明改写后的文法是 LL(1) 文法：

有两处容易被问住，提前想好答案。第一处：G → ε为什么填在)和#两列，因为FOLLOW(G) = { ), # }，G 出现在 E 的尾部，E 后面只可能跟右括号或输入结束符。第二处：S → ε为什么填了四列，因为 S 出现在 T 的尾部，T 后面可能跟加减号（同级运算要继续）、右括号、结束符，所以FOLLOW(S)是四个符号。填表时漏列是高频错误，漏掉某一列不会立刻报错，要等测试用例走到那个分支才暴露，属于典型的“当时能跑、验收翻车”。

3. 数据结构与分析栈：三个数组加一个产生式类

3.1 产生式结构体设计：origin、array、length 三件套

LL(1) 分析器的核心数据结构是“产生式”，它需要承载三样信息：左部是谁、右部符号序列是什么、右部有多长。用一个轻量类就够，不必上std::string，因为右部最长只有 3 个符号（+TG、*FS、(E)），定长字符数组更贴近课设环境，也不必担心动态内存。

// 产生式：origin 为左部非终结符，array 为右部符号串，length 为右部符号个数 class type { public: char origin; // 左部，如 'E' char array[5]; // 右部，如 "TG"、"+TG"、"(E)"、ε 记作 '^' int length; // 右部符号个数，用于逆序入栈的循环边界 };

array[5]是留了余量的，实际最长右部+TG只有 3 个字符，加上字符串结束符占 4 字节。如果后面要扩展成赋值语句S → id = E，5 就不够了，通常的做法是把它提到 8 或 16，同时把length的判断改成动态读取，别在代码里硬编码 3。

产生的实例一共 10 个，对应改写后文法的 10 条产生式（含 3 条 ε 产生式）：

这里有个血泪经验：变量命名要跟产生式严格对应，g是+TG、g1是-TG、g2是 ε，一旦串行，填表时把g1填到加号列，程序不会崩，但i-i会被当成i+i走完流程输出了 RIGHT。这种错误靠肉眼看代码看不出来，只能靠测试用例挡。

3.2 分析栈、剩余串与指针约定

分析器需要四个数组和四个整型游标：

char A[30]; // 分析栈，栈底放 '#'，栈顶放当前待处理符号 char B[30]; // 剩余输入串，末尾必须带 '#' char v1[8] = {'i','+','-','*','/','(',')','#'}; // 终结符，同时是分析表的列索引 char v2[5] = {'E','G','T','S','F'}; // 非终结符，同时是分析表的行索引 int top = 0; // 栈顶下标，约定始终指向栈顶有效元素 int b = 0; // 剩余串当前待匹配位置 int l = 0; // 输入串总长度（含 '#'） int k = 0; // 步骤计数器，输出时从 0 开始编号

指针约定是整套代码里最容易被忽略、又最容易导致输出错位的部分。我的做法是：top永远指向栈顶有效元素，入栈用A[++top] = x，出栈用x = A[top--]；b永远指向“下一个待匹配的输入符号”，匹配成功后才b++。把这两条写死在注释里，后面所有打印和对齐都以此为基准，就不会出现“栈打出来少一位、剩余串多一位”的玄学现象。

3.3 表初始化与分析栈输出对齐

预测分析表用二维数组type C[5][8]。初始化时先把所有格子填成一个哨兵产生式，左部设为'N'，表示“此处无产生式”，后面查表时只要判断origin == 'N'就知道是语法错误，不需要额外维护一个布尔矩阵。

type C[5][8]; // C[非终结符行号][终结符列号] void initTable() { // 第一步：全表置空哨兵，'N' 表示该格子无产生式 for (int m = 0; m < 5; m++) for (int n = 0; n < 8; n++) C[m][n].origin = 'N'; // 第二步：按第 2 章那张 5×8 表逐格填入 C[0][0] = e; C[0][5] = e; // E → TG 于 i, ( C[1][1] = g; C[1][2] = g1; C[1][6] = g2; C[1][7] = g2; // G 行：+, -, ), # C[2][0] = t; C[2][5] = t; // T → FS 于 i, ( C[3][1] = s2; C[3][2] = s2; C[3][3] = s; // S 行：+,-,* 处 C[3][4] = s1; C[3][6] = s2; C[3][7] = s2; // S 行：/,),# C[4][0] = f1; C[4][5] = f; // F → i / F → (E) }

分析栈的打印看着简单，实际是错得最多的地方。正确的打印函数要跟top的约定一致，只打到top为止：

// 打印分析栈：从栈底 0 打到栈顶 top void printStack(const char A[], int top) { for (int a = 0; a <= top; a++) cout << A[a]; cout << "\t\t"; } // 打印剩余串：先补 b 个空格做左对齐，再输出 B[b..l] void printRest(const char B[], int b, int l) { for (int j = 0; j < b; j++) cout << ' '; for (int j = b; j <= l; j++) cout << B[j]; cout << "\t\t\t"; }

printRest里补空格那一步不是装饰，是为了让输出表在终端里逐行对齐，看的人能一眼看出“剩余串正在从左往右被吃掉”。如果补的是b个空格，那么第 k 步的剩余串首字符正好落在第 k 列，整张表读起来就是一条斜线，答辩时非常直观。反过来说，如果这里写成j <= b或者j < l，表格立刻歪掉，虽然不影响分析结果，但会给评委留下“细节没打磨”的印象。

4. 驱动循环：查表、匹配、逆序入栈的一条主线

4.1 主循环骨架与三个分支的划分

整个分析器就是一个循环，每次取栈顶符号x，判断它是终结符还是非终结符，然后走三条分支之一：终结符匹配、非终结符展开、出错。循环的终止条件是栈顶为#且当前输入符号也是#。

// 初始格局：栈底 '#'，栈顶文法开始符 'E' A[0] = '#'; A[++top] = 'E'; int k = 0; // 步骤号 bool finish = false; char x, ch = B[0]; // ch 为当前输入符号 cout << "步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n"; do { x = A[top--]; // 弹出栈顶符号（注意：先弹出，后打印会错位，见第 5 章） /* 三个分支在这里展开 */ } while (!finish);

这个骨架里有一处细节值得单独说：x = A[top--]把出栈和取符号合成了一句，写起来短，但对打印不友好——等到打印的时候栈顶已经被弹掉了。我在实际项目里的做法是拆成两句，先取x = A[top]，打印完当前格局，再top--。多写一行，换来的是输出表跟教科书上的分析过程完全对得上，验收时省掉一堆解释。

4.2 终结符分支：匹配与推进

终结符分支只做两件事：跟当前输入符号比较，相等就推进，不等就报错。注意#要单独处理，它是分析的结束标志，遇到它说明整串分析成功。

bool isTerminal(char c) { for (int j = 0; j < 8; j++) if (c == v1[j]) return true; return false; } if (isTerminal(x)) { if (x == '#' && ch == '#') { // 双方都是结束符，接受 printStack(A, top); printRest(B, b, l); cout << "acc!" << endl; finish = true; } else if (x == ch) { // 栈顶终结符与输入符号匹配 printStack(A, top); printRest(B, b, l); cout << "匹配 " << x << endl; ch = B[++b]; // 输入指针后移，取下一个符号 } else { // 终结符不匹配 printStack(A, top); printRest(B, b, l); cout << "ERROR：期望 " << x << "，实际 " << ch << endl; finish = true; } }

ch = B[++b]这句是“先自增后取值”，等价于b = b + 1; ch = B[b];。要保证B数组末尾一定有#，否则b会一路越界读到未初始化内存，Windows 上可能读到一串随机字符，Linux 上直接段错误，同一份代码换个环境就翻车。

4.3 非终结符分支：查表、逆序入栈、ε 出栈

非终结符分支是整个程序的核心动作：用x查行号、用ch查列号，取出产生式，然后把右部逆序压栈——因为栈是后进先出，要让最左符号最后入栈、最先被处理。

int row = -1, col = -1; for (int j = 0; j < 5; j++) if (x == v2[j]) { row = j; break; } for (int j = 0; j < 8; j++) if (ch == v1[j]) { col = j; break; } type prod = C[row][col]; if (prod.origin != 'N') { // 表格该格有产生式 printStack(A, top); printRest(B, b, l); cout << prod.origin << " -> "; for (int j = 0; j < prod.length; j++) cout << prod.array[j]; cout << endl; // 逆序入栈：右部最后一位先入，第一位最后入，保证左端先出栈 for (int j = prod.length - 1; j >= 0; j--) A[++top] = prod.array[j]; // ε 产生式只入栈了 '^'，要立刻弹掉，否则栈顶残留占位符无法匹配任何终结符 if (A[top] == '^') top--; } else { // 表格该格为空，语法错误 printStack(A, top); printRest(B, b, l); cout << "ERROR：非终结符 " << x << " 面临输入 " << ch << " 时无产生式可用" << endl; finish = true; }

逆序入栈那两行看起来简单，但它决定了分析顺序。以E → TG为例，逆序入栈后栈从底到顶是# T G，栈顶是T，先展开 T——正是最左推导的要求。如果写成正序入栈，栈顶变成G，会先尝试展开G，遇到i查表得到空，程序立刻报错，而输入串其实是合法的。这类 bug 的表现是“所有带括号和乘法的表达式都错，纯加法却对”，非常迷惑。

ε 的产生式要单独处理。g2的右部是^，长度 1，入栈后栈顶是^，它既不是终结符也不是非终结符，下一轮循环查表必然失败。所以在入栈之后立刻判断并弹出。有的实现是在 ε 产生式分支里干脆跳过入栈，两种写法等价，但前一种更统一，因为打印“所用产生式”的代码只有一份。

4.4 词法与语法合并：从扫描器输出到分析栈输入

实验要求第二条明确写着“将词法、语法分析合在一起构成一个完整的程序”。很多人的做法是把扫描器结果手工敲一遍，这不算合并。真正的合并是在两个模块之间加一层 token 映射：扫描器输出种别码序列（例如UCON,PL,UCON,MU,ID），映射函数把它翻译成单字符终结符，再拼上#送进B数组。

// 扫描器种别码 → 语法分析终结符的映射表 char mapToken(const string &t) { if (t == "UCON" || t == "ID") return 'i'; // 无符号常数与变量都归约为运算对象 i if (t == "PL") return '+'; if (t == "MI") return '-'; if (t == "MU") return '*'; if (t == "DI") return '/'; if (t == "LP") return '('; if (t == "RP") return ')'; return '\0'; // 未识别，交给词法错误报告 }

这一层映射有两个坑。第一个是分隔符，扫描器输出的常常是带逗号的串，甚至有全角逗号混进去，直接用cin >> ch逐字符读会把逗号也当成输入符号，落进“输入串中有非法字符”的分支。处理方式是先按分隔符切分，再逐个映射。第二个是错误分层，词法阶段发现非法字符，应该报“词法错误：第 N 个 token 无法识别”，而不是笼统地报语法错——语法分析器拿到的是一个\0，它没有能力判断这是拼写错误还是缺少运算对象。把两个层次的错误信息分开，出错定位的精度会差一个量级，这也是验收时最容易被追问的点。

5. 避坑与排查：五条最容易翻车的点

5.1 分析栈打印错位，过程表对不上教科书

现象：程序能输出 RIGHT，但打印出的分析栈每一行都比教材上的少一个符号，或者第 1 步的栈是E而不是#E，整张表看着别扭。

原因：出栈和打印的顺序写反了。x = A[top--]先把top减了 1，再调用打印函数，此时栈顶已经少了一位；为了把输出“掰回来”，有人会硬编码for (a = 0; a <= top + 1; a++)，多打一位。这种补丁只在“每次恰好弹一个符号”时成立，遇到 ε 产生式多弹一次，表格立刻又歪。

解决：把约定写死——top始终指向栈顶有效元素，打印范围就是0..top。出栈拆成x = A[top]; printStack(); top--;或者干脆在弹出前打印。别用+1这种补偿式写法，它没有后悔药，改一处要连带改三处。

5.2 直接对原始文法建表，程序死循环

现象：输入任意合法串，程序卡在第 3、4 步不动，栈长度不增不减，CPU 占满。

原因：E → E+T这种直接左递归没有消除就填了表。分析栈弹出E，查表又压回E+T，E永远在栈顶，输入指针b一动不动。

解决：建表前先做消除左递归和提左公因子的改写，改完再算 FIRST/FOLLOW。验证办法很简单：把改写后的文法逐条看一遍，任何一条产生式的右部首符号如果等于左部，就是没改干净。另外，改写后要重新验证一遍语言等价，用i-i-i、i/i/i各测一次，确认结合性没变。

5.3 ε 产生式的占位符残留在栈顶

现象：输入i+i#，前几步正常，走到G → ε之后报“非终结符 ^ 面临输入 # 时无产生式可用”，而i+i#明明是合法句子的前缀。

原因：ε 产生式右部用^占位，逆序入栈后^留在栈顶。下一轮循环把它当非终结符去v2里找行号，找不到，row保持 -1，C[-1][col]直接越界读内存，运气好读到'N'报错，运气不好读到别的产生式继续跑出一堆乱码。

解决：入栈后立即判断if (A[top] == '^') top--;。同时在查表前加一道防御：row < 0 || col < 0时直接输出“内部错误：符号未在终结符/非终结符表中注册”，把越界挡在查表之前。这道防御在调试期能救命，别嫌它啰嗦。

5.4 token 流没有归一化，词法语法接不上

现象：单独测i+i*i#全对，接上扫描器之后，所有输入都报“输入串中有非法字符”。

原因：扫描器输出的是UCON,PL,UCON,MU,ID这种带逗号（甚至全角逗号）的种别码串，而语法分析器的B数组期望的是单字符终结符序列i+i*i#。中间缺了映射层，逗号被当成输入符号，第一个就非法退出。

解决：在扫描器和分析器之间固定加一层mapToken，先按分隔符切分，再逐 token 映射，映射失败的 token 单独报词法错误并给出位置。同时把输入串末尾的#由分析器补齐，不许由调用方手工拼，避免“有时有 #、有时没有”的随机错误。

5.5 出错就 exit，错误串没有任何中间结果

现象：输入i+#，屏幕上一片空白然后程序结束；或者输入(i+i#，只打印了一个“出错”就没了。验收时被要求“显示分析至此所得的中间结果”，拿不出来。

原因：错误分支里直接写了exit(1)，把已经算出来的分析栈和剩余串一起丢掉了。更糟的是有的实现连正确的接受分支也用exit(1)，脚本化测试时返回码非 0，被测试框架判成失败。

解决：错误处理只设finish = true跳出循环，不调用exit；跳出去之后统一打印一次“出错现场”，包括当前步骤号、分析栈内容、剩余串内容、栈顶符号与当前输入符号、以及一句人能看懂的原因（“期望)，实际#”比“出错”有用十倍）。正常接受时用return 0结束进程。顺带说，exit用多了还有一个副作用：局部对象的析构不执行，如果后面把输出重定向到文件，缓冲区没刷新，文件里是空的——这类问题查起来非常耗时间。

6. 验收与答辩：用一张分析过程表自证正确

验收不是“跑通一个例子”，而是拿一组覆盖分支的用例，配合逐行可核对的过程表，证明程序在每条路径上都对。我一般会准备下面这张表，测试时按行执行、记录实际输出，跟期望逐条对照：

T02 的过程表要能背下来，答辩时很可能被点名讲其中一步。以i+i*i#为例，前几步是这样的：

走到第 6 步之后栈里是#GT，剩余串是i*i#，跟第 1 步格局相同但输入前进了一段——这个“格局重现、输入推进”的现象正好说明 G 的递归展开在消耗加减号，讲清楚这一点，比背十行输出更有说服力。

答辩常问的三个问题，答案要提前捋顺。第一问“为什么FOLLOW(E)里有#”，因为 E 是开始符号，#是输入结束标志，任何能跟在完整句子后面的符号都进FOLLOW(E)。第二问“文法有二义性吗，怎么证明”，改写后的 LL(1) 文法每个表格格子最多一条产生式，无冲突即无二义，这是最直接的证明路径。第三问“换成while语句怎么扩展”，回答思路是把 G、S 那层“运算符尾巴”的写法迁移过去，Stmt → id = E | while ( E ) Stmt，同样先消除左递归、再算 FIRST/FOLLOW、再补表，流程完全复用。

从那以后我每次做这类分析器，收尾前都强制走一遍“三串对照”：一组合法串、一组错在中间、一组错在开头，三组的过程表都要能逐行念出来，念不顺的地方就是还没吃透的地方。希望帮到你。

本文还有配套的精品资源，点击获取