〔重庆理工大学〕编译原理实验报告【语义分析和中间代码生成实验】

《编译原理》实验报告（第三次）

学号： 1230904XXXX 姓名： 段 X X 时间： 2026/5/22

CQUT编译原理实验报告【语义分析和中间代码生成实验】

• 《编译原理》实验报告（第三次）
• 1 实验目的
• 2 实验内容
• • 2.1 语义分析实验
  • 2.2 中间代码生成实验
• 3 实验方案
• • 3.1 方案描述
  • • 3.1.1 语义分析模块
    • • 1.核心数据结构
      • 2.语义分析总流程
      • 3.AST 解析与重构
      • 4.符号表与作用域管理
      • 5.语义错误检测规则
      • 6.核心函数说明
    • 3.1.2 中间代码生成模块
    • • 1.核心数据结构
      • 2.中间代码生成总流程
      • 3.词法分析器（Lexer）
      • 4.递归下降语法分析与语法制导翻译
      • 5.回填与跳转管理
      • 6.临时变量管理
  • 3.2 方案分析
  • • 3.2.1 语义分析方案优劣
    • • 1.优势
      • 2.劣势与局限性
    • 3.2.2 中间代码生成方案优劣
    • • 1.优势
      • 2.劣势与局限性
    • 3.2.3 方案对比与选择依据
• 4 实验测试
• • 4.1 语义分析实验测试
  • 4.2 中间代码生成实验测试
• 5 实验结论
• • 5.1 整体实验总结
  • 5.2 核心问题与解决方案复盘
  • 5.3 实验收获与心得
  • 5.4 实验不足与优化改进方向
• 6 实验源代码
• • 1.实验一语义分析（python语言）
  • 2.实验二中间代码生成（python语言）
• 7 实验报告（电子版Word文档）
• • 1.编译原理实验报告【语义分析和中间代码生成实验】
  • 2.解压包密码
• 8 实验源代码（python语言）
• • 1.编译原理实验源代码【语义分析和中间代码生成实验】
  • 2.解压包密码

1 实验目的

1.掌握抽象语法树（AST）解析方法，能够将文本格式的 AST 重构为内存树形结构，为后续语义检查提供数据基础。

2.理解符号表的核心作用，设计并实现支持嵌套作用域的符号表管理机制，完成常量表、变量表、函数表的构建与持久化输出。

3.掌握 Sample 语言10 类核心语义错误的检测规则与定位方法，实现错误局部化记录、去重与标准化输出。

4.理解语法制导翻译与中间代码生成原理，掌握四元式的数据结构设计、临时变量管理与真假链回填算法。

5.实现赋值表达式、布尔表达式、控制语句（if/while/for/do-while）、函数调用与返回的四元式翻译，完成编译器前端到中端的流程衔接。

6.严格遵循实验输入输出规范，实现多文件协同输出（错误信息、符号表、四元式），满足自动评测要求。

2 实验内容

本次实验包含语义分析与中间代码生成两大核心模块，基于前序词法分析、语法分析实验成果，完成编译器前端到中端的完整实现。

2.1 语义分析实验

1.AST 解析与重构：读取input.txt中文本格式的 AST，通过正则与栈结构重构内存树形节点，提取节点类型、行号、子节点信息。

2.符号表设计与管理：

（1）构建嵌套作用域栈，支持局部作用域覆盖全局作用域、内层覆盖外层的符号查找规则。

（2）分别维护常量表、变量表、函数表，记录符号名称、类型、作用域、行号信息，最终输出至const.txt/var.txt/function.txt。

3.语义错误检测：实现 10 类语义错误的全量检测，严格按行号与编码输出至output.txt，每行仅记录一个错误。

4.错误处理机制：检测到错误仅记录信息，不中断遍历流程，完成全量错误检测后按行号升序输出。

2.2 中间代码生成实验

1.整合编译流程：融合词法分析、语法分析、语义分析模块，接收无语法语义错误的 Sample 源程序。

2.四元式结构设计：定义四元式数据结构，包含运算符、左操作数、右操作数、结果四个分量，支持跳转、赋值、运算、函数调用等操作。

3.语法制导翻译实现：

（1）实现常量 / 变量声明、赋值表达式、算术 / 逻辑表达式的四元式生成。

（2）实现 if、while、for、do-while 控制语句的真假链回填与跳转四元式生成。

（3）实现函数定义、参数传递、函数调用、返回语句的四元式翻译。

4.临时变量管理：自动生成递增临时变量（t1、t2…），统一管理表达式运算的中间结果。

5.标准化输出：按编号顺序将四元式序列写入output.txt，符合自动评测格式要求。

3 实验方案

本次实验基于前序词法分析、语法分析的实验成果，针对Sample语言完成语义分析检测与中间代码四元式生成两大核心功能开发。全程采用模块化、分层化的程序设计思想，将语义检查、符号表管理、错误处理、语法制导翻译、四元式生成、跳转回填等核心逻辑解耦拆分，保证代码可读性、可调试性与可扩展性。同时严格遵循LL(1)文法规则与语法制导翻译原理，适配嵌套作用域、多类型语法语句、函数调用等复杂场景，完全满足本次实验的功能要求与自动评测标准。

3.1 方案描述

本次实验采用模块化设计，分为语义分析模块与中间代码生成模块，两模块独立实现、协同工作，严格遵循实验规范。语义分析模块以语法分析输出的AST为输入，完成符号表构建、嵌套作用域管理、全量语义错误检测；中间代码生成模块整合编译全流程，对无语法、语义错误的源码进行语法制导翻译，生成标准化四元式中间代码。

3.1.1 语义分析模块

1.核心数据结构

（1）AST 节点结构

python
class Node:
def __init__(self, name, line, indent):
self.name = name # 节点类型/内容
self.line = line # 行号
self.indent = indent# 缩进层级
self.ch = [] # 子节点列表

该节点结构为AST树形结构的基础单元，统一存储所有语法成分的核心信息。其中name区分节点类型（声明、语句、表达式、函数等），line精准记录源码行号用于错误定位，indent用于还原AST层级关系，ch子节点列表构建完整树形嵌套结构，支撑后续递归遍历与语义检查。

（2）符号表结构

A.作用域栈ctx：列表元素为字典，每个字典对应一层作用域，存储{变量名: {kind: const/var, type: int/float/char}}。采用栈结构完美适配Sample语言嵌套作用域特性，实现全局作用域、函数局部作用域、语句块局部作用域的层级管理。

B.符号列表：c_list（常量）、v_list（变量）、f_list（函数）、f_info（函数参数与返回值）。分类存储所有自定义符号信息，最终分别导出至对应文件，实现符号表持久化存储。

（3）错误存储：errs字典，{行号: 错误编码}，保证每行唯一错误，自动去重，符合实验“单行列单错误”的评测规则。

2.语义分析总流程

该流程图完整呈现了语义分析的完整执行链路，从程序启动读取文本格式AST开始，依次完成AST解析重构、核心参数初始化、AST节点递归遍历与各类语义错误针对性检测、合法符号录入存储，最终经过错误去重排序后完成错误信息与多类符号表文件的标准化输出，实现全流程自动化语义校验。如图1所示。

图1 语义分析总流程图

3.AST 解析与重构

采用缩进匹配 + 栈结构重构 AST，解决文本AST无法直接用于程序遍历的问题，精准还原源码层级语义结构：

（1）逐行读取AST文本文件，通过正则表达式精准匹配每行的缩进空格数、节点名称、源码行号，过滤无效空行与冗余字符；

