简介编译原理实验二语法分析·算符优先实验报告doc文档面向计算机专业学生与编译原理初学者用于完成课程实验、理解算符优先分析法。内容基于华北水利水电学院实验要求围绕文法G(E)E→#E#E→ET|TT→T*F|FF→(E)|i 展开详细介绍FirstVt/LastVt集合求解、算符优先关系表构造并以(ii)*i和ii)*i为例输出归约过程。文档附完整C程序源码包含init、analyse、testchar、remainString等核心函数逐段说明变量作用与函数流程可直接对照实现或修改调试帮助解决“如何用程序实现算符优先分析”的实验难点。资源包共1个doc文件体积540KB结构清晰。目前已有131人学习浏览适合作课程实验报告模板、编译原理复习资料或上机实践参考。1. 算符优先分析实验一个能直接跑通的表达式语法分析器拿到这份实验报告资源时我第一反应是它把编译原理里最“反直觉”的一个环节讲明白了自下而上的算符优先分析本质上不是在做语法树推导而是在不断“找最左素短语并归约”。文档的亮点在于它没有停留在 FirstVT 和 LastVT 集合的理论推导上而是直接把一张 6×6 的算符优先关系表硬编码进priority数组然后用一个不到 200 行的 C 程序把(ii)*i和ii)*i两个句子的完整移进-归约过程逐行打了出来。这份资源适合三类人正在做编译原理课程设计的学生、需要快速理解算符优先分析法与 LR(0)/SLR(1) 差别的考研党以及想用最短代码验证一种语法分析策略的工程师。顺着它的代码往下拆你会发现它把“查表”和“栈操作”这两个核心动作耦合得极紧——这正是理解算符优先分析的关键。2. 从文法到优先关系表FirstVT、LastVT 与 init() 的对应关系2.1 文法 G(E) 的产生式编号与终结符集合实验采用的表达式文法如下注意它自带一个扩充产生式E→#E##作为输入串的界符也参与优先关系表的构建(0) E - #E# (1) E - ET (2) E - T (3) T - T*F (4) T - F (5) F - (E) (6) F - i这个文法的终结符集合是{, *, i, (, ), #}一共 6 个所以优先关系表是 6×6。非终结符只有E, T, F三个而且文法中没有左递归消除的痕迹——算符优先分析法天然能处理左递归文法因为它根本不构造 LR 自动机只关心终结符之间的优先关系。这一点是它和 LR 家族分析器最大的分野算符优先分析跳过了非终结符的归约细节直接以终结符为锚点决定动作。2.2 FirstVT 与 LastVT 的手工推导要在init()里填对priority数组必须先手工算出每个非终结符的 FirstVT 和 LastVT。以 FirstVT 为例规则是若P→a...或P→Qa...则a ∈ FirstVT(P)。逐条套用E→ETFirstVT(E) 加入E→TFirstVT(E) 加入 FirstVT(T)T→T*FFirstVT(T) 加入*T→FFirstVT(T) 加入 FirstVT(F)F→(E)FirstVT(F) 加入(F→iFirstVT(F) 加入i迭代直到集合不再变化得到FirstVT(E) {, *, (, i} FirstVT(T) {*, (, i} FirstVT(F) {(, i}LastVT 的规则是对称的若P→...a或P→...aQ则a ∈ LastVT(P)。同样迭代后得到LastVT(E) {, *, ), i} LastVT(T) {*, ), i} LastVT(F) {), i}2.3 优先关系表的构造规则与 6×6 矩阵落地优先关系不是比较运算符优先级而是基于句型的相邻终结符关系三条规则如下a,b为终结符P,Q为非终结符若产生式右部出现...aQ...则a FirstVT(Q)中的每个终结符若出现...Qb...则LastVT(Q) b中的每个终结符若出现...aQb...或...ab...则a b例如产生式E→ET中E后紧跟按规则 2LastVT(E)的全部元素都大于所以LastVT(E) {, *, ), i}与交叉处全部填。同理E→ET中后是T按规则 1 FirstVT(T) {*, (, i}。全部枚举后就是程序里那个priority数组。以下把表从代码里抽出来$表示无优先关系意味着该输入串必然被拒绝算符*i()#*i$$($)$$#$注意i行与(列是$正确解释是表达式i(i这种相邻终结符序列在规范句型中不可能出现所以遇到即报错。代码中用字符$占位而不是用\0或空格这给analyse()里的合法性检查提供了方便——只要查表结果是$直接判定句子非法。init()函数做的事就是把上面这张表按行填进priority[6][6]没有任何计算逻辑。教学上这是合理的先手工构造表再用程序查表分析实验目标是把分析过程跑通而不是实现 FirstVT/LastVT 的自动计算。如果你想扩展成自动构造见第 5 章。3. analyse() 里的移进与归约分析栈维护和算符索引回退3.1 栈结构与 j 的“回退查找”逻辑analyse()是整个程序的核心它维护了一个字符数组AnalyseStack栈底固定是#k指向栈顶。每次从输入串读入一个终结符a然后从栈顶向下找最近的一个终结符记其位置为j。代码里的实现是if (AnalyseStack[k] || AnalyseStack[k] * || AnalyseStack[k] i || AnalyseStack[k] ( || AnalyseStack[k] ) || AnalyseStack[k] #) j k; else j k - 1;这里有一个隐蔽的约定算符优先分析中归约时会把AnalyseStack[k]置为N非终结符标记所以栈顶可能不是终结符。但程序只用一个N字符表示任何非终结符这带来一个后果——栈里可能出现连续的多个N比如一次归约后栈变成#NN此时栈顶是N程序j k - 1找到了没问题。但如果栈是#NNj k - 1找到的仍然是N此时testchar()没有对N的处理分支程序逻辑上就漏掉了这种情况。实践中表达式文法的归约动作通常不会产生连续两个N在栈顶相邻因为任何归约结果都对应一个完整产生式而文法中不存在E→NN这种右部。不过这个假设并不是所有文法都成立理解这一点对后面调试很重要。3.2 归约分支的“向前探测”循环当priority[z][n]的查表结果是时说明栈顶终结符的优先级高于当前输入符号应当归约。这里的实现是一个死循环for (;;)从j位置开始向左扫描Q AnalyseStack[j]; if (AnalyseStack[j-1] || ... || AnalyseStack[j-1] #) j j - 1; else j j - 2; z1 testchar(AnalyseStack[j]); n1 testchar(Q); p1 priority[z1][n1]; if (p1 ) { // 找到最左素短语的尾 count; k j 1; i--; AnalyseStack[k] N; int r strlen(AnalyseStack); for (int r1 k 1; r1 r; r1) AnalyseStack[r1] \0; break; }这个循环本质是在找“最左素短语”的头。Q是当前已知的素短语尾终结符j持续向左移动每次用priority[当前终结符][Q]判断若结果是说明当前终结符的优先级低于Q则这个位置就是素短语的左边界。找到后直接做两件事k j 1栈顶指针跳到素短语头部随后AnalyseStack[k] N把整个素短语覆盖成一个非终结符i--当前输入符号不消费因为归约后需要重新比较新的栈顶终结符与当前输入符这里i--的作用非常关键归约完成后外层for循环会执行i两者抵消相当于当前输入符号被“重新处理”一次。如果漏掉这行输入串会被提前消费导致归约时机错乱。strlen配合\0截断栈的写法也很巧妙归约后把k1往后的位置全部置空等效于弹出栈顶若干元素。这个操作的时间复杂度是 O(n)对教学场景完全够用。3.3 移进分支与剩余串的裁剪查表结果是或时执行移进核心代码较短但逻辑点集中k k 1; AnalyseStack[k] a; remainString();remainString()的实现是把remain数组整体左移一位丢弃第一个字符void remainString() { int i strlen(remain); for (int j 0; j i; j) remain[j] remain[j 1]; remain[i - 1] \0; }这个函数每次移进都会被调用整体算法时间复杂度是 O(n²)因为每移进一个字符都要做一次字符串拷贝。这不是性能最优的实现但胜在直观——剩余输入串的打印会和实际分析过程严格同步调试时能一眼看出当前分析到输入串的哪个位置。3.4 “承受”动作归约成功的判定当栈顶终结符与当前符号的优先关系是时代码会额外做一次判断z2 testchar(AnalyseStack[j]); n2 testchar(#); p2 priority[z2][n2]; if (p2 ) { printf(承受\n该句子是该文法的合法句子。\n); break; }这个分支只在AnalyseStack[j]是#且当前输入a也是#时进入。换句话说只有分析到栈内只剩#N#且输入也读到末尾#才判定为合法。注意这里判定成功的条件是priority[#][#] 也就是说文法必须含有E→#E#这样的产生式且#和#之间的优先关系是相等的。如果文法没有这个界符机制这个判定分支需要重新设计。4. 两组测试句子实测合法与不合法的分析路径对比4.1 (ii)*i 的完整归约过程推演用程序跑(ii)*i输出会逐行打印步骤、分析栈、优先关系、当前符号、剩余串和动作。手动推演前几步来验证代码逻辑步骤1 栈# 当前:( 剩余:ii)*i# 动作:移进 步骤2 栈#( 当前:i 剩余:i)*i# 动作:移进 步骤3 栈#(i 当前: 剩余:i)*i# 动作:归约 (用 F-i) 步骤4 栈#(N 当前: 剩余:i)*i# 动作:归约 (用 T-F) 步骤5 栈#(N 当前: 剩余:i)*i# 动作:移进 (程序输出可能显示为移进实际是查表 )第 3 步是i与查表得到进入归约分支找到最左素短语i归约成N。这里提一个容易混淆的点代码用统一的N代替所有非终结符所以你看不到E/T/F的区分这是算符优先分析的典型简化——分析过程只关心终结符的优先关系非终结符的具体类型不影响动作决策。继续推演到关键位置——处理完(ii)后的状态栈#N 当前:* 剩余:i# 动作:查表 priority[#][*] 移进 栈#N* 当前:i 剩余:# 动作:查表 priority[*][i] 移进 栈#N*i 当前:# 剩余:(空) 动作:查表 priority[i][#] 归约 栈#N*N 当前:# 剩余:(空) 动作:查表 priority[*][#] 归约 栈#NN 当前:# 剩余:(空) 动作:继续归约 栈#N 当前:# 剩余:(空) 动作:查表 priority[#][#] 接受注意最后一步栈是#N而非#N#——因为#是界符分析过程中栈底#不参与归约当栈顶N与输入#查表得到时程序判定接受。整个过程中i与、与i、(与i等关系的查表结果直接对应第 2 章那张优先关系表。如果表里某个交叉项填错分析过程会提前进入错误分支或无限循环。4.2 ii)*i 的报错路径与判定点对于非法句子ii)*i程序会中途退出。手工推到报错位置栈#i 当前: 剩余:i)*i# 查表 priority[i][] 归约 栈#N 当前: 剩余:i)*i# 查表 priority[#][] 移进 栈#N 当前:i 剩余:)*i# 查表 priority[][i] 移进 栈#Ni 当前:) 剩余:*i# 查表 priority[i][)] 归约 栈#NN 当前:) 剩余:*i# 这里出现问题优先关系表里 # 与 ) 的关系是什么查priority[5][4]即#行)列表中是$。于是程序走到p $分支打印“该句子不是该文法的合法句子”并 return。这个例子的价值在于它不是等到最后才发现错误而是在)出现时立刻通过$标记识别出——#与)之间不可能存在相邻关系因为合法的表达式不可能以)开头除非是()空括号但文法中F→()并不存在F→(E)要求括号内必须有表达式。所以算符优先分析法对错误输入有“尽早发现”的能力这点优于某些自顶向下方法要回溯后才能报错。4.3 代码中可复用的输出格式设计程序把分析过程同时打印到屏幕和写入文件li文件写入的格式与屏幕输出基本一致但少了一列“优先关系”。这个设计有两个用意一是方便提交实验报告时把运行结果直接贴进去二是把 stdout 和文件输出分离避免日志和交互信息混在一起。如果你要改造成自己的实验建议把fprintf(fp, ...)统一封装成一个log_step(count, stack, remain, action)函数这样以后换输出格式或加时间戳都只需改一处。5. 算符优先法的边界素短语、冲突处理与调试技巧5.1 为什么不是规范归约素短语与最左素短语算符优先分析法有个经常被考到的结论它找到的归约串是最左素短语而不是规范句型的句柄。两者的差别在于素短语是至少含一个终结符、且不再含更小素短语的短语而句柄是规范归约中每次应被归约的直接短语。对应到代码实现上for(;;)循环从j向左扫描并连续执行j j - 1或j j - 2的过程实际上就是在寻找最左素短语的边界。这个边界寻找规则完全依赖priority表中的关系——当当前终结符与Q的查表结果是时就认为找到了素短语的头。这里有个实践中容易踩的坑如果文法中存在E→EE这类二义性产生式本实验的文法特意改成E→ET、T→T*F来规避priority表中可能会出现某两个终结符既有又有的冲突项。代码里init()的赋值是在编译期固定写死的遇到冲突会直接覆盖前一个值导致分析器对某些合法输入产生误判。检查方法是把生成的优先关系表打印出来人工核对是否存在同一行列同时出现和的情况。5.2 testchar() 的边界条件与字符集扩展testchar()函数只有 6 个终结符的映射分支对非终结符N没有定义。如果输入串中出现空格、换行、或i以外的标识符字符比如变量名abcanalyse()里的第一道防线是if (a || a* || ai || a( || a) || a#) n testchar(a); else { printf(错误该句子不是该文法的合法句子\n); break; }也就是说输入串中任何不属于终结符集合的字符都会直接触发报错。这个设计的好处是简单可靠坏处是——如果文法扩展了新的终结符比如增加赋值号或比较符你必须在三个地方同步修改init()里的表、testchar()的映射、analyse()里的字符判断条件。漏改任何一处都会出现难以排查的运行时错误。可以把字符判断做成一个查表函数int isTerminal(char c) { return c || c * || c i || c ( || c ) || c #; }这样三个地方的判断逻辑就统一了以后扩展终结符只需改这一处和testchar()。5.3 FirstVT 集合自动构造的增量算法如果不想手工推 FirstVT/LastVT常见的做法是使用一个“增量迭代”算法先初始化每个非终结符的集合然后反复扫描产生式把新元素加入直到不再变化。伪代码如下def compute_firstvt(productions, non_terminals, terminals): firstvt {nt: set() for nt in non_terminals} changed True while changed: changed False for lhs, rhs in productions: # 情况1: P - a... if rhs[0] in terminals: if rhs[0] not in firstvt[lhs]: firstvt[lhs].add(rhs[0]) changed True # 情况2: P - Q a... elif len(rhs) 2 and rhs[0] in non_terminals and rhs[1] in terminals: if rhs[1] not in firstvt[lhs]: firstvt[lhs].add(rhs[1]) changed True # 情况3: P - Q..., 加入 FirstVT(Q) if rhs[0] in non_terminals: for vt in firstvt[rhs[0]]: if vt not in firstvt[lhs]: firstvt[lhs].add(vt) changed True return firstvt这个算法用集合运算替代了手工迭代测试时可以把输出与手工推导的{, *, (, i}对照。最后一步的优化很明确优先关系表本质上是 FirstVT 和 LastVT 集合的笛卡尔积映射一旦集合算对表就可以程序化生成手工填表容易在边界处出错特别是#行和)行这几条边界的$项。5.4 复现实验时的环境注意事项资源中的代码是早期 C 风格使用了iostream.h这在现代编译环境下如 GCC 9 的默认模式可能无法直接编译因为它已经废弃。复现实验时不需要改逻辑只需做两个替换把#includeiostream.h换成#includeiostream和#includecstring把gets(input)换成cin.getline(input, SIZE)。fopen(li, a)和fopen(li, w)的混合使用也值得留意程序先以写模式打开文件写文法关闭后以追加模式写分析步骤这保证了li文件里最终包含完整的实验记录。如果你在 Linux 下运行注意当前用户对工作目录是否有写权限否则fopen返回空指针时程序没有判空处理会直接崩溃。本文还有配套的精品资源点击获取