第一章 概述
1.1 设计目的
编译原理课程设计通过要求学生完成设计一个简单的程序语言的编译系统，旨在加深对程序语言结构和机器处理方式的理解，初步掌握高级语言到机器指令转换的基本方法，提高工程设计的基本技能及分析、解决实际问题的能力，为毕业设计和以后的工程实践打下良好的基础。学生通过本次设计,可巩固和加深理解编译程序工作过程，提高综合运用课程所学知识的能力，提升查阅手册及文献资料的能力，能够就复杂工程问题与同行进行有效沟通和交流，能就计算机专业问题，以口头、文稿、图表等方式，清晰地讲解系统实现的主要思路，准确表达自己的观点。
1.2 设计内容
设计语言子集编译器的实现。包括设计一个文法，实现词法分析、语法分析、语义分析及中间代码生成、优化和目标代码生成等各阶段的功能。
编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。主要包括词法分析、语法分析、语义分析及中间代码生成、目标代码优化和目标代码的生成。总体结构如图1-1所示。
图1-1 总体结构图
(1)词法分析是编译过程中的一个基本步骤，主要负责处理源代码文本，将其分解为一系列有意义的单元，称为“标记”（tokens）。这些标记包括关键字、标识符、整数、运算符和界符。主要任务是逐字符读取代码样例，识别出单独的标记；将字符序列分类为不同类型的标记，例如识别一个单词是否是关键字、整数、或者是一个变量名。特点是能够简化语法分析，使得语法分析的工作更加简单和直接。
(2)语法分析是编译过程中的一个关键步骤，紧随词法分析之后。在这个阶段，编译器接收词法分析输出的标记（tokens）流，并尝试构造这些标记的结构化表示，即语法树。这个过程涉及检查标记流是否符合特定编程语言的语法规则。语法分析的主要任务是构建语法树，根据源代码中标记的排列和编程语言的语法规则，构建一棵语法树，其中每个节点代表一个语言结构（如表达式、语句等）；验证代码样例语句是否遵循编程语言的语法规则，不符合规则的代码将被标记为语法错误；在遇到语法错误时提供错误信息，并尝试从错误中恢复，继续分析后续代码。方法主要包括自顶向下分析和自底向上分析。自顶向下分析是从最高层的语法结构开始分析，逐步展开到更小的结构。本设计使用的递归下降分析就是一种常见的自顶向下分析方法。自底向上分析则是从最基本的语法单位开始构建，逐步合并成更高级的结构。
(3)语义分析是编译过程中的一个关键步骤，它紧随语法分析之后。语义分析的主要任务是确保源代码中的语句在语法结构上正确之后，还要符合语言定义的语义规则，即确保程序的含义是合法的和逻辑上一致的。主要任务是确保操作符和操作数的类型是兼容的，例如不能将整数类型赋值给字符串类型的变量。确保所有使用的变量和函数都已被声明，并且它们的使用与声明时的类型和形式相匹配。检查变量和函数的作用域，确保它们在合适的范围内被访问。
(4)目标代码优化是编译过程中的一个重要阶段，它发生在语义分析之后。在这个阶段，编译程序尝试改善中间代码，使生成的目标代码（例如机器码或字节码）更高效、占用更少的资源，同时保持程序的语义不变。本设计使用的优化是DAG优化。
(5)目标代码生成是编译过程中的最后一步。主要任务是将经过前面阶段（词法分析、语法分析、语义分析和代码优化）处理的中间表示（如抽象语法树或优化后的中间代码）转换为目标代码。这个目标代码可以是机器码、字节码或者其他形式的低级代码。本设计目标代码的生成是汇编语言语句。
第二章 需求分析
2.1 所实现语言功能概述
本设计主要分为五个阶段：词法分析、语法分析、语义分析、DAG优化和目标代码生成。每个阶段在功能上是串联的，它一方面是从上一个阶段获取得到的分析结果来进行分析，另一方面将分析结果传递给下一个阶段。只能按照从前到后顺序执行，否则程序就会报错。这五个阶段分为编译器的前端，中间代码以及后端。通过该程序可以达到实现一个简单的编译程序，能够对简单的程序设计语言进行编译。
实现了int型变量定义、四则运算、函数调用、if条件判断、while循环判断、注释功能(仅限’//’)、比较运算、逻辑运算符、return语句、赋值语句等语言功能。
2.2 所实现语言的文法
1.Program → ‘int’ ‘main’ ‘(‘ ‘)’ ‘{‘ Declarations Statements ‘}’
2.Declarations → Declaration Declarations | ε
3.Declaration → ‘int’ IdentifierList ‘;’
4.IdentifierList → Identifier ‘,’ IdentifierList | Identifier
5.Statements → Statement Statements | ε
6.Statement → Assignment ‘;’ | WhileStatement | IfStatement
7.Assignment → Identifier ‘=’ Expression
8.WhileStatement → ‘while’ ‘(‘ Condition ‘)’ ‘{‘ Statements ‘}’
9.IfStatement → ‘if’ ‘(‘ Condition ‘)’ ‘{‘ Statements ‘}’ ElsePart
10.ElsePart → ‘else’ ‘{‘ Statements ‘}’ | ε
11.Condition → Identifier RelOp Identifier
12.Expression → Identifier ‘+’ Identifier | Identifier | Number
13.Identifier → [a-zA-Z_][a-zA-Z0-9_]*
14.Number → [0-9]+
15.RelOp → ‘<‘ | ‘>’ | ‘==’ | ‘!=’ | ‘<=’ | ‘>=’
2.3 设计目标和实现的功能
设计目标：
1.实现一个功能完整的简易编译器。主要包括词法分析、语法分析、语义分析、代码优化和目标代码生成等基本功能。
2.添加一些对编译器使用有帮助的功能，例如文件加载、预处理和结果保存等功能。
3.编写一个简易的GUI界面。使得用户操作起来更加方便。
4.进行模块化设计。将各个编译功能组件独立模块化，以便单独测试和修改。
实现的功能：
本设计实现的是一个简单的编译器模拟器，实现的具体功能包括：
1.文件加载：该功能主要用于获取输入代码样例，当使用该功能时，就不需要在输入框中输入代码。提高了效率，节省了时间。
2.去除注释：该功能用于清除代码中的注释，只保留实际的代码部分。但是只能处理注释格式为’//’的注释。
3.词法分析：该功能将代码分解为基本的词法单元（如关键字、标识符、整数、界符和运算符），并对这些词法单元进行分类。
4.语法分析：在词法分析的基础上，检查代码遵循特定的语法规则。确保代码结构上的正确性。该功能使用递归下降的分析方法，属于自顶向下的分析方法。
5.语义分析：该功能将生成中间代码。同时，它还会处理一些语义层面的问题，例如变量的定义和使用。主要使用拉链回填技术来生成中间代码。
6.DAG优化：该功能使用DAG对代码进行优化，以提高执行效率和减少资源消耗。
7.目标代码生成：该功能将经过优化的中间代码转换成目标机器能理解和执行的代码。这是编译过程的最终阶段。转换成的目标代码为汇编语言语句。
8.文件保存：提供了保存结果到文件的功能，实现数据持久化存储，方便用户操作。
9.GUI界面：整个编译程序模拟器通过一个图形用户界面呈现，包括输入代码文本框、按钮进行各阶段的编译处理，以及展示处理结果的文本框。
10.退出功能：提供了直接关闭GUI界面和程序的功能，方便用户操作。
第三章 总体设计
3.1 编译程序功能描述
本文主要分为五个阶段：词法分析、语法分析、语义分析、DAG优化和目标代码生成。每个阶段在功能上是串联的，它一方面是从上一个阶段获取分析得到的结果来进行分析，另一方面将结果传递给下一个阶段。只能按照从前到后的顺序执行，否则程序就会报错。由编译程序的五个阶段就对应了编译系统的结构，这五个对应阶段分为编译器的前端，中间代码以及后端。通过该程序可以实现一个简单的编译程序，能够对指定的程序设计语言进行编译。
3.2 编译程序总体构造
编译程序的界面设计主要包括为四部分。最上方为编译程序的标题显示，左半部分显示输入的代码样例，右半部分显示输出的结果，中间区域部分包括加载文件、预处理、词法分析、语法分析、语义分析、DAG优化、目标代码生成、结果保存和程序退出9个按钮。如图3-1所示：
图3-1 编译程序界面设计图
总体构造如图3-2所示。
图3-2 总体构造图
第四章 详细设计
4.1 文件加载方法
文件加载功能是通过一个按钮触发的，允许用户从他们的文件系统中选择并加载一个文本文件。详细设计描述如下：
GUI设计：
按钮创建：使用Tkinter创建一个按钮，标记为“加载文件”。
按钮功能绑定：将按钮的点击事件绑定到一个函数上，当点击按钮后，就会调用该函数。
功能实现：
当用户点击“加载文件”按钮时，会调用函数并执行下述操作。
1.文件选择对话框：调用函数弹出一个文件选择对话框，允许用户选择一个文件。这个对话框可以过滤文件类型，例如在本设计中只显示文本文件。
2.文件读取：如果用户选择了文件（即文件路径非空），则使用open函数以读取模式打开该文件。
3.内容显示：读取文件内容，并将其插入到主界面上的左侧文本框中，用于后续的编译处理。
用户交互流程：
1.点击按钮：用户点击“加载文件”按钮。
2.选择文件：用户在弹出的文件选择对话框中浏览并选择一个文本文件。
3.显示内容：应用程序读取所选文件的内容，并在GUI的文本框中显示这些内容。
错误处理：
1.如果用户取消了文件选择或未选择任何文件，程序不会执行读取操作，也不会更改文本框的现有内容。
文件加载功能使得用户可以方便地将外部代码加载到编译程序中，进行词法分析、语法分析等处理。这样提高了程序的实用性和用户体验。
4.2 预处理方法
预处理主要负责处理输入的源代码，包括去除源代码中的注释，并对源代码进行初步的格式化处理。详细设计描述如下：
功能描述：
1.去除注释：将源代码中的所有注释删除。在本设计中，它处理的是单行注释（以’//’开头的注释）。
2.格式化处理：包括去除多余的空白字符、调整换行等，以保证代码的清晰和一致性。
实现步骤：
1.分割源代码：将输入的源代码按行分割，以便逐行检查和处理。
2.检查并去除注释：逐行检查代码，如果发现行内有’//’，则只保留该行’//’ 之前的部分。
3.重组代码：将处理过的各行重新组合成一个完整的字符串。
4.更新GUI显示：将处理后的代码显示在GUI的文本框中，供用户查看和后续操作。
GUI交互：
按钮触发：用户通过点击“预处理”按钮来启动预处理功能。
文本框更新：预处理后的代码会展示在GUI的文本框中。
错误处理:
如果输入为空或不包含任何有效代码，预处理将什么也不做。
预处理功能不仅清除了不必要的注释，还可以通过格式化使得代码更加规范，为后续的词法分析、语法分析等步骤打下良好基础。
4.3 词法分析方法
词法分析是编译器过程的一部分，负责将输入的源代码文本拆分为一系列的令牌（tokens）。这些令牌是构成源代码的基本元素，如关键字、标识符、运算符等。在本编译程序中，词法分析由tokenize和analyze_tokens函数完成。
1.tokenize函数：此函数用于将输入的文本字符串拆分为一系列令牌。它遍历输入字符串的每个字符，并根据字符的类型（字母、数字、运算符、界符等）来组合或分离令牌。对于字母字符，它会组合连续的字母以形成标识符或关键字。对于数字字符，它会组合连续的数字形成数字令牌。对于运算符和界符（如`+`, `-`, `*`, `/`, `;`, `{`, `}`等），它会将它们作为单独的令牌。
2.analyze_tokens函数：此函数接收由tokenize函数生成的令牌列表，并对每个令牌进行进一步的分类。检查每个令牌，确定它是关键字、标识符、整数、运算符还是界符，并输出的相应分类。如果令牌是数字，它被分类为整数。如果令牌是预定义的关键字之一（如int，if，else等），它被分类为关键字。如果令牌是字母组成的，它被分类为标识符。其他的令牌被视为运算符或界符。
这两个函数合在一起，实现了源代码到令牌序列的转换，为后续的语法分析和语义分析等步骤奠定了基础。词法分析是编译过程中非常重要的一步，因为它将源代码从字符序列转换为更易于处理的令牌序列。
单词分类表如表4-1所示。
表4-1 单词分析表
| 单词名称 | 种类编码 | 单词名称 | 种类编码 |
| int | 1 | long | 18 |
| auto | 2 | register | 19 |
| break | 3 | return | 20 |
| case | 4 | short | 21 |
| char | 5 | signed | 22 |
| const | 6 | sizeof | 23 |
| continue | 7 | static | 24 |
| default | 8 | struct | 25 |
| main | 9 | switch | 26 |
| do | 10 | typedef | 27 |
| double | 11 | union | 28 |
| else | 12 | unsigned | 29 |
| extern | 13 | void | 30 |
| float | 14 | volatile | 31 |
| for | 15 | while | 32 |
| goto | 16 | 标识符 | 33 |
| if | 17 | 常数 | 34 |
符号分类表如表4-2所示。
表4-2 符号分析表
| 符号名称 | 种类编码 | 符号名称 | 种类编码 |
| + | 35 | ( | 47 |
| – | 36 | ) | 48 |
| * | 37 | ^ | 49 |
| / | 38 | , | 50 |
| < | 39 | # | 51 |
| <= | 40 | % | 52 |
| > | 41 | [ | 53 |
| >= | 42 | ] | 54 |
| = | 43 | { | 55 |
| == | 44 | } | 56 |
| <> | 45 | . | 57 |
| ; | 46 | // | 58 |
4.4 语法分析方法
语法分析是编译过程中的一个重要阶段，它负责根据给定的语法规则检查源代码的结构。这一阶段通过一系列函数来实现，每个函数都对应特定的语法规则。以下是对这些函数详细设计：
1.’S’()函数
功能：`S`()函数作为语法分析的入口点，用于解析程序的最外层结构。专门用于检查一个形式为`int main() { … }`的主函数结构。
实现：函数首先检查是否存在`int`关键字，紧接着是`main`，然后是括号`(`和`)`，最后是大括号`{`和`}`。在这些元素之间，它会调用`G`函数来处理`{`和`}`之间的代码。
2.’I’()函数
功能：用于解析 if 语句，包括可选的 else 分支。
实现：首先验证 if 和括号 ()，然后调用 G() 来处理 if 语句块内的语句。如果存在 else 关键字，同样会调用 G() 来处理 else 语句块。
3.’W’()函数
功能：用于解析 while 循环。
实现：检查 while 关键字、循环条件(括号内的表达式)和循环体(大括号内的语句)。循环条件的解析是通过调用 parse_condition() 实现的。
4.’G’()函数
功能：用于递归地处理程序中的多个语句。
实现：它根据当前令牌的类型调用相应的函数（如`D`、`A`或`R`）来处理
特定类型的语句，并在遇到`}`时停止递归。
5.’D’()函数
功能：用于解析变量声明，例如`int x, y;`。
实现：检查`int`关键字，然后是一个或多个用逗号分隔的标识符，最后以分号结束。
6.’A’()函数
功能：用于解析赋值语句。
实现：检查一个标识符，后面跟着`=`运算符和一个表达式（通过调用`E`函数解析），最后以分号结束。
7.’E’()函数
功能：用于解析表达式，特别是包含算术运算的表达式。
实现：处理数字或标识符，后面可能跟着一个算术运算符（如`+`, `-`, `*`, `/`）和另一个操作数。如果存在运算符和第二个操作数，它会生成一个临时变量来存储运算结果。
8.’R’()函数
功能：用于解析`return`语句。
实现：检查`return`关键字，后面跟着一个数字，最后以分号结束。
9.错误处理
在这些函数中，如果当前令牌与预期的语法结构不匹配的话，就会抛出异常，指示语法错误。是一种常见的错误处理方式，用于在解析过程中立即报告错误。
预测分析表如表4-3所示。其中数字1-14代表着本设计所设计的语言文法。
表4-3 预测分析表
| 非终结符 | int | { | } | identifier | , | while | if | else | number | + |
| Program | 1 | |||||||||
| Declarations | 2 | 2 | 2 | |||||||
| Declaration | 3 | |||||||||
| IdentifierList | 4 | 4 | ||||||||
| Statements | 5 | 5 | 5 | 5 | 5 | 5 | ||||
| Statement | 6 | 6 | 6 | |||||||
| Assignment | 7 | |||||||||
| WhileStatement | 8 | |||||||||
| IfStatement | 9 | |||||||||
| Condition | 11 | 10 | ||||||||
| ElsePart | 12 | |||||||||
| Expression | 13 | 12 | 12 | |||||||
| Identifier | ||||||||||
| Number | 14 |
4.5 语义分析及中间代码生成方法
语义分析是对源代码进行深入理解和检查的阶段，不仅确保代码遵循语法规则，还要确保它在逻辑上是有意义的。在本设计中主要通过semantic_analysis函数实现，其详细分析如下：
semantic_analysis函数
1.中间代码处理：函数从全局变量intermediate_code中获取中间代码。这些代码通常是由语法分析阶段生成的，表示源代码中更复杂结构的简化形式。
2.遍历中间代码：函数遍历每一条中间代码。这些代码可能是赋值语句，也可能是算术表达式。
3.解析赋值语句：通过调用parse_assignment函数，解析每个赋值语句。将赋值语句分解为更简单的操作，如单独的算术运算和赋值。
4.生成三地址代码：对于每个解析出的操作，函数生成一个对应的三地址代码。这种代码形式通常包含一个操作符和两个操作数，以及一个结果变量。例如，对于表达式c=a+b;可能会生成类似于temp1 = a+b; c = temp1;的代码。
5.三地址代码的格式：三地址代码的格式是(操作符, 操作数1, 操作数2, 结果)。函数按照这种格式生成代码，并将其添加到结果中，以便在GUI中显示。
parse_assignment函数
这个函数用于解析赋值语句，并根据需要将其分解为基本的操作。
1.简单赋值：对于形式为c=a;的简单赋值语句，如果a是单个变量或常量，它会直接生成一个赋值操作。
2.复杂赋值：对于包含算术运算的赋值语句，函数会将算术部分分解成单独的操作。例如，c=a+b;会被分解为两个步骤：先计算a+b，然后将结果赋值给c。
3.临时变量生成：对于每个算术操作，函数生成一个临时变量来存储中间结果。这有助于简化后续的代码优化和目标代码生成步骤。
4.6 代码优化方法
目标代码优化是编译器中用于改进中间代码的一个重要步骤。本设计使用的优化方法是DAG优化。这一过程通过识别和合并重复的表达式以及优化变量赋值来减少不必要的计算。下面是详细分析：
dag_optimization函数
1.初始化DAG和临时变量：
函数开始时，创建一个DAG字典来存储节点（变量或操作）及其父节点列表。同时，建立一个集合来跟踪所有的临时变量。
2.表达式处理：
update_expression函数负责在表达式中替换掉临时变量，用它们在DAG中的父节点代替。这有助于识别已经计算过的表达式。evaluate_expression函数尝试执行表达式的计算，但如果涉及变量，则保持原样。
3.遍历中间代码：
函数遍历`intermediate_code`列表中的每个代码项。对于每个赋值操作，它会分解左侧变量和右侧表达式。
4.构建DAG：
在处理每个赋值操作时，函数会在DAG中更新或创建新的节点。如果左侧变量不是临时变量，则在DAG中将其与表达式结果关联。
5.生成优化后的代码：
函数根据DAG的结构重新生成优化后的中间代码，通常只包括非临时变量的赋值操作。
6.输出优化后的代码：
优化后的中间代码被写入输出，以供后续阶段使用或在GUI的结果文本区域中显示。
dag_optimization函数提供了一个编译器中DAG优化的基本实现框架。这种优化是编译器设计中的一个重要环节，能够提高代码执行效率和减少运行时间。
4.7 目标代码生成方法
目标代码生成阶段是编译过程的关键部分，它负责将中间表示的代码转换为可以直接在目标机器上运行的代码。下面是详细设计分析：
target_code_generation函数
1.初始化目标代码列表：函数开始时创建一个列表target_code，用于存储生成的目标代码指令。
2.遍历中间代码：函数遍历之前语义分析阶段生成的`intermediate_code。这些中间代码通常表示为简单的赋值或算术运算形式。
3.代码转换：对每条中间代码进行处理，根据其操作类型生成对应的目标代码指令。对于算术运算，如加、减、乘、除，会生成相应的目标代码指令，例如ADD R1, a，其中R1是生成的寄存器，a是操作数。对于赋值操作，会生成类似于MOV R1, a的指令，其中R1是寄存器，a是赋值的源值。
4 .目标代码输出：将生成的每条目标代码指令添加到target_code列表中，并最终将这些指令显示在GUI的结果文本区域。
4.8 文件保存方法
文件保存功能允许用户将程序处理的结果保存到他们的文件系统中。详细设计描述如下：
功能描述：
保存结果到文件：用户可以将在文本框中显示的任何内容（如编译分析结果）保存到一个文本文件中。
自定义文件名和位置：用户可以选择保存文件的名称和位置。
实现步骤：
1.获取文本框内容：从GUI中的文本框获取当前显示的内容。
2.打开文件保存对话框：提供一个文件保存对话框，允许用户选择保存文件的位置并输入文件名。
3.写入文件：将获取的内容写入用户指定的文件中。
GUI交互：
按钮触发：用户通过点击“结果保存”按钮来启动文件保存功能。
文件保存对话框：用户在弹出的文件保存对话框中选择保存路径和文件名。
注意事项
1.在文件保存对话框中，设置默认的文件扩展名为.txt和文件类型过滤，以便用户更容易地创建正确类型的文件。
2.如果文本框中没有内容，程序仍然允许保存，但结果文件将是空的。
3.如果用户在文件保存对话框中取消操作，程序不会执行保存操作。
4.9 退出程序方法
退出程序功能是通过一个按钮触发的，允许用户直接关闭程序和GUI界面。详细设计描述如下：
GUI设计：
按钮创建：使用Tkinter创建一个按钮，标记为“退出程序”。
按钮功能绑定：将按钮的点击事件绑定到一个函数上，当点击按钮后，就会调用该函数。
功能实现：
当用户点击“退出程序”按钮时，会调用关闭函数来关闭程序和GUI界面。