（2）维护节点栈结构，栈顶始终为当前层级的父节点。通过对比当前行与栈顶节点的缩进层级，实现入栈、出栈、挂载子节点操作，自动适配多层嵌套的复合语句、函数体、条件循环语句；

（3）以Program作为唯一根节点，自上而下构建完整树形结构，保留所有语法成分的层级、行号、属性信息，为后续精准语义检查提供完整数据支撑。

4.符号表与作用域管理

符号表管理是语义分析的核心核心，本次实验实现了嵌套作用域动态管理机制，严格遵循高级语言作用域覆盖规则，精准区分全局、局部变量/常量的作用范围：

（1）作用域规则：进入复合语句、函数体、循环体等代码块时，调用append新建一层局部作用域，隔离内层符号与外层符号；

（2）退出代码块时，调用pop销毁当前局部作用域，释放局部符号，避免不同代码块符号污染；

（3）符号查找遵循由内到外、就近匹配原则，从栈顶内层作用域向栈底全局作用域遍历，内层符号优先覆盖外层同名符号，完全贴合C类语言语义规则。

（4）符号检查规则：同层级作用域内禁止同名符号重复定义，触发301重复声明错误；

（5）表达式、语句中使用的标识符，若所有层级作用域均无定义，触发302未声明使用错误；

（6）全局作用域中禁止同名函数重复定义，触发303函数重定义错误；

（7）常量属于只读符号，任何场景下对常量赋值均触发309修改常量错误。

5.语义错误检测规则

该表格系统性汇总了本次实验要求检测的10类核心语义错误编码、对应错误类型及精细化检测判定逻辑，全面覆盖符号定义与使用、函数调用、数值运算、语句使用、常量操作等所有语义校验场景，是程序实现精准语义错误检测、合规报错的核心规则依据。

6.核心函数说明

（1）parse()：AST文本解析核心函数，通过正则匹配与栈操作，将纯文本AST转换为内存树形Node结构，还原完整语法层级。

（2）walk()：递归遍历核心函数，深度优先遍历所有AST节点，根据节点类型分发对应的语义检查逻辑，覆盖全语法成分。

（3）chk_expr()：表达式专属检查函数，统一检测标识符未定义、常量赋值、运算类型不匹配、左值非法等表达式语义错误。

（4）record_error()：错误记录核心函数，自动去重、校验行号，保证每行仅存储一个错误，统一错误输出格式。

（5）find()：符号查询核心函数，遍历嵌套作用域栈，实现标识符精准查找，返回符号类型与属性。

3.1.2 中间代码生成模块

1.核心数据结构

（1）Token 结构：存储单词类型、值、行号，承接词法分析结果，为语法解析与翻译提供基础词法单元。

（2）四元式结构

python
class Quaternion:
def __init__(self, op, arg1, arg2, result):
self.op = op # 运算符：运算、跳转、函数、系统指令
self.arg1 = arg1 # 左操作数：变量、常量、临时变量、空占位符
self.arg2 = arg2 # 右操作数：变量、常量、临时变量、空占位符
self.result = result# 结果：变量、临时变量、跳转地址、空占位符

四元式是本次实验生成的核心中间代码形式，结构简洁、独立于硬件，是编译器中端优化、目标代码生成的基础。覆盖赋值、算术运算、逻辑运算、条件跳转、无条件跳转、函数操作、系统退出等所有指令类型。

（3）代码生成器：CodeGen类，全局维护四元式序列列表、临时变量自增计数器、跳转回填栈、break/continue跳转待回填列表，统一管理中间代码生成全流程。

2.中间代码生成总流程

图2 中间代码生成总流程图

该流程图清晰展示了编译中端中间代码生成的全流程逻辑，以无语法语义错误的Sample源码为输入，经词法分析生成Token序列、初始化代码生成器后，通过递归下降语法分析匹配各类语法成分并同步完成语法制导翻译，结合跳转地址批量回填处理，最终生成规范完整的四元式中间代码并标准化输出。如图2所示。

3.词法分析器（Lexer）

（1）兼容中英文关键字、全角/半角符号自动归一化处理，规避输入格式问题导致的解析异常；

（2）精准识别Sample语言所有关键字、自定义标识符、整型/浮点/字符常量、运算符、分隔符，生成标准化Token序列，无冗余、无遗漏；

（3）封装peek()预查看、consume()消费Token、expect()匹配校验三大核心接口，为语法解析的精准推进提供底层支撑。

4.递归下降语法分析与语法制导翻译

本次中间代码生成采用语法制导翻译技术，在递归下降语法分析识别语法成分的同时，同步执行语义翻译动作，边解析、边生成四元式，实现语法解析与中间代码生成一体化。

（1）非终结符对应解析函数：针对每一类语法成分独立编写解析翻译函数，包括变量常量声明、各类表达式、if语句、while/for/do-while循环、函数定义与调用、返回语句等，全覆盖实验要求语法成分。

（2）表达式翻译：严格按照运算符优先级分层解析（逻辑或→逻辑与→关系运算→加减运算→乘除运算→单目运算→初等项），优先计算子表达式并生成临时变量存储结果，保证运算优先级与结合性完全符合源码语义。

（3）控制语句回填算法：解析条件语句时，先生成不完整的跳转四元式，将待回填的四元式索引存入真假链列表；

（4）当对应分支语句块解析完成后，批量回填跳转目标地址，补全四元式，精准实现分支跳转逻辑。

（5）函数翻译：标准化生成函数专属四元式，包括程序入口main、参数定义para、函数调用call、返回指令ret、程序结束sys，完整还原函数调用与执行流程。

5.回填与跳转管理

跳转回填是控制语句中间代码生成的核心难点，本次通过真假链与栈结构完美解决跳转地址未知问题：

（1）真假链：分别存储条件为真、条件为假时待回填的跳转四元式索引，批量管理、统一回填，提升代码生成效率；

（2）backpatch()：通用回填函数，支持批量为多个待回填四元式赋值目标地址，适配所有分支、循环场景；

（3）break/continue：采用栈结构维护多层循环的跳转列表，内层循环跳转优先回填，完美适配嵌套循环场景。

6.临时变量管理

（1）new_temp()自动生成规则：临时变量从t1开始自增编号，每产生一个新的中间运算结果，自动分配全新临时变量，无重复、无混乱；

（2）所有复合表达式的中间运算结果均通过临时变量存储，避免运算值覆盖，保证四元式执行顺序与源码运算逻辑完全一致，输出格式标准化、规范化。

3.2 方案分析

3.2.1 语义分析方案优劣

1.优势

（1）AST 解析高效稳定：基于栈结构的AST重构算法时间复杂度为O(n)，线性遍历所有AST节点，无论简单单语句程序还是多层嵌套复杂程序，均可快速完成解析，适配所有实验测试用例。

（2）作用域管理精准严谨：嵌套栈作用域机制完全对标标准C类语言语义规则，精准区分全局、局部符号，正确实现内层覆盖外层、同级查重的核心逻辑，无符号误判、漏判问题。

（3）错误检测全面规范：全覆盖实验要求的10类语义错误，实现错误自动去重、行号精准定位、按序输出，严格匹配自动评测格式标准，检测准确率100%。

（4）模块化解耦性强：将AST解析、符号表管理、语义检查、错误记录、文件输出拆分为独立函数，各模块职责单一，互不干扰，便于调试、修改与后续功能扩展。

（5）符号表标准化输出：分类导出常量表、变量表、函数表，表格信息完整规范，包含符号名、类型、作用域、行号等核心信息，可为后续语义优化、代码生成提供完整数据支撑。

2.劣势与局限性

（1）输入兼容性有限：仅支持文本格式AST输入，无法直接对接语法分析阶段的内存AST结构，需要格式转换，适配场景单一，仅适用于教学实验场景。

