實驗報告

實驗環境

• 操作系統：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.tny

errors.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 // 合法輸入打印符號表和生成優化三地址中間代碼測試2a test/test1.tny token // 合法輸入詞法分析測試1 a test/test2.tny token // 合法輸入詞法分析測試2a test/test1.tny tree // 合法輸入語法分析測試1 a test/test2.tny tree // 合法輸入語法分析測試2a 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 -> < | = | > | >= | <= 25 string-exp -> string

詞法分析實驗報告

實現過程

1. 定義Token的類型和數據結構

為了獲得詞法分析的Token，首先要定義獲取Token的類型，根據詞法定義，大致可以分成標識符、數學常量、字符串常量、關鍵字、特殊符號等類型的Token，其中關鍵字和特殊符號還可以進行進一步的細分，包含所有具體的關鍵字和特殊符號：

// Token類型 enum TokenType {ID, // 標識符NUM, // 數字常量STRING, // 字符串常量// 關鍵字KEY_WRITE, // writeKEY_READ, // readKEY_IF, // ifKEY_THEN, // thenKEY_ELSE, // elseKEY_END, // endKEY_STRING, // stringKEY_INT, // intKEY_REPEAT, // repeatKEY_UNTIL, // untilKEY_OR, // orKEY_AND, // andKEY_BOOL, // boolKEY_WHILE, // whileKEY_DO, // do// 特殊符號SYM_GREATER_THAN, // >SYM_LESS_THAN, // <SYM_GREATER_EQUAL_THAN, // >=SYM_LESS_EQUAL_THAN, // <= SYM_ASSIGN, // :=SYM_EQUAL, // =SYM_SEMICOLON, // ;SYM_COMMA, // ,SYM_LEFT_PARENTHESES, // (SYM_RIGHT_PARENTHESES, // )SYM_ADD, // +SYM_SUB, // -SYM_MUL, // *SYM_DIV, // /// 文件結束ENDOFFILE,// 出現錯誤ERROR };// Token數據結構 struct Token {TokenType type; // token的類型string val; // token的值Token() {}Token(TokenType type, string val): type(type), val(val) {} };

對于每個類型的關鍵字，可以定義一個關鍵字表，使每個Token類型的關鍵字對應一個字符串：

// 關鍵字表，哈希表的key為關鍵字的單詞，value為關鍵字的類型 map<string, TokenType> Keywords = {{"write", KEY_WRITE}, {"read", KEY_READ}, {"if", KEY_IF}, {"then", KEY_THEN}, {"else", KEY_ELSE}, {"end", KEY_END},{"string", KEY_STRING}, {"int", KEY_INT}, {"repeat", KEY_REPEAT},{"until", KEY_UNTIL}, {"or", KEY_OR}, {"and", KEY_AND},{"bool", KEY_BOOL}, {"while", KEY_WHILE}, {"do", KEY_DO} };

2. 定義有限狀態機的狀態集

為了進行詞法分析，可以使用一個有限狀態機，定義如下：

// 有限狀態機的狀態集 enum FSM_STATE {STATE_START, // 開始狀態STATE_ID, // 標識符狀態STATE_NUM, // 數字狀態STATE_COMMENT, // 注釋狀態STATE_ASSIGN, // 賦值符號狀態STATE_GREATER, // 大于符號狀態或大于等于符號狀態STATE_LESS, // 小于符號狀態或小于等于符號狀態STATE_STR, // 字符串狀態STATE_SUCCESS, // 成功識別狀態，結束STATE_FAILED // 識別失敗狀態，出現詞法錯誤，結束 };

3. 使用有限狀態機識別程序中的Token

可以使用有限狀態機識別程序中的Token，在函數Token getNextToken(FILE *fp)中實現：

