企业官网建设流程全解析

简介：一份面向编译原理课程的实验文档资源，聚焦自上而下的递归下降语法分析，覆盖从文法改造到分析器构造的完整流程。文档首先对原始文法执行消除左递归处理，给出改造后的产生式及各非终结符的FIRST集与FOLLOW集，并以表格验证其满足LL(1)条件；随后结合词法分析器，补充识别float关键字并设置种别编码26，进而设计A()、M()、P()等递归下降子程序，同时提供Java代码与运行结果，便于对照调试。资源仅含1个doc文档，大小80KB，内容紧凑但步骤完整，从实验目的、文法规则、集合计算到核心代码均有覆盖，还包含函数体、声明语句块、表达式等语法单元的递归匹配演示，适合编译原理初学者理解语法分析原理，也可直接作为课程实验报告或答辩展示的参考模板。资源虽为单文档，但精炼完整，已有531人学习与下载，实用性强。

1. 递归下降分析是编译原理实验里性价比最高的自上而下方案

编译原理实验里，自上而下的语法分析往往被安排成第一次真刀真枪的代码实践，递归下降分析又是其中性价比最高的实现方式。它不需要引入 yacc、bison 或任何解析器生成器，一台编译器、一个词法推进函数、四个相互调用的递归函数，就足以把“算术表达式是否合法、优先级是否正确”讲清楚。我第一次写通这段代码时最意外的不是它通过了测试，而是它居然能一边输出最左推导、一边校验一个 18 层括号嵌套的表达式。下面从文法化简、FIRST/FOLLOW 决策，到可复现的 C 语言实现和运行结果，再讲几个让实验翻车的细节，覆盖从零到能交实验报告的全过程。

2. 自上而下语法分析的设计：从文法化简到 FIRST / FOLLOW 决策表

2.1 非终结符对应函数：递归下降为什么是“自上而下”

自上而下的意思是：语法分析从文法的开始符号出发，每一步试图推导出当前看到的输入符号。以算术表达式文法E -> E + T | T、T -> T * F | F、F -> (E) | id | num为例，如果输入是id + id * id，分析器要从E开始，反复用产生式右侧替换最左面的非终结符，直到推导出来的终结符序列恰好等于输入串。这个推导过程是最左推导，因为每一步都替换当前最左的非终结符。

递归下降把这条推导链直接翻译成函数调用。每个非终结符对应一个函数：E对应的函数负责E的产生式，当推导需要展开T时，函数体里调用T()；T需要展开F时调用F()。函数调用栈几乎就是语法树的生长路径。和 LR 分析表不同，递归下降不需要构造状态转换表，产生式直接写在if和函数调用里，因此调试时能直接看到推导路径。

但这也带来约束：分析器必须能预先决定用哪一条产生式。递归下降通常采用向前看一个 token 的预测策略，输入 token 一旦被消费就不再回退，这使分析器落在 LL(1) 的范围。遇到含公共前缀或左递归的文法，就必须先改写成适合预测的形式。这个取舍很重要，后面避坑章节会反复提到。

2.2 消除左递归与提取公因子：写递归体前必须做的两步

左递归是递归下降的第一大敌人。若保留E -> E + T，那么E()函数的第一行就会调用E()，而E()又调用E()，递归无限增长。要从文法上把直接左递归消掉：对形如A -> A α | β的产生式，改写为A -> β A'，A' -> α A' | ε。这里A'是新增的非终结符，ε代表空串。

对表达式文法应用这条规则，得到下面的对应关系：

这段改写是手工完成的，也是实验报告里第一个要解释清楚的地方。改写后每个非终结符的产生式右侧都以一个非终结符或终结符开头，E、T不会无限调用自己。注意E'和T'是新增非终结符，写 C 代码时不能出现带撇号的函数名，所以我用Ep、Tp代替。

除了左递归，左公因子也会让预测选择为难。典型例子是条件语句：S -> if E then S | if E then S else S。两条产生式都以if开头，向前看一个 token 无法区分。提取公因子后变成S -> if E then S S'，S' -> else S | ε。这样遇到else时选后者，遇到其他情况选空。公共前缀在文法设计里越早处理越省事，否则后面写出来的函数全是回溯逻辑，就不是纯粹的递归下降了。

2.3 FIRST 和 FOLLOW 怎么用：什么时候能选空产生式

