简介本资源是天津理工大学《编译原理》课程配套实验三的完整报告文档面向计算机专业本科生及编译技术初学者聚焦语义分析与中间代码生成核心能力训练。报告基于表达式文法G[E]系统实现LL1、算符优先或LR任一分析法下的语法制导翻译包含属性文法设计、四元式中间代码生成、变量结构体定义、分析表构造含19×13预测/动作表、C源码实现及多组测试用例验证结果覆盖语义动作设计、错误处理与调试心得。资源为单个Word文档.doc大小381KB内容共17页涵盖实验目的、要求、过程记录、源程序片段、测试数据与结论总结结构完整、注释详实便于理解语义分析落地细节。目前已有376人学习下载适合课程实验复现、编译器前端开发入门与四元式生成机制深度研习。1. 天津理工大学编译原理实验3语义分析与中间代码生成——不是抄代码是亲手把ii*i翻译成(, i, i, t1)、(*, t1, i, t2)的黑匣子拆开你有没有试过写完一个表达式ab*c编译器没报错但运行结果不对调试半天发现中间代码里b*c被提前算成了t1而at1却被错误地生成为(, a, b, t1)—— 少了一个操作数。这不是 bug是语义分析阶段就埋下的坑。天津理工大学这门《编译原理》实验3就是让你亲手把「语法正确 ≠ 语义正确」这句话用 C 一行行敲进内存里。它不教你怎么写 Java 编译器而是逼你站在 LR 分析器的栈顶一边看状态转移表一边在stack[pointer].endchar t3这行代码上加断点确认P→(E)规约后括号里的E对应的中间变量t2是否真的传到了P的endchar字段里。这份实验报告不是交差材料它是你第一次真正触碰到「编译器如何理解程序员意图」的实体切片文法 G[E] 的 18 条产生式、手写的 19×13 LR(0) 分析表、四元式结构体variable_T的operate/var1/var2/num四字段设计、甚至get_tx(7)函数里硬编码到t16的临时变量命名逻辑——全都是可执行、可调试、可修改的真实工程片段。适合刚啃完王生原《编译原理第3版》第三章、正在为「语法制导翻译」概念发晕的大三学生也适合想补全编译前端实战链路、但被 LLVM 或 ANTLR 抽象层绕晕的工程师。它不讲理论推导只讲当输入串是ii*i#时第 7 步s9移进后栈顶符号*对应的列索引j2状态i9查表得s10此时你必须立刻意识到接下来要压入状态a对应十进制 10而a在getraw()里被映射为10行——这个细节决定了你的四元式序列会不会在乘法处多出一个空行。2. 从 LR 分析表到四元式生成为什么选 LR(0) 而不是 LL(1) 或算符优先2.1 文法 G[E] 的 LR(0) 可行性验证消除左递归与冲突的本质先直说结论本实验强制采用 LR 分析法具体是 LR(0)不是因为老师偏爱而是文法 G[E] 的结构天然排斥 LL(1)。看这两条E → E T | E - T | T T → T * F | T / F | F存在直接左递归E → ET和间接左递归E→T→F→P→(E)。LL(1) 要求对任意非终结符 A其所有产生式A→α|β必须满足FIRST(α) ∩ FIRST(β) ∅。但E→ET和E→T的FIRST都包含i、(冲突无法通过改写彻底消除改写后仍需回溯。而 LR(0) 的核心优势在于它用状态机而非预测集合驱动分析每个状态对应一个项目集闭包能天然容纳左递归文法。我们来看实验中实际使用的table[19][13]—— 它的行数 19 恰好对应 LR(0) 自动机的 19 个状态从0到i即 18列数 13 对应终结符,-,*,/,^,),#,(,i8 个加非终结符E,T,F,P4 个再加#起始符共 13 列。这个表不是凭空写的是用标准算法构造增广文法 → 求项目集规范族 → 构造 DFA → 填 ACTION/GOTO 表生成的。比如状态0首行遇到i查得s6表示移进并转到状态6遇到(查得s5移进转状态5而遇到#查得err因为句子未开始。这种「状态输入符号→动作」的映射正是 LR 分析器跳过预测、直奔确定性的根基。提示不要试图手动推导这个表。实验已提供完整table[19][13]重点是理解s5/s6/r1/r2/acc这些动作码的含义。s是 shift移进r是 reduce规约数字是目标状态或产生式编号如r1对应E→ETacc是 accept接受。err不是错误是语法拒绝——说明当前输入不符合文法。2.2 四元式结构体variable_T的设计逻辑为什么是四字段而非三元式四元式(op, arg1, arg2, result)是中间代码最直观的表示但实验代码里variable_T的定义暴露了更深层的设计考量typedef struct variable_T { char operate; // 操作符如 , *, ^ string var1; // 第一操作数可能是 i、t3 或 a string var2; // 第二操作数同上若为单目运算如负号此处为空 int num; // 该四元式的序号用于生成 resultt1, t2... } variable_T;注意var1和var2是string而非int且num是独立字段。这直接服务于语义动作嵌入。以E→ET规约为例对应r1分支// r1 分支关键逻辑简化 string se stack[po-2].endchar; // E 的值如 t1 string st stack[po].endchar; // T 的值如 i tsize; // 新增四元式序号 t[tsize].num tsize 1; // 序号从 1 开始 t[tsize].operate ; // 操作符 t[tsize].var1 se; // 第一操作数 t[tsize].var2 st; // 第二操作数 cout ( t[tsize].operate , t[tsize].var1 , t[tsize].var2 ,t t[tsize].num );这里se和st直接取自符号栈中对应位置的endchar字段char_stack结构体而endchar存储的是该符号规约后的代表变量名如t1或i。num字段则确保t[tsize].num能正确映射到get_tx()函数返回的t1、t2字符串。如果用三元式(op, arg1, arg2)result就得动态拼接易出错而四元式显式分离result让t[tsize].num成为唯一标识后续优化如公共子表达式删除可直接基于num关联。2.3char_stack与endchar字段语义信息如何在符号栈中传递LR 分析器的符号栈stack[size]通常只存符号本身如E,i但本实验的char_stack结构体额外携带了endchar字段typedef struct char_stack { char content; // 当前符号如 i, E, string endchar; // 该符号对应的中间变量名如 i, t3, t1 int num; // 与该符号相关的中间变量序号冗余见下文 } char_stack;endchar是语义传递的核心载体。例如当输入i时s6移进后stack[pointer].content i同时stack[pointer].endchar i见switch_method中s6分支未显式赋值但初始化时endchar默认为空需在移进i时手动设为i—— 实际代码中s5/s6等移进分支未设置endchar这是第一个坑见 3.1。当规约发生时如r10: P→ipopstackc(stack, pointer, 1)弹出i后pushstack(..., P, c_out, 1)压入P此时stack[pointer].endchar被设为ir10分支末尾stack[(*pointer)].endchari;。这样P就继承了i的语义值。同理r9: P→(E)规约时先po--找到E的位置取stack[po].endchar即E的值如t2然后赋给新压入的P的endchar。endchar如同一条隐形的语义链在每次规约中将子节点的计算结果向上归并。num字段看似冗余tsize已记录总数但它在r7F→P^F等需要访问多个子节点的规约中用于快速定位栈中P和F的位置po和po-2避免字符串查找开销。2.4get_tx(int num)的硬编码局限为什么只支持到t16get_tx()函数用switch硬编码了1到16的数字到t1到t16的映射string get_tx(int num) { switch(num) { case 1: return t1; case 2: return t2; ... case 16: return t16; default: return ; // 未处理 } }这暴露了实验的边界它面向教学不追求工业级健壮性。tsize初始为-1每次tsize后t[tsize].num tsize 1所以num最大为16。若测试用例过长如ii*ii*i*i*i*i*i*i*i*i*i*i*i*itsize超过15数组t[size]下标0~1023足够但get_tx返回空字符串会导致四元式输出为(, t1, ,t17)——var2为空。这不是 bug是教学设计的刻意留白它逼你思考「如何动态生成临时变量名」答案是to_string()或sprintf但实验要求你先理解t1/t2的语义本质——它们是编译器为保存中间计算结果而分配的虚拟寄存器名字本身不重要重要的是num的唯一性和可追溯性。后续若扩展为 SSA 形式t1_1,t1_2的版本号机制正是从这里起步。3. 语法制导翻译的落地实现从输入串到四元式序列的完整流程3.1 主循环while(str[index]!\0)的每一步解析以ii#为例主函数main()的核心是这个循环while(str[index]!\0){ top gettop(state_stack, pointer_state); // 取状态栈顶 i getraw(top); // 将状态字符转为行号0→0, a→10 j getcol(str[index]); // 将输入符号转为列号i→8, →0 production table[i][j]; // 查表得动作 switch_method(stack, pointer, state_stack, pointer_state, production, str, index); }我们以输入ii#注意末尾#是结束符为例追踪前几步初始state_stack [0],pointer_state 0,stack [#],pointer 0,index 0,str ii#Step 1top0→i0,str[0]i→j8,table[0][8]s6switch_method执行s6index指向pushstack(..., i, 6, 0)→stack [#,i],state_stack [0,6]Step 2top6→i6,str[1]→j0,table[6][0]r10r10分支弹出stack和state_stack各 1 个i和6压入P和c_out查table[6][11]得r10对应P的 GOTO 列jgetcol(P)12table[6][12]r10→c_outr? 实际代码中r10分支用getcol(P)但table列索引12对应Ptable[6][12]是r10getraw_content(r10)会失败这是第二个坑见 4.1。正确逻辑应查GOTO[P]即table[i][getcol(P)]i6时table[6][12]应为状态号如c但实验表中r10行P列是r10说明表已预填 GOTO 值。r10分支实际执行stack[pointer].endchari完成P→i语义传递。Step 3stack [#,P],state_stack [0,c]假设c是P的 GOTO 状态str[1]→j0,table[?][0]查得r8F→P或r6T→F... 最终触发r1: E→ET生成(, i, i, t1)。每一步都严格依赖table的正确性。getraw()和getcol()是查表的桥梁将字符映射为整数索引任何映射错误如getcol(()返回7但表中(列是第 7 列都会导致越界或误动作。3.2switch_method中r分支的语义动作实现以r1: E→ET为例r1分支是语义分析的精华所在代码虽长但逻辑清晰else if(productionr1){ int po (*pointer); // 当前栈顶位置 string st stack[po].endchar; // T 的值右部第二个符号 po - 2; // 回退到 E 的位置ET 共3符号E在栈底 string se stack[po].endchar; // E 的值右部第一个符号 tsize; // 新增四元式 t[tsize].num tsize 1; // 序号 t[tsize].operate ; // 操作符 t[tsize].var1 se; // E 的值 t[tsize].var2 st; // T 的值 cout (, se , st , t t[tsize].num ); // 输出四元式 // 规约弹出3个符号E, ,T压入 E并设置其 endchar popstack(state_stack, pointer_state, 3); popstackc(stack, pointer, 3); // 查 GOTO[E]用当前状态栈顶第二个状态弹出3个后的新栈顶查 E 列 int p (*pointer_state); p - 3; // 新栈顶位置 char second state_stack[p]; // 新栈顶状态字符 int i getraw(second); // 行号 int j getcol(E); // E 列号 char c_out getraw_content(table[i][j]); // GOTO 状态字符 pushstack(stack, pointer, state_stack, pointer_state, E, c_out, 1); string s get_tx(t[tsize].num); // t1 stack[(*pointer)].endchar s; // E 的 endchar 设为 t1 }关键点栈索引计算E→ET右部 3 个符号故pop3 个E在栈中位置是po-2因po是Tpo-1是po-2是E。GOTO 查找规约后压入E需查当前栈顶状态弹出后的新栈顶在E列的 GOTO 值即table[i][j]i由新栈顶状态字符转换j由E转换。endchar 传递新压入的E的endchar设为t1这样后续E→ET再次规约时se就是t1实现嵌套计算。3.3 测试用例设计与结果验证如何证明四元式正确实验要求提供测试数据和结果。有效测试需覆盖文法所有分支基础i#→ 应输出r10P→i、r8F→P、r6T→F、r3E→T无四元式单符号无运算。二元运算ii#→ 应生成(, i, i, t1)对应r1。优先级ii*i#→ 应先算i*ir4或r5生成(*, i, i, t1)再算it1r1生成(, i, t1, t2)。若先算ii则是优先级错误。括号(ii)*i#→ 应先算括号内iir1P→(E)传递t1再T→F最后(*, t1, i, t2)。幂运算i^i^i#→ 注意右结合应生成(^, i, i, t1)再(^, i, t1, t2)。验证方法手动画语法树按后序遍历子节点先于父节点生成四元式。例如ii*i的树E /|\ E T /|\ T * F | i后序iF→iT→iF→(*, i, i, t1)T→(, i, t1, t2)E。输出顺序必须匹配。4. 避坑指南5 个血泪经验总结的常见问题与排查4.1endchar未初始化导致空字符串移进i时忘记设endchar现象输入i#输出四元式为(, , ,t1)或程序崩溃。原因s5/s6等移进分支在pushstack时只设置了content和sx状态但未设置stack[(*pointer)].endchar。char_stack结构体初始化时endchar为空字符串r10分支stack[(*pointer)].endchari是规约时才赋值但移进i后stack[pointer].endchar仍是空导致后续r10取stack[po].endchar为空。解决在s5/s6/s7...分支中pushstack后立即设置endchar// 在 s6 分支中添加 if(str i) stack[(*pointer)].endchar i; else if(str () stack[(*pointer)].endchar (; // 或空因括号不参与计算更优方案在pushstack函数内增加string endchar_param参数并在调用时传i。4.2getraw_content()对非数字字符处理不当table[i][j]返回r10时崩溃现象r10分支执行getraw_content(r10)switch中无case r10默认输出错误并返回-1c_out为非法字符。原因getraw_content()函数只处理单字符1到h但table中r动作是字符串r1、r10不能直接传入。getraw_content()应只用于s和GOTO的状态字符如s5中的5c而r动作的数字部分10应单独提取。解决修改switch_method对production先判断前缀if(production.substr(0,1) s) { char sx production[1]; // s5 → 5 // ... 移进逻辑 } else if(production.substr(0,1) r) { int rule_num stoi(production.substr(1)); // r10 → 10 // ... 进入 r10 分支 }getraw_content()仅用于s和GOTO查表不再传r字符串。4.3tsize越界与get_tx()返回空临时变量超 16 个现象长表达式ii*ii*i*i*i*i*i*i*i*i*i*i*i*i#输出(, t1, ,t17)var2为空。原因get_tx(17)无case返回空字符串。t[size]数组大小1024足够但get_tx()是瓶颈。解决重写get_tx()使用std::to_stringstring get_tx(int num) { return t to_string(num); }需#includestring并确保编译器支持 C11。4.4getcol(()返回7但表中(列是第 7 列0-indexed索引错位现象输入(i)#在(处查表得err分析失败。原因getcol()中case ( : return 7;但table是 13 列索引0到127是合法的。问题在于table初始化时/* 0 */行的(列是第 7 个s5但若getcol(()返回81-indexed则越界。检查getcol函数确认case (返回7且table列顺序与getcol返回值严格对应,-,*,/,^,),#,(,i,E,T,F,P→ 索引0到12。解决打印j值调试确保str[index](时j7。4.5popstackc弹出后stack[pointer].content未清零栈残留导致gettop错误现象多次运行后gettop(state_stack, pointer_state)返回随机字符。原因popstackc()函数中stack[p].content\0清零但pointer未同步更新下次pushstack时可能覆盖未清零位置。解决popstackc中(*pointer)--后确保stack[(*pointer)1].content为\0或在pushstack前检查stack[(*pointer)1].content是否为\0。5. 进阶技巧如何将四元式序列导出为文件并做简单优化5.1 导出四元式到文本文件避免控制台刷屏丢失结果实验输出全在cout长表达式结果易滚动消失。添加文件导出功能#includefstream // 在 main() 开头 ofstream outfile(quadruples.txt); if(!outfile.is_open()) { cout Cannot open file! endl; return 1; } // 在 switch_method 的四元式输出处替换 cout 为 outfile // 例如 r1 分支 outfile (, se , st , t t[tsize].num ) endl; // main() 结尾 outfile.close();这样每次运行生成quadruples.txt可反复查看、比对。文件格式为纯文本每行一个四元式便于后续脚本处理。5.2 识别并合并公共子表达式从ii和i*i到t1ii、t2i*i四元式优化第一步是 CSECommon Subexpression Elimination。观察quadruples.txt(, i, i, t1) (*, i, i, t2) (, t1, t2, t3)ii和i*i都含i,i但操作符不同不可合并。真正 CSE 是(, a, b, t1) (*, t1, c, t2) (, a, b, t3) // 重复计算 ab可删去第三行改t3为t1。实现思路遍历四元式列表对每个(op, arg1, arg2, res)检查前面是否存在(op, arg1, arg2, res_prev)若存在则替换后续所有res为res_prev。用mapstring, string记录(op,arg1,arg2)→res映射。5.3 构建符号表为变量i添加类型和作用域信息当前i被当作字面量但真实编译器需符号表。扩展char_stackstruct Symbol { string name; // i string type; // int int scope; // 0: global, 1: local }; mapstring, Symbol symbol_table; // 在 r10: P→i 时 symbol_table[i] {i, int, 0};endchar可改为Symbol*指针指向符号表项实现语义检查如ii要求i类型为int。5.4 从四元式到三地址码的转换为后续目标代码生成铺路四元式(op, arg1, arg2, res)可直接转为三地址码res arg1 op arg2。例如(, i, i, t1) → t1 i i (*, t1, i, t2) → t2 t1 * i只需修改cout格式// 替换原输出 cout t t[tsize].num t[tsize].var1 t[tsize].operate t[tsize].var2 endl;这更接近 LLVM IR 的%t1 add i32 %i, %i形式是向后端演进的关键一步。从那以后我每次写语义分析代码都强制走一遍ii*i#的单步调试盯着pointer、pointer_state、stack和state_stack的每一行变化确认endchar的传递路径是否连贯。因为语义分析不是魔法它只是把人脑里「ii*i先算乘」的直觉翻译成栈顶两个i和一个*触发r4再把t1塞进T的endchar里——这个过程一旦断掉整个中间代码就废了。希望帮到你。本文还有配套的精品资源点击获取