（2）类型检查机制简单：严格禁止所有类型不匹配运算，不支持高级语言的隐式类型转换、强制类型转换与类型推导功能，距离工业级编译器类型检查有一定差距。

（3）错误容错能力较弱：仅实现错误检测、记录与上报功能，无错误自动修复、错误提示文本输出、错误分级处理能力，仅满足基础评测需求，调试友好度不足。

3.2.2 中间代码生成方案优劣

1.优势

（1）编译流程完整闭环：完整整合词法分析、语法分析、语义校验、中间代码生成全流程，实现从原始源码到四元式中间代码的一键转换，完整还原编译器前端+中端工作机制。

（2）回填算法精准高效：基于真假链与栈的跳转回填机制，完美解决分支、循环语句跳转地址滞后绑定的难题，精准实现所有控制语句的语义逻辑，无跳转错乱、地址缺失问题。

（3）四元式格式高度规范：严格遵循实验指定的四元式输出格式，临时变量编号规则统一、指令类型齐全、分量赋值规范，完全适配自动评测系统校验标准。

（4）递归下降扩展性强：采用非终结符对应独立解析函数的设计，代码结构清晰，后续新增switch、数组、结构体等语法成分时，仅需新增对应解析翻译函数，无需重构整体框架。

（5）零依赖跨平台运行：基于纯Python原生代码实现，无第三方库依赖，跨Windows、Linux、Mac平台运行，兼容性强、调试便捷。

2.劣势与局限性

（1）无中间代码优化机制：采用直译式翻译逻辑，完全按照源码执行顺序生成四元式，存在大量冗余临时变量与冗余运算指令，未实现常量折叠、公共子表达式消除、跳转优化等编译优化算法。

（2）语法覆盖范围有限：仅支持实验要求的基础语法成分，不支持switch分支、数组、指针、结构体、字符串等高级语法，无法适配复杂Sample程序翻译。

（3）无中间代码持久化复用：每次程序运行均重新解析源码、生成四元式，无法将生成的中间代码持久化存储、复用，执行效率较低。

3.2.3 方案对比与选择依据

本次实验选择手工遍历 AST + 递归下降语法制导翻译，核心原因：

1.贴合编译原理教学核心目标，深度吃透底层编译逻辑，手工实现可深度理解符号表管理、语义检查、语法制导翻译、跳转回填的底层原理，区别于工具自动生成的黑盒实现，实训价值极高。能够完整复刻编译器中端的运行链路，有效规避工具封装带来的知识盲区，全方位夯实编译原理核心理论与实操结合能力，精准适配课程实训的核心教学诉求。

2.适配实验开发场景，开发成本可控且调试便捷，Sample语言语法规则简单、结构清晰，手工开发成本可控，代码逻辑清晰，便于调试排错、精准适配实验评测规则。可以精准对标实验定制化的报错编码、行号输出、四元式格式规范，可随时微调逻辑适配评测规则，有效规避自动化工具格式固化、无法自定义适配的短板。

3.模块化手工架构灵活性高，完美适配实验评测标准，可根据实验要求精准调整错误检测规则、四元式输出格式、符号表存储规则，完美匹配自动评测标准。本方案所有核心逻辑均自主定义，模块化架构解耦性强，后续新增语义规则、拓展语法成分、优化代码格式均可快速迭代，适配实验各类功能拓展需求。

4 实验测试

本次实验为保证功能完整性、准确性与稳定性，针对语义分析与中间代码生成两大模块设计分层全覆盖测试方案，包含单一错误专项测试、混合错误综合测试、基础语法测试、复杂控制语句测试、函数调用专项测试共15组测试用例，所有用例均严格贴合实验评分标准与样例规范，全方位验证程序功能的正确性、稳定性与规范性。

4.1 语义分析实验测试

语义分析测试核心目标：验证10类语义错误的检测精度、符号表构建准确性、嵌套作用域有效性、错误去重与排序功能，所有测试用例均采用实验标准AST输入格式，输出结果严格匹配评测规范。

测试总结：语义分析模块11组专项、综合测试用例全部通过，10类语义错误检测全覆盖、零误报、零漏报，嵌套作用域符号管理精准，符号表分类输出规范，错误去重、排序功能正常，完全满足实验功能要求与自动评测标准。同时完美适配内层变量覆盖外层、函数参数重载、多层嵌套循环等复杂场景，语义校验逻辑严谨可靠。如图3所示。

图3 语义分析测试结果

4.2 中间代码生成实验测试

中间代码生成测试核心目标：验证各类语法成分的四元式生成准确性、临时变量规范性、跳转回填正确性、函数指令完整性，测试用例覆盖基础声明、复合表达式、分支语句、循环语句、函数调用五大核心场景，完全对标实验样例与评分标准。

测试总结：中间代码生成模块6组测试用例全部通过，覆盖基础声明、复合运算、分支、循环、函数调用所有核心语法。临时变量编号规范、运算优先级解析准确、跳转回填无误差、函数指令完整，输出四元式格式与实验样例完全一致，无冗余、无缺失、无逻辑错误，完全满足自动评测要求。综合测试用例验证了程序的兼容性与稳定性，可完整处理多语法混合的复杂Sample源码。如图4所示。

图4 中间代码生成测试结果

5 实验结论

5.1 整体实验总结

本次编译原理第三次实验完整完成语义分析与中间代码生成两大核心模块的设计与开发，承接前序词法分析、语法分析的实验成果，成功搭建起「词法分析→语法分析→语义分析→中间代码生成」的完整编译器前端与中端链路，全面达成本次实验预设的所有教学目标与功能指标。本次实验基于Python纯手工实现，无任何工具自动生成，深度落地编译原理核心理论，圆满完成所有测试用例，程序运行稳定、输出规范、检测精准。

在语义分析模块中，成功实现文本AST解析重构、嵌套作用域符号表动态管理、10类标准语义错误的精准检测与定位，完成常量表、变量表、函数表的分类持久化输出，严格遵循Sample语言语义规则，解决了符号重定义、未定义使用、类型不匹配、函数调用异常、跳转语句非法使用等一系列语义校验问题，错误检测准确率100%，完全适配实验自动评测标准。

在中间代码生成模块中，基于语法制导翻译技术，实现了所有基础语法与扩展语法的四元式中间代码生成，精准处理表达式优先级、分支循环跳转回填、临时变量管理、函数调用与返回逻辑。生成的四元式结构规范、逻辑严谨、执行顺序与源码完全一致，成功将高级语言源码翻译为独立于硬件的中间代码，为后续编译器优化、目标代码生成奠定了坚实基础。

5.2 核心问题与解决方案复盘

实验开发过程中，针对语义分析与中间代码生成的核心难点问题，逐一分析并落地解决方案，有效解决了编译过程中的典型问题：

1.嵌套作用域符号冲突问题：初始开发中存在内层符号无法覆盖外层、同级符号查重失效的问题。通过优化作用域栈的进出逻辑，严格遵循「先入后出、就近查找」原则，区分全局与局部作用域，精准实现同级查重、内层覆盖外层的语义规则，彻底解决符号判定异常问题。

2.语义错误重复上报问题：多语法嵌套场景下，单行代码容易触发多条错误、重复报错。通过设计行号去重字典，限制每行仅存储一条优先级最高的错误，实现错误精准过滤、标准化输出，符合实验评测规则。

3.控制语句跳转地址缺失问题：if、while、for等控制语句解析时，跳转目标地址滞后未知，导致四元式不完整。通过引入真假链与批量回填算法，先记录待跳转四元式索引，语句块解析完成后统一回填地址，完美解决跳转地址缺失难题。

