miniC语言编译器设计与实现（编译原理实验课程）

￡神魔★判官ぃ 2024-04-01 13:57 63阅读 0赞

目 录  
1 选题背景 1  
1.1 总体任务 1  
1.2 目标 1  
1.3 主要技术 1  
2 实验一 词法分析和语法分析 2  
2.1 词法的文法描述 2  
2.2 语法的文法描述 3  
2.3 词法分析器设计 5  
2.4 语法分析器设计 8  
2.5 词法及语法分析器运行截图 12  
2.6 小结 3  
3 实验二 语义分析 5  
3.1 语义子程序描述 5  
3.2 符号表的设计 7  
3.3 语义错误类型定义 9  
3.4 语义分析实现技术 10  
3.5 语义分析结果 12  
3.6小结 16  
4 实验三 中间代码生成 18  
4.1 中间代码格式定义 18  
4.2 中间代码生成规则定义 19  
4.3 中间代码生成过程 21  
4.4 中间代码生成结果 24  
4.5 小结 26  
5 实验四 目标代码生成 27  
5.1 指令集选择 27  
5.2 寄存器分配算法 27  
5.3 目标代码生成算法 28  
5.4 目标代码生成结果 32  
5.5 目标代码运行结果 36  
5.6 小结 38  
6 总结 39  
参考文献 42  
1 选题背景  
1.1 总体任务  
根据密码学编程时的某个函数（例如计算最大公约数函数）需要完成的程序功能，运用编译原理课程中的知识，设计一个类C语言程序设计语言相应的词法及语法，并实现该语言的编译器，将源码翻译为能在模拟器上运行的目标代码。  
1.2 目标  
通过资料查阅、分析设计、编程实现等步骤，逐步培养学生解决工程问题的能力，提高独立思考、灵活运用理论知识以解决实际问题的能力；  
通过构造简化编译器的过程，了解编译器各部分的理论知识，找出理论与实践中的差异；灵活运用第三方工具协助解决工程问题；综合运用数据结构、算法、汇编语言、C语言编程等前序课程的知识和技能。  
1.3 主要技术  
开发环境：Ubantu 18.04.5虚拟机系统，Visual Studio 2019编辑器。  
关键技术：Flex、Bison工具，老师所给的关键代码段，C语言知识，以及Linux  
系统下的相关终端操作。  
运行环境：Ubantu 18.04.5虚拟机系统  
2 实验一 词法分析和语法分析  
2.1 词法的文法描述  
词法分析器的构造技术线路，首选一个就是设计能准确表示各类单词的正则表达式。用正则表达式表示的词法规则等价转化为相应的有穷自动机FA，确定化、最小化，最后依据该FA，编写对应的词法分析程序。  
词法分析分为三个部分：定义部分，规则部分，用户子程序定义部分。  
1.定义部分  
第一个部分为定义部分，其中可以有一个%\{到%\}的区间部分，主要包含c语言的一些宏定义，如文件包含、宏名定义，以及一些变量和类型的定义和声明。会直接被复制到词法分析器源程序lex.yy.c中。%\{到%\}之外的部分是一些正规式宏名的定义，这些宏名在后面的规则部分会用到。  
2.规则部分  
第二个部分为规则部分，一条规则的组成为:  
正规表达式 动作  
表示词法分析器一旦识别出正规表达式所对应的单词，就执行动作所对应的操作，返回单词的种类码。在这里可写代码显示（种类编码，单词的自身值），观察词法分析每次识别出来的单词，作为实验检查的依据。  
词法分析器识别出一个单词后，将该单词对应的字符串保存在yytext中，其长度为yyleng,  
3.用户子程序部分  
第三个部分为用户子程序部分，这部分代码会原封不动的被复制到词法分析器源程序lex.yy.c中。  
高级语言的词法分析器，需要识别的单词有五类:关键字（保留字)、运算符、界符、常量和标识符。本文转载自http://www.biyezuopin.vip/onews.asp?id=16987依据mini-c语言的定义，在此给出各单词的种类码和相应符号说明:

#include "def.h"
    #include <stdio.h>
    
    struct node *mknode(int kind,struct node *first,struct node *second, struct node *third,int pos ){
        
      struct node *tempnode = (struct node*)malloc(sizeof(struct node));
      tempnode->kind = kind;
      tempnode->ptr[0] = first;
      tempnode->ptr[1] = second;
      tempnode->ptr[2] = third;
      tempnode->pos = pos;
      return tempnode;
    }
    
    void display(struct node* T,int indent){
        
        if(T){
        
            switch (T->kind){
        
                case EXT_DEF_LIST:  
                    display(T->ptr[0],indent);
                    display(T->ptr[1],indent);
                    break;
                case EXT_VAR_DEF:
                    printf("%*c%s\n",indent,' ',"外部变量定义：");     
                    display(T->ptr[0],indent+5);
                    printf("%*c%s\n",indent+5,' ',"变量名：");
                    display(T->ptr[1],indent+5);
                    break;
                case FUNC_DEF:
                    printf("%*c%s\n",indent,' ',"函数定义：");
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent+5);
                    display(T->ptr[2],indent+5);
                    break;
                case ARRAY_DEF:
                    printf("%*c%s\n",indent,' ',"数组定义：");
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent+5);
                    break;
                case FUNC_DEC:
                    printf("%*c%s%s\n",indent,' ',"函数名：",T->type_id);
                    printf("%*c%s\n",indent,' ',"函数型参：");
                    display(T->ptr[0],indent+5);
                    break;
                case ARRAY_DEC:
                    printf("%*c%s%s\n",indent,' ',"数组名：",T->type_id);
                    printf("%*c%s\n",indent,' ',"数组大小：");
                    display(T->ptr[0],indent+5);
                    break;
                case EXT_DEC_LIST:
                    display(T->ptr[0],indent+5);
                    if(T->ptr[1]->ptr[0]==NULL)
                        display(T->ptr[1],indent+5);
                    else
                        display(T->ptr[1],indent);
                    break;
                case PARAM_LIST:
                    display(T->ptr[0],indent);
                    display(T->ptr[1],indent);
                    break;
                case PARAM_DEC:
                    display(T->ptr[0],indent);
                    display(T->ptr[1],indent);
                    break;
                case VAR_DEF:
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent+5);
                    break;
                case DEC_LIST:
                    printf("%*c%s\n",indent,' ',"变量名：");
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent);
                    break;
                case DEF_LIST:
                    printf("%*c%s\n",indent+5,' ',"LOCAL VAR_NAME：");
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent);
                    break;
                case COMP_STM:
                    printf("%*c%s\n",indent,' ',"复合语句：");
                    printf("%*c%s\n",indent+5,' ',"复合语句的变量定义：");
                    display(T->ptr[0],indent+5);
                    printf("%*c%s\n",indent+5,' ',"复合语句的语句部分：");
                    display(T->ptr[1],indent+5);
                    break;
                case STM_LIST:
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent);
                    break;
                case EXP_STMT:
                    printf("%*c%s\n",indent,' ',"表达式语句：");
                    display(T->ptr[0],indent+5);
                    break;
                case IF_THEN:
                    printf("%*c%s\n",indent,' ',"条件语句（if-else）：");
                    printf("%*c%s\n",indent,' ',"条件：");
                    display(T->ptr[0],indent+5);
                    printf("%*c%s\n",indent,' ',"IF语句：");
                    display(T->ptr[1],indent+5);
                    break;
                case IF_THEN_ELSE:
                    printf("%*c%s\n",indent,' ',"条件语句（if-else-if）：");
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent+5);
                    break;
                case WHILE:
                    printf("%*c%s\n",indent,' ',"循环语句（while）：");
                    printf("%*c%s\n",indent+5,' ',"循环条件：");
                    display(T->ptr[0],indent+5);
                    printf("%*c%s\n",indent+5,' ',"循环体：");
                    display(T->ptr[1],indent+5);
                    break;
                case FOR:
                    printf("%*c%s\n",indent,' ',"循环语句（for）：");
                    printf("%*c%s\n",indent+5,' ',"循环条件：");
                    display(T->ptr[0],indent+5);
                    printf("%*c%s\n",indent+5,' ',"循环体：");
                    display(T->ptr[1],indent+5);
                    break;
                case FUNC_CALL:
                    printf("%*c%s\n",indent,' ',"函数调用：");
                    printf("%*c%s%s\n",indent+5,' ',"函数名：",T->type_id);
                    printf("%*c%s\n",indent+5,' ',"第一个实际参数表达式：");
                    display(T->ptr[0],indent+5);
                    break;
                case ARGS:
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent+5);
                    break;
                case ID:
                    printf("%*cID： %s\n",indent,' ',T->type_id);//控制新的一行输出的空格数，indent代替%*c中*
                    break;
                case INT:
                    printf("%*cINT： %d\n",indent,' ',T->type_int);  
                    break;
                case FLOAT:
                    printf("%*cFLOAT： %f\n",indent,' ',T->type_float);  
                    break;
                case CHAR:
                    printf("%*cCHAR： %c\n",indent,' ',T->type_char);
                case ARRAY:
                    printf("%*c数组名称： %s\n",indent,' ',T->type_id);  
                    break;
                case TYPE:
                    if(T->type==INT)
                        printf("%*c%s\n",indent,' ',"类型：int");
                    else if(T->type==FLOAT)
                        printf("%*c%s\n",indent,' ',"类型：float");
                    else if(T->type==CHAR)
                        printf("%*c%s\n",indent,' ',"类型：char");
                    else if(T->type==ARRAY)
                        printf("%*c%s\n",indent,' ',"类型：char型数组");
                    break;
                case ASSIGNOP:
                case OR:
                case AUTOADD_L:
                case AUTOSUB_L:
                case AUTOADD_R:
                case AUTOSUB_R:
                case AND:
                case RELOP:
                case PLUS:
                case MINUS:
                case STAR:
                case DIV:
                case COMADD:
                case COMSUB:
                    printf("%*c%s\n",indent,' ',T->type_id);
                    display(T->ptr[0],indent+5);
                    display(T->ptr[1],indent+5);
                    break;
                case RETURN:
                    printf("%*c%s\n",indent,' ',"返回语句：");
                    display(T->ptr[0],indent+5);
                    break;  
            }
        }
    }

