简介一份面向编译原理课程的实验文档资源聚焦自上而下的递归下降语法分析覆盖从文法改造到分析器构造的完整流程。文档首先对原始文法执行消除左递归处理给出改造后的产生式及各非终结符的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 - β AA - α A | ε。这里A是新增的非终结符ε代表空串。对表达式文法应用这条规则得到下面的对应关系原产生式消除左递归后E - E T | TE - T EE - T E | εT - T * F | FT - F TT - * F T | εF - (E) | id | num不变这段改写是手工完成的也是实验报告里第一个要解释清楚的地方。改写后每个非终结符的产生式右侧都以一个非终结符或终结符开头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 SS - 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){ )、$ }。非终结符FIRSTFOLLOWE(、id、num)、$E、ε)、$T(、id、num、)、$T*、ε、)、$F(、id、num、*、)、$提示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对应ETp对应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 同时打出来核对。这样能很快发现优先级和结合性的错位不用等到最后的语义分析阶段才暴露问题。这个习惯帮我避免过好几次乘除和加减层级颠倒的翻车希望这个思路也能帮你在编译原理实验里少踩几个坑。本文还有配套的精品资源点击获取