4.表达式运算优先级错乱问题：复合表达式容易出现运算顺序与源码不一致的问题。通过分层设计表达式解析函数，严格按照编译原理规定的运算符优先级与结合性分层解析，配合临时变量存储中间结果，保证运算逻辑完全贴合源码语义。

5.临时变量混乱问题：多表达式嵌套场景下临时变量重复、编号混乱。通过全局唯一自增计数器管理临时变量，每次运算自动分配新变量，无重复、无覆盖，保证中间代码逻辑严谨。

5.3 实验收获与心得

本次实验是对编译原理核心中端知识的深度实操落地，相较于前两次词法、语法分析实验，本次实验更侧重语义逻辑校验与代码翻译原理，让我对编译器的完整工作机制有了系统性、深层次的理解：

1.理论认知升级：彻底理解了符号表、嵌套作用域、语义检查、语法制导翻译、四元式中间代码、真假链回填等核心知识点的底层原理。明白了语法分析仅校验代码格式合法，而语义分析校验代码逻辑合法，中间代码生成是高级语言到机器语言的过渡核心，打通了编译前端与中端的知识壁垒。

2.实操能力提升：熟练掌握AST树形结构遍历、嵌套数据结构管理、递归程序设计、批量回填算法、文件持久化输出等编程技巧，能够独立完成小型高级语言的语义校验与中间代码生成开发，大幅提升了编译原理工程化实践能力。

3.工程思维养成：深刻体会模块化、解耦式编程的重要性，通过拆分解析、检查、翻译、输出模块，让复杂的编译流程变得清晰可控。同时理解了编译器容错机制、标准化输出、自动评测适配的工程设计思路。

4.问题排查能力强化：在解决跳转错乱、符号误判、类型报错、四元式冗余等问题的过程中，积累了编译器调试、树形结构排错、递归逻辑优化的实战经验。

5.4 实验不足与优化改进方向

本次实验程序已完整满足教学与评测要求，但相较于工业级编译器，仍存在一定局限性，后续可从以下维度优化扩展：

1.完善语义检测机制：当前类型检查不支持隐式、强制类型转换，后续可新增类型推导、类型转换校验、变量未使用警告、函数声明定义匹配等语义检测功能，丰富错误体系，增加错误文本描述，提升调试友好度。

2.新增中间代码优化：当前直译式生成的四元式存在冗余指令，后续可实现常量折叠、公共子表达式消除、跳转优化、死代码删除等编译优化算法，精简中间代码，提升代码执行效率。

3.扩展语法支持范围：新增数组、指针、结构体、switch分支、字符串等高级语法的语义校验与中间代码生成，完善Sample语言的语法覆盖范围。

6 实验源代码

1.实验一语义分析（python语言）

import sys
import re

# 全局数据结构
errs = {}
c_list = []
v_list = []
f_list = []
f_info = {}
ctx = [{}]
blt = {'printf', 'scanf', 'getchar', 'putchar', 'gets', 'puts', 'malloc', 'free', 'exit'}

# 跳过这些节点类型以提取真实名称
skip = {
'ArraySubscriptExpr', 'DeclRefExpr', 'MemberExpr', 'ParenExpr',
'ImplicitCastExpr', 'CStyleCastExpr', 'UnaryOperator', 'BinaryOperator',
'CXXStaticCastExpr', 'CXXConstCastExpr', 'CXXReinterpretCastExpr',
'OpaqueValueExpr', 'CallExpr', 'InvokeExpr', 'ReturnStmt', 'BreakStmt', 'ContinueStmt'
}

class Node:
def __init__(self, name, line, indent):
self.name = name
self.line = line
self.indent = indent
self.ch = []

def parse(text):
"""从文本构建AST树"""
lines = text.strip('\\n').split('\\n')
root = Node("Root", None, –1)
stk = [root]
for row in lines:
if not row.strip(): continue
m = re.match(r'^(\\s*)(.*?)(?:\\[(\\d+)\\])?\\s*$', row)
if not m: continue
sp, nm, ln = m.groups()
ind = len(sp)
ln = int(ln) if ln else None
nd = Node(nm.strip(), ln, ind)
while stk and stk[–1].indent >= ind:
stk.pop()
stk[–1].ch.append(nd)
stk.append(nd)
return root.ch[0] if root.ch else root

def rpt(ln, code):
"""记录错误"""
if ln is not None and ln not in errs:
errs[ln] = code

def max_line(nd):
"""子树中最大行号"""
m = nd.line if nd.line else 0
for c in nd.ch:
m = max(m, max_line(c))
return m

def find(name):
"""在作用域链中查找符号"""
for s in reversed(ctx):
if name in s:
return s[name]
return None

def find_nodes(nd, k1, k2=""):
"""按节点名关键字查找"""
res = []
if k1 in nd.name or (k2 and k2 in nd.name):
res.append(nd)
for c in nd.ch:
res.extend(find_nodes(c, k1, k2))
return res

def has_brk(nd):
"""检查是否有break语句（跳过循环/switch内部）"""
if 'BreakStmt' in nd.name or nd.name == 'Break':
return True
for c in nd.ch:
cn = c.name
if 'WhileStmt' in cn or 'ForStmt' in cn or 'SwitchStmt' in cn:
continue
if cn in ['While', 'For', 'Switch']:
continue
if has_brk(c):
return True
return False

def norm(t):
"""归一化类型名称"""
if not t:
return 'unknown'
t = t.replace('const ', '').replace('unsigned ', '').replace('long ', '').replace('short ', '').strip()
if t == 'double':
return 'float'
return t

def get_fun_name(c):
"""从函数声明节点提取函数名和返回类型"""
c = c.split('[')[0].strip()
m = re.search(r'(?:Function|Func)?(?:Decl|Def)\\s*\\((.*?)\\)', c)
if not m:
m = re.search(r'\\((.*?)\\)', c)
if not m:
return "", ""
inner = m.group(1).strip()
sig = inner.split('(')[0].strip()
parts = sig.split()
if len(parts) >= 2:
fn = parts[–1].replace('*', '')
rt = " ".join(parts[:–1])
return fn, norm(rt)
return parts[0] if parts else "", "void"

def get_call(c, children):
"""提取函数名和实参子树"""
c_clean = c.split('[')[0].strip()
m = re.search(r'(?:Call|Invoke)(?:Expr)?\\s*\\(\\s*([A-Za-z_]\\w*)\\s*\\)', c_clean)
if m:
return m.group(1), children
if children:
cur = children[0]
while cur:
nm = cur.name.split('[')[0].strip()
m2 = re.search(r'\\(\\s*([A-Za-z_]\\w*)\\s*\\)', nm)
if m2:
return m2.group(1), children[1:]
m3 = re.search(r'^[A-Za-z_]\\w*$', nm)
if m3 and m3.group(0) not in skip:
return m3.group(0), children[1:]
if cur.ch:
cur = cur.ch[0]
else:
break
return "", children

def get_var(nd):
"""提取变量名（穿透Cast等节点）"""
if not nd:
return ""
c = nd.name.split('[')[0].strip()
m = re.search(r'\\(\\s*([A-Za-z_]\\w*)\\s*\\)', c)
if m:
return m.group(1)
m = re.search(r'^[A-Za-z_]\\w*$', c)
if m and m.group(0) not in skip:
return m.group(0)
m = re.search(r'[A-Za-z_]\\w*', c)
if m and m.group(0) not in skip:
return m.group(0)
if nd.ch:
return get_var(nd.ch[0])
return ""

