使用C++对TINY+语言进行词法分析、语法分析、语义分析和中间代码生成 |
您所在的位置：网站首页 › while语句的语法树 › 使用C++对TINY+语言进行词法分析、语法分析、语义分析和中间代码生成 |
使用C++对TINY+语言进行词法分析、语法分析、语义分析和中间代码生成
|
实验报告
实验环境
操作系统：Win 10编译器：g++
项目地址
项目地址 实验目的构造TINY＋的语义分析程序并生成中间代码 实验内容构造符号表，构造TINY＋的语义分析器，构造TINY＋的中间代码生成器 实验要求能检查一定的语义错误，将TINY＋程序转换成三地址中间代码。提交词法分析、语法分析和语义分析程序及中间代码生成的实验报告。 项目介绍 文件夹结构 tiny+ |-- errors.h |-- generation.cpp |-- generation.h |-- lexical.cpp |-- lexical.h |-- main.cpp |-- syntax.cpp |-- syntax.h |-- test |-- lexical_illegal_input.tny |-- sematic_illegal_input.tny |-- syntax_illegal_input.tny |-- test1.tny |-- test2.tnyerrors.h为错误信息管理文件，lexical.cpp和lexical.h为词法分析文件，负责生成词法分析token，syntax.cpp和syntax.h为语法分析文件，负责进行语法分析，生成语法树，generation.cpp和generation.h 负责生成三地址中间代码，main.cpp为主函数，test文件夹里的文件为测试文件。 运行方式进入tiny+文件夹目录，在命令提示符中输入： g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/test1.tny // 合法输入打印符号表和生成三地址中间代码测试1 a test/test2.tny // 合法输入打印符号表和生成三地址中间代码测试2 a test/test1.tny optimize // 合法输入打印符号表和生成优化三地址中间代码测试1 a test/test2.tny optimize // 合法输入打印符号表和生成优化三地址中间代码测试2 a test/test1.tny token // 合法输入词法分析测试1 a test/test2.tny token // 合法输入词法分析测试2 a test/test1.tny tree // 合法输入语法分析测试1 a test/test2.tny tree // 合法输入语法分析测试2 a test/lexical_illegal_input.tny token // 错误输入词法分析测试 a test/syntax_illegal_input.tny tree // 错误输入语法分析测试 a test/sematic_illegal_input.tny // 错误输入语义分析测试 TINY+的词法定义 关键字：在TINY的关键字write read if then else return begin end main string int real repeat until的基础上，扩充了or and bool char while do这几个关键字，小写字母表示，自定义标识符不能和关键字重复。特殊符号：在TINY的特殊符号; , ( ) + - * / := == != =的基础上，扩充了> < = '这几个特殊符号。其他种类的单词包括标识符ID，数字NUM以及字符串STRING，他们的正规表达式的定义如下： 标识符是以字母开头，由字母和数字混合构成的符号串：ID=letter (letter | digit)* TINY+中对数字的定义和TINY相同：NUM=digit digit* 一个字符串类型的单词是用单引号括起来的字符申’…'，引号内可出现除了’以外的任何符号。一个字符串不能跨行定义：STRING=any character except'' 小写和大写字母是不同的：letter=a|...|z|A|...|Z digit=0|...|9 空白包括空格、回车以及Tab。所有的空白在词法分析时，被当作单词ID, NUM以及保留字的分隔符，在词法分析之后，他们不被当作单词保留。注释是用花括号括起来的符号串{…}，注释不能嵌套定义，但注释的定义可以跨行。 TINY+的语法定义TINY+的语法用EBNF定义如下： 1 program -> declarations stmt-sequence 2 declarations -> decl;declarations | ε 3 decl -> type-specifier varlist 4 type-specifier -> int | bool | char 5 varlist -> identifier { , identifier } 6 stmt-sequence -> statement {; statement } 7 statement -> if-stmt | repeat-stmt | assign-stmt | read-stmt | write-stmt | while-stmt 8 while-stmt -> while bool-exp do stmt-sequence end 9 if-stmt -> if bool-exp then stmt-sequence [else stmt-sequence] end 10 repeat-stmt -> repeat stmt-sequence until bool-exp 11 assign-stmt -> identifier:=exp 12 read-stmt -> read identifier 13 write-stmt -> write exp 14 exp -> arithmetic-exp | bool-exp | string-exp 15 arithmetic-exp -> term { addop term } 16 addop -> + | - 17 term -> factor { mulop factor } 18 mulop -> * | / 19 factor -> (arithmetic-exp) | number | identifier 20 bool-exp -> bterm { or bterm } 21 bterm -> bfactor { and bfactor} 22 bfactor -> comparison-exp 23 comparison-exp -> arithmetic-exp comparison-op arithmetic-exp 24 comparison-op -> < | = | > | >= | string 词法分析实验报告 实现过程 1. 定义Token的类型和数据结构为了获得词法分析的Token，首先要定义获取Token的类型，根据词法定义，大致可以分成标识符、数学常量、字符串常量、关键字、特殊符号等类型的Token，其中关键字和特殊符号还可以进行进一步的细分，包含所有具体的关键字和特殊符号： // Token类型 enum TokenType { ID, // 标识符 NUM, // 数字常量 STRING, // 字符串常量 // 关键字 KEY_WRITE, // write KEY_READ, // read KEY_IF, // if KEY_THEN, // then KEY_ELSE, // else KEY_END, // end KEY_STRING, // string KEY_INT, // int KEY_REPEAT, // repeat KEY_UNTIL, // until KEY_OR, // or KEY_AND, // and KEY_BOOL, // bool KEY_WHILE, // while KEY_DO, // do // 特殊符号 SYM_GREATER_THAN, // > SYM_LESS_THAN, // < SYM_GREATER_EQUAL_THAN, // >= SYM_LESS_EQUAL_THAN, // = buffer_len) { // 如果可以继续往缓冲区读取字符 if (fgets(buffer, BUFFER_MAX_LEN - 1, fp)) { // 进行换行 cur_line_num++; // 更新缓冲区的已读长度和当前行的读取字符位置 buffer_len = strlen(buffer); cur_pos = 0; // 读取字符 c = buffer[cur_pos++]; } // 否则文件结束，读取的字符为EOF else { isEOF = true; c = EOF; } } // 否则直接读取字符 else { c = buffer[cur_pos++]; } is_save_char = true; switch (fsm_state) { // 初始状态 case STATE_START: // 如果读取字符为字母，那么下一状态为标识符状态 if (isalpha(c)) fsm_state = STATE_ID; // 如果读取字符为数字，那么下一状态为数字常量状态 else if (isdigit(c)) fsm_state = STATE_NUM; // 如果读取字符为左大括号，那么下一状态为注释状态，不保存字符 else if (c == '{') { fsm_state = STATE_COMMENT; is_save_char = false; } // 如果读取字符为右大括号，由于不是在注释状态下读到，那么下一状态为识别失败状态，不保存字符 else if (c == '}') { fsm_state = STATE_FAILED; is_save_char = false; cur_token_type = ERROR; cur_token_val = errors[ERROR_COMMENTS_LEFT_BRACE_MISSING].error_message; } // 如果读取字符为:，那么下一状态为赋值符号状态 else if (c == ':') { fsm_state = STATE_ASSIGN; } // 如果读取字符为>，那么下一状态为大于等于符号状态 else if (c == '>') { fsm_state = STATE_GREATER; } // 如果读取字符为，之后识别的字符为=，识别到token类型为大于等于 if (c == '=') { cur_token_type = SYM_GREATER_EQUAL_THAN; } // 之前识别的字符为>，之后识别的字符为其它，之前识别到的token类型为大于，回退一个位置再来识别 else { cur_token_type = SYM_GREATER_THAN; is_save_char = false; back_to_last_pos(isEOF, cur_pos); } break; // 小于符号状态或小于等于符号状态 case STATE_LESS: fsm_state = STATE_SUCCESS; // 之前识别的字符为 token可以看到：
生成词法分析的Token序列到Token文件。 词法错误测试test\lexical_illegal_input.tny： $ string s = '123 {comment } {comment进入tiny+文件夹目录，在命令提示符中输入： g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/lexical_illegal_input.tny token可以看到：
第1行存在非法符号错误，词法分析不能识别$符号 第2行存在单引号不匹配错误，字符串的右边缺少了一个单引号 第3和4行验证注释可以跨行，没有出错 第5行存在注释的括号不匹配错误，注释缺少右括号。 语法分析实验报告 实现过程 1. 构建语法树首先观察TINY+的语法定义，可以看到，语法树应该首先从program结点生成，program结点可以导出两个儿子结点declarations和stmt-sequence，declarations结点的儿子结构较为简单，而对于stmt-sequence结点，根据第6条语法定义stmt-sequence -> statement {; statement }，其会生成statement，而根据第7条语法定义，statement会生成if-stmt、repeat-stmt、assign-stmt、read-stmt、write-stmt、while-stmt这几种语句，每种语句又包含了不同的exp计算操作和逻辑操作表达式，根据这些可能生成的语法树结点，在syntax.h文件中，可以定义结点为： // 生成程序结点，program -> declarations stmt_sequence SyntaxTreeNode *program(FILE *fp, Token & cur_token); // 生成声明结点 // declarations -> decl;declarations | ε， // decl -> type-specifier varlist // type-specifier -> int | bool | char // varlist -> identifier { , identifier } SyntaxTreeNode *declarations(FILE *fp, Token & cur_token); // 生成语句序列结点 // stmt-sequence -> statement {; statement } // statement -> if-stmt | repeat-stmt | assign-stmt | read-stmt | write-stmt | while-stmt SyntaxTreeNode *stmt_sequence(FILE *fp, Token & cur_token); // 生成while语句结点 SyntaxTreeNode *while_stmt(FILE *fp, Token & cur_token); // 生成if语句结点 SyntaxTreeNode *if_stmt(FILE *fp, Token & cur_token); // 生成repeat语句结点 SyntaxTreeNode *repeat_stmt(FILE *fp, Token & cur_token); // 生成assign语句结点 SyntaxTreeNode *assign_stmt(FILE *fp, Token & cur_token, Token identifier_token); // 生成read语句结点 SyntaxTreeNode *read_stmt(FILE *fp, Token & cur_token); // 生成write语句结点 SyntaxTreeNode *write_stmt(FILE *fp, Token & cur_token); // 生成比较逻辑操作表达式结点 SyntaxTreeNode *comparison_exp(FILE *fp, Token & cur_token); // 生成或逻辑操作表达式结点 SyntaxTreeNode *or_exp(FILE *fp, Token & cur_token); // 生成与逻辑操作表达式结点 SyntaxTreeNode *and_exp(FILE *fp, Token & cur_token); // 生成加减计算操作表达式结点 SyntaxTreeNode *add_or_sub_exp(FILE *fp, Token & cur_token); // 生成乘除计算操作表达式结点 SyntaxTreeNode *mul_or_div_exp(FILE *fp, Token & cur_token); // 生成因子结点 SyntaxTreeNode *factor(FILE *fp, Token & cur_token); 2. 语法树的结构根据上面定义语法树结点，每个结点与其可能生成的结点的关系大概为： program declarations ID(INT)ID(BOOL)ID(STRING) stmt_sequence if-stmt if部分then部分else部分 repeat-stmt repeat部分until部分 assign-stmt ID部分exp部分 read-stmt read部分ID部分 write-stmt write部分exp部分 while-stmt while部分do部分 3. 代码实现3.1 词法分析生成的token： 在词法分析中，生成的Token的数据结构为： // Token数据结构 struct Token { TokenType type; // token的类型 string val; // token的值 Token() {} Token(TokenType type, string val): type(type), val(val) {} };token的类型有： // Token类型 enum TokenType{ ID, // 标识符 NUM, // 数字常量 STRING, // 字符串常量 // 关键字 KEY_WRITE, // write KEY_READ, // read KEY_IF, // if KEY_THEN, // then KEY_ELSE, // else KEY_END, // end KEY_STRING, // string KEY_INT, // int KEY_REPEAT, // repeat KEY_UNTIL, // until KEY_OR, // or KEY_AND, // and KEY_BOOL, // bool KEY_WHILE, // while KEY_DO, // do // 特殊符号 SYM_GREATER_THAN, // > SYM_LESS_THAN, // < SYM_GREATER_EQUAL_THAN, // >= SYM_LESS_EQUAL_THAN, // declarations stmt_sequence SyntaxTreeNode *program(FILE *fp, Token & cur_token); // 生成声明结点 SyntaxTreeNode *declarations(FILE *fp, Token & cur_token); // 生成语句序列结点 SyntaxTreeNode *stmt_sequence(FILE *fp, Token & cur_token); // 生成while语句结点 SyntaxTreeNode *while_stmt(FILE *fp, Token & cur_token); // 生成if语句结点 SyntaxTreeNode *if_stmt(FILE *fp, Token & cur_token); // 生成repeat语句结点 SyntaxTreeNode *repeat_stmt(FILE *fp, Token & cur_token); // 生成assign语句结点 SyntaxTreeNode *assign_stmt(FILE *fp, Token & cur_token, Token identifier_token); // 生成read语句结点 SyntaxTreeNode *read_stmt(FILE *fp, Token & cur_token); // 生成write语句结点 SyntaxTreeNode *write_stmt(FILE *fp, Token & cur_token); // 生成比较逻辑操作表达式结点 SyntaxTreeNode *comparison_exp(FILE *fp, Token & cur_token); // 生成或逻辑操作表达式结点 SyntaxTreeNode *or_exp(FILE *fp, Token & cur_token); // 生成与逻辑操作表达式结点 SyntaxTreeNode *and_exp(FILE *fp, Token & cur_token); // 生成加减计算操作表达式结点 SyntaxTreeNode *add_or_sub_exp(FILE *fp, Token & cur_token); // 生成乘除计算操作表达式结点 SyntaxTreeNode *mul_or_div_exp(FILE *fp, Token & cur_token); // 生成因子结点 SyntaxTreeNode *factor(FILE *fp, Token & cur_token);3.3 创建语法树： 在main函数中，可以直接调用语句SyntaxTreeNode *root = create_syntax_tree(fp);创建语法树，从TINY+的EBNF定义可以看到，应该从program结点开始构建语法树，那么创建语法树的函数实现为： // 创建语法树 SyntaxTreeNode *create_syntax_tree(FILE *fp) { // 获取第一个token Token token = getNextToken(fp); SyntaxTreeNode *root = program(fp, token); if (token.type != ENDOFFILE) { printf("Program exits halfway!\n"); } return root; }对于program结点，根据语法规则，program -> declarations stmt-sequence，那么在生成program结点的函数中，应该生成declarations结点和stmt-sequence结点： // 生成program结点，按照定义，program -> declarations stmt_sequence SyntaxTreeNode *program(FILE *fp, Token & cur_token) { SyntaxTreeNode *declarations_node = declarations(fp, cur_token); return stmt_sequence(fp, cur_token); }对于declarations结点，其生成函数为： // 生成declarations结点，按照定义 // declarations -> decl;declarations | ε， // decl -> type-specifier varlist // type-specifier -> int | bool | char // varlist -> identifier { , identifier } SyntaxTreeNode *declarations(FILE *fp, Token & cur_token) { while (cur_token.type == KEY_INT || cur_token.type == KEY_BOOL || cur_token.type == KEY_STRING) { Token temp_token = cur_token; do { // 跳过类型声明 Token identifier = getNextToken(fp); cur_token = identifier; if (check_and_get_next(fp, cur_token, ID)) { Symbol *symbol = symbol_table.insert(identifier.val); symbol->token = copy_token(identifier); switch (temp_token.type) { case KEY_INT: symbol->value_type = VALTYPE_INT; break; case KEY_BOOL: symbol->value_type = VALTYPE_BOOL; break; case KEY_STRING: symbol->value_type = VALTYPE_STR; break; default: break; } } } while (cur_token.type == SYM_COMMA); check_and_get_next(fp, cur_token, SYM_SEMICOLON); } return NULL; }对于stmt-sequence结点，因为stmt-sequence -> statement {; statement }，而statement -> if-stmt | repeat-stmt | assign-stmt | read-stmt | write-stmt | while-stmt，所以stmt-sequence结点可以生成6种语句结点，其实现为： // 生成stmt_sequence结点 SyntaxTreeNode *stmt_sequence(FILE *fp, Token & cur_token) { SyntaxTreeNode *node1 = nullptr, *node2 = nullptr; vector statement_type{KEY_IF, KEY_REPEAT, ID, KEY_READ, KEY_WRITE, KEY_WHILE}; Token last_token = cur_token; while (check_vector_and_get_next(fp, statement_type, cur_token)) { switch (last_token.type) { case KEY_IF: // 构建if_stmt结点 node2 = if_stmt(fp, cur_token); break; case KEY_REPEAT: // 构建repeat_stmt结点 node2 = repeat_stmt(fp, cur_token); break; case ID: // 构建assign_stmt结点 node2 = assign_stmt(fp, cur_token, last_token); break; case KEY_READ: // 构建read_stmt结点 node2 = read_stmt(fp, cur_token); break; case KEY_WRITE: // 构建write_stmt结点 node2 = write_stmt(fp, cur_token); break; case KEY_WHILE: // 构建while_stmt结点 node2 = while_stmt(fp, cur_token); break; default: break; } if (node1 == nullptr) { node1 = node2; } else { node1 = SyntaxTreeNode::create_node(STMT_SEQUENCE, node1, node2); } if (cur_token.type == SYM_SEMICOLON) { check_and_get_next(fp, cur_token, SYM_SEMICOLON); } last_token = cur_token; } return node1; }生成的6种语句结点继续生成其它的子结点，最后完成语法树的构建。 3.4 打印语法树： 在main函数中，创建语法树之后，可以通过调用语句print_syntax_tree(root);打印语法树，其实现为： #define PER_TAB_SPACE_NUM 2 // 一次缩进的空格数 // 打印相应空格数 void print_space_num(int space_num) { for (int i = 0; i < space_num; i++) printf(" "); } // 打印语法树 void print_syntax_tree(SyntaxTreeNode *root) { static int space_num = 0; // 每一行前打印的空格数 // 如果结点不是语句序列结点，那么进行缩进 if (root->node_type != STMT_SEQUENCE) { space_num += PER_TAB_SPACE_NUM; } if (root) { print_space_num(space_num); switch (root->node_type) { case STMT_SEQUENCE: break; case WHILE_STMT: printf("STMT: (Key, While)\n"); if (root->token) printf("%s\n", root->token->val.c_str()); break; case IF_STMT: printf("STMT: (Key, If)\n"); if (root->token) printf("%s\n", root->token->val.c_str()); break; case REPEAT_STMT: printf("STMT: (Key, Repeat)\n"); break; case ASSIGN_STMT: if (root->token) printf("STMT: (Key, Assign to %s)\n", root->token->val.c_str()); break; case READ_STMT: if (root->token) printf("STMT: (Key, Read %s)\n", root->token->val.c_str()); break; case WRITE_STMT: printf("STMT: (Key, Write)\n"); break; case GREATER_THAN_EXPR: printf("EXP LogOp: (Symbol, >)\n"); break; case LESS_THAN_EXPR: printf("EXP LogOp: (Symbol, =)\n"); break; case LESS_EQUAL_THAN_EXPR: printf("EXP LogOp: (Symbol, z then A:=1 end; y:=2;注释掉发现语义错误就会直接退出的代码之后，进入tiny+文件夹目录，在命令提示符中输入： g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/sematic_illegal_input.tny可以看到：
第2行存在重复声明错误，标识符x被声明了两次。 第5行存在赋值语句左右部类型不相等错误，把整数1赋值给了字符串z。 第7行存在一个二元操作符的两个操作数类型不相等错误，整型变量A不能和布尔类型变量z比较。 第11行存在一个标识符没有声明就使用错误，标识符y没有声明就被使用了。 |
【本文地址】