# C0语言编译系统 **Repository Path**: libraly/C0 ## Basic Information - **Project Name**: C0语言编译系统 - **Description**: C/0编译系统，它由编译程序和解释程序两部分组成。编译程序需要运行在Linux环境下，解释程序可以在多平台运行。C/0编译程序的源语言为C/0，目标语言是一个基于栈的指令机代码。 - **Primary Language**: C++ - **License**: Apache-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 4 - **Forks**: 0 - **Created**: 2021-10-16 - **Last Updated**: 2024-10-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # C/0语言编译系统 ## 介绍 ##### 概述 C/0编译系统，它由编译程序和解释程序两部分组成。编译程序需要运行在Linux环境下，解释程序可以在多平台运行。C/0编译程序的源语言为C/0，目标语言是一个基于栈的指令机代码。 ##### 主要文件介绍 ![image-20211211125351177.png (408×596) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/image-20211211125351177.png) 1. flex的输入文件lexer.l，bison的输入文件parser.y。 2. ast.h & ast.cpp:建立抽象语法树 3. BuildSym.h & BuildSym.cpp:建立符号表 4. TypeChecker.h & TypeChecker.cpp:静态语义分析 5. CodeGenerator.h & CodeGenerator.cpp:目标代码生成 6. main.cpp & main.h:主函数 7. Interpreter.h & Interpreter.cpp:解释器，可运行在各个平台。 ##### 文件接口介绍 1. parser.y 文件中需要用到lexer.l 生成的yylex()进行词法分析； 2. parser.y 文件中进行语法制导的语义计算时，需要用到 ast 类，根据类型创建不同的结点； 3. main.cpp 需要用到的 语法分析函数yyparser() 由 parser.y 生成。 4. BuildSym类，TypeChecker类，CodeGenerator类都继承Visitor类，并通过访问者模式访问AST结点。访问者模式包括的接口有visit()，accept(); 5. CodeGenerator类的showCode()函数可将目标代码打印，并将其输出到fa.txt。 6. Interpreter程序可读取目标代码fa.txt并解释执行。 ##### 主要数据结构及算法 1. 语法树； 2. 符号表； 3. 栈和队列； ## 软件架构 ### 设计思路 1. 在实际的编译器中，静态语义分析和中间代码生成的实现通常是采用多遍的方法，本程序也采用多遍方式实现编译。 2. 使用Visitor设计模式现实多遍的方法。 3. 利用Flex-Bison工具链实现词法、语法分析，当Bison运行时，生成对应的AST。 4. 通过多次遍历AST，实现打印语法树、创建符号表、静态语义分析及目标代码生成的相关处理操作。 ### 程序结构 ##### 模块划分 编译程序完成从源程序到目标程序的翻译工作。理论上分为以下六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成，下面就除代码优化的其他阶段，及解释程序划分模块进行介绍。 C0编译器的工作原理如图。我们将程序分成如下4个阶段。 ![程序结构图](https://gitee.com/liyuanmay/c0/raw/master/picture/未命名文件(8).svg) - 阶段一：词法和语法分析。借助flex和bison实现词法和语法分析，一遍扫描源程序后直接产生一种高级中间表示，即抽象语法树（AST）。 - 阶段二：语义分析。遍历抽象语法树构造符号表，实现静态语义检查，产生带标注的抽象语法树。这一阶段对抽象语法树进行两遍扫描：第一遍扫描的时候建立符号表的信息，并且检测符号声明冲突以及跟声明有关的符号引用问题；第二遍扫描的时候检查所有的语句以及表达式的参数的数据类型。 - 阶段三：中间（目标）代码生成。将带标注的抽象语法树所表示的输入程序翻译成另一种中间表示方式，即基于栈的指令机代码，它同时也是本编译系统的目标代码，可在解释器上执行。 - 阶段四：解释执行。读取目标代码，解释执行，这一阶段可在不同平台运行。 注：CMake集成了名为“FindFLEX”和“FindBISON”的modules。 功能：查找Flex和Bison可执行文件，并提供一个宏来生成自定义生成规则。即把 .y 和 .l 文件编译为c/c++文件。 ### 程序流程图 ![未命名文件 (6)](https://gitee.com/liyuanmay/c0/raw/master/picture/未命名文件(6).svg) ## 安装教程及运行环境 1. 本系统编译程序在 Linux 环境下测试运行，作者使用的虚拟机镜像为 ubuntu； 2. 安装flex，查看版本。 3. 安装bison，查看版本。 4. 安装CLion。CLion is also available as a snap package. If you’re on Ubuntu 16.04 or later, you can install CLion from the command line. 5. 解释程序在windows环境运行。 ```shell sudo apt install flex flex --verison sudo apt install bison bison --version sudo snap install clion --classic ``` ## 使用说明 编译程序main函数 ```c++ int main() { parse();//语法分析生成抽象语法树 showAst(); ast::genSym(node);//生成符号表 showSym(); ast::semanticCheck(node);//静态语义分析 TypeChecker::checkMain(); ast::genCode(node);//生成目标代码 CodeGenerator::entry(); showCode(); return 0; } ``` 解释程序main函数 ```c++ int main() { Interpreter::read();//读取fa.txt Interpreter::interpret();//解释执行 return 0; } ``` 1. 运行编译程序，输入测试文件文件名； 2. 选择是否打印AST，是否打印符号表，是否打印目标代码； 3. 目标代码将输出到fa.txt 4. 解释程序读取fa.txt，并解释执行，c0程序运行结果将输出到fa2.txt。 ## C/0语言说明 ### 语言定义 C0语言的语法结构定义如下： <程序>->[<变量定义部分>] {<自定义函数定义部分>} <主函数> ​ <变量定义部分>-> int id {, id}; <自定义函数定义部分>-> ( int id | void id) '(' ')' <分程序> <主函数>->void main'(' ')' <分程序> ​ <分程序>->'{' [<变量定义部分>] <语句序列> '}' ​ <语句序列>-><语句> {<语句>} ​ <语句>-> <条件语句>｜<循环语句> | '{'<语句序列>'}' | <自定义函数调用语句> | <赋值语句> | <返回语句> | <读语句> | <写语句> | ; ​ <条件语句>->if '('<表达式>')' | <语句> [else <语句> ] <循环语句>->while '(' <表达式>')' <语句> <自定义函数调用语句>-><自定义函数调用>; <赋值语句>->id = <表达式>; <返回语句>->return ['(' <表达式> ')'] ; <读语句>->scanf '(' id ')'; <写语句>->printf '(' [ <表达式>] ')'; ​ <表达式>-> [+｜-] <项> { (+｜-) <项>} <项> -> <因子>｛(*｜/) <因子>｝ <因子> -> id｜'(' <表达式>')' | num | <自定义函数调用> ​ <自定义函数调用>->id '(' ')' 其中，id代表标识符，num代表整数，其含义及构成方式与C语言相一致；C0源程序中的变量需先定义后使用，其作用域与生存期与C语言相一致；自定义函数可超前使用（调用在前，定义在后）。 ### 目标代码 C/0编译程序的目标语言，可以看作基于栈的虚拟机的汇编语言。虚拟机是一种简单的纯栈式结构的机器，它有一个栈式存储器，有3个控制寄存器：指令寄存器ip、栈顶寄存器tp和基址寄存器bp。程序运行期间的数据存储和算术以及逻辑运算都在栈顶进行。 虚拟机的指令格式形如 F L A 它由3个部分构成，其含义如下： F： 指令的操作码。 L： 若起作用，则表示引用层与声明层之间的层次差；若不起作用，则置为0。 A： 不同的指令含义不同。 虚拟机完整的指令合集: | LIT 0 a | 将常数值取到栈顶，a为常数值 | | ------- | -------------------------------------------------- | | LOD t a | 将变量值取到栈顶，a为相对地址，t为层数 | | STO t a | 将栈顶内容送入某变量单元中，a为相对地址，t为层数 | | CAL 0 a | 调用函数，a为函数地址 | | INT 0 a | 在运行栈中为被调用的过程开辟a个单元的数据区 | | JMP 0 a | 无条件跳转至a地址 | | JPC 0 a | 条件跳转，当栈顶值为0，则跳转至a地址，否则顺序执行 | | ADD 0 0 | 次栈顶与栈顶相加，退两个栈元素，结果值进栈 | | SUB 0 0 | 次栈顶减去栈顶，退两个栈元素，结果值进栈 | | MUL 0 0 | 次栈顶乘以栈顶，退两个栈元素，结果值进栈 | | DIV 0 0 | 次栈顶除以栈顶，退两个栈元素，结果值进栈 | | RED 0 0 | 从命令行读入一个输入置于栈顶 | | WRT 0 0 | 栈顶值输出至屏幕并换行 | | RET 0 0 | 函数调用结束后,返回调用点并退栈 | ### 栈式机 以如下代码为例： ```c++ int a,b; int A() { int e ,f ; ... } void main() { int c ,d; ... } ``` 栈结构如图 ![image-20211211132410417.png (606×728) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/image-20211211132410417.png) main()函数也是一个函数，进入时为第一层，因此进入主函数需要执行指令‘CAL 0 X’。 ### 模块划分 编译程序完成从源程序到目标程序的翻译工作。理论上分为以下六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成，下面就这些方面，从除代码优化外的五个角度分别加以叙述。 ## 词法分析 #### Flex介绍 Flex（快速词法分析器生成器）是lex的免费开源软件替代品。它是生成[词法分析器](https://www.zhihu.com/search?q=词法分析器&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra={"sourceType"%3A"article"%2C"sourceId"%3A89473441})（也称为“扫描器”或“词法分析器”）的计算机程序。扫描仪是识别文本中的词汇模式的程序。该flex 程序读取给定的输入文件，或它的标准输入，如果没有指定文件名，为扫描仪产生的描述。描述采用成对的正则表达式和C代码（称为rules）形式。flex生成一个C源文件作为输出， 文字库默认情况下，它定义了一个例程yylex()。可以编译该文件并将其与Flex运行时库链接以生成可执行文件。运行可执行文件时，它将分析其输入以查找正则表达式的出现。只要找到一个，它就会执行相应的C代码。经常连同Yacc或GNU Bison一起使用。 #### lexer.l文件 ```flex %{ #include "../include/ast.h" #include #include "c0parser.hpp" %} INTERGER [0-9] NOTE_S \/\/(.)*\n NOTE_M \/\*(.|\n)*?\*\/ IDENTIFIER [_a-zA-Z][_a-zA-Z0-9]* %% "(" {return '(';} ")" {return ')';} "{" {return '{';} "}" {return '}';} "," {return ',';} ";" {return ';';} "+" {return '+';} "-" {return '-';} "*" {return '*';} "/" {return '/';} "=" {return '=';} "int" {return INT;} "else" {return ELSE;} "if" {return IF;} "return" {return RETURN;} "void" {return VOID;} "while" {return WHILE;} " " { /*no action and no return*/ } "\t" { /*no action and no return*/ } "\n" { /*no action and no return*/ } {NOTE_S}* { /*no action and no return*/ } {NOTE_M}* { /*no action and no return*/ } {INTERGER}+ {yylval.number = atoi(yytext); return NUMBER;} {IDENTIFIER} {strcpy(yylval.strValue, yytext); return ID;} %% int yywrap(){ return 1; } ``` flex是将字符序列转换为单词(Token)的过程。return到对应的token中供语法解析器调用。 ## 语法分析 #### Bison介绍 Bison是一种通用[解析器](https://www.zhihu.com/search?q=解析器&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra={"sourceType"%3A"article"%2C"sourceId"%3A89479111})生成器，它将带注释的上下文无关文法转换为使用LALR（1）解析器表的确定性LR或广义LR（GLR）解析器 。作为一项实验性功能，Bison还可以生成IELR（1）或规范的LR（1）解析器表。一旦您精通Bison，就可以使用它来开发各种语言解析器，从用于简单台式计算器的语言解析器到复杂的编程语言。 Bison与Yacc向上兼容：所有正确编写的Yacc语法都应与Bison一起使用，而无需进行任何更改。熟悉Yacc的任何人都应该可以轻松使用Bison。您需要精通C或C ++编程才能使用Bison。还支持将Java作为实验功能。 #### parser.y文件 ```bison %{ #include "../include/ast.h" void yyerror(char *); int yylex(void); %} %union{ int number; char strValue[100]; past pAst; } %token IF ELSE INT VOID WHILE RETURN AND OR %token ID %token NUMBER %type CompUnit CompUnits Decl VarDecl VarDef InitVal FuncDef Block BlockItem Stmt Exp LVal PrimaryExp Number UnaryExp FuncRParams MulExp AddExp VarDeclMul VarDefMul InitValMul BlockMul %% CompUnits: CompUnit {$$ = ast::newNextNode((char*)"CompUnit", $1, NULL); node = $$; } | CompUnits CompUnit {$$ = ast::newNextNode((char*)"CompUnit", $1, $2); node = $$; } ; CompUnit: Decl {$$ = $1;} | FuncDef {$$ = $1;} ; Decl: VarDecl {$$ = ast::newBasicNode((char*)"Decl", $1, NULL, NULL); } ; VarDeclMul: VarDef {$$ = ast::newNextNode((char*)"VarDecl_list", $1, NULL);} | VarDeclMul ',' VarDef {$$ = ast::newNextNode((char*)"VarDecl_list", $1, $3);} ; VarDecl: INT VarDeclMul ';' {$$ = ast::newBasicNode((char*)"VarDecl", ast::newTypeNode((char*)"int"), $2, NULL);} ; VarDef: ID {$$ = ast::newBasicNode((char*)"VarDef", ast::newIDNode(yylval.strValue), NULL,NULL); } | ID '=' InitVal {$$ = ast::newBasicNode((char*)"VarDef", ast::newIDNode($1), $3, NULL);} | ID VarDefMul {$$ = ast::newBasicNode((char*)"VarDef",ast::newNextNode((char*)"VarDef_para", ast::newIDNode($1), $2), NULL, NULL);} | ID VarDefMul '=' InitVal {$$ = ast::newBasicNode((char*)"VarDef",ast::newNextNode((char*)"VarDef_para", ast::newIDNode($1), $2), $4, NULL); } ; InitValMul: InitVal {$$ = ast::newNextNode((char*)"InitVal_list", $1, NULL);} | InitValMul ',' InitVal {$$ = ast::newNextNode((char*)"InitVal_list", $1, $3);} ; InitVal: Exp {$$ = $1;} | '{' '}' {$$ = ast::newBasicNode((char*)"InitVal_empty", NULL, NULL, NULL);} | '{' InitValMul '}' {$$ = $2;} ; FuncDef: VOID ID '(' ')' Block {$$ = ast::newBasicNode((char*)"FuncDef",ast::newNextNode((char*)"FuncDef_para", ast::newTypeNode((char*)"void"), ast::newIDNode($2)), $5, NULL);} | INT ID '(' ')' Block {$$ = ast::newBasicNode((char*)"FuncDef",ast::newNextNode((char*)"FuncDef_para", ast::newTypeNode((char*)"int"), ast::newIDNode($2)), $5, NULL);} ; BlockMul: BlockItem {$$ = ast::newNextNode((char*)"Block_list", $1, NULL);} | BlockMul BlockItem {$$ = ast::newNextNode((char*)"Block_list", $1, $2);} ; Block: '{' '}' {$$ = ast::newBasicNode((char*)"Block_empty", NULL, NULL, NULL);} | '{' BlockMul '}' {$$ = $2;} ; BlockItem: Decl {$$ = $1;} | Stmt {$$ = $1;} ; Stmt: LVal '=' Exp ';' {$$ = ast::newBasicNode((char*)"Assign_Stmt", $1, $3, NULL);} | Exp ';' {$$ = $1;} | ';' {$$ = ast::newBasicNode((char*)"Stmt_empty", NULL, NULL, NULL);} | Block {$$ = $1;} | IF '(' AddExp ')' Stmt {$$ = ast::newBasicNode((char*)"If_Stmt", $3, $5, NULL);} | IF '(' AddExp ')' Stmt ELSE Stmt {$$ = ast::newBasicNode((char*)"IfElse_Stmt", $3, ast::newNextNode((char*)"If_Else", $5, $7), NULL);} | WHILE '(' AddExp ')' Stmt {$$ = ast::newBasicNode((char*)"While_Stmt", $3, $5, NULL);} | RETURN Exp ';' {$$ = ast::newBasicNode((char*)"Return_Stmt",$2,NULL,NULL);} | RETURN ';' {$$ = ast::newBasicNode((char*)"Return_Stmt",NULL,NULL,NULL);} ; Exp: AddExp {$$ = $1;} ; LVal: ID {$$ = ast::newIDNode(yylval.strValue);} ; PrimaryExp: '(' Exp ')' {$$ = $2;} | LVal {$$ = $1;} | Number {$$ = $1;} ; Number: NUMBER {$$ = ast::newNum(yylval.number);} ; UnaryExp: PrimaryExp {$$ = $1;} | ID '(' ')' {$$ = ast::newBasicNode((char*)"UnaryExp", ast::newIDNode($1), NULL, NULL);} | ID '(' FuncRParams ')' {$$ = ast::newBasicNode((char*)"UnaryExp", ast::newIDNode($1), $3, NULL);} | '+' UnaryExp {$$ = ast::newBasicNode((char*)"UnaryExp", ast::newExpr('+', NULL, $2), NULL, NULL);} | '-' UnaryExp {$$ = ast::newBasicNode((char*)"UnaryExp", ast::newExpr('-', NULL, $2), NULL, NULL);} ; FuncRParams: Exp {$$ = ast::newNextNode((char*)"FuncRParams_list", $1, NULL);} | FuncRParams ',' Exp {$$ = ast::newNextNode((char*)"FuncRParams_list", $1, $3);} ; MulExp: UnaryExp {$$ = $1;} | MulExp '*' UnaryExp {$$ = ast::newExpr('*', $1, $3);} | MulExp '/' UnaryExp {$$ = ast::newExpr('/', $1, $3);} ; AddExp: MulExp {$$ = $1;} | AddExp '+' MulExp {$$ = ast::newExpr('+', $1, $3);} | AddExp '-' MulExp {$$ = ast::newExpr('-', $1, $3);} ; ``` Bison将单词流（由yylex()生成）作为其输入，进行语法检查，并进行语法执导的语义计算，构建由输入单词(Token)组成的数据结构（即抽象语法树）。 ### CMakeLists.txt ```cmake cmake_minimum_required(VERSION 3.20) project(c0) set(CMAKE_CXX_STANDARD 23) find_package(BISON) find_package(FLEX) BISON_TARGET(MyParser grammar/parser.y ${CMAKE_CURRENT_BINARY_DIR}/parser.cpp) FLEX_TARGET(MyScanner grammar/lexer.l ${CMAKE_CURRENT_BINARY_DIR}/lexer.cpp) ADD_FLEX_BISON_DEPENDENCY(MyScanner MyParser) include_directories(${CMAKE_CURRENT_BINARY_DIR}) add_executable(c0 src/main.cpp ${BISON_MyParser_OUTPUTS} ${FLEX_MyScanner_OUTPUTS} src/ast.cpp src/BuildSym.cpp src/CodeGenerator.cpp src/Interpreter.cpp src/TypeChecker.cpp) target_link_libraries(c0 ${FLEX_LIBRARIES}) ``` cmake可直接将.l和.y文件编译为对应的cpp文件，并链接到程序中。 ## 中间代码生成 本程序构建抽象语法树作为中间代码。 #### 抽象语法树 ##### 介绍 抽象语法树（AST）是一种非常接近源代码的中间表示，它的特点是： 1. 不含我们不关心的终结符（例如逗号），而只含像标识符、常量之类的终结符； 2. 不具体体现语法分析的具体步骤； 3. 能够完整体现源程序的语法结构，使后续过程可以反复利用。 合理定义抽象语法树的结点类型是编译器设计人员的主要责任之一。 ##### ast.h ```c++ #ifndef COMPILE_AST_H #define COMPILE_AST_H #include #include using namespace std; typedef class ast *past; class CompUnit; ... class ast { public: class Visitor { public: virtual void visit(CompUnit *) = 0; ... }; char *strValue; char *nodeType; int ivalue; past next; past left; past right; static past newNum(int value); static past newExpr(int oper, past left, past right); static past newDoubleExpr(char *logic_oper, past left, past right); static past newBasicNode(char *nodeType, past left, past right, past next); static past newNextNode(char *nodeType, past older, past younger); static past newTypeNode(char *strVal); static past newIDNode(char *strVal); virtual void accept(Visitor *) = 0; static void showAst(past node, int nest); static void genSym(past node); static void genCode(past node); static past newAstNode(char *); virtual ~ast() = default; }; extern ast *node; class CompUnit : public ast { public: void accept(Visitor *v) override { v->visit(this); } }; ... extern char *whichFunc; #endif //COMPILE_AST_H ``` 采用访问者模式，其中每个AST结点的种类的对应各自的一个class，且都是抽象类ast的子类。 注：本段程序仅列出其中一个子类CompUnit，其余用"..."省略。 ##### ast.cpp 以构建Basic结点为例： ```c++ past ast::newBasicNode(char *nodeType, past left, past right, past next) { char *node_type = new char; strcpy(node_type, nodeType); past root = newAstNode(node_type); root->nodeType = node_type; root->left = left; root->right = right; root->next = next; return root; } ``` ##### 抽象语法树展示 测试用例为： ```c++ int a,b; int main(){ a=10; b=5; int c=a*2+b+3; return c; } ``` 测试结果为： ![运行结果.png (751×674) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/运行结果.png) ## 多遍的方法 AST是一种非常接近源代码的中间表示，能够完整体现源程序的语法结构，同时也没有损失源程序的任何语义信息。因此，在多遍的编译器中，静态语义分析和中间代码生成的相关处理常常是通过多次遍历AST来完成。甚至符号表的创建也可以放在生成AST之后。例如，可以第一次遍历时创建符号表，第二次遍历时进行静态语义分析，而第三次遍历时生成TAC。 在实际的编译器中，静态语义分析和中间代码生成的实现通常是采用多遍的方法，一种被广泛采用的实现技术是Visitor设计模式。 #### 访问者模式 就多遍方法的实现而言，每一遍扫描都要针对AST的所有结点进行同类的处理，处理到不同的结点时有不同的行为。如果是采用面向对象技术来设计编译器，则通过Visitor设计模式可以很方便的实现这一需求。 设计模式是人们为解决同类设计问题总结出来的行之有效的软件设计定式，合理使用设计模式，可以使软件更加容易理解和维护，节省大量开发时间和工作量。 Visitor模式可以有效解决多次遍历AST时费时且容易出错，并且需要不断修改一个抽象类的问题。这种方法将每一次对AST遍历的工作收集到一个收集到一个单独的class，而不是将这些工作分散至不同的结点class。 本系统采用c++作为主要语言，因此可以通过Visitor模式实现需求。下面以符号表建立为例，简要介绍Visitor模式的在本程序的实现。 #### Visitor实现 Visitor模式提供一种所谓双重分派的技术，可以简洁地支持这种将每一遍遍历工作收集到一个单独class的解决方法。方法如下： （1）针对每个结点类 CompUnit，intValue，Decl，···，Visitor类都有对应方法。 ```c++ class Visitor { public: virtual void visit(CompUnit *) = 0; virtual void visit(intValue *) = 0; virtual void visit(Decl *) = 0; . . . }; ``` （2）每一次遍历工作对应的class都继承这一抽象类Visitor，如下所示。这些功能类将对方法 visit(VarDef *)，visit(FuncDef *)，void visit(UnaryExp *)，···进行重载。 ```c++ class BuildSym : public ast::Visitor { public: char *name{};//名字 char *kind{};//类型 char *scope{};//作用域 int size = 2;//大小 int level{};//层次 int adr{};//地址 int location{};//位置 void visit(VarDef *) override; void visit(FuncDef *) override; void visit(UnaryExp *) override; . . . private: past node{}; }; ``` 在类BuildSym中的 visit(VarDef *)，visit(FuncDef *)，void visit(UnaryExp *)，...将具体定义针对各个结点类（VarDef ，FuncDef ，UnaryExp，···）实现建立符号表的功能。 举例如下： ```c++ void BuildSym::visit(VarDef *) {//登录全局变量或局部变量 if (global) { gv[gvNum].kind = (char *) "variable"; gv[gvNum].scope = (char *) "global"; for (int i = 0; i < gvNum; i++) { if (strcmp(node->left->strValue, gv[i].name) == 0) { cerr << " Redefinition of '" << node->left->strValue << "' as different kind of symbol" << endl; return; } } for (int i = 0; i < fNum; i++) { if (strcmp(node->left->strValue, func[i].name) == 0) { cerr << "Redefinition of '" << node->left->strValue << "' as different kind of symbol" << endl; return; } } gv[gvNum].name = node->left->strValue; gv[gvNum].adr = vAdr++; gvNum++; return; } else { lv[lvNum].level = 0; lv[lvNum].kind = (char *) "variable"; lv[lvNum].scope = whichFunc; lv[lvNum].name = node->left->strValue; lv[lvNum].adr = func[fNum - 1].size ++; lvNum++; } } void BuildSym::visit(FuncDef *) {//登录函数 global = false; vAdr = 2; func[fNum].kind = (char *) "function"; func[fNum].level = 1; for (int k = 0; k < gvNum; k++) { if (strcmp(node->left->left->next->strValue, gv[k].name) == 0) { cerr << " Redefinition of '" << node->left->left->next->strValue << "' as different kind of symbol" << endl; return; } } for (int j = 0; j < fNum; j++) { if (strcmp(node->left->left->next->strValue, func[j].name) == 0) { cerr << " Redefinition of '" << node->left->left->next->strValue << "' as different kind of symbol" << endl; return; } } func[fNum].name = node->left->left->next->strValue; fNum++; whichFunc = node->left->left->next->strValue; } void BuildSym::visit(UnaryExp *) { for (int i = 0; i < fNum; i++) { if (strcmp(node->left->strValue, func[i].name) == 0) { if (!func[i].hasBeenCalled) { func[i].level++; func[i].hasBeenCalled = true; for (int j = 0; j < lvNum; j++) { if (strcmp(lv[j].scope, func[i].name) == 0) { lv[j].level = func[i].level; } } } } } } ``` （3）为抽象类ast增加一个接收Visitor对象的方法 void accept(Visitor *) ，如下所示，ast中纯虚函数: ```c++ class ast { public: ... virtual void accept(Visitor *) = 0; virtual ~ast() = default; ... }; ``` （4）结点类 VarDef ，FuncDef ，UnaryExp，···都重载方法 void accept(Visitor *) ，但方法体都一样，都只有一条语句 v->visit(this)，如下所示。 ```c++ class CompUnit : public ast { public: void accept(Visitor *v) override {//子类需要重写accept函数。 v->visit(this); } }; class Decl : public ast { public: void accept(Visitor *v) override {//子类需要重写accept函数。 v->visit(this); } }; ``` 此处利用函数重载的特性，，即使Visitor类中visit()同名，但是由于传入的参数即各个对象所属子类不同，因此一个visit方法可以实现不同的功能，以此简化了Visitor类中抽象方法接口的定义。 ![未命名文件 (7)](https://gitee.com/liyuanmay/c0/raw/master/picture/未命名文件(7).svg) 这种设计的好处是，每当需要新增加一遍扫描工作时，仅需增加一个新的类，通过继承Visitor类和重载其中的方法将这一遍扫描的工作收集到这个类中，而不影响代码的其他部分。例如，如果需要对AST进行另外两边扫描，分别进行静态语义检查和目标代码生成，则只需要增加新的类TypeChecker和CodeGenerator，并分别将语义检查和目标代码生成的全部功能封装在其中。 ## 语义分析 ##### TypeChecker.h ```c++ #include "main.h" class TypeChecker : public ast::Visitor { public: explicit TypeChecker(past node) : node(node) {} void visit(VarDef *) override {} void visit(FuncDef *) override; void visit(UnaryExp *) override {} . . . static void checkMain(); private: past node{}; }; ``` ##### TypeChecker.cpp ```c++ void TypeChecker::visit(parameter *) { for (int i = 0; i < gvNum; i++) { if (strcmp(gv[i].name, node->strValue) == 0) return; } for (int i = 0; i < fNum; i++) { if (strcmp(func[i].name, node->strValue) == 0) return; } for (int i = 0; i < lvNum; i++) { if (strcmp(lv[i].name, node->strValue) == 0 && strcmp(lv[i].scope, whichFunc) == 0) return; } if (strcmp(node->strValue, "scanf") == 0 || strcmp(node->strValue, "printf") == 0) return; cerr << "Use of undeclared identifier '" << node->strValue << "'"; exit(1); } void TypeChecker::visit(FuncDef *) { whichFunc = node->left->left->next->strValue; } void TypeChecker::visit(Return_Stmt *) { for (int i = 0; i < gvNum; i++) { if (strcmp(gv[i].name, node->left->strValue) == 0) { for (int j = 0; j < fNum; j++) { if (strcmp(func[j].name, whichFunc) == 0) { if (strcmp(gv[i].typeGLF, func[j].typeGLF) == 0) return; } } } } for (int i = 0; i < lvNum; i++) { if (strcmp(lv[i].name, node->left->strValue) == 0) { for (int j = 0; j < fNum; j++) { if (strcmp(func[j].name, whichFunc) == 0) { if (strcmp(lv[i].typeGLF, func[j].typeGLF) == 0) return; } } } } cerr << "Void function '" << whichFunc << "' should not return a value"; exit(4); } void TypeChecker::checkMain() { for (int i = 0; i < fNum; i++) { if (strcmp(func[i].name, "main") == 0) return; } cerr<<"undefined reference to `main'"; exit(6); } ``` ##### 出错返回码 | 出错情况 | 返回码 | | :----------------------: | :----: | | 使用未定义的标识符或函数 | 1 | | 函数返回值不正确 | 4 | | 重复定义 | 5 | | 未定义main函数 | 6 | | 语法错误 | 8 | ## 目标代码生成 ##### CodeGenerator.h ```c++ #include "ast.h" #include #include using namespace std; extern int bl; class CodeGenerator : public ast::Visitor { public: CodeGenerator() = default; static void entry(); explicit CodeGenerator(past node) : node(node) {} void visit(VarDef *) override; void visit(FuncDef *) override; void visit(Assign_Stmt *) override; . . . private: past node{}; }; ``` ##### CodeGenerator.cpp 处理Assign_Stmt结点为例： ```c++ void CodeGenerator::visit(Assign_Stmt *) { queue q; stack p; bl++; if (node != nullptr) q.push(node); //根节点进队列 while (!q.empty()) { past expr = q.front(); p.push(expr); if (expr->left != nullptr) //如果有左孩子，入队 q.push(expr->left); if (expr->right != nullptr) //如果有右孩子，入队 q.push(expr->right); q.pop(); } while (!p.empty()) { past p1 = p.top(); p.pop(); if (!p.empty()) { past p2 = p.top(); if (strcmp(p1->nodeType, "expr") == 0) {//p1 is expr switch (p1->ivalue) { case '+': code.emplace_back(fct::ADD, 0, 0); break; case '-': code.emplace_back(fct::SUB, 0, 0); break; case '*': code.emplace_back(fct::MUL, 0, 0); break; case '/': code.emplace_back(fct::DIV, 0, 0); break; } if (strcmp(p2->nodeType, "parameter") == 0) { for (int i = 0; i < gvNum; i++) { if (strcmp(p2->strValue, gv[i].name) == 0) { for (int j = 0; j < fNum; j++) { if (strcmp(whichFunc, func[j].name) == 0) { if (p.size() == 2) code.emplace_back(fct::STO, func[j].level, gv[i].adr); else code.emplace_back(fct::LOD, func[j].level, gv[i].adr); } } } } } if (strcmp(p2->nodeType, "parameter") == 0) { for (int i = 0; i < lvNum; i++) { if (strcmp(p2->strValue, lv[i].name) == 0) { if (p.size() == 2) code.emplace_back(fct::STO, 0, gv[i].adr); else code.emplace_back(fct::LOD, 0, gv[i].adr); } } } if (strcmp(p2->nodeType, "intValue") == 0) { code.emplace_back(fct::LIT, 0, p2->ivalue); } } else if (strcmp(p2->nodeType, "expr") == 0) {//p2 is expr switch (p2->ivalue) { case '+': code.emplace_back(fct::ADD, 0, 0); break; case '-': code.emplace_back(fct::SUB, 0, 0); break; case '*': code.emplace_back(fct::MUL, 0, 0); break; case '/': code.emplace_back(fct::DIV, 0, 0); break; } if (strcmp(p1->nodeType, "parameter") == 0) { for (int i = 0; i < gvNum; i++) { if (strcmp(p1->strValue, gv[i].name) == 0) { for (int j = 0; j < fNum; j++) { if (strcmp(whichFunc, func[j].name) == 0) { code.emplace_back(fct::LOD, func[j].level, gv[i].adr); } } } } } if (strcmp(p1->nodeType, "parameter") == 0) { for (int i = 0; i < lvNum; i++) { if (strcmp(p1->strValue, lv[i].name) == 0) { code.emplace_back(fct::LOD, 0, gv[i].adr); } } } if (strcmp(p1->nodeType, "intValue") == 0) { code.emplace_back(fct::LIT, 0, p1->ivalue); } } else {//have no expr if (strcmp(p1->nodeType, "parameter") == 0) { for (int i = 0; i < gvNum; i++) { if (strcmp(p1->strValue, gv[i].name) == 0) { for (int j = 0; j < fNum; j++) { if (strcmp(whichFunc, func[j].name) == 0) { code.emplace_back(fct::LOD, func[j].level, gv[i].adr); } } } } } if (strcmp(p1->nodeType, "parameter") == 0) { for (int i = 0; i < lvNum; i++) { if (strcmp(p1->strValue, lv[i].name) == 0) { code.emplace_back(fct::LOD, 0, gv[i].adr); } } } if (strcmp(p1->nodeType, "intValue") == 0) { code.emplace_back(fct::LIT, 0, p1->ivalue); } if (strcmp(p2->nodeType, "parameter") == 0) { for (int i = 0; i < gvNum; i++) { if (strcmp(p2->strValue, gv[i].name) == 0) { for (int j = 0; j < fNum; j++) { if (strcmp(whichFunc, func[j].name) == 0) { if (p.size() == 2) code.emplace_back(fct::STO, func[j].level, gv[i].adr); else code.emplace_back(fct::LOD, func[j].level, gv[i].adr); } } } } } if (strcmp(p2->nodeType, "parameter") == 0) { for (int i = 0; i < lvNum; i++) { if (strcmp(p2->strValue, lv[i].name) == 0) { if (p.size() == 2) code.emplace_back(fct::STO, 0, lv[i].adr); else code.emplace_back(fct::LOD, 0, lv[i].adr); } } } if (strcmp(p2->nodeType, "intValue") == 0) { code.emplace_back(fct::LIT, 0, p2->ivalue); } } } else { BlockList(); return; } p.pop(); } BlockList(); } ``` 例如： $$ RET = a + b * 5 + 2; $$ 利用队列实现层序遍历，并将结点入栈。得到栈后，每次出栈两个结点，根据不同情况分别处理，并生成目标代码。 ![image-20211211161020482.png (554×379) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/image-20211211161020482.png) 2021/12/16注：经过今天的上课，我了解到后序遍历可以更加方便的实现这一过程，不过我当初考虑后续遍历时，由于一开始手写目标代码时就是先将b和5取到栈顶，于是在后序遍历首先把a取到栈顶栈顶时就pass掉了后序遍历，认为它不能实现，如果我当时能再往下进行两步也许就能发现它的可行性了。 当时经过思考，转而使用了目前的这种贴近计算机思维的方法，经过上课得知，我所做的操作其实就是将结点先转化为一种称为逆波兰式（后缀式）的表达形式，然后转化为目标代码。 ###### BlockList() ```c++ void BlockList() { if (whichFunc) { for (int i = 0; i < fNum; i++) { if (strcmp(func[i].name, whichFunc) == 0) { if (bl == func[i].blockList) { code.emplace_back(fct::RET, 0, 0); } } } } } ``` 检测是否需要添加"RET 0 0"。 ###### entry() ```c++ void CodeGenerator::entry() { code[0].a = int(code.size()); for (int i = 0; i < fNum; i++) { code[i + 1].a = func[i].location; } code.emplace_back(fct::INT, 0, gvNum + 2); for (int i = 0; i < fNum; i++) { if (strcmp(func[i].name, "main") == 0) { code.emplace_back(fct::CAL, 0, func[i].location); } } code.emplace_back(fct::RET, 0, 0); } ``` 程序入口：添加程序入口语句。 ## 解释程序 ##### Interpreter.h ```c++ #ifndef C0_INTERPRETER_H #define C0_INTERPRETER_H #include #include #include "CodeGenerator.h" using namespace std; extern fstream fa;//虚拟机代码 NOLINT extern FILE *fa1;//源文件 NOLINT extern ofstream fa2;//输出结果 NOLINT const int cxMax = 200;//最多的虚拟机代码数 enum fct { LIT, LOD, STO, CAL, INT, JMP, JPC, ADD, SUB, MUL, DIV, RED, WRT, RET, }; extern int cx; class Interpreter { private: fct f;//虚拟机代码指令 int l;//引用层和声明层的层次差 int a;//根据f的不同而不同 public: Interpreter() = default; Interpreter(fct f, int l, int a) { this->f = f; this->l = l; this->a = a; } static void interpret(); [[maybe_unused]] static void showCode(); friend void CodeGenerator::entry(); }; int gen(fct x, int y, int z); string fctToStr(fct f); int base(int l, vector &s, int bp); extern vector code;//存放虚拟机代码的容器 const map fctMap = {//NOLINT {fct::LIT, "LIT"}, {fct::LOD, "LOD"}, {fct::STO, "STO"}, {fct::CAL, "CAL"}, {fct::INT, "INT"}, {fct::JMP, "JMP"}, {fct::JPC, "JPC"}, {fct::ADD, "ADD"}, {fct::SUB, "SUB"}, {fct::MUL, "MUL"}, {fct::DIV, "DIV"}, {fct::RED, "RED"}, {fct::WRT, "WRT"}, {fct::RET, "RET"}, }; ``` ##### Interpreter.cpp ```c++ #include "../include/Interpreter.h" #include #include fstream fa;//虚拟机代码 NOLINT FILE *fa1;//源文件 NOLINT ofstream fa2;//输出结果 NOLINT int cx; vector code;//存放虚拟机代码的容器 string fctToStr(fct f) { return fctMap.at(f); } void Interpreter::interpret() { fa2.open("fa2.txt"); int ip;//instruction pointer指令指针 int bp;//base pointer指令基址 int sp;//stack pointer栈顶指针 Interpreter i{};//存放当前指令 vector stack;//栈 cout << "start c0" << endl; ip = bp = sp = 0; do { i = code[ip];//读取当前指令 ip++; switch (i.f) { case LIT://将a的值取到栈顶 stack.resize(sp + 1); stack[sp] = i.a; sp++; break; case LOD://将变量值取到栈顶，a为相对地址，l为层数 stack.resize(sp + 1); stack[sp] = stack[base(i.l, stack, bp) + i.a]; sp++; break; case STO://将栈顶内容送入某变量单元中，a为相对地址，l为层数 stack.resize(sp); sp--; stack[base(i.l, stack, bp) + i.a] = stack[sp]; break; case CAL://调动地址为a的过程，不可嵌套 stack.resize(sp + 2); stack[sp] = bp; stack[sp + 1] = ip; bp = sp; ip = i.a; break; case INT://在运行栈中为被调用的过程开辟a个单元的数据区 sp += i.a; stack.resize(sp); break; case JMP://无条件转移至地址a ip = i.a; break; case JPC://若栈顶为0，则转移至地址a sp--; if (stack[sp] == 0) { ip = i.a; } break; case ADD://此栈顶与栈顶相加，结果存入次栈顶 sp--; stack[sp - 1] = stack[sp - 1] + stack[sp]; break; case SUB://此栈顶与栈顶相减，结果存入次栈顶 sp--; stack[sp - 1] = stack[sp - 1] - stack[sp]; break; case MUL://此栈顶与栈顶相乘，结果存入次栈顶 sp--; stack[sp - 1] = stack[sp - 1] * stack[sp]; break; case DIV://此栈顶与栈顶相除，结果存入次栈顶 sp--; stack[sp - 1] = stack[sp - 1] / stack[sp]; break; case RED://从命令行读入一个输入置于栈顶 stack.resize(sp + 1); cout << "?"; fa2 << "?"; cin >> stack[sp]; fa2 << stack[sp] << endl; sp++; break; case WRT://栈顶的值输出至控制台并换行 cout << stack[sp - 1] << endl; fa2 << stack[sp - 1] << endl; sp--; break; case RET://结束被调用过程，返回调用点，退栈并将返回值存入退栈后的栈顶 int rv;//Return value记录返回值 rv = stack[sp - 1]; sp = bp; bp = stack[sp]; ip = stack[sp + 1]; stack[sp] = rv; sp++; stack.resize(sp); break; } } while (ip != 0); fa2.close(); } ``` ###### base() ```c++ int base(int l, vector &s, int bp) { int b; b = bp; while (l > 0) { b = s[b]; l--; } return b; } ``` 通过过程基址求下l层过程的基址。 ###### gen() ```c++ void CodeGenerator::showCode() { fa.open("fa.txt", ios::out); for (auto &i: code) { cout << fctToStr(i.f) << " " << i.l << " " << i.a << endl; gen(i.f, i.l, i.a); } fa.close(); } int gen(fct x, int y, int z) { if (cx >= cxMax) { cout << "Program too long"; return -1; } fa << fctToStr(x) << " " << y << " " << z << endl; cx++; return 0; } ``` 打印目标代码到 fa.txt。 ## 测试设计 将目标代码从Linux虚拟机分享到windows主机，在windows平台下运行。 - 测试用例1 源代码： ```c++ int a, b; int ADD() { int RET; RET = a + b; return RET; } void main() { scanf(a); scanf(b); printf(ADD()); } ``` 目标代码： ![image-20211211170135559.png (1920×1080) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/image-20211211170135559.png) AST、符号表及运行结果： ![Ubuntu-2021-12-11-16-44-49.png (1920×1080) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/Ubuntu-2021-12-11-16-44-49.png) ![Ubuntu-2021-12-11-16-49-40.png (1920×1080) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/Ubuntu-2021-12-11-16-49-40.png) ![屏幕截图2021-12-17135128.png (1115×624) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/屏幕截图2021-12-17135128.png) - 测试用例2 源代码： ```c++ int a,b,c; int pos_neg() { c = a - b; printf(a); if (c) { if ((c + 1) / c) return 1; else return -1; } else return 0; } void main() { a = 0; b = 5; while(pos_neg()) a = a + 1; } ``` 目标代码及运行结果： ![Ubuntu-2021-12-14-13-26-41.png (1914×914) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/Ubuntu-2021-12-14-13-26-41.png) ![屏幕截图2021-12-17135313.png (1115×624) (gitee.com)](https://gitee.com/liyuanmay/c0/raw/master/picture/屏幕截图2021-12-17135313.png) ## 心得 这次实践作业，使我对编译原理有了更加深刻的认识。从一开始的理论学习，到仔细认真研学课本后PL/0的C语言编译实现代码，再到自己上手实践，编写C0语言的编译器和解释器，深切体会到了开发一个完完整整的高级语言编译器的不易。 我们小组使用了gitee作为工具，极大的方便了我们小组成员之间的合作。同时使用了现在主流的跨平台编辑器CLion作为开发工具，它完美地实现了Linux系统下的c++开发，同时又很好的集成了gitee的功能，使得gitee的使用更加得心应手。学习并熟悉了这两个工具的使用，为以后工作打下了基础。 在了解了PL/0的编译过程后，我发现它是一款简单的编译器，而我的目标是实现一款接近现实使用的编译器。通过老师和课本上的介绍，讨论课的深入了解，我对前人的智慧结晶lex和yacc工具产生了极大的兴趣，并希望能在课程项目中得以应用。于是我查阅了相当多资料，并上网学习网课，终于找到了实现的方法。同时我在翻看教材的同时发现书后面介绍了许多能更好实现的方法，如访问者模式，于是又学习了访问者模式的使用，并运用到项目中来，更好的实现了项目。 这次的编译器开发大作业，是从理论入手，再到理论结合实践，最终在实践中去认识和发现、创新的过程，在这次过程中，我认识到了编译原理的奥妙，学习到了其中的原理，做到了创新，也最终实现了自己一开始上这门课时定下的目标。 ## 参与贡献 1. Fork 本仓库 2. 新建 Feat_xxx 分支 3. 提交代码 4. 新建 Pull Request