递归下降函数里最容易被忽略的是空产生式。以E' -> + T E' | ε为例，当 lookahead 是+时选择带加号的产生式；当 lookahead 是右括号或结束符时选择空。判断“什么时候可以选空”用的就是 FOLLOW(E')。这是 LL(1) 分析和递归下降的通用决策：选带终结符的产生式要看 FIRST 集，选空产生式要看 FOLLOW 集。

先手工计算这套文法的关键集合。FIRST 是某个非终结符能推出的第一个终结符的集合。FIRST(E) 由 FIRST(T) 展开，而 FIRST(T) 由 FIRST(F) 决定，F的开头是(、id、num，所以 FIRST(E)=FIRST(T)=FIRST(F)={ (、id、num }。E'的开头是+，T'的开头是*，二者都还能推出空，所以 FIRST(E')={ +、ε }，FIRST(T')={ *、ε }。FOLLOW 是出现在某个非终结符之后的终结符集合。E出现在开始位置，所以$在 FOLLOW(E) 里；又因为F -> (E)，右括号也在 FOLLOW(E) 里。E'跟在E后面，所以 FOLLOW(E')=FOLLOW(E)={ )、$ }。

提示：FOLLOW(T') 和 FOLLOW(T) 不一样。初学者很容易把T'的 FOLLOW 直接抄成T的 FOLLOW，导致在Tp()函数里空分支判断错。计算时只要记住T'会出现在T可能出现的位置，还要额外加上T'前面那条产生式里跟在T'后面的终结符。

3. 手写递归下降分析器：C 语言最小实现与运行结果

3.1 终结符定义与词法推进：一个函数管住所有 token 读取

先约定终结符。本实验最小文法只需要标识符、数字、加号、乘号、左右括号和结束符六类。实际上我只区分了“以字母开头的标识符/数字字面量”和“单字符运算符”，这样词法扫描器只有二十多行。词法推进函数必须和递归函数分开，递归函数只判断当前 token，不直接移动指针，这一点对后面排错特别重要。

#include <stdio.h> #include <ctype.h> #include <string.h> static char *src; /* 当前待扫描的输入位置 */ static char token[64]; /* 最近读到的终结符原文 */ /* 读取下一个终结符，存到全局 token 数组中 */ static void advance(void) { while (*src == ' ' || *src == '\t' || *src == '\n') { src++; /* 跳过空白符与换行符 */ } if (*src == '\0') { strcpy(token, "$"); /* 用 $ 表示输入结束 */ src++; return; } if (isalpha(*src)) { /* 标识符：字母开头，后接字母或数字 */ int n = 0; while (isalpha(*src) || isdigit(*src)) { token[n++] = *src++; } token[n] = '\0'; } else if (isdigit(*src)) { /* 数字：连续的数字字面量 */ int n = 0; while (isdigit(*src)) { token[n++] = *src++; } token[n] = '\0'; } else { /* 单字符运算符或括号 */ token[0] = *src++; token[1] = '\0'; } } static int match(const char *s) { if (strcmp(token, s) == 0) { advance(); /* 只有匹配成功才推进词法 */ return 1; } return 0; }

代码逻辑说明：advance()是唯一能移动src指针的地方，它把空格、制表符、换行全部跳过，再按“标识符、数字、单字符运算符”三类读 token。数字和标识符都可能有多个字符，因此用循环读满；$是人为追加的结束标记，让递归函数可以判断输入是否耗尽。match()负责比较和推进，后续语法函数只判断 token，不触碰src指针。

给参数和边界提三个要点：第一，isalpha(*src)判断的是原始字符，不是 token 数组，别写成isalpha(token[0])，否则首次调用时会读到未初始化内容；第二，数字分支没有校验“数字后紧跟字母”的情况，所以12abc会被拆成12和abc，本实验文法里没有相邻终结符语法，这种输入会被拒绝，不影响判定；第三，EOF 分支里src++只是为了让src不再指向\0，避免重复触发 EOF 分支。

3.2 递归函数 E / T / F 与空产生式的写法

现在把消除左递归后的文法翻译成函数。Ep对应E'，Tp对应T'。每个函数都和产生式一一对应，函数体里先打印当前使用的产生式，再根据 token 选择分支。

static int E(void); static int Ep(void); static int T(void); static int Tp(void); static int F(void); static int E(void) { printf("E -> T E'\n"); if (!T()) return 0; return Ep(); } static int Ep(void) { if (strcmp(token, "+") == 0) { advance(); printf("E' -> + T E'\n"); if (!T()) return 0; return Ep(); } /* 当前 token 不是 + 时，选择空产生式 */ printf("E' -> ε\n"); return 1; } static int T(void) { printf("T -> F T'\n"); if (!F()) return 0; return Tp(); } static int Tp(void) { if (strcmp(token, "*") == 0) { advance(); printf("T' -> * F T'\n"); if (!F()) return 0; return Tp(); } printf("T' -> ε\n"); return 1; } static int F(void) { if (strcmp(token, "(") == 0) { advance(); printf("F -> ( E )\n"); if (!E()) return 0; if (!match(")")) { printf("语法错误：缺少右括号，当前 token 是 %s\n", token); return 0; } return 1; } if (isalpha(token[0]) || isdigit(token[0])) { printf("F -> %s\n", token); advance(); return 1; } printf("语法错误：期望因子(id/num/(E))，实际 token 是 %s\n", token); return 0; }

代码逻辑说明：E()调用T()再调用Ep()，对应E -> T E'。Ep()看到+就消耗+并继续递归，看到其他 token 就走 ε 分支返回成功。这样写对输入id + id * id第 2 章手工推演的推导顺序完全一致。T()和Tp()同理。F()是对因子层的处理：遇到左括号就递归调用E()去解析括号内表达式，解析完必须再匹配一个右括号；遇到标识符或数字就直接作为因子。

这里有个关键参数点：isalpha(token[0])判断的是 token 数组的第一个字符，和 3.1 词法里判断源字符的逻辑不同。由于advance()已经把数字和标识符整段读进 token，所以只要 token 首字符是字母或数字，就说明当前是一个合法的因子。如果实验文法里要支持负号，应在F()中增加-分支，形如F -> - F，而不是在词法层把负号吞掉，否则优先级会出错。

3.3 main 函数与三种运行结果：接受、拒绝、错误定位

主函数只需要三件事：读入一行输入、初始化词法状态、调用顶层E()并检查是否消费完所有 token。用fgets读入而不是scanf("%s")，因为%s会吞掉换行且无法处理空格分隔的表达式。

int main(void) { char input[256]; printf("请输入一个算术表达式："); fgets(input, sizeof(input), stdin); src = input; advance(); /* 读入第一个 token */ if (E() && strcmp(token, "$") == 0) { printf("accept：该表达式属于该文法\n"); } else { printf("reject：该表达式不属于该文法\n"); } return 0; }

运行效果如下。输入id + id * id时，程序会打印完整的最左推导过程，正好对应 2.1 节说的“函数调用栈就是语法树生长路径”：

$ ./parser 请输入一个算术表达式：id + id * id E -> T E' T -> F T' F -> id T' -> ε E' -> + T E' T -> F T' F -> id T' -> * F T' F -> id T' -> ε E' -> ε accept：该表达式属于该文法

输入id + * id时，错误会被定位到乘号处，因为F()在看到*时发现它不能作为因子的开头：

$ ./parser 请输入一个算术表达式：id + * id E -> T E' T -> F T' F -> id T' -> ε E' -> + T E' T -> F T' 语法错误：期望因子(id/num/(E))，实际 token 是 * reject：该表达式不属于该文法

输入(id + id) * id时，括号内的E会先完成整个推导，然后回到外层Tp()处理乘号。这个例子是判断优先级是否正确最直接的测试用例，建议每个实验都跑一遍。

4. 递归下降分析常见问题与避坑：现象、原因、解决

4.1 左递归没消除，程序一跑就栈溢出

现象：输入任意字符串，程序马上段错误，或者用 gdb 调试时看到E()函数里的栈帧反复出现。原因：把E -> E + T直接抄成int E(){ if(!E()) ... }，或者写成while(...){ E(); }，递归调用没有消费 token，栈越叠越高。解决：先用 2.2 节的改写把左递归消掉，再写函数体；函数体第一行先打印当前规则，再检查 token，避免无意识地递归。也可以在开发阶段临时给E()加一个depth参数，超过 200 就打印“疑似左递归”并退出，这是最快速的自检手段。

4.2 词法指针被多处挪用，token 对不上号

现象：输入id + id时前面几个 token 都匹配成功，但到某个位置总是差一个字符，调试发现src已经指向加号后面的id，加号被偷偷跳过。原因：一些人为了省事直接在F()里写src++或调用自己写的next_char()，同时又保留了全局 token。两条路径都在消费字符，等于把输入重复读了一遍。解决：词法状态只由advance()修改，递归函数只能通过 token 数组判断输入，消费 token 必须经过match()。即使某条分支出错，也不要手动改src，直接返回 0，由最外层决定 reject。

4.3 空产生式盲目成功，错误定位晚了半拍

现象：输入id / id，程序没有在/处报错，而是到最后才 reject；或者错误消息指向了后面的某个 id，让你以为错误发生在表达式末尾。原因：Ep()里看到 token 不是+就无条件走空产生式返回成功，根本没有查 FOLLOW(E')。按照 LL(1) 理论，/不在 FIRST(E') 里，也不在 FOLLOW(E') 里，此时应当当场报“非法 token”。解决：空分支加一个 FOLLOW 检查，以Ep()为例：

static int Ep(void) { if (strcmp(token, "+") == 0) { advance(); printf("E' -> + T E'\n"); if (!T()) return 0; return Ep(); } /* FOLLOW(E') = { ), $ }，遇到其他 token 直接报错 */ if (strcmp(token, ")") != 0 && strcmp(token, "$") != 0) { printf("语法错误：E' 遇到非法 token %s\n", token); return 0; } printf("E' -> ε\n"); return 1; }

注意Tp()的 FOLLOW 比Ep()多一个+，因为T'后面可以跟+。所以Tp()空分支要允许)、$、+三个 token，漏掉+会导致id + id这种合法输入被误报。

4.4 优先级层次写反，括号表达式验证不出来

现象：输入(id + id) * id和id + id * id，打印的推导序列看不出结构差异；或者后续做 AST 验证时发现乘法被挂在加法外层。原因：文法层次写反了。有人把T写成T -> T + F | F，有人把E'里放*，导致加号和乘号的嵌套顺序颠倒。解决：使用 2.2 节标准文法，并用两个用例对比：id + id * id的输出里第二个T内部先出现F再出现T' -> * F T'，说明乘号作用域在加号之下；(id + id) * id的输出里括号内先完成整个E的推导，回到外层Tp()才消费乘号。如果这两种输入打印出的层叠结构一样，优先级就没有正确体现。

4.5 换行符、多位数和负数：词法边界最容易翻车

现象：用fgets读入后，第一行还能识别，从第二行开始报“非法字符”；输入-3直接被拒；用scanf("%c")读字符时，12 + 3的数字被拆成一个一个字符。原因：换行符没有在词法扫描里跳过；负号没有被文法覆盖；数字识别没有做连续循环。解决：advance()里把空格、\t、\n、\r全部跳过；数字和标识符写成连续循环，见 3.1 节代码；负号要么在文法里增加F -> - F产生式，要么在实验报告里说明本实验终结符集合不含负号，输入时把负数写成(0-3)的形式。这里的关键是实验范围要和文法声明保持一致，不要在报告里写“支持负数”，代码里却只支持无符号数。

5. 把递归下降分析器改造成 AST 生成器：30 行代码看清楚语法树长什么样

5.1 用循环代替尾递归，让加减法保持左结合

实验如果只要求判断合法性，第 3 章的代码已经足够；但大多数编译原理实验下一步就是语义分析，需要一个语法树。常见做法是让每个递归函数返回节点指针，而不是返回布尔值。对于加减法这类左结合运算，我一般会放弃Ep()的尾递归写法，改成 while 循环，原因下面说。

typedef struct Node { char op; struct Node *left; struct Node *right; } Node; Node* new_node(char op, Node* l, Node* r) { Node* n = (Node*)malloc(sizeof(Node)); n->op = op; n->left = l; n->right = r; return n; } Node* E(void) { Node* n = T(); while (strcmp(token, "+") == 0 || strcmp(token, "-") == 0) { char op = token[0]; advance(); Node* r = T(); n = new_node(op, n, r); } return n; }

代码逻辑说明：每次循环把当前已经解析出的左操作数n和右操作数r拼成一个新节点，循环结束后n就是整棵表达式树的根。T()也同样用循环处理乘除，然后F()返回数字或标识符叶子节点。这里用循环而不是Ep()递归，是因为id - id - id在通常语义里是左结合，即(id - id) - id；而递归写法会生成右倾树，变成id - (id - id)，求值结果恰好相反。如果实验要求打印推导序列，保留第 3 章的递归版本；如果做 AST，优先用循环版本。两者解析的句型集合相同，但对后续翻译阶段的影响不同。

我每写完一个递归下降分析器，都会先用三组固定输入跑一遍：普通优先级用例、括号优先级用例、错误定位用例，再生成一个随机长表达式，把推导输出和 AST 同时打出来核对。这样能很快发现优先级和结合性的错位，不用等到最后的语义分析阶段才暴露问题。这个习惯帮我避免过好几次乘除和加减层级颠倒的翻车，希望这个思路也能帮你在编译原理实验里少踩几个坑。

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