def expr_type(nd):
"""推断表达式的类型"""
if not nd:
return 'unknown'
c = nd.name
if re.match(r'^-?\\d+$', c) or 'IntegerLiteral' in c:
return 'int'
if re.match(r'^-?\\d+\\.\\d*(f|F)?$', c) or 'FloatingLiteral' in c:
return 'float'
if c.startswith("'") or c.startswith('"') or 'CharacterLiteral' in c or 'StringLiteral' in c:
return 'char'
if len(c) == 1 and c.isupper():
return 'char'

n = get_var(nd)
if re.match(r'^[A-Za-z_]\\w*$', n):
s = find(n)
if s:
return s['type']

c_clean = c.split('[')[0].strip()
op = c_clean
m_op = re.search(r'(?:Operator|Assign)\\s*\\(\\s*([^\\s\\w\\)]+)\\s*\\)', c_clean)
if m_op:
op = m_op.group(1)

if op in ['+', '-', '*', '/', '%', '=', '+=', '-=', '*=', '/=', '%='] or 'Assign' in c_clean:
if len(nd.ch) >= 2:
t1 = expr_type(nd.ch[0])
t2 = expr_type(nd.ch[1])
if t1 == 'mismatch' or t2 == 'mismatch':
return 'mismatch'
if t1 != 'unknown' and t2 != 'unknown' and norm(t1) != norm(t2):
return 'mismatch'
return t1 if t1 != 'unknown' else t2
elif len(nd.ch) == 1:
return expr_type(nd.ch[0])
elif op in ['>', '<', '>=', '<=', '==', '!=', '&&', '||', '!']:
return 'int'

if 'Cast' in c or 'ParenExpr' in c:
if nd.ch:
return expr_type(nd.ch[0])

if 'Call' in c or 'Invoke' in c:
fn, _ = get_call(c, nd.ch)
if fn in blt:
return 'unknown'
if fn in f_info:
return f_info[fn]['type']
return 'unknown'

return 'unknown'

def chk_expr(nd):
"""检查表达式中的错误：未定义变量、类型不匹配、常量赋值等"""
c = nd.name
if 'Call' in c or 'Invoke' in c:
fn, args = get_call(c, nd.ch)
if not fn:
for a in nd.ch:
chk_expr(a)
return
if fn in blt:
for a in args:
chk_expr(a)
return

if fn not in f_info:
rpt(nd.line, 304)
else:
exp = f_info[fn]['params']
if len(args) != len(exp):
rpt(nd.line, 305)
else:
for i in range(len(args)):
at = expr_type(args[i])
if at != 'unknown' and at != 'mismatch' and norm(at) != norm(exp[i]):
rpt(nd.line, 306)
break
for a in args:
chk_expr(a)
return

c_clean = c.split('[')[0].strip()
op = c_clean
m_op = re.search(r'(?:Operator|Assign)\\s*\\(\\s*([^\\s\\w\\)]+)\\s*\\)', c_clean)
if m_op:
op = m_op.group(1)

is_op = op in ['+', '-', '*', '/', '%', '>', '<', '>=', '<=', '==', '!=', '&&', '||', '=', '+=', '-=', '*=', '/=', '%=', '!', '++', '–'] or 'Assign' in c_clean or 'Operator' in c_clean
if is_op:
is_assign = ('=' in op) or (op in ['++', '–']) or ('Assign' in c_clean)
if is_assign and nd.ch:
lhs = nd.ch[0]
n = get_var(lhs)
s = find(n)
if s and s['kind'] == 'const':
rpt(nd.line, 309)
if len(nd.ch) >= 2:
t1 = expr_type(nd.ch[0])
t2 = expr_type(nd.ch[1])
if t1 != 'unknown' and t2 != 'unknown' and norm(t1) != norm(t2):
rpt(nd.line, 310)
for cld in nd.ch:
chk_expr(cld)
return

if not nd.ch:
n = get_var(nd)
if re.match(r'^[A-Za-z_]\\w*$', n):
kw = {'int','float','char','void','double','break','return','continue','if','else','while','for','switch','case','default','const','unsigned','long','short'}
if n not in kw:
lit = False
if len(n) == 1 and n.isupper():
lit = True
if re.match(r'^-?\\d+$', n) or re.match(r'^-?\\d+\\.\\d*(f|F)?$', n):
lit = True
if n.startswith("'") or n.startswith('"'):
lit = True
if not lit and not find(n):
rpt(nd.line, 302)
return

for cld in nd.ch:
chk_expr(cld)

def walk(nd, loop=False, sw=False, is_func_body=False):
"""遍历AST，执行语义检查"""
c = nd.name

if 'FunctionDecl' in c or 'FuncDecl' in c or 'FunctionDef' in c:
fn, rt = get_fun_name(c)
if not fn:
return

has_body = any('Compound' in ch.name or 'Block' in ch.name for ch in nd.ch)
is_redecl = False

if fn in f_info:
if has_body:
if f_info[fn]['has_body']:
is_redecl = True
else:
f_info[fn]['has_body'] = True
else:
is_redecl = True

if is_redecl:
rpt(nd.line, 303)

if fn not in f_info:
pts = []
for ch in nd.ch:
if 'Compound' in ch.name or 'Block' in ch.name:
break
ns = ch.name.split('[')[0].strip()
m_parm = re.search(r'\\((.*?)\\)', ns)
p_str = m_parm.group(1) if m_parm else ns
parts = p_str.split()
if len(parts) >= 2:
pts.append(norm(" ".join(parts[:–1])))
elif len(parts) == 1 and parts[0] != 'void':
pts.append(norm(parts[0]))
f_info[fn] = {'type': rt, 'params': pts, 'has_body': has_body}
f_list.append((fn, rt))

ctx.append({})
for ch in nd.ch:
if 'Compound' in ch.name or 'Block' in ch.name:
break
ns = ch.name.split('[')[0].strip()
m_parm = re.search(r'\\((.*?)\\)', ns)
p_str = m_parm.group(1) if m_parm else ns
parts = p_str.split()
if len(parts) >= 2:
vn = parts[–1].replace('*', '').replace('&', '')
vt = " ".join(parts[:–1])
if vn in ctx[–1]:
rpt(ch.line, 301)
else:
ctx[–1][vn] = {'kind': 'var', 'type': vt}
v_list.append((vn, vt))

body = next((ch for ch in nd.ch if 'Compound' in ch.name or 'Block' in ch.name), None)
if body:
walk(body, False, False, True)
rets = find_nodes(body, 'ReturnStmt', 'Return')
el = max_line(nd)
is_void = (rt == 'void')
err_flag = False

if not is_void:
if not rets:
err_flag = True
else:
for r in rets:
if not r.ch:
err_flag = True
else:
ret_t = expr_type(r.ch[0])
if ret_t != 'unknown' and ret_t != 'mismatch' and norm(ret_t) != norm(rt):
err_flag = True
else:
for r in rets:
if r.ch:
err_flag = True
if err_flag:
rpt(el, 307)
ctx.pop()
return

if 'VarDecl' in c or 'ConstDecl' in c or 'ParmDecl' in c:
m = re.search(r'\\((.*?)\\)', c)
if m:
parts = m.group(1).split()
if len(parts) >= 2:
vn = parts[–1].split('[')[0].replace('*', '')
vt = " ".join(parts[:–1])
is_const = ('Const' in c.split('(')[0]) or ('const' in parts[:–1])
kind = 'const' if is_const else 'var'

if vn in ctx[–1]:
rpt(nd.line, 301)
else:
ctx[–1][vn] = {'kind': kind, 'type': vt}
if kind == 'const':
c_list.append((vn, vt))
else:
v_list.append((vn, vt))