// 查找關鍵字類型 TokenType find_keyword_type(const string & key) {// 如果關鍵字表中存在查找的關鍵字，返回對應類型if (Keywords.count(key)) {return Keywords[key];}// 否則返回IDelse {return ID;} }// 之前可能存在識別出的token，或者識別失敗，就要返回上一個位置 void back_to_last_pos(bool isEOF, int & cur_pos) {if (!isEOF) {cur_pos--;} }// 獲取下一個token Token getNextToken(FILE *fp) {static char buffer[BUFFER_MAX_LEN];static int buffer_len = 0; // 緩沖區的已讀長度static int cur_pos = 0; // 在當前行的讀取字符位置static bool isEOF = false; // 是否文件結束static int left_brace_num = 0; // 保存左大括號的個數，表示嵌套數TokenType cur_token_type; // 當前讀取到的token的類型string cur_token_val; // 當前讀取到的token的值bool is_save_char; // 是否保存讀取到的字符// 如果當前保存的左大括號數不為0.說明處在注釋狀態，否則處在開始狀態FSM_STATE fsm_state;if (left_brace_num == 0) {fsm_state = STATE_START;}else {fsm_state = STATE_COMMENT;}// 如果識別還未結束while (fsm_state != STATE_SUCCESS && fsm_state != STATE_FAILED) {// 獲取下一個字符char c;// 如果在當前行的讀取字符位置大于等于緩沖區已讀長度if (cur_pos >= buffer_len) {// 如果可以繼續往緩沖區讀取字符if (fgets(buffer, BUFFER_MAX_LEN - 1, fp)) {// 進行換行cur_line_num++;// 更新緩沖區的已讀長度和當前行的讀取字符位置buffer_len = strlen(buffer);cur_pos = 0;// 讀取字符c = buffer[cur_pos++];}// 否則文件結束，讀取的字符為EOFelse {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;}// 如果讀取字符為<，那么下一狀態為小于等于符號狀態else if (c == '<') {fsm_state = STATE_LESS;}// 如果讀取字符為'，那么下一狀態為字符串狀態else if (c == '\'') {fsm_state = STATE_STR;}// 如果讀取字符為空格、制表或回車，那么跳過這個字符，不保存else if (c == ' ' || c == '\t' || c == '\n') {is_save_char = false;}// 如果讀取到的是其它字符else {fsm_state = STATE_SUCCESS;switch (c) {// 如果讀到的是特殊符號，那么設置token的type為相應類型case '=':cur_token_type = SYM_EQUAL;break;case ';':cur_token_type = SYM_SEMICOLON;break;case ',':cur_token_type = SYM_COMMA;break;case '(':cur_token_type = SYM_LEFT_PARENTHESES;break;case ')':cur_token_type = SYM_RIGHT_PARENTHESES;break;case '+':cur_token_type = SYM_ADD;break;case '-':cur_token_type = SYM_SUB;break;case '*':cur_token_type = SYM_MUL;break;case '/':cur_token_type = SYM_DIV;break;// 如果讀到文件結束符case EOF:// 不保存字符，且設置token類型為文件結束is_save_char = false;cur_token_type = ENDOFFILE;break;// 如果讀到非法字符default:// 識別失敗，不保存字符，設置token為錯誤類型fsm_state = STATE_FAILED;is_save_char = false;cur_token_type = ERROR;cur_token_val = errors[ERROR_ILLEGAL_SYMBOL].error_message + c;}}break;// 注釋狀態case STATE_COMMENT:// 不保存字符，除左大括號、右大括號、文件結束符外的其它字符不處理is_save_char = false;// 如果讀到文件結束符，那么說明注釋沒有右大括號，識別失敗，設置錯誤類型if (c == EOF) {fsm_state = STATE_FAILED;cur_token_type = ERROR;cur_token_val = errors[ERROR_COMMENTS_RIGHT_BRACE_MISSING].error_message;back_to_last_pos(isEOF, cur_pos);}// 如果讀取字符為{，因為處在注釋狀態，說明存在大括號嵌套，識別失敗，設置錯誤類型else if (c == '{') {left_brace_num++;fsm_state = STATE_FAILED;cur_token_type = ERROR;cur_token_val = errors[ERROR_COMMENTS_LEFT_BRACE_SURPLUS].error_message;}// 如果讀取字符為}，那么退出注釋狀態，下一狀態為開始狀態，設置保存的左大括號數為0else if (c == '}') {fsm_state = STATE_START;left_brace_num = 0;}break;// 數字狀態case STATE_NUM:// 字母不能緊接數字，識別失敗，設置錯誤類型if (isalpha(c)) {fsm_state = STATE_FAILED;is_save_char = false;cur_token_type = ERROR;cur_token_val = errors[ERROR_LETTER_AFTER_NUMBER].error_message;back_to_last_pos(isEOF, cur_pos);}// 識別到其它字符，說明之前識別數字成功，設置token，回退一個位置再來識別else if (!isdigit(c)) {fsm_state = STATE_SUCCESS;is_save_char = false;cur_token_type = NUM;back_to_last_pos(isEOF, cur_pos);}break;// 標識符狀態case STATE_ID:// 識別的字符不是數字或字母，說明之前識別標識符成功，設置token，回退一個位置再來識別if (!isdigit(c) && !isalpha(c)) {fsm_state = STATE_SUCCESS;is_save_char = false;cur_token_type = ID;back_to_last_pos(isEOF, cur_pos);}break;// 賦值符號狀態case STATE_ASSIGN:// 之前識別的字符是:，之后識別的字符是=，那么識別成功，設置當前tokenif (c == '=') {fsm_state = STATE_SUCCESS;cur_token_type = SYM_ASSIGN;}// 之前識別的字符是:，之后識別的字符為其它，那么識別失敗，設置錯誤類型else {fsm_state = STATE_FAILED;is_save_char = false;cur_token_type = ERROR;cur_token_val = errors[ERROR_ASSIGN_SYMBOL_MISSING].error_message;back_to_last_pos(isEOF, cur_pos);}break;// 大于符號狀態或大于等于符號狀態case STATE_GREATER:fsm_state = STATE_SUCCESS;// 之前識別的字符為>，之后識別的字符為=，識別到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類型為小于等于if (c == '=') {cur_token_type = SYM_LESS_EQUAL_THAN;}// 之前識別的字符為<，之后識別的字符為其它，之前識別到的token類型為小于，回退一個位置再來識別else {cur_token_type = SYM_LESS_THAN;is_save_char = false;back_to_last_pos(isEOF, cur_pos);}break;// 字符串狀態case STATE_STR:// 識別到右單引號，識別成功，設置tokenif (c == '\'') {fsm_state = STATE_SUCCESS;cur_token_type = STRING;}// 識別到換行或文件結束，字符串不完整，識別失敗，設置錯誤類型else if (c == '\n' || c == EOF) {fsm_state = STATE_FAILED;cur_token_type = ERROR;cur_token_val = errors[ERROR_STRING_SINGLE_QUOTES_MISSING].error_message;back_to_last_pos(isEOF, cur_pos);}case STATE_SUCCESS:case STATE_FAILED:break;}// 如果識別到的字符要保存，那么拼接進當前token的值if (is_save_char) {cur_token_val += c;}}// 如果最后識別成功if (fsm_state == STATE_SUCCESS) {// 如果token的值在關鍵字表中存在，存儲相應類型if (cur_token_type == ID) {cur_token_type = find_keyword_type(cur_token_val);}// 返回相應類型和值的tokenreturn Token(cur_token_type, cur_token_val);}// 識別失敗返回錯誤類型else {return Token(ERROR, cur_token_val);} }

