基于C语言构造一个高级语言的子集的编译器【100012141】

# 1 选题背景 ## 1.1任务 通过简单自定义语言编译器的完整实现，掌握编译原理理论知识，提高灵活运用理论知识以解决实际问题的能力；提高系统软件编写能力。 ## 1.2目标 课程目标是构造一个高级语言的子集的编译器，目标代码是汇编语言。按照任务书，实现的方案可以有很多种选择。 ## 1.3语言定义 采用简化的 C 语言的文法：mini-c 作为本次实验的语言。其文法如下所示： G[program]: program → ExtDefList ExtDefList→ExtDef ExtDefList | ε ExtDef→Specifier ExtDecList ; |Specifier FunDec CompSt Specifier→int | float | char ExtDecList→VarDec | VarDec , ExtDecList VarDec→ID FucDec→ID ( VarList ) | ID ( ) VarList→ParamDec , VarList | ParamDec ParamDec→Specifier VarDec CompSt→{ DefList StmList } StmList→Stmt StmList | ε Stmt→Exp ; | CompSt | return Exp ; | if ( Exp ) Stmt | if ( Exp ) Stmt else Stmt | while ( Exp ) Stmt | for( Exp ) Stmt DefList→Def DefList | ε Def→Specifier DecList ; DecList→Dec | Dec , DecList Dec→VarDec | VarDec = Exp Exp →Exp =Exp | Exp && Exp | Exp || Exp | Exp < Exp | Exp <= Exp | Exp == Exp | Exp != Exp | Exp > Exp | Exp >= Exp | Exp + Exp | Exp - Exp | Exp \* Exp | Exp / Exp | ID | INT | FLOAT | CHAR | ( Exp ) | - Exp | ! Exp | ID ( Args ) | ID ( ) | Exp + + | Exp - - | Exp + = Exp | Exp - = Exp | Exp \* = Exp | Exp / = Exp Args→Exp , Args | Exp 说明：program 为文件开始符号；ExtDefList 指程序语句列表；ExtDef 指某一 行的语句；ExtDefList 指后面多行语句；标识符 Specifier；变量声明列表ExtDecList；函数 FunDec；函数体 CompSt；函数声明 FunDec；变量列表VarList；参数声明 ParamDec；变量声明 VarDec；Dec 代表声明语句；Stmt 代表函数内部声明语句；StmtList 代表声明语句列表；Exp 代表表达式；ID 为对应的变量或函数名字。 ## 1.4主要技术 开发环境：Ubuntu18.04 系统，gnome terminal，Visual Studio Code 编辑器 关键技术：Flex、Bison、C 语言基本知识、抽象语法树 AST、mips32 汇编指令、终端相关操作。 总体说明：本实验由四个部分组成：词法分析、语法分析、语义分析、中间代码生成、目标代码生成。首先将设定的识别词法规则编写进 lex 文件中，将对应的语法规则编写进 bison 文件中，利用此文件对相应的 C 代码进行词法分析与语法分析；对抽象语法树进行遍历输出相应的节点信息。在此过程中，构建符号表，结合抽象语法树的节点信息对程序进行语义分析，生成中间代码。最后，将相应的汇编代码翻译成目标代码 MIPS32 指令，生成的指令最终能在 QtSpim 机器上成功运行。 # 2 实验一 词法分析和语法分析 ## 2.1单词文法描述 按照语法定义列出所有的终结符以及非终结符，如表 2.1 所示： 表 2.1: 语法符号 |单词符号类型|单词种类码|正则表达式| | :- | :- | :- | |{id}|ID|[A-Za-z] [A-Za-z0-9]\*| |{int}|INT|[0-9]+| |{float}|FLOAT|([0-9]\*\.[0-9]+)| |"int"|TYPE|| |"float"|TYPE|| |"return"|RETURN|| |"if"|IF|| |"else"|ELSE|| |"while"|WHILE|| |"for"|FOR|| |";"|SEMI|| |","|COMMA|| |''>''\|"<"\|">="\|"<="\|"=="\|"!="| RELOP | | |"="|ASSIGNOP|| |"+"|PLUS|| |“+=”|COMADD|| |“-=”|COMSUB|| |“++”|AUTOADD|| |“—"|AUTOSUB|| |"-"|MINUS|| |"\*"|STAR|| |"/"|DIV|| |"&&"|AND|| |"\|\|"|OR| | |"!"|NOT|| |"("|LP|| |")"|RP|| |"{"|LC|| |"}"|RC|| |"["|LB|| |"]"|RB|| |"//"[^\n]\*|代表单行注释|| |“/”\*(\s.)\*?\*”/”|代表多行注释|| ## 2.2语法文法描述 首先定义非终结符的类型，结合 bison 的语法规则，%type 定义非终结符的语义值类型，形式是%type <union 的成员名> 非终结符。 定义的非终结符如下： %type <ptr> program ExtDefList ExtDef Specifier ExtDecList FuncDec ArrayDec CompSt VarList VarDec ParamDec Stmt StmList DefList Def DecList Dec Exp Args 举一个例子进行说明，其中%type <ptr> program ExtDefList，这表示非终结符 ExtDefList 属性值的类型对应联合中成员 ptr 的类型，在本实验中对应一个树结点的指针。 其次，利用%token 定义终结符的语义值类型。%token <type\_id> ID，表示识别出来一个标识符后，标识符的字符串串值保存在成员 type\_id 中。 %token <type\_int> INT//指定 INT 的语义值是 type\_int,由词法分析得到的数值。 %token <type\_id> ID RELOP TYPE //指定 ID,RELOP 的语义值是 type\_id,由词法分析得到的标识符字符串。 %token <type\_float> FLOAT //指定 ID 的语义值是 type\_id,由词法分析得到的标识符字符串。 %token <type\_char> CHAR %token LP RP LC RC SEMI COMMA LB RB %token PLUS MINUS STAR DIV ASSIGNOP AND OR NOT IF ELSE WHILE R ETURN COMADD COMSUB FOR //+=comadd，-=comsub，for，=assignop 然后，定义运算符的优先级与结合性，如表 2.2 所示 表 2.2 算符优先级与结合性 |优先级|结合性|符号| | :-: | :- | :- | |高|左|“+=”，”-="| ||左|“=”| ||左|“||”| ||左|“&&”| ||左|">"|"<"|">="|"<="|"=="|"!="| ||左|“+”, “-“| ||左|“\*”，“/”| |低|右|“！”，“++”，“—”| 再次，是语法定义的核心部分：语法规则部分。语法规则由 1.1 中所定义的语法规则编写，具体实现代码如下，具体的分析写到每一句当中： program: ExtDefList { display($1,0);} /\*归约到 program，开始显示语法树,语义分析\*//\*ExtDefList：外部定义列表，即是整个语法树\*/ *ExtDefList*: {$$=NULL;}/\*整个语法树为空\*/ | ExtDef ExtDefList {$$=mknode(EXT_DEF_LIST,$1,$2,NULL,yylineno);}//每一个 EXTDEFLIST 的结点,其第 1 棵子树对应一个外部变量声明或函数 /\*外部声明，声明外部变量或者声明函数\*/ ExtDef: Specifier ExtDecList SEMI {$$=mknode(EXT_VAR\_DEF,$1,$2,NULL,y ylineno);}//该结点对应一个外部变量声明 | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);}//数组定义 | Specifier FuncDec CompSt {$$=mknode(FUNC_DEF,$1,$2,$3,yylineno);}//该结点对应一个函数定义,类型+函数声明+复合语句 | error SEMI {$$=NULL; printf("---缺少分号---\n");} /\*表示一个类型，int、float 和 char\*/Specifier: TYPE {$$=mknode(TYPE,NULL,NULL,NULL,yylineno);strcpy($$->ty pe\_id,$1);$$->type=(!strcmp($1,"int")?INT:(!strcmp($1,"float")?FLOAT:CHAR));} /\*变量名称列表，由一个或多个变量组成，多个变量之间用逗号隔开\*/*ExtDecList*: VarDec {$$=$1;}/\*每一个 EXT_DECLIST 的结点,其第一棵子树对应一个变量名(ID 类型的结点),第二棵子树对应剩下的外部变量名\*/ | VarDec COMMA ExtDecList {$$=mknode(EXT_DEC_LIST,$1,$3,NULL,yylineno);} /\*变量名称，由一个 ID 组成\*/ VarDec: ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}//ID 结点,标识符符号串存放结点的 type_id /\*函数名+参数定义\*/ FuncDec: ID LP VarList RP {$$=mknode(FUNC_DEC,$3,NULL,NULL,yylineno);strcpy($$->type\_id,$1);}//函数名存放在$$->type_id | ID LP RP {$$=mknode(FUNC_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}//函数名存放在$$->type_id | error RP {$$=NULL; printf("---函数左括号右括号不匹配---\n");} /\*数组声明\*/ ArrayDec: ID LB Exp RB {$$=mknode(ARRAY_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} | ID LB RB {$$=mknode(ARRAY_DEC,NULL,NULL,NULL,yylineno);strc py($$->type_id,$1);} | error RB {$$=NULL;printf("---数组定义错误---\n");} /\*参数定义列表，有一个到多个参数定义组成，用逗号隔开\*/ VarList: ParamDec {$$=mknode(PARAM