if nd.ch:
e_t = expr_type(nd.ch[0])
if e_t != 'unknown' and e_t != 'mismatch' and norm(e_t) != norm(vt):
rpt(nd.line, 310)
if nd.ch:
chk_expr(nd.ch[0])
return

if 'Compound' in c or 'Block' in c:
if not is_func_body:
ctx.append({})
for ch in nd.ch:
walk(ch, loop, sw)
if not is_func_body:
ctx.pop()
return

if 'WhileStmt' in c or 'ForStmt' in c or c in ['While', 'For']:
for ch in nd.ch:
walk(ch, True, sw)
return

if 'SwitchStmt' in c or c == 'Switch':
for ch in nd.ch:
walk(ch, loop, True)
return

if 'CaseStmt' in c or 'DefaultStmt' in c or c in ['Case', 'Default']:
if not has_brk(nd):
rpt(max_line(nd), 308)
for ch in nd.ch:
walk(ch, loop, True)
return

if 'BreakStmt' in c or c == 'Break':
if not loop and not sw:
rpt(nd.line, 308)
return

if 'ReturnStmt' in c or c == 'Return':
if nd.ch:
chk_expr(nd.ch[0])
return

if 'IfStmt' in c or c == 'If' or 'Program' in c or 'Root' in c or 'Stmt' in c or 'Decl' in c or 'TranslationUnit' in c:
for ch in nd.ch:
walk(ch, loop, sw)
return

chk_expr(nd)

def main():
try:
with open('input.txt', 'r', encoding='utf-8') as f:
txt = f.read()
except FileNotFoundError:
return

root = parse(txt)
walk(root)

with open('output.txt', 'w', encoding='utf-8') as f:
for l in sorted(errs.keys()):
f.write(f"{l} {errs[l]}\\n")

def save(fn, data):
with open(fn, 'w', encoding='utf-8') as f:
for n, t in data:
f.write(f"{n} {t}\\n")

save('const.txt', c_list)
save('var.txt', v_list)
save('function.txt', f_list)

if __name__ == "__main__":
main()

2.实验二中间代码生成（python语言）

import sys

# ==================== 词法分析器 (Lexer) ====================

TK_INT, TK_FLOAT, TK_CHAR, TK_CONST, TK_IF, TK_ELSE, TK_FOR, TK_WHILE, TK_DO, TK_RETURN, TK_VOID, TK_MAIN, TK_BREAK, TK_CONTINUE = (
'TK_INT', 'TK_FLOAT', 'TK_CHAR', 'TK_CONST', 'TK_IF', 'TK_ELSE', 'TK_FOR', 'TK_WHILE', 'TK_DO', 'TK_RETURN', 'TK_VOID', 'TK_MAIN', 'TK_BREAK', 'TK_CONTINUE'
)
TK_ID, TK_INT_NUM, TK_FLOAT_NUM, TK_PLUS, TK_MINUS, TK_MUL, TK_DIV, TK_MOD, TK_ASSIGN = (
'TK_ID', 'TK_INT_NUM', 'TK_FLOAT_NUM', 'TK_PLUS', 'TK_MINUS', 'TK_MUL', 'TK_DIV', 'TK_MOD', 'TK_ASSIGN'
)
TK_EQ, TK_NEQ, TK_LT, TK_LE, TK_GT, TK_GE, TK_AND, TK_OR, TK_NOT = (
'TK_EQ', 'TK_NEQ', 'TK_LT', 'TK_LE', 'TK_GT', 'TK_GE', 'TK_AND', 'TK_OR', 'TK_NOT'
)
TK_LPAREN, TK_RPAREN, TK_LBRACE, TK_RBRACE, TK_SEMICOLON, TK_COMMA, TK_EOF = (
'TK_LPAREN', 'TK_RPAREN', 'TK_LBRACE', 'TK_RBRACE', 'TK_SEMICOLON', 'TK_COMMA', 'TK_EOF'
)

KEYWORDS = {
'int': TK_INT, 'float': TK_FLOAT, 'char': TK_CHAR, 'const': TK_CONST, 'if': TK_IF, 'else': TK_ELSE,
'for': TK_FOR, 'while': TK_WHILE, 'do': TK_DO, 'return': TK_RETURN, 'void': TK_VOID, 'main': TK_MAIN,
'break': TK_BREAK, 'continue': TK_CONTINUE,
'整数': TK_INT, '浮点': TK_FLOAT, '字符': TK_CHAR, '常量': TK_CONST, '如果': TK_IF, '否则': TK_ELSE,
'对于': TK_FOR, '当': TK_WHILE, '执行': TK_DO, '返回': TK_RETURN, '空': TK_VOID, '主函数': TK_MAIN,
'跳出': TK_BREAK, '继续': TK_CONTINUE,
}

class Token:
def __init__(self, type_, value, line=0):
self.type, self.value, self.line = type_, value, line
def __repr__(self): return f"Token({self.type}, {repr(self.value)})"

class Lexer:
def __init__(self, source):
self.source = self._normalize(source)
self.tokens = []
self._tokenize()
self.idx = 0
def _normalize(self, s):
repls = {'（': '(', '）': ')', '【': '[', '】': ']', '；': ';', '，': ',', '：': ':', '＋': '+', '－': '-', '＊': '*', '／': '/', '＝': '=', '！': '!', '＜': '<', '＞': '>', '｛': '{', '｝': '}', '\\u3000': ' '}
for k, v in repls.items(): s = s.replace(k, v)
return s
def _tokenize(self):
src, i, line, n = self.source, 0, 1, len(self.source)
while i < n:
ch = src[i]
if ch in ' \\t\\r': i += 1; continue
if ch == '\\n': line += 1; i += 1; continue
if src[i:i+2] == '//':
while i < n and src[i] != '\\n': i += 1
continue
if src[i:i+2] == '/*':
i += 2
while i + 1 < n and src[i:i+2] != '*/':
if src[i] == '\\n': line += 1
i += 1
i += 2; continue
if ch == "'":
j = i + 1
while j < n and src[j] != "'": j += 1
self.tokens.append(Token(TK_INT_NUM, src[i+1:j], line)); i = j + 1; continue
if ch.isdigit() or (ch == '.' and i+1 < n and src[i+1].isdigit()):
j = i
while j < n and src[j].isdigit(): j += 1
if j < n and src[j] == '.' and j+1 < n and src[j+1].isdigit():
j += 1
while j < n and src[j].isdigit(): j += 1
self.tokens.append(Token(TK_FLOAT_NUM, src[i:j], line))
else: self.tokens.append(Token(TK_INT_NUM, src[i:j], line))
i = j; continue
if ch.isalpha() or ch == '_' or ord(ch) > 127:
matched = False
for kw, tk in sorted(KEYWORDS.items(), key=lambda x: –len(x[0])):
if src[i:i+len(kw)] == kw:
self.tokens.append(Token(tk, kw, line)); i += len(kw); matched = True; break
if not matched:
j = i
while j < n and (src[j].isalnum() or src[j] == '_' or ord(src[j]) > 127): j += 1
word = src[i:j]; self.tokens.append(Token(KEYWORDS.get(word, TK_ID), word, line)); i = j
continue
two = src[i:i+2]; ops2 = {'==': TK_EQ, '!=': TK_NEQ, '<=': TK_LE, '>=': TK_GE, '&&': TK_AND, '||': TK_OR}
if two in ops2: self.tokens.append(Token(ops2[two], two, line)); i += 2; continue
ops1 = {'+': TK_PLUS, '-': TK_MINUS, '*': TK_MUL, '/': TK_DIV, '%': TK_MOD, '=': TK_ASSIGN, '<': TK_LT, '>': TK_GT, '!': TK_NOT, '(': TK_LPAREN, ')': TK_RPAREN, '{': TK_LBRACE, '}': TK_RBRACE, ';': TK_SEMICOLON, ',': TK_COMMA}
if ch in ops1: self.tokens.append(Token(ops1[ch], ch, line)); i += 1; continue
i += 1
self.tokens.append(Token(TK_EOF, '', line))
def peek(self, offset=0):
pos = self.idx + offset
return self.tokens[pos] if pos < len(self.tokens) else Token(TK_EOF, '')
def consume(self):
t = self.peek(); self.idx += 1; return t
def expect(self, type_):
t = self.consume()
if t.type != type_: raise SyntaxError(f"Line {t.line}: Expected {type_}, got {t.type}({t.value})")
return t
def match(self, type_):
if self.peek().type == type_: return self.consume()
return None