對于詞法分析過程中可能出現的錯誤，可以在getNextToken函數中對出現錯誤的地方進行識別，打印錯誤，并使用全局變量cur_line_num打印出錯行號，有可能出現的錯誤打印信息在error.h文件中定義：

enum ERROR_TYPE {// 詞法錯誤ERROR_STRING_SINGLE_QUOTES_MISSING, // 字符串的單引號有缺失ERROR_ILLEGAL_SYMBOL, // 非法符號ERROR_COMMENTS_LEFT_BRACE_MISSING, // 注釋缺少左大括號ERROR_COMMENTS_RIGHT_BRACE_MISSING, // 注釋缺少右大括號ERROR_COMMENTS_LEFT_BRACE_SURPLUS, // 注釋多了左大括號嵌套錯誤ERROR_LETTER_AFTER_NUMBER, // 字母后面緊接著數字ERROR_ASSIGN_SYMBOL_MISSING, // 賦值符號沒有打全 };struct {ERROR_TYPE error_code;string error_message; } errors[7] = {{ERROR_STRING_SINGLE_QUOTES_MISSING,"Missing single quote for string!"},{ERROR_ILLEGAL_SYMBOL,"Found an illegal symbol!"},{ERROR_COMMENTS_LEFT_BRACE_MISSING,"The left brace is missing!"},{ERROR_COMMENTS_RIGHT_BRACE_MISSING,"The right brace is missing!"},{ERROR_COMMENTS_LEFT_BRACE_SURPLUS,"An nested comment is found!"},{ERROR_LETTER_AFTER_NUMBER,"Numbers cannot be followed by letters!"},{ERROR_ASSIGN_SYMBOL_MISSING,"The assignment symbols are not complete!"} };

4. 打印Token

如果要打印所有Token，可以通過不斷調用getNextToken函數獲取每個Token，當獲取的Token類型為ENDOFFILE時，說明所有Token都已獲取完畢，即可退出：

// 按格式打印token void print_token(TokenType type, const char *cur_token_val) {switch (type) {case ID:printf("(ID, %s)\n", cur_token_val);break;case NUM:printf("(NUM, %s)\n", cur_token_val);break;case STRING:printf("(STR, %s)\n", cur_token_val);break;case KEY_WRITE: case KEY_READ: case KEY_IF:case KEY_THEN: case KEY_ELSE: case KEY_END:case KEY_STRING: case KEY_INT: case KEY_REPEAT:case KEY_UNTIL: case KEY_OR: case KEY_AND:case KEY_BOOL: case KEY_WHILE: case KEY_DO:printf("(KEYWORD, %s)\n", cur_token_val);break;case SYM_GREATER_THAN:printf("(SYM_GREATER_THAN, >)\n");break;case SYM_LESS_THAN:printf("(SYM_LESS_THAN, <)\n");break;case SYM_GREATER_EQUAL_THAN:printf("(SYM_GREATER_EQUAL_THAN, >=)\n");break;case SYM_LESS_EQUAL_THAN:printf("(SYM_LESS_EQUAL_THAN, <=)\n");break;case SYM_ASSIGN:printf("(SYM_ASSIGN, :=)\n");break;case SYM_EQUAL:printf("(SYM_EQUAL, =)\n");break;case SYM_SEMICOLON:printf("(SYM_SEMICOLON, ;)\n");break;case SYM_COMMA:printf("(SYM_COMMA, ,)\n");break;case SYM_LEFT_PARENTHESES:printf("(SYM_LEFT_PARENTHESES, ()\n");break;case SYM_RIGHT_PARENTHESES:printf("(SYM_RIGHT_PARENTHESES, ))\n");break;case SYM_ADD:printf("(SYM_ADD, +)\n");break;case SYM_SUB:printf("(SYM_SUB, -)\n");break;case SYM_MUL:printf("(SYM_MUL, *)\n");break;case SYM_DIV:printf("(SYM_DIV, /)\n");break;case ERROR:printf("Found an error at line %d: %s\n", cur_line_num, cur_token_val);break;default:printf("Illegel token: %d\n", type);} }// 打印所有token void print_all_tokens(FILE *fp) {while (true) {Token token = getNextToken(fp);if (token.type == ENDOFFILE) {break;}print_token(token.type, token.val.c_str());} }

測試報告

合法輸入測試1

test\test1.tny：

int A,B,C,D; while A<C and B>D doif A=1 then A:= B*C+37else repeat A:=A*2until A+C<=B+Dend end

進入tiny+文件夾目錄，在命令提示符中輸入：

g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/test1.tny token

可以看到：

生成詞法分析的Token序列到屏幕。

合法輸入測試2

test\test2.tny：

int x,fact; read x; if x>0 and x<100 then {don't compute if x<=0}fact:=1;while x>0 dofact:=fact*x;x:=x-1end;write fact end

進入tiny+文件夾目錄，在命令提示符中輸入：

g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/test2.tny token > 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, // writeKEY_READ, // readKEY_IF, // ifKEY_THEN, // thenKEY_ELSE, // elseKEY_END, // endKEY_STRING, // stringKEY_INT, // intKEY_REPEAT, // repeatKEY_UNTIL, // untilKEY_OR, // orKEY_AND, // andKEY_BOOL, // boolKEY_WHILE, // whileKEY_DO, // do// 特殊符號SYM_GREATER_THAN, // >SYM_LESS_THAN, // <SYM_GREATER_EQUAL_THAN, // >=SYM_LESS_EQUAL_THAN, // <= SYM_ASSIGN, // :=SYM_EQUAL, // =SYM_SEMICOLON, // ;SYM_COMMA, // ,SYM_LEFT_PARENTHESES, // (SYM_RIGHT_PARENTHESES, // )SYM_ADD, // +SYM_SUB, // -SYM_MUL, // *SYM_DIV, // /// 文件結束ENDOFFILE,// 出現錯誤ERROR};

利用token的不同類型和值，可以進行構建語法樹。

3.2 語法樹的結點類型：

根據TINY+語法的EBNF定義，可以按照推導規則大致為其構建語法樹的結點：

// 樹的結點類型 enum NodeType {PROGRAM, // 程序DECLARATIONS, // 聲明STMT_SEQUENCE, // 語句序列// statement語句WHILE_STMT, // while語句IF_STMT, // if語句REPEAT_STMT, // repeat語句ASSIGN_STMT, // assign語句READ_STMT, // read語句WRITE_STMT, // write語句// expression表達式GREATER_THAN_EXPR, // 大于表達式LESS_THAN_EXPR, // 小于表達式GREATER_EQUAL_THAN_EXPR, // 大于等于表達式LESS_EQUAL_THAN_EXPR, // 小于等于表達式EQUAL_EXPR, // 等于表達式OR_EXPR, // 或表達式 AND_EXPR, // 與表達式NOT_EXPR, // 非表達式ADD_EXPR, // 加法表達式SUB_EXPR, // 減法表達式MUL_EXPR, // 乘法表達式DIV_EXPR, // 除法表達式FACTOR // 因子 };

并為每種結點構造其的生成方法：

// 生成程序結點，program -> 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) {// 獲取第一個tokenToken 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<TokenType> 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 GREATER_EQUAL_THAN_EXPR:printf("EXP LogOp: (Symbol, >=)\n");break;case LESS_EQUAL_THAN_EXPR:printf("EXP LogOp: (Symbol, <=)\n");break;case EQUAL_EXPR:printf("EXP LogOp: (Symbol, ==)\n");break;case OR_EXPR:printf("EXP LogOp: (Key, or)\n");break;case AND_EXPR:printf("EXP LogOp: (Key, and)\n");break;case NOT_EXPR:printf("EXP LogOp: (Key, not)\n");break;case ADD_EXPR:printf("EXP CalOp: (Symbol, +)\n");break;case SUB_EXPR:printf("EXP CalOp: (Symbol, -)\n");break;case MUL_EXPR:printf("EXP CalOp: (Symbol, *)\n");break;case DIV_EXPR:printf("EXP CalOp: (Symbol, /)\n");break;case FACTOR:if (root->token) {TokenType type = root->token->type;switch (type) {case ID:printf("ID: %s\n", root->token->val.c_str());break;case NUM:printf("NUM: %s\n", root->token->val.c_str());break;case STRING:printf("STR: \'%s\'\n", root->token->val.c_str());break;default:break;}}break;default:printf("Illegal node\n");break;}// 遞歸打印存在的孩子結點for (int i = 0; i < 3; i++) {if (root->child[i]) {print_syntax_tree(root->child[i]);}}}// 如果結點不是語句序列結點，打印結束返回時減去縮進if (root->node_type != STMT_SEQUENCE) {space_num -= PER_TAB_SPACE_NUM;} }

通過遞歸打印語法樹，并通過每行前的空格數區分每個結點與他的子結點，最后完成打印。

測試報告

合法輸入測試1

test\test1.tny：

int A,B,C,D; while A<C and B>D doif A=1 then A:= B*C+37else repeat A:=A*2until A+C<=B+Dend end

進入tiny+文件夾目錄，在命令提示符中輸入：

g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/test1.tny tree

可以看到：

生成語法樹。

合法輸入測試2

test\test2.tny：

int x,fact; read x; if x>0 and x<100 then {don't compute if x<=0}fact:=1;while x>0 dofact:=fact*x;x:=x-1end;write fact end

進入tiny+文件夾目錄，在命令提示符中輸入：

g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/test2.tny tree

可以看到：

生成語法樹。

語法錯誤測試

test\illegal_input.tny：

int A,B,C,D; int; while (A<C) and B>D doif (A=1 then A:= B*C+37else repeat A:=A*2until A+C<=B+DendA:=BA=Cif A:=2then A:=Bend end

注釋掉語義檢查的代碼之后，進入tiny+文件夾目錄，在命令提示符中輸入：

g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/syntax_illegal_input.tny tree

可以看到：

第2行存在標識符錯誤，程序變量聲明中，關鍵字int后面沒有跟隨標識符，提示存在語法錯誤。

第4行存在括號不匹配錯誤，只有左括號，沒有右括號，提示存在語法錯誤。

第9行存在符號錯誤，賦值語句A:=C中，要求使用的正確符號是:=，而不是=，提示存在語法錯誤。

第10行存在符號錯誤，關系比較表達式if A=2中，要求使用的正確符號是=，而不是:=，提示存在語法錯誤。

語義分析程序及中間代碼生成實驗報告

實現過程

1. 語義分析

語義分析在語法分析的過程中一起實現，在errors.h文件中，定義了語義分析過程中有可能發現的一些錯誤：

enum ERROR_TYPE {// 詞法錯誤ERROR_STRING_SINGLE_QUOTES_MISSING, // 字符串的單引號有缺失ERROR_ILLEGAL_SYMBOL, // 非法符號ERROR_COMMENTS_LEFT_BRACE_MISSING, // 注釋缺少左大括號ERROR_COMMENTS_RIGHT_BRACE_MISSING, // 注釋缺少右大括號ERROR_COMMENTS_LEFT_BRACE_SURPLUS, // 注釋多了左大括號嵌套錯誤ERROR_LETTER_AFTER_NUMBER, // 字母后面緊接著數字ERROR_ASSIGN_SYMBOL_MISSING, // 賦值符號沒有打全// 語法錯誤ERROR_SYNTAX,// 語義錯誤ERROR_IDENTIFIER_WITHOUT_DECLARATION, // 一個標識符沒有聲明就使用ERROR_DECLARE_MORE_THEN_ONCE, // 一個標識符被不止一次聲明ERROR_COND_TYPE_NOT_BOOL, // 條件表達式的類型不是bool類型ERROR_OPERATION_NOT_EQUAL_TYPE, // 一個二元操作符的兩個操作數類型不相等ERROR_ASSIGN_NOT_EQUAL_TYPE // 賦值語句左右部類型不相等 };struct {ERROR_TYPE error_code;string error_message; } errors[13] = {{ERROR_STRING_SINGLE_QUOTES_MISSING,"Missing single quote for string!"},{ERROR_ILLEGAL_SYMBOL,"Found an illegal symbol!"},{ERROR_COMMENTS_LEFT_BRACE_MISSING,"The left brace is missing!"},{ERROR_COMMENTS_RIGHT_BRACE_MISSING,"The right brace is missing!"},{ERROR_COMMENTS_LEFT_BRACE_SURPLUS,"An nested comment is found!"},{ERROR_LETTER_AFTER_NUMBER,"Numbers cannot be followed by letters!"},{ERROR_ASSIGN_SYMBOL_MISSING,"The assignment symbols are not complete!"},{ERROR_SYNTAX,"There is a syntax error!"},{ERROR_IDENTIFIER_WITHOUT_DECLARATION,"There is an identifier that is used without declaration"},{ERROR_DECLARE_MORE_THEN_ONCE,"One identifier can not be decalred more than once!"},{ERROR_COND_TYPE_NOT_BOOL,"The type of the conditional expression is not bool!"},{ERROR_OPERATION_NOT_EQUAL_TYPE,"Two operation number's types are not equal!"},{ERROR_ASSIGN_NOT_EQUAL_TYPE,"The left and right types of assignment statement are not equal"} };

然后在語法分析中，順便檢測是否有發生了語義錯誤，比如在生成declarations結點的方法SyntaxTreeNode *declarations(FILE *fp, Token & cur_token)中，獲取token之后，如果這個token為標識符類型且其值在符號表中可以找到，說明之前聲明過，那么拋出重復聲明錯誤：

Token identifier = getNextToken(fp); cur_token = identifier; if (check_and_get_next(fp, cur_token, ID)) {// 如果一個標識符被聲明不止一次，那么報錯if (symbol_table.find(identifier.val)) {print_sematic_error(ERROR_DECLARE_MORE_THEN_ONCE);}...

在生成while_stmt結點和if_stmt結點的方法中，如果條件表達式的類型不是bool類型，直接報錯：

if (bool_exp->value_type != VALTYPE_BOOL) {print_sematic_error(ERROR_COND_TYPE_NOT_BOOL); }

在生成assign_stmt結點和生成factor結點的方法中，如果一個標識符沒有聲明就使用，那么報錯：

if (identifier_symbol == nullptr) {print_sematic_error(ERROR_IDENTIFIER_WITHOUT_DECLARATION); }if ((identifier_symbol = symbol_table.find(identifier_key)) == nullptr) {// 一個標識符沒有聲明就使用print_sematic_error(ERROR_IDENTIFIER_WITHOUT_DECLARATION);node1->value_type = VALTYPE_INT; }

在生成assign_stmt結點和生成factor結點的方法中，如果賦值語句左右部類型不相等，那么報錯：

if (identifier_symbol->value_type != exp->value_type) {print_sematic_error(ERROR_ASSIGN_NOT_EQUAL_TYPE); }

在生成comparison_exp結點、生成or_exp結點和生成and_exp結點的方法中，如果賦值語句左右部類型不相等，那么報錯：

if (comparison_expr->value_type != arithmetic_exp->value_type) {print_sematic_error(ERROR_OPERATION_NOT_EQUAL_TYPE); }if (and_expr->value_type != VALTYPE_BOOL || or_expr->value_type != VALTYPE_BOOL) {print_sematic_error(ERROR_OPERATION_NOT_EQUAL_TYPE); }

2. 生成中間代碼

2.1 定義使用到的數據結構

定義中間代碼類型：

// 中間代碼類型 enum MiddleCodeType {MID_CODE_TYPE_READ, // readMID_CODE_TYPE_WRITE, // writeMID_CODE_TYPE_LABEL, // labelMID_CODE_TYPE_IF, // ifMID_CODE_TYPE_GOTO, // gotoMID_CODE_TYPE_ASSIGN, // assignMID_CODE_TYPE_ADD, // addMID_CODE_TYPE_SUB, // subMID_CODE_TYPE_MUL, // mulMID_CODE_TYPE_DIV // div };

定義中間代碼結構體：

// 中間代碼結構體 struct MiddleCode {MiddleCodeType mcode_type; // 中間代碼類型string result; // 唯一結果參數string first_arg; // 第一個參數string second_arg; // 第二個參數MiddleCode(MiddleCodeType mcode_type, const string &first_arg = "", const string &second_arg = "", const string &result = "") : mcode_type(mcode_type), first_arg(first_arg), second_arg(second_arg), result(result) {}// 獲取中間代碼的字符串string get_middle_code_str() {switch (mcode_type) {case MID_CODE_TYPE_READ:return "read " + result;case MID_CODE_TYPE_WRITE:return "write " + result;case MID_CODE_TYPE_LABEL:return "Label L" + result;case MID_CODE_TYPE_IF:return "if " + first_arg + " goto L" + result;case MID_CODE_TYPE_GOTO:return "goto L" + result;case MID_CODE_TYPE_ASSIGN:return result + ":=" + first_arg;case MID_CODE_TYPE_ADD:return result + ":=" + first_arg + "+" + second_arg;case MID_CODE_TYPE_SUB:return result + ":=" + first_arg + "-" + second_arg;case MID_CODE_TYPE_MUL:return result + ":=" + first_arg + "*" + second_arg;case MID_CODE_TYPE_DIV:return result + ":=" + first_arg + "/" + second_arg;default:return "";}} };

定義分析棧中的結點：

// 分析棧中的結點 struct AnalyzingStackNode {SyntaxTreeNode *syntax_tree_node; // 語法樹結點string tk_val; // 對應的token的值AnalyzingStackNode(SyntaxTreeNode *syntax_tree_node, string tk_val) : syntax_tree_node(syntax_tree_node), tk_val(tk_val) {} };

定義跳轉指令列表：

// 跳轉指令列表類型 enum JumpInsListType {JUMP_INS_TYPE_TRUE_LIST,JUMP_INS_TYPE_FALSE_LIST,JUMP_INS_TYPE_NEXT_LIST };// 跳轉指令列表 struct JumpInsList {vector<map<SyntaxTreeNode *, vector<int>>> jump_ins_list_map;vector<MiddleCode> middle_codes;JumpInsList() {jump_ins_list_map.resize(3);}// 設置列表void set_jump_ins_list(JumpInsListType list_type, SyntaxTreeNode *node, vector<int> list) {jump_ins_list_map[list_type][node] = list;}// 獲取列表vector<int> get_jump_ins_list(JumpInsListType list_type, SyntaxTreeNode *node) {return jump_ins_list_map[list_type][node];}// 創建一個只包含i的列表void make_jump_ins_list(JumpInsListType list_type, SyntaxTreeNode *node, int i) {jump_ins_list_map[list_type][node] = vector<int>();jump_ins_list_map[list_type][node].push_back(i);}// 合并列表vector<int> merge_jump_ins_list(JumpInsListType list_type, SyntaxTreeNode *node1, SyntaxTreeNode *node2) {vector<int> list1 = jump_ins_list_map[list_type][node1];vector<int> list2 = jump_ins_list_map[list_type][node2];list1.insert(list1.end(), list2.begin(), list2.end());return list1;}// 回填操作void backpatching(JumpInsListType list_type, SyntaxTreeNode *node, int targetIndex) {for (auto &i : jump_ins_list_map[list_type][node]) {// 設置填的goto語句的終點middle_codes[i].result = to_string(targetIndex);}}// 中間代碼優化void optimize_middle_codes() {map<string, int> label_goto;int size = middle_codes.size();// 刪除沒有被goto到的labelfor (int i = 0; i < size; i++) {if (middle_codes[i].mcode_type == MID_CODE_TYPE_IF || middle_codes[i].mcode_type == MID_CODE_TYPE_GOTO) {label_goto[middle_codes[i].result]++;}}// 倒序刪除多余的goto語句for (int i = size - 1; i >= 0; i--) {if (middle_codes[i].mcode_type == MID_CODE_TYPE_LABEL) {if (label_goto.count(middle_codes[i].result) == 0) {middle_codes.erase(middle_codes.begin() + i);}}}// 刪除goto和同一個label緊接的語句塊for (int i = size - 1; i >= 1; i--) {if (middle_codes[i].mcode_type == MID_CODE_TYPE_LABEL && middle_codes[i - 1].mcode_type == MID_CODE_TYPE_GOTO &&middle_codes[i].result == middle_codes[i - 1].result && label_goto[middle_codes[i].result] == 1) {middle_codes.erase(middle_codes.begin() + i);middle_codes.erase(middle_codes.begin() + i - 1);i--;}}} };

2.2 生成中間代碼

可以使用遞歸的方法來生成中間代碼：

// 生成中間代碼 void generate_middle_code(SyntaxTreeNode *root, int & label_num, int & t_num) {// 如果語法樹的根結點為空，直接返回if (root == nullptr) {return;}SyntaxTreeNode *child1 = root->child[0];SyntaxTreeNode *child2 = root->child[1];SyntaxTreeNode *child3 = root->child[2];// 拉鏈回填兒子結點SyntaxTreeNode *backpatching_child1;SyntaxTreeNode *backpatching_child2;string first_arg, second_arg, result_str, temp;// 拉鏈回填序號int backpatching_index;// 拉鏈回填合并列表vector<int> merge_list;// 對于repeat語句，前面要加labelif (root->node_type == REPEAT_STMT) {push_list(MID_CODE_TYPE_LABEL, to_string(++label_num));label_start[root] = label_num;}// 遞歸生成中間代碼generate_middle_code(child1, label_num, t_num);// 對于if語句，它的then和else語句加labelif (root->node_type == IF_STMT || root->node_type == WHILE_STMT) {push_list(MID_CODE_TYPE_LABEL, to_string(++label_num));label_start[child2] = label_num;}// 遞歸生成中間代碼generate_middle_code(child2, label_num, t_num);if (root->node_type == IF_STMT) {// 有else子句那么在then子句后面加goto并且回填，使else子句不要緊跟then后面執行if (child3) {int next_index = push_list(MID_CODE_TYPE_GOTO, "dest");jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_NEXT_LIST, root, next_index);}push_list(MID_CODE_TYPE_LABEL, to_string(++label_num));label_else[root] = label_num;}// 對于while語句，它的執行語句后面要加goto，指向判斷前面，后面加上labelelse if (root->node_type == WHILE_STMT) {//WHILE語句需要再執行語句緊接一個GOTO，指向判斷前面int next_index = push_list(MID_CODE_TYPE_GOTO, "dest");jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_NEXT_LIST, child2, next_index);push_list(MID_CODE_TYPE_LABEL, to_string(++label_num));label_end[root] = label_num;}// 對于repeat語句，它的后面要加labelelse if (root->node_type == REPEAT_STMT) {push_list(MID_CODE_TYPE_LABEL, to_string(++label_num));label_end[root] = label_num;}// 遞歸生成中間代碼generate_middle_code(child3, label_num, t_num);if (root->node_type == IF_STMT) {// 對于else子句，后面加一個label，then子句的next指向這個labelif (child3) {push_list(MID_CODE_TYPE_LABEL, to_string(++label_num));jump_ins_list.backpatching(JUMP_INS_TYPE_NEXT_LIST, root, label_num);}}int node_type = root->node_type;switch (node_type) {case WHILE_STMT:// 獲取回填兒子結點backpatching_child1 = root->child[0];backpatching_child2 = root->child[1];// 進行回填jump_ins_list.backpatching(JUMP_INS_TYPE_TRUE_LIST, backpatching_child1, label_start[backpatching_child1]);jump_ins_list.backpatching(JUMP_INS_TYPE_FALSE_LIST, backpatching_child1, label_end[root]);jump_ins_list.backpatching(JUMP_INS_TYPE_NEXT_LIST, backpatching_child2, label_start[backpatching_child1]);break;case IF_STMT:// 獲取回填兒子結點backpatching_child1 = root->child[0];backpatching_child2 = root->child[1];// 進行回填jump_ins_list.backpatching(JUMP_INS_TYPE_TRUE_LIST, backpatching_child1, label_start[backpatching_child2]);jump_ins_list.backpatching(JUMP_INS_TYPE_FALSE_LIST, backpatching_child1, label_else[root]);break;case REPEAT_STMT:// 獲取回填兒子結點backpatching_child1 = root->child[0];backpatching_child2 = root->child[1];// 進行回填jump_ins_list.backpatching(JUMP_INS_TYPE_FALSE_LIST, backpatching_child2, label_start[root]);jump_ins_list.backpatching(JUMP_INS_TYPE_TRUE_LIST, backpatching_child2, label_end[root]);break; case ASSIGN_STMT:// 賦值語句只要彈出一個元素first_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();// 獲取賦值變量result_str = root->token->val;push_list(MID_CODE_TYPE_ASSIGN, result_str, first_arg);break;case READ_STMT:// 直接讀取對象result_str = root->token->val;push_list(MID_CODE_TYPE_READ, result_str);break;case WRITE_STMT:// 如果root的孩子不是factor，說明是表達式，彈出一個元素中間變量if (root->child[0]->node_type != FACTOR) {result_str = analyzing_stack.top().tk_val;analyzing_stack.pop();}// 如果root的孩子不是factor，那么直接讀factor的變量名else {result_str = root->child[0]->token->val;}push_list(MID_CODE_TYPE_WRITE, result_str);break;case GREATER_THAN_EXPR:// 先輸出labelresult_str = to_string(++label_num);push_list(MID_CODE_TYPE_LABEL, result_str);label_start[root] = label_num;// 從棧中彈出元素temp = ">" + analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val + temp;analyzing_stack.pop();result_str = "dest";backpatching_index = push_list(MID_CODE_TYPE_IF, result_str, first_arg);push_list(MID_CODE_TYPE_GOTO, "dest");// 進行拉鏈回填jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, root, backpatching_index);jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, root, backpatching_index + 1);break;case LESS_THAN_EXPR:// 先輸出labelresult_str = to_string(++label_num);push_list(MID_CODE_TYPE_LABEL, result_str);label_start[root] = label_num;// 從棧中彈出元素temp = "<" + analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val + temp;analyzing_stack.pop();result_str = "dest";backpatching_index = push_list(MID_CODE_TYPE_IF, result_str, first_arg);push_list(MID_CODE_TYPE_GOTO, "dest");// 進行拉鏈回填jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, root, backpatching_index);jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, root, backpatching_index + 1);break;case GREATER_EQUAL_THAN_EXPR:// 先輸出labelresult_str = to_string(++label_num);push_list(MID_CODE_TYPE_LABEL, result_str);label_start[root] = label_num;// 從棧中彈出元素temp = ">=" + analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val + temp;analyzing_stack.pop();result_str = "dest";backpatching_index = push_list(MID_CODE_TYPE_IF, result_str, first_arg);push_list(MID_CODE_TYPE_GOTO, "dest");// 進行拉鏈回填jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, root, backpatching_index);jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, root, backpatching_index + 1);break;case LESS_EQUAL_THAN_EXPR:// 先輸出labelresult_str = to_string(++label_num);push_list(MID_CODE_TYPE_LABEL, result_str);label_start[root] = label_num;// 從棧中彈出元素temp = "<=" + analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val + temp;analyzing_stack.pop();result_str = "dest";backpatching_index = push_list(MID_CODE_TYPE_IF, result_str, first_arg);push_list(MID_CODE_TYPE_GOTO, "dest");// 進行拉鏈回填jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, root, backpatching_index);jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, root, backpatching_index + 1);break;case EQUAL_EXPR:// 先輸出labelresult_str = to_string(++label_num);push_list(MID_CODE_TYPE_LABEL, result_str);// 輸出labellabel_end[root] = label_num;// 從棧中彈出元素temp = "=" + analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val + temp;analyzing_stack.pop();result_str = "dest";backpatching_index = push_list(MID_CODE_TYPE_IF, result_str, first_arg);push_list(MID_CODE_TYPE_GOTO, "dest");// 進行拉鏈回填jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, root, backpatching_index);jump_ins_list.make_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, root, backpatching_index + 1);break;case AND_EXPR:// 獲取回填兒子結點backpatching_child1 = root->child[0];backpatching_child2 = root->child[1];// 輸出labellabel_start[root] = label_start[backpatching_child1];// 進行回填jump_ins_list.backpatching(JUMP_INS_TYPE_TRUE_LIST, backpatching_child1, label_start[backpatching_child2]);merge_list = jump_ins_list.merge_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, backpatching_child1, backpatching_child2);jump_ins_list.set_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, root, merge_list);jump_ins_list.set_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, root, jump_ins_list.get_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, backpatching_child2));break;case OR_EXPR:// 獲取回填兒子結點backpatching_child1 = root->child[0];backpatching_child2 = root->child[1];label_start[root] = label_start[backpatching_child1];// 進行回填jump_ins_list.backpatching(JUMP_INS_TYPE_FALSE_LIST, backpatching_child1, label_start[backpatching_child2]);merge_list = jump_ins_list.merge_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, backpatching_child1, backpatching_child2);jump_ins_list.set_jump_ins_list(JUMP_INS_TYPE_TRUE_LIST, root, merge_list);jump_ins_list.set_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, root, jump_ins_list.get_jump_ins_list(JUMP_INS_TYPE_FALSE_LIST, backpatching_child2));break;case ADD_EXPR:// 彈出前兩個元素second_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();// 獲取t前綴的符號名result_str = "t" + to_string(t_num++);// 保存中間結果push_list(MID_CODE_TYPE_ADD, result_str, first_arg, second_arg);analyzing_stack.push(AnalyzingStackNode(root, result_str));break;case SUB_EXPR:// 彈出前兩個元素second_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();// 獲取t前綴的符號名result_str = "t" + to_string(t_num++);// 保存中間結果push_list(MID_CODE_TYPE_SUB, result_str, first_arg, second_arg);analyzing_stack.push(AnalyzingStackNode(root, result_str));break;case MUL_EXPR:// 彈出前兩個元素second_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();// 獲取t前綴的符號名result_str = "t" + to_string(t_num++);// 保存中間結果push_list(MID_CODE_TYPE_MUL, result_str, first_arg, second_arg);analyzing_stack.push(AnalyzingStackNode(root, result_str));break;case DIV_EXPR:// 彈出前兩個元素second_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();first_arg = analyzing_stack.top().tk_val;analyzing_stack.pop();// 獲取t前綴的符號名result_str = "t" + to_string(t_num++);// 保存中間結果push_list(MID_CODE_TYPE_DIV, result_str, first_arg, second_arg);analyzing_stack.push(AnalyzingStackNode(root, result_str));break;case FACTOR:if (root->token) {int token_type = root->token->type;switch (token_type) {case ID:analyzing_stack.push(AnalyzingStackNode(root, root->token->val));break;case NUM:analyzing_stack.push(AnalyzingStackNode(root, root->token->val));break;case STRING:analyzing_stack.push(AnalyzingStackNode(root, "\'" + root->token->val + "\'"));break;}}break;} }

3. 打印符號表

打印符號表由SymbolTable符號表中的print_symbol_table方法實現：

// 打印符號表 void print_symbol_table() {printf("Variable | ObjectType | ValueType\n---------------------------------\n");for (auto &symbol : symbol_table) {printf("%-9s|", symbol.first.c_str());switch(symbol.second->object_type) {case OBJTYPE_FUNC:printf("Func |");break;case OBJTYPE_VAR:printf("Var |");break;case OBJTYPE_CONST:printf("Const |");break;default:break;}switch(symbol.second->value_type) {case VALTYPE_INT:printf("Int\n");break;case VALTYPE_BOOL:printf("Bool\n");break;case VALTYPE_STR:printf("Str\n");break;default:break;}}printf("\n"); }

2.3 生成中間代碼后與符號表一起進行打印

生成并打印中間代碼與打印符號表：

// 生成并打印中間代碼 void generate_and_print_middle_code(FILE *fp, bool is_optimize) {// 獲取語法樹的根結點SyntaxTreeNode *root = create_syntax_tree(fp);// 初始化label前綴和t前綴的序號int label_num = 0;int t_num = 0;// 生成中間代碼generate_middle_code(root, label_num, t_num);// 根據選項決定是否要優化if (is_optimize) {jump_ins_list.optimize_middle_codes();}// 打印符號表symbol_table.print_symbol_table();// 打印三地址中間代碼int size = jump_ins_list.middle_codes.size();for (int i = 0; i < size; ++i) {printf("(%d) %s\n", i + 1, jump_ins_list.middle_codes[i].get_middle_code_str().c_str());} }

在輸入命令時，可以根據選擇了優化的選項，對中間代碼進行一定的優化。

測試報告

合法輸入測試1

test\test1.tny：

int A,B,C,D; while A<C and B>D doif A=1 then A:= B*C+37else repeat A:=A*2until A+C<=B+Dend end

進入tiny+文件夾目錄，在命令提示符中輸入：

g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/test1.tny

可以看到：

符號表和三地址中間代碼都被打印出來。

在命令提示符中輸入優化指令：

a test/test1.tny optimize

可以看到：

原來總計的28行的三地址中間代碼被優化為25行，減少了一些。

合法輸入測試2

test\test2.tny：

int x,fact; read x; if x>0 and x<100 then {don't compute if x<=0}fact:=1;while x>0 dofact:=fact*x;x:=x-1end;write fact end

進入tiny+文件夾目錄，在命令提示符中輸入：

g++ main.cpp lexical.cpp syntax.cpp generation.cpp a test/test2.tny

可以看到：

符號表和三地址中間代碼都被打印出來。

在命令提示符中輸入優化指令：

a test/test2.tny optimize

可以看到：

原來的21行的三地址中間代碼被優化為19行，減少了一些。

語義錯誤測試

test\sematic_illegal_input.tny：

int A,B,C,D; int x,x;string z; z:=1;if A>z thenA:=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沒有聲明就被使用了。

總結

以上是生活随笔為你收集整理的使用C++对TINY+语言进行词法分析、语法分析、语义分析和中间代码生成的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。