基于Python实现一个C语言的编译器【100010711】

# 实现一个类 C 语言的编译器 # 一、课程设计重述 ## 1.1 目的 掌握使用高级程序语言实现一个一遍完成的、简单语言的编译器的方法；掌握简单的词法分析器、语法分析器、符号表管理、中间代码生成以及目标代码 生成的实现方法；掌握将生成代码写入文件的技术。 ## 1.2 要求 使用高级程序语言作为实现语言，实现一个类 C 语言的编译器。编码实现编译器的组成部分。 要求的类 C 编译器是个一遍的编译程序，词法分析程序作为子程序，需要的时候被语法分析程序调用; 使用语法制导的翻译技术，在语法分析的同时生成中间代码，并保存到文件中。 - 要求输入类 C 语言源程序，输出中间代码表示的程序; - 要求输入类 C 语言源程序，输出目标代码(可汇编执行)的程序。 - 实现过程、函数调用的代码编译 # 二、需求分析 ## 2.1 任务输入及其范围 - 输入上限：一段带过程调用的代码段。 - 输入下限：符合语法规则的语句。 - 一段带过程调用的代码段实例如下： ## 2.2 输出形式 ### 2.2.1 输出中间代码表示的程序 示例如下：  ### 2.2.2 输出目标代码(可汇编执行)的程序 示例如下：  ## 2.3 程序功能 - 类 C 编译器是个一遍的编译程序，词法分析程序作为子程序，需要的时候被语法分析程序调用。 - 使用语法制导的翻译技术，在语法分析的同时生成中间代码，并保存到文件中。 - 要求输入类 C 语言源程序，输出中间代码表示的程序。 - 要求输入类 C 语言源程序，输出目标代码(可汇编执行)的程序。 - 实现过程、函数调用的代码编译。 ## 2.4 测试数据 ### 2.4.1 变量重定义 ```c++ int a;int a; ``` ### 2.4.2 使用未声明的变量 ```c++ int main() { = 1; } ``` ### 2.4.3 使用未定义的函数 ```c++ int main() { int a; = demo(1); return ; } ``` ### 2.4.4 变量赋值时类型错误 ```c++ int main() { int a; a = 1; void b; b = a; return 1; } ``` ### 2.4.5 函数形参和实参不匹配 ```c++ int demo() { return 1; } int main() { int c; = demo(1); return 1; } ``` ### 2.4.6 寄存器是否正常选用 ```c++ int main(void) { int a; int b; int c; int d; int e; int f; int g; int h; int i; int j; int k; int l; int m; int n; int o; int p; int q; int r; int s; int t; int u; a=0; b=1; c=2; d=3; e=4; f=5; g=6; h=7; i=8; j=9; k=10; l=11; m=12; n=13; o=14; p=15; q=16; r=1 7; s=18; t = 19; u = 20; a=0; b=1; c=2; d=3; e=4; f=5; g=6; h=7; i=8; j=9; k=10; l=11; m=12; n=13; o=14; p=15; q=16; r=1 7; s=18; t=19; return 1; } ``` # 三、概要设计 ## 3.1 任务的分解 & 数据类型的定义 注：根据任务设计书，这两点是分来的，但是如果是合并在一起说明更具连贯性。特此说明。 一般来说，一个编译器主要有五个步骤：词法分析语法分析语义分析 中间代码生成目标代码生成 根据要求，一遍实现的编译器，LR(1)是适用的。在语法分析的过程中，语义分析、中间代码生成也在同步进行。故这三个部分可以合并。 同时，使用面向对象的方法，将每个阶段看作一个对象，对该部分的操作就是该对象的方法。这大大方便了程序的开发和维护。 另外还有 GUI。这部分和 PyQt 相关。 而对于每一部分来说，又需要不同的数据结构来维护，接下来将详细说明。 ### 3.1.1 语法文件读取与解析，词法分析 – CFG 类 设置 CFG 类，做两件事： 读取语法文件，进行解析，获取起始符号、终结符、变元、产生式，设置广义起始符，生成 LR1 需要的加点产生式，也就是项目 item 对输入代码使用正则识别，生成 token 流 | 成员名称及类型 | 描述 | | --------------------- | -------------- | | TerminalSymbols = [] | 终结符 | | StartSymbol | 广义起始符 | | OriginStartSymbol | 原语法的起始符 | | NonTerminalSymbols=[] | 变元 | | Reserved={} | 保留字 | | Items=[] | 加点的项目 | | 方法的名称 | 功能描述 | | -------------- | ---------------------------- | | loadGrammer | 读取文法 | | calFirstSet | 计算 First 集 | | calNTFirstSet | 计算非终结符的 First 集 | | getDotItems | 将 item 加点 | | generateTokens | 生成 tokens 流 | | scanLine | 扫描代码的每一行，获取 token | 模块设计思路与分析说明： 这一部分是对于语法的处理。我们知道，LR(1)语法中的项目（Item）是带点的，读入产生式后，getDotItems 给所有产生式的所有位置加点。 对于单个所有符号（包括终结符和非终结符）都有 First 集。在之后的语法分析步骤中，需要计算一个字符串的 First 集，只需要根据规则调用单个字符的 First 集计算即可。“cal”指的是 calculate，计算，calFirstSet 将单个字符的 First 集结果保存供后续分析使用。 ### 3.1.2 构建项目集规范族 – ItemSetSpecificationFamily 类 模块设计思路与分析说明： 核心函数是 getLR1Closure，GO 和 buildFamily，三者通过 LR1 的算法构建项目集族的 DFA。 ItemSetSpecificationFamily 中的属性和方法描述如下: | 方法的名称 | 功能描述 | | ------------- | ------------------------------------- | | getLeftNT | 获取某个非终结符的产生式 | | getLR1Closure | 根据 LR1 的方法算 Closure 集 | | GO | 状态转移函数 | | edge2str | 将状态转移的边转为 string 方便比较 | | getFirstSet | 获取字符串的 First 集 | | extendItem | 根据 LR1 文法，将 item 进行终结符拓展 | | buildFamily | 通过算法构建项目集族 | 数据成员描述如下： | itemSets = [] | 项目集，也就是 DFA 的状态 | | ------------------------- | --------------------------- | | prods=[] | 项目集规范族的 DFA 的产生式 | | 其它来自 CFG 类的语法数据 | | ### 3.1.3 语法、语义、中间代码生成 – SyntacticAnalyzer 类 模块设计思路与分析说明： 核心函数是 getTables，即通过 ItemSetSpecificationFamily 中构建的 DFA 生成 ACTION 和 GOTO 表。通过这两张表就能对任意字符串给出是否符合 LR1 文法的判断。 核心函数是 isRecognizable，其中又有 semanticAnalyze 作语义分析。 SyntacticAnalyzer 中的属性和方法描述如下: | 方法的名称 | 功能描述 | | --------------- | --------------------------------------- | | item2prodIdx | 给一个 item，返回该项目对应的产生式编号 | | getTables | 计算 ACTION 和 GOTO 数组 | | isRecognizable | 判断一个字符串是否能被识别 |