![在这里插入图片描述][3c6ed748dfe047e5be136bb832b7010d.png_pic_center]  
![在这里插入图片描述][8703cf2f696e4fdfbec8fab7a5769491.png_pic_center]  
![在这里插入图片描述][f8d041e23fad40bca766551f7bb238de.png_pic_center]  
![在这里插入图片描述][8e66a3faba624950b76356d173a49650.png_pic_center]  
![在这里插入图片描述][23a70e6d2d294d8bb37e22df608b0ee0.png_pic_center]  
![在这里插入图片描述][e9e02d260c2d4ba498d97b6fc730c8c8.png_pic_center]  
![在这里插入图片描述][a9a88b6c42b746b48c1ca79c88f24980.png_pic_center]  
![在这里插入图片描述][9450edf9e9274ef39f04021c4d448c24.png_pic_center]  
![在这里插入图片描述][dc5e4778be6f4e6cb46e9227706dd5ba.png_pic_center]  
![在这里插入图片描述][9a09ce289f344c18814595e392884404.png_pic_center]  
![在这里插入图片描述][56d356286f51464b8e0ed7618420366e.png_pic_center]  
![在这里插入图片描述][5e136e2e3a1e476a9781d45998d1a36c.png_pic_center]  
![在这里插入图片描述][d58ab3f5974b4bf9a01e35ead43377dd.png_pic_center]  
![在这里插入图片描述][9552079395b545429539a421811d919c.png_pic_center]  
![在这里插入图片描述][5e41700b246a41f09d0dd4fe299e8ed4.png_pic_center]  
![在这里插入图片描述][40af800f37794bef86bf02ec51bcb035.png_pic_center]  
![在这里插入图片描述][3447087e847c459faa6228cc5e3df25a.png_pic_center]  
![在这里插入图片描述][fb2f2b603dfb438ea3f5e300c1fd9d2b.png_pic_center]  
![在这里插入图片描述][4b7ad7fd5efe4112bb4fe48e442928a5.png_pic_center]  
![在这里插入图片描述][632c2499a50640e1a0c4fb65600c5904.png_pic_center]  
![在这里插入图片描述][cbf01ab3952e4f76a5682954ad5f5059.png_pic_center]  
![在这里插入图片描述][9e428f7bdf8f4573ad0c722377cd6fa0.png_pic_center]  
![在这里插入图片描述][464032535e024945bc6c916f18bac168.png_pic_center]