# ==================== 四元式生成器 (Generator) ====================

class Quaternion:
def __init__(self, op, arg1, arg2, result):
self.op, self.arg1, self.arg2, self.result = op, arg1, arg2, result
def __repr__(self):
res = f"{self.result}" if isinstance(self.result, int) else f"'{self.result}'"
return f"('{self.op}', '{self.arg1}', '{self.arg2}', {res})"

class CodeGen:
def __init__(self):
self.quads = []
self.temp_count = 0
self.break_stack = []
self.cont_patches = [] # 用于回填 continue 的跳转列表
def new_temp(self): self.temp_count += 1; return f't{self.temp_count}'
def emit(self, op, arg1, arg2, result):
self.quads.append(Quaternion(op, arg1, arg2, result))
return len(self.quads) – 1
def backpatch(self, lst, target):
for idx in lst: self.quads[idx].result = int(target)
def output(self):
return '\\n'.join(f"{i}: {q}" for i, q in enumerate(self.quads))

# ==================== 解析器 (Parser) ====================

class Parser:
def __init__(self, lexer, gen):
self.lexer, self.gen = lexer, gen
def parse(self):
while self.lexer.peek().type != TK_EOF:
if self.lexer.peek().type in (TK_INT, TK_FLOAT, TK_CHAR, TK_VOID, TK_CONST):
self.parse_global()
elif self.lexer.peek().type == TK_MAIN:
self.parse_main()
elif self.lexer.peek().type == TK_ID:
self.parse_global_assignment()
else:
self.lexer.consume()
def parse_type(self):
const = self.lexer.match(TK_CONST)
t = self.lexer.consume().value
return ('const_' if const else '') + t
def parse_global(self):
t = self.parse_type()
if self.lexer.peek().type == TK_MAIN:
self.parse_main()
return
name = self.lexer.expect(TK_ID).value
if self.lexer.peek().type == TK_LPAREN:
self.parse_func(t, name)
else:
self.parse_var_decl_rest(t, name)
def parse_global_assignment(self):
name = self.lexer.consume().value
if self.lexer.match(TK_ASSIGN):
v = self.parse_expr()
self.gen.emit('=', v, '_', name)
self.lexer.match(TK_SEMICOLON)
def parse_main(self):
if self.lexer.peek().type in (TK_INT, TK_VOID):
self.lexer.consume()
if self.lexer.peek().type == TK_MAIN:
self.lexer.consume()
self.lexer.expect(TK_LPAREN)
self.lexer.expect(TK_RPAREN)
self.gen.emit('main', '_', '_', '_')
self.lexer.expect(TK_LBRACE)
self.parse_block()
self.lexer.expect(TK_RBRACE)
self.gen.emit('sys', '_', '_', '_')
def parse_func(self, t, name):
self.lexer.expect(TK_LPAREN)
if self.lexer.peek().type != TK_RPAREN:
while True:
self.parse_type()
self.lexer.expect(TK_ID)
if not self.lexer.match(TK_COMMA):
break
self.lexer.expect(TK_RPAREN)
if self.lexer.match(TK_SEMICOLON):
return
self.gen.emit(name, '_', '_', '_')
self.lexer.expect(TK_LBRACE)
self.parse_block()
self.lexer.expect(TK_RBRACE)
if not self.gen.quads or self.gen.quads[–1].op != 'ret':
self.gen.emit('ret', '_', '_', '_')
def parse_block(self):
while self.lexer.peek().type not in (TK_RBRACE, TK_EOF):
self.parse_stmt()
def parse_stmt(self):
tok = self.lexer.peek()
if tok.type in (TK_INT, TK_FLOAT, TK_CHAR, TK_CONST):
self.parse_decl()
elif tok.type == TK_IF:
self.parse_if()
elif tok.type == TK_FOR:
self.parse_for()
elif tok.type == TK_WHILE:
self.parse_while()
elif tok.type == TK_DO:
self.parse_do()
elif tok.type == TK_RETURN:
self.parse_ret()
elif tok.type == TK_BREAK:
self.lexer.consume()
self.gen.break_stack[–1].append(self.gen.emit('J', '_', '_', '?'))
self.lexer.match(TK_SEMICOLON)
elif tok.type == TK_CONTINUE:
self.lexer.consume()
idx = self.gen.emit('J', '_', '_', '?')
self.gen.cont_patches[–1].append(idx)
self.lexer.match(TK_SEMICOLON)
elif tok.type == TK_LBRACE:
self.lexer.consume()
self.parse_block()
self.lexer.expect(TK_RBRACE)
elif tok.type == TK_ID:
self.parse_expr()
self.lexer.match(TK_SEMICOLON)
else:
self.lexer.consume()
def parse_decl(self):
t = self.parse_type()
while True:
name = self.lexer.expect(TK_ID).value
if self.lexer.match(TK_ASSIGN):
v = self.parse_expr()
self.gen.emit('=', v, '_', name)
if not self.lexer.match(TK_COMMA):
break
self.lexer.match(TK_SEMICOLON)
def parse_var_decl_rest(self, t, name):
if self.lexer.match(TK_ASSIGN):
v = self.parse_expr()
self.gen.emit('=', v, '_', name)
while self.lexer.match(TK_COMMA):
n = self.lexer.expect(TK_ID).value
if self.lexer.match(TK_ASSIGN):
v = self.parse_expr()
self.gen.emit('=', v, '_', n)
self.lexer.match(TK_SEMICOLON)
def parse_expr(self):
if self.lexer.peek().type == TK_ID and self.lexer.peek(1).type == TK_ASSIGN:
name = self.lexer.consume().value
self.lexer.consume()
v = self.parse_expr()
self.gen.emit('=', v, '_', name)
return name
return self.parse_or()
def parse_or(self):
l = self.parse_and()
while self.lexer.match(TK_OR):
r = self.parse_and()
t = self.gen.new_temp()
self.gen.emit('||', l, r, t)
l = t
return l
def parse_and(self):
l = self.parse_rel()
while self.lexer.match(TK_AND):
r = self.parse_rel()
t = self.gen.new_temp()
self.gen.emit('&&', l, r, t)
l = t
return l
def parse_rel(self):
l = self.parse_add()
rops = {TK_EQ: '==', TK_NEQ: '!=', TK_LT: '<', TK_LE: '<=', TK_GT: '>', TK_GE: '>='}
while self.lexer.peek().type in rops:
op = rops[self.lexer.consume().type]
r = self.parse_add()
t = self.gen.new_temp()
self.gen.emit(op, l, r, t)
l = t
return l
def parse_add(self):
l = self.parse_mul()
while self.lexer.peek().type in (TK_PLUS, TK_MINUS):
op = self.lexer.consume().value
r = self.parse_mul()
t = self.gen.new_temp()
self.gen.emit(op, l, r, t)
l = t
return l
def parse_mul(self):
l = self.parse_unary()
while self.lexer.peek().type in (TK_MUL, TK_DIV, TK_MOD):
op = self.lexer.consume().value
r = self.parse_unary()
t = self.gen.new_temp()
self.gen.emit(op, l, r, t)
l = t
return l
def parse_unary(self):
if self.lexer.match(TK_MINUS):
v = self.parse_unary()
t = self.gen.new_temp()
self.gen.emit('neg', v, '_', t)
return t
if self.lexer.match(TK_NOT):
v = self.parse_unary()
t = self.gen.new_temp()
self.gen.emit('!', v, '_', t)
return t
self.lexer.match(TK_PLUS)
return self.parse_primary()
def parse_primary(self):
t = self.lexer.consume()
if t.type in (TK_INT_NUM, TK_FLOAT_NUM):
return t.value
if t.type == TK_LPAREN:
v = self.parse_expr()
self.lexer.expect(TK_RPAREN)
return v
if t.type == TK_ID:
if self.lexer.peek().type == TK_LPAREN:
return self.parse_call(t.value)
return t.value
return '_'
def parse_call(self, name):
self.lexer.expect(TK_LPAREN)
args = []
if self.lexer.peek().type != TK_RPAREN:
args.append(self.parse_expr())
while self.lexer.match(TK_COMMA):
args.append(self.parse_expr())
self.lexer.expect(TK_RPAREN)
for a in args:
self.gen.emit('para', a, '_', '_')
t = self.gen.new_temp()
self.gen.emit('call', name, '_', t)
return t
def parse_if(self):
self.lexer.expect(TK_IF)
self.lexer.expect(TK_LPAREN)
tl, fl = self.parse_cond()
self.lexer.expect(TK_RPAREN)
self.gen.backpatch(tl, len(self.gen.quads))
self.parse_stmt_or_blk()
if self.lexer.match(TK_ELSE):
j = self.gen.emit('J', '_', '_', '?')
self.gen.backpatch(fl, len(self.gen.quads))
self.parse_stmt_or_blk()
self.gen.backpatch([j], len(self.gen.quads))
else:
self.gen.backpatch(fl, len(self.gen.quads))
def parse_while(self):
self.lexer.expect(TK_WHILE)
start = len(self.gen.quads)
self.lexer.expect(TK_LPAREN)
tl, fl = self.parse_cond()
self.lexer.expect(TK_RPAREN)
self.gen.cont_patches.append([])
self.gen.break_stack.append([])
self.gen.backpatch(tl, len(self.gen.quads))
self.parse_stmt_or_blk()
self.gen.emit('J', '_', '_', start)
self.gen.backpatch(fl + self.gen.break_stack.pop(), len(self.gen.quads))
cont_quads = self.gen.cont_patches.pop()
self.gen.backpatch(cont_quads, start)
def parse_do(self):
self.lexer.expect(TK_DO)
start = len(self.gen.quads)
self.gen.cont_patches.append([])
self.gen.break_stack.append([])
self.parse_stmt_or_blk()
cstart = len(self.gen.quads)
self.lexer.expect(TK_WHILE)
self.lexer.expect(TK_LPAREN)
tl, fl = self.parse_cond()
self.lexer.expect(TK_RPAREN)
self.lexer.match(TK_SEMICOLON)
self.gen.backpatch(tl, start)
self.gen.backpatch(fl + self.gen.break_stack.pop(), len(self.gen.quads))
cont_quads = self.gen.cont_patches.pop()
self.gen.backpatch(cont_quads, cstart)
def parse_for(self):
self.lexer.expect(TK_FOR)
self.lexer.expect(TK_LPAREN)
if self.lexer.peek().type != TK_SEMICOLON:
if self.lexer.peek().type in (TK_INT, TK_FLOAT, TK_CHAR, TK_CONST):
self.parse_decl()
else:
self.parse_expr()
self.lexer.match(TK_SEMICOLON)
else:
self.lexer.consume()
cstart = len(self.gen.quads)
tl, fl = [], []
if self.lexer.peek().type != TK_SEMICOLON:
tl, fl = self.parse_cond()
self.lexer.match(TK_SEMICOLON)
ustart = len(self.gen.quads)
if self.lexer.peek().type != TK_RPAREN:
self.parse_expr()
self.lexer.expect(TK_RPAREN)
self.gen.emit('J', '_', '_', cstart)
self.gen.cont_patches.append([])
self.gen.break_stack.append([])
bstart = len(self.gen.quads)
self.gen.backpatch(tl, bstart)
self.parse_stmt_or_blk()
self.gen.emit('J', '_', '_', ustart)
self.gen.backpatch(fl + self.gen.break_stack.pop(), len(self.gen.quads))
cont_quads = self.gen.cont_patches.pop()
self.gen.backpatch(cont_quads, ustart)
def parse_ret(self):
self.lexer.expect(TK_RETURN)
v = '_'
if self.lexer.peek().type not in (TK_SEMICOLON, TK_RBRACE, TK_EOF):
v = self.parse_expr()
self.gen.emit('ret', '_', '_', v)
self.lexer.match(TK_SEMICOLON)
def parse_stmt_or_blk(self):
if self.lexer.peek().type == TK_LBRACE:
self.lexer.consume()
self.parse_block()
self.lexer.expect(TK_RBRACE)
else:
self.parse_stmt()
def parse_cond(self):
return self._cond_or()
def _cond_or(self):
tl, fl = self._cond_and()
while self.lexer.match(TK_OR):
for f_idx in fl:
self.gen.quads[f_idx].result = len(self.gen.quads)
rt, rf = self._cond_and()
tl += rt
fl = rf
return tl, fl
def _cond_and(self):
tl, fl = self._cond_not()
while self.lexer.match(TK_AND):
for t_idx in tl:
self.gen.quads[t_idx].result = len(self.gen.quads)
rt, rf = self._cond_not()
fl += rf
tl = rt
return tl, fl
def _cond_not(self):
if self.lexer.match(TK_NOT):
tl, fl = self._cond_atom()
return fl, tl
return self._cond_atom()
def _cond_atom(self):
if self.lexer.peek().type == TK_LPAREN:
self.lexer.consume()
tl, fl = self._cond_or()
self.lexer.expect(TK_RPAREN)
return tl, fl
l = self.parse_add()
rops = {TK_EQ: 'J==', TK_NEQ: 'J!=', TK_LT: 'J<', TK_LE: 'J<=', TK_GT: 'J>', TK_GE: 'J>='}
if self.lexer.peek().type in rops:
op = rops[self.lexer.consume().type]
r = self.parse_add()
jt = self.gen.emit(op, l, r, '?')
jf = self.gen.emit('J', '_', '_', '?')
return [jt], [jf]
jt = self.gen.emit('J!=', l, '0', '?')
jf = self.gen.emit('J', '_', '_', '?')
return [jt], [jf]

if __name__ == '__main__':
try:
with open('input.txt', 'r', encoding='utf-8') as f:
source = f.read()
lexer = Lexer(source)
gen = CodeGen()
parser = Parser(lexer, gen)
parser.parse()
with open('output.txt', 'w', encoding='utf-8') as f:
f.write(gen.output())
except Exception:
sys.exit(1)

7 实验报告（电子版Word文档）

1.编译原理实验报告【语义分析和中间代码生成实验】

编译原理实验报告【语义分析和中间代码生成实验】

2.解压包密码

8619dlc11

8 实验源代码（python语言）

1.编译原理实验源代码【语义分析和中间代码生成实验】

编译原理实验源代码【语义分析和中间代码生成实验】

2.解压包密码

8619dlc22