编译原理实验二：算符优先分析法从原理到C语言实现

简介这是一份编译原理课程中语法分析算符优先法的完整实验报告面向计算机专业学生、课程实验者及准备综合实验的读者。实验选择典型的算符优先分析法以赋值语句中的算术表达式为分析对象围绕给定文法 E→#E#、E→ET|T、T→T*F|F、F→(E)|i完成 FirstVt 与 LastVt 集合的求解、算符优先关系表的构造并对 (ii)*i、ii)*i 两个句子执行正确性判断和归约过程输出。资源为 1 个 doc 文档压缩包大小约 540KB正文包含实验题目、实验内容、程序源代码、算符优先关系表和实验结论。源代码中 init 函数负责把优先关系写入数组analyse 函数执行句子的算符优先分析testchar 函数判断终结符在优先表中的位置remainString 函数处理移进后剩余串读者可对照这些模块复现算法流程也可借鉴报告结构撰写课程作业。目前已有 132 人学习对理解自底向上的语法分析思想有直接参考价值。1. 实验二语法分析算符优先它是编译原理实验里最「值钱」的一次动手如果你正在写编译原理课程的实验二——语法分析而题目偏偏是算符优先分析法那多半已经翻过教材里那一章被 FIRSTVT、LASTVT 和那张优先关系表搞得有点晕。这个实验不像词法分析那样正则一写就过它要求你真正理解「移进—归约」的骨架分析器拿着一个栈一边读输入串一边查表决定是推进栈还是用文法的某条产生式把栈顶的某一截换掉。算符优先的特殊在于它只看终结符之间的关系不关心非终结符之间怎么推导所以它比递归下降更机械、比 LR 分析更容易手动实现但对文法的限制也更苛刻。适合做这个实验的人是对递归下降那种「手写函数互相调用」的套路已经有点腻、想看看表驱动分析器长什么样的学生做完它你会发现后面无论是 SLR 还是 LALR思路都顺着这一条线走。2. 从文法到优先关系表FIRSTVT、LASTVT 与手工建表的三步走2.1 为什么算符优先分析法只盯着终结符看语法分析的任务是判断一个 token 序列能不能由文法推导出来。LL(1) 的做法是看「下一个输入符号」决定用哪条产生式展开递归下降则是写一个函数对应一个非终结符靠调用关系模拟推导。算符优先走的是一条完全不同的路它把非终结符当作「不透明的占位符」只在栈顶终结符与当前输入终结符之间比较优先级关系用这个关系决定该移进还是该归约。这样做的代价是你不再知道每一步具体推导出了哪个非终结符好处是分析算法极其规整——一张二维表、一个栈、一个循环就能跑完整个分析过程。这是整个实验的第一个关键认知算符优先不是用来理解「句子怎么推导出来的」而是回答「从左边读进来的时候先合并哪一段」。它适合表达式这类运算符层次分明的文法比如经典的算术表达式文法E - E T | T T - T * F | F F - ( E ) | i这个文法是二义的——如果只看终结符关系ii*i有两种归约顺序都能得到 E但人写表达式时约定*比优先级高。算符优先分析器要做的事就是把这种「人的约定」变成终结符之间的、、关系让机器也照这个顺序归约。2.2 手工求 FIRSTVT 与 LASTVT两条规则加一张迭代表优先关系表建立在两个集合之上FIRSTVT(A) 和 LASTVT(A)。FIRSTVT(A) 是「非终结符 A 可能推导出的第一个终结符」的集合这里的「第一个」允许跳过若干个非终结符但不能跳过终结符。LASTVT(A) 是「A 可能推导出的最后一个终结符」的集合规则对称。求 FIRSTVT 有两条规则不要死记要理解它们的来源规则一若有产生式 A - a... 或 A - B a...则 a 属于 FIRSTVT(A) 规则二若有产生式 A - B ...则 FIRSTVT(B) 全部并入 FIRSTVT(A)规则一说的是一眼能看到的第一个终结符规则二是说 A 的推导前缀如果是一个非终结符 B那么 B 能打头的终结符A 也能打头。注意规则二可以传递A - BB - C那么 FIRSTVT(C) 也会一路传到 A。手工算的时候先逐条产生式列出「直接可得」的集合然后反复扫所有产生式把规则二能带进来的全部带进来直到集合不再变化。LASTVT 对称规则一若有产生式 A - ...a 或 A - ...aB则 a 属于 LASTVT(A) 规则二若有产生式 A - ...B则 LASTVT(B) 全部并入 LASTVT(A)用上面那个表达式文法算一遍结果是FIRSTVT(E) { , *, (, i } FIRSTVT(T) { *, (, i } FIRSTVT(F) { (, i } LASTVT(E) { , *, ), i } LASTVT(T) { *, ), i } LASTVT(F) { ), i }这里最容易翻车的地方是漏掉和*的传递E - E T里 E 的第一个终结符就是这个直接属于 FIRSTVT(E)不需要任何传递而T - T * F的*同理。但如果表达式文法写成E - T | E T那么E - T这条产生式会触发规则二把 FIRSTVT(T) 全部并入 FIRSTVT(E)。两种写法结果一致但迭代过程不同手工推导时容易懵建议在草稿纸上用「第一遍列出所有直接项、第二遍补传递项」的方式分层写。2.3 优先关系表三条判定规则和一张 6×6 矩阵有了 FIRSTVT 和 LASTVT终结符之间的三种关系就有了定义关系 a b存在产生式 A - ... a B ...且 b 属于 FIRSTVT(B) 关系 a b存在产生式 A - ... B b ...且 a 属于 LASTVT(B) 关系 a b存在产生式 A - ... a b ... 或 A - ... a B b ...逐条解释。的含义是「栈顶终结符 a 后面跟着一个非终结符 B而 B 能推导出以 b 开头的串」所以 a 的优先级低于 b分析器应该先处理 B 内部的东西也就是把 b 移进栈。的含义反过来a 在一个非终结符 B 的末尾B 后面紧跟着 b说明 B 的部分已经完整可以归约a 的优先级高于 b。只出现在同一个产生式的相邻终结符或隔一个非终结符的终结符之间最典型的就是括号对(和)以及# 与 #的配对。手工填表时用一个二维表行是栈顶终结符或栈内终结符列是当前输入终结符第 i 行第 j 列填、、或留空。空表示「这两个终结符相邻时没有任何合法关系」分析时遇到空直接报语法错误。对上面的表达式文法配上#作为结束符表大致长这样栈内\输入i*()#i*()#填表有三个检查点。第一同一个格子里不能同时出现两种关系否则文法就不是算符优先文法程序跑起来会陷入「该移进还是该归约」的自我矛盾。第二#与#必须填因为分析成功时栈内符号是#E输入串剩下#两者相遇表示接受。第三(和)的关系必须填不然括号表达式会分析失败。2.4 素短语与最左素短语归约到底归约什么移进—归约分析中「归约」不是随便从栈顶弹出几个符号就完事。算符优先分析里归约的对象是「最左素短语」。素短语的定义是它是一个短语至少含一个终结符并且不再包含更小的素短语。用人话说就是栈顶那一截「能看成某个产生式右部」且「带终结符」的最小片段。举例来说栈内符号是# i i输入是* i #算符优先分析会在与*之间发现关系于是先归约i i里的第二个i而不是整个i i。这个「先归约小的、靠近栈顶的素短语」的特性保证了乘法的优先级高于加法。实现归约时不需要真的判断「素短语」三个字算法上只要做一件事从栈顶往下找找到第一个满足「与上一个终结符之间是关系」的终结符位置从这个位置到栈顶就是归约边界。这个归约边界的查找逻辑是实验代码里最容易写错的地方。它不是简单地「遇到非终结符就跳过」而是要在栈内终结符之间做比较。完整流程在下一章展开。3. 用 C 语言实现算符优先分析器数据结构、主循环与核心代码3.1 三个核心数据结构符号栈、优先关系表、输入缓冲区这个实验我用纯 C 写因为编译原理实验的主流语言就是 C 或 Java而 C 的静态数组能把「表驱动」这件事表现得更直观。三个关键结构#define MAX_STACK 100 #define MAX_INPUT 100 char stack[MAX_STACK]; // 符号栈存终结符和非终结符 int top 0; // 栈顶指针stack[top] 是栈顶符号 char input[MAX_INPUT]; // 输入串缓冲区 int ip 0; // 输入指针input[ip] 是当前读入符号 // 优先关系表行是栈内终结符列是当前输入终结符 // 值 1 表示 2 表示 3 表示 0 表示错误 int priority_table[7][7];用数字代替、、字符存表好处是查表函数可以直接返回 int归约逻辑里判断priority 0就是关系不需要字符比较。栈底先压入#输入串末尾手动追加一个#这样主循环只用检查「栈内终结符与当前输入符的关系」不需要单独处理输入耗尽的情况。3.2 查表函数与「栈顶终结符」的获取查表前先想清楚一件事栈顶不一定是个终结符栈顶可能是个非终结符比如归约完F压栈后栈内是# ( F栈顶是 F。但优先关系只定义在终结符之间所以取「栈顶终结符」要从栈顶往下找第一个终结符。这里有个隐蔽的坑栈顶的非终结符会「遮蔽」它下面的终结符吗不会。算符优先分析中任何两个相邻终结符之间最多只隔一个非终结符这是文法本身保证的性质。所以从栈顶往下找最多跳过一层非终结符就到了终结符。// 返回栈内当前位置向下的第一个终结符pos 是查找起点通常是 top char get_top_terminal(int pos) { while (pos 0 !is_terminal(stack[pos])) { pos--; } return stack[pos]; }对应地找归约边界时需要一个「从栈顶向下扫描、跳过非终结符并比较终结符关系」的函数。这个函数的逻辑是归约的核心单独放一节说。3.3 主循环三种动作「移进、归约、接受」与错误处理主循环的逻辑很机械把它写成注释里的伪代码再翻译成 C能避免逻辑混乱// 主循环不断比较栈内终结符 a 与当前输入符 b // 若 a b移进 b // 若 a b若 b 是 # 则接受否则移进 b // 若 a b归约归约后不消费输入继续下一轮比较 // 若关系不存在报语法错误注意并不直接对应接受只有# #才是接受。( )这种关系出现时也是移进因为)进栈后才能和(配对形成可归约的素短语。void analyze() { stack[0] #; top 0; ip 0; while (1) { char a get_top_terminal(top); // 栈内终结符 char b input[ip]; // 当前输入符 int rel get_relation(a, b); // 查优先关系表 if (rel LESS) { // a b移进 stack[top] b; ip; } else if (rel EQUAL) { if (a # b #) { printf(分析成功\n); return; } stack[top] b; // 其余 都移进 ip; } else if (rel GREATER) { // a b归约 int boundary find_reduce_boundary(top, a); printf(归约从位置 %d 到栈顶 %d\n, boundary, top); top boundary; // 弹出素短语 stack[top] N; // 压入非终结符 N代表归约结果 } else { printf(语法错误栈内 %c 与输入 %c 无优先关系\n, a, b); return; } } }移进时压入的是输入符号本身包括终结符。归约时压入一个统一的非终结符占位符N这一步对所有产生式一视同仁——因为算符优先分析不关心具体归约成哪个非终结符它只关心栈内终结符的先后顺序。如果你想在实验报告里展示「归约成了 E 还是 T」可以把这个占位符替换成具体的非终结符但需要另写一个「根据素短语内容选产生式右部」的匹配函数不是本实验的必做项。3.4 归约边界查找从栈顶向下找「第一个 关系」这是整个实验代码里最考验理解的部分。归约边界查找的规则是从栈顶终结符开始依次和它下方的每一个终结符比较若发现「下方终结符 当前终结符」则归约边界就是下方终结符所在位置之后的所有内容。以# i i * i #分析到某一步为例假设栈内是# i i *输入是i #栈顶终结符是*取*与输入i查表* i移进i。栈变成# i i * i输入是#栈顶终结符i与#查表i #归约。归约边界查找栈顶终结符i位置 5向下找位置 4 是** i成立归约边界是*之后即从位置 5 到栈顶只弹出一个i。弹出i压入N栈变成# i i * N栈顶终结符是*重新与输入#比较* #继续归约。代码实现如下int find_reduce_boundary(int top, char top_terminal) { int pos top; char current top_terminal; // 当前要比较的终结符从栈顶终结符开始 while (pos 0) { pos--; // 向下移动一位 while (pos 0 !is_terminal(stack[pos])) { pos--; // 跳过非终结符 } if (pos 0) { break; } char below stack[pos]; // 下方终结符 int rel get_relation(below, current); if (rel LESS) { return pos 1; // below current归约边界是 below 之后 } // 如果 below current 或 说明 below 也在素短语内继续向下找 current below; } return 0; // 错误情形正常文法不会走到这里 }注意一个细节循环里每向下扫描到一个终结符就要把current更新为这个终结符。因为素短语可能横跨多个终结符比如i i归约时和两侧的i是一个整体边界要一直找到素短语的最左端。如果只比较「最初那个栈顶终结符」和所有下方终结符的关系会漏掉中间层导致归约时多弹出或漏弹。这个current below的更新是血泪经验漏了这一行程序会归约出完全错误的栈内容而且不报错、不死循环就是结果全错。3.5 完整代码骨架与编译运行方式把上面几个函数拼起来再加上优先关系表的初始化函数init_table()一个能跑的最小分析器就齐了。init_table()没有技术含量就是把第二章手填的那张 6×6 表按行写成赋值语句void init_table() { // 以符号 i * ( ) # 的顺序对应 0~5 列 // 行栈内终结符列当前输入终结符 // 1: , 2: , 3: priority_table[0][1] 2; // i priority_table[0][2] 2; // i * priority_table[0][4] 2; // i ) priority_table[0][5] 2; // i # // ... 完整赋值见实验报告附件 }编译运行用一条命令gcc -o parser parser.c ./parser输入测试串时记得把#也打进去比如直接输入ii*i#程序会边分析边打印每一步的动作。如果你用 IDE 做实验记得把输入串的结尾#和栈底#区分清楚——一个是input数组里的字符一个是stack[0]的初始值两者在任何时刻都不该混用。4. 把实验报告写成「能验收的样子」测试用例、运行结果与分析过程4.1 为什么运行结果展示不能只贴一张截图编译原理实验的验收老师最反感的是只给结论不给过程。算符优先分析器的输出不像词法分析那样「输入一串 token输出一个列表」——它每一步都在做选择选择的依据是优先关系表里查到的那个、或。所以报告里必须有一张「分析步骤表」把每一步的栈状态、剩余输入、当前关系、执行动作列出来。这张表既是给老师看的验收依据也是你自己排查 bug 的调试工具。4.2 测试用例设计至少覆盖四类情况不要只测一个ii*i#就交差。设计测试用例要覆盖四类情况正常优先级、括号嵌套、错误输入、连续运算符。我常用的测试集合是输入串预期结果覆盖点ii*i#成功乘法的优先级高于加法i*(ii)#成功括号内先归约(ii)*i#成功括号内容完成后才与*比较ii#成功最简单正确串i**i#失败连续*优先表无关系ii*#失败末尾运算符后缺操作数()#失败空括号(与)直接相邻时关系不合法ii)#失败右括号无匹配左括号每一条失败用例都要在报告里写出「失败发生在哪一步」比如i**i#分析到第二个*时栈内是# i *栈顶终结符是*当前输入也是*查表发现格子里没有关系报错。这个过程不需要代码输出多详细的信息print 出「语法错误栈内 * 与输入 * 无优先关系」就足够支撑报告了。4.3 分析过程表的标准格式表格有四列就够步骤、符号栈、剩余输入、动作。以ii*i#为例前半程的表长这样步骤符号栈剩余输入动作1#ii*i#移进 i2#ii*i#归约i 归约为 N3#Ni*i#移进 4#Ni*i#移进 i5#Ni*i#归约i 归约为 N6#NN*i#移进 *7#NN*i#移进 i8#NN*i#归约i 归约为 N9#NN*N#归约N*N 归约为 N10#NN#归约NN 归约为 N11#N#接受注意第 9 步和第 10 步归约动作没有消费输入所以剩余输入不变只是栈发生变化。写报告时这一步最容易让人看得一头雾水所以我通常会在动作列加一个括号注明「不消费输入」或者把剩余输入留空。另一种做法是在归约那几步把剩余输入写成#并加粗一眼能看出「输入没动栈在变」。4.4 报告里除了代码和表格还要有什么模板化的实验报告结构是「实验目的、实验原理、数据结构、算法流程、核心代码、运行结果、体会」每个学校格式略有出入但内容上有三处是加分项。第一推导过程要写全。把文法的 FIRSTVT、LASTVT、优先关系表这三步推导过程放进报告正文而不是只放最终表格。老师看你有没有真正理解集合构造规则很多时候就是扫一眼你有没有写「传递规则」这一步。第二错误处理说明要单独写一段讲明白「无优先关系时报错」和「归约找不到边界时报错」是两种不同的错误路径。第三体会部分别写空话写「调试中发现优先关系表漏填了(与)的关系导致括号表达式在归约时边界查找走到栈底」这种具体到符号的记录是报告的加分项。4.5 给出现 bug 时的输出对比如果某一步归约边界找错了栈里会压入一个N之后带上)之类的孤立符号比如# N )这时下一轮查)与#会报错。这个现象在报告「调试记录」里写出来能体现实验的真实性——比写「一次通过」更可信。实际上这个实验一次通过的可能性极低优先关系表 36 个格子里漏填一个都可能让某个合法串在奇怪的位置报错。5. 实验二算符优先的 5 个翻车点现象、原因、解决办法5.1 优先关系表漏填了#行程序分析完报错而不是接受现象ii*i#每一轮分析都正常走到了栈内# N、输入#这一步但程序报错「语法错误栈内 # 与输入 # 无优先关系」。原因初始化优先关系表时#与#的交叉点没填get_relation返回 0主循环走了错误分支。解决检查表初始化函数的最后一行确认priority_table[#][#] EQUAL写上了。这个坑看起来蠢但十个跑这个实验的人里至少有两三个栽在它身上因为写初始化表的时候注意力全在、*、(、)这些符号上#的行为容易被忘。检查方法也简单打印整张表的代码写出来一眼就能看到哪个格子是空的。5.2 归约边界查找时没有更新 current导致归约后栈残缺现象输入ii*i#归约完i之后下一轮归约N*N时弹出太多符号栈里出现# N加上一个不该出现的最终报错或者死循环。原因find_reduce_boundary里没有执行current below边界查找始终拿最初的栈顶终结符和下方所有终结符比导致素短语的边界被错误地扩展到第一个满足关系的终结符之外。解决在循环里每比较完一个终结符就更新 current代码见 3.4 节。这个 bug 的特点是「不报错、结果错得离谱」因为# i i * i #可能错误地归约成把也吞进去的N而分析器自己不知道继续跑下去直到输入耗尽才报「分析成功」但输出的归约序列和文法对不上。验收时老师让你解释归约序列你对着错误序列说不出话比直接报错更尴尬。5.3 输入串里的非法符号没做预检查越界读内存现象输入ii*i#正常但输入i$i#或i1#时程序崩溃或打印乱码。原因get_relation里直接拿当前输入符号查表遇到表里没有的符号时数组下标越界或者返回了错误的默认值。解决主循环开头加一个判断当前输入符不是终结符集合中的成员时直接报错。if (!is_terminal(b)) { printf(非法符号: %c\n, b); return; }这个预检查不是可选项。优先表是按固定 6 个终结符建的任何表外的符号都意味着「这个 token 不属于该文法的终结符集合」在词法分析阶段就该被拦截。但实验里很多人偷懒把词法分析和语法分析写在一个程序里token 直接送进来不做检查的结果就是内存越界。跑完实验记得多试几个非法输入把这种防御性检查写进代码报告里也值得写一笔。5.4 把关系一律当移进处理括号内永远无法归约现象输入(i)#时分析完(和i之后遇到)时移进然后栈变成# N ( N )接着)与#比较为归约边界查找却找不到合适的边界程序卡死或报错。原因主循环里看到就移进没有错这是正确策略错的是优先关系表里把(与)的关系填错了比如填成了或而不是。解决回到第二章的手工算法检查产生式F - ( E )(和)中间隔了一个非终结符 E按规则应填。这个坑提醒一个底层概念不代表「相等」它只代表「同一产生式内的相邻结构」。(和)配对时分析器必须先移进)让)和(在栈里形成上下文然后靠)与下一个输入符的关系触发归约把( N )一整个复杂片段归约成N。如果直接把(与)填成(会提前触发归约但(单独不构成任何产生式的右部程序就崩了。5.5 分析成功条件写成了「输入读完」而非「栈内 #N 与输入 # 相遇」现象输入空串#时程序直接报成功输入ii#时成功但输入ii#加上末尾多个#比如ii##时程序也报成功。原因主循环的成功条件写成了ip strlen(input)而不是检查栈顶终结符 # 当前输入 #。解决严格按 3.3 节的逻辑只有a # b #才接受。这个坑在设计测试用例时会暴露多输入几个#程序竟然「成功」了。这在理论上不是大事——词法分析器不会产生连续两个#——但实验报告的验收环节老师经常故意输入这种边界串看你的程序稳不稳。成功判定条件必须只认「栈顶终结符与输入符都是#」任何输入串末尾带多个#的情况分析到第一个#就该接受并忽略后续内容——严格做法是报错「#后还有输入」宽松做法是接受但绝不能把输入指针扫到头作为成功条件。6. 从实验报告到编译器前端算符优先分析还能往哪走做完这个实验大多数人的第一反应是「终于写完了下一题」。但如果把实验报告交上去就把它扔了有点浪费——算符优先分析器是理解自底向上语法分析的绝佳起点它和后面课程设计里的表达式求值、符号表、中间代码生成都是直接相关的。一个值得做的进阶改动是在归约时带上语义动作。既然归约是在栈上把N*N换成一个N那在这个「换」的过程中顺带做算术运算就实现了表达式求值。做法是把栈元素从 char 改成结构体每个元素同时记录符号和值归约时根据素短语内容做相应的运算。比如N*N归约时弹出两个值相乘把结果压入新栈元素的 value 字段。这样分析器就升级成了一个计算器。这个改造不需要改主循环只改归约函数的内部逻辑适合作为实验报告的「选做加分项」写进体会。另一个思路是把优先关系表的构建从手工改成程序自动生成。实验里 6 个终结符的表手填还行如果给文法增加一元负号、幂运算^、比较运算符表会膨胀到 10 个符号以上手填就非常容易出错。自动构建的思路是先用迭代算法求出所有非终结符的 FIRSTVT 和 LASTVT然后扫描所有产生式按三种关系的判定规则填入矩阵。这相当于把第二章的手工步骤程序化工作量约 100 行代码但对理解集合迭代传播的帮助非常大。做的时候注意迭代终止条件——集合不再变化就停不要写成无限循环。第三个方向是把这个分析器接上词法分析器和符号表形成一个小型编译器的前端。词法分析器把源代码切成 token 流符号表登记每个标识符的名字和类型算符优先分析器处理表达式语法——三者串起来你就有了一台能解析并计算带变量赋值语句的小机器。这个思路用你手头已有的实验资源就能搭不需要引入第三方框架。课程设计阶段如果有「实现一个计算器语言」之类的题目这个算符优先实验就是现成的心脏。最后说一个我的习惯写完这个实验后我会把测试用例和对应的分析步骤表保留在实验报告附件里而不是只截图。因为学期末的课程设计里我经常要回头翻这张表来回忆归约边界算法为什么这么写——那种「当时明明懂了但一周后就忘了」的感觉太熟悉了留下可复现的调试记录就是给未来的自己留后悔药。算符优先分析器的核心代码量不大但每一行都是对「栈与表」这两个概念肌肉记忆式训练认真把它做透后面学 SLR 分析表时你会觉得无比轻松。希望这份实验笔记帮你在实验二少翻几次车把时间省下来琢磨那些真正有意思的进阶玩法。本文还有配套的精品资源点击获取