[3c6ed748dfe047e5be136bb832b7010d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d92f14f7346b4ed3b964466b38d027d5.png
[8703cf2f696e4fdfbec8fab7a5769491.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b5c3fe04b0014a129f02f8d77dab2d83.png
[f8d041e23fad40bca766551f7bb238de.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1e15448dd4b5461ebfd57e5ae65ba01e.png
[8e66a3faba624950b76356d173a49650.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5cb126d0cd2a4b68b54415e4c3482896.png
[23a70e6d2d294d8bb37e22df608b0ee0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1948f25a722b478f8515d76bd3a84471.png
[e9e02d260c2d4ba498d97b6fc730c8c8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/17a411a98ed742369d7eae9331ffa709.png
[a9a88b6c42b746b48c1ca79c88f24980.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cc89673fd8574574bb1284709c9c26ad.png
[9450edf9e9274ef39f04021c4d448c24.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3e8276b9643d45c094c725079bdc18b1.png
[dc5e4778be6f4e6cb46e9227706dd5ba.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1047138b13bd4432bb659d8aae835978.png
[9a09ce289f344c18814595e392884404.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cbe7476b694c47fdb82adccfcc1edd0f.png
[56d356286f51464b8e0ed7618420366e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7d39e25f604945d1ac5da686abe9df5e.png
[5e136e2e3a1e476a9781d45998d1a36c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3a8c41fd8f78414aab808d03c2608e07.png
[d58ab3f5974b4bf9a01e35ead43377dd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/890cf71201d346edb74c594d6fdd7510.png
[9552079395b545429539a421811d919c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c1aafdade31c45278ed2aa9cd52c31a4.png
[5e41700b246a41f09d0dd4fe299e8ed4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d3177c250a7a4e04820ed3f6833ac83a.png
[40af800f37794bef86bf02ec51bcb035.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b8e0bb62ba784e82a7923573be0be152.png
[3447087e847c459faa6228cc5e3df25a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d8e24438fe94441d8b2d20f99dedcee7.png
[fb2f2b603dfb438ea3f5e300c1fd9d2b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4a08504c2937418b82f1c1f27d3eda2d.png
[4b7ad7fd5efe4112bb4fe48e442928a5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/433c13a51e66422abd82ca628c9190b3.png
[632c2499a50640e1a0c4fb65600c5904.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dc156b9b935047dcb0b8f4fc4df3123a.png
[cbf01ab3952e4f76a5682954ad5f5059.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b8ad40a0dd624899aa12471f2c79d4a1.png
[9e428f7bdf8f4573ad0c722377cd6fa0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e54662d0fdfe4508be5c19602e405737.png
[464032535e024945bc6c916f18bac168.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9a17361aa71a4e94adb44dcaac42197d.png