編譯原理課程設計實驗報告

1、編譯原理課程設計實驗報告實驗目的：這個實驗的目的是構造C minus語言的編譯器，要求能夠編譯C minus語言的程序并且生成中間代碼。在實驗的過程中，學會使用flex/bison這兩個重要的工具。實驗內容： 參見教材 p491 appendix A.設計一cminus語言編譯器語言介紹。Decaf（cminus）語言的關鍵字：int while if else return void運算符：+ - * / > < = , . != <= >= = () C minus語言的限制。數字：支持10進制整數。小數可以采用科學記數法，如1E3也是合法的。字符串：字符串內部不允

2、許出現換行，即字符串變量必須在同一行內。注釋：C minus語言允許采用/*/注釋，并且注釋不可以嵌套，即下面的注釋是不合法的：/*This is /*a valid */comment*/程序流程圖開始詞法分析語法分析建立符號表類型檢查代碼生成結束語法樹符號表程序的流程參照了書本TINY編譯器的實例程序：語法分析器(Parser)調用詞法分析器得到符合詞法的字，建立語法樹；符號表通過對語法樹的分析，建立符號表，同時檢查變量未定義等錯誤；類型檢查包括檢查表達式兩邊是否匹配，函數參數是否匹配等等；經由上述步驟而未出錯的源程序被認為是合法程序，然后代碼生成通過語法樹和符號表生成P Code中間代碼

3、，并將變量地址存入符號表。其中類型檢查和代碼生成不要求實現。本次實驗要求分組，一組五人，一人完成一個部分。本組實驗分組成員以及分工介紹：汪晨風：（設計并實現cminus符號表）；E02620105蔡其星：（編寫cminus.l文件，并用lex工具生成c代碼）；E02620107趙婷：（設計cminus語法樹結構）；E02620106馬培良：編寫cminus.y文件，并用yacc工具生成可執(zhí)行代碼）；E02620121丘廷：（進行程序的測試）以下為具體實驗分步報告以及過程：第一部分：設計cminus符號表符號表是編譯器中的主要繼承屬性，并且在語法樹之后，形成了主要的數據結構。符號表主要的操作有插

4、入、查找和刪除。雜湊表（hash表）通常為符號表的實現提供了最好的選擇，因為所有3種操作都能在幾乎恒定的時間內完成，在實踐中也是最常使用。該課程設計所用的C-符號表采用建立雜湊表的方法。雜湊表是一個入口數組，稱作“桶( b u c k e t )”，使用一個整數范圍的索引，通常從0到表的尺寸減1。雜湊函數(hash fuction)把索引鍵(在這種情況下是標識符名，組成一個字符串)轉換成索引范圍內的一個整數的雜湊值，對應于索引鍵的項存儲在這個索引的“桶”中。每個“桶”實際上又是一個線性表，通過把新的項插入到“桶”表中來解決沖突在任何情況下，“桶”數組的實際大小要選擇一個素數，因為這將使一般的雜

5、湊函數運行得更好。雜湊函數。在符號表實現中使用的雜湊函數將字符串(標識符名)轉換成0. . . s i z e- 1范圍內的一個整數。一般這通過3步來進行。首先，字符串中的每個字符轉換成一個非負整數。然后，這些整數用一定的方法組合形成一個整數。最后，把結果整數調整到0. . . s i z e- 1范圍內。沖突的一個好的解決辦法是，當加上下一個字符的值時，重復地使用一個常量作為乘法因子。因此，如果ci 是第i 個字符的數字值， hi 是在第i 步計算的部分雜湊值，那么hi 根據下面的遞歸公式計算，h0 = 0，hi 1 = ahi ci ，最后的雜湊值用h = hn m o d s i z e

6、計算。這里n 是雜湊的名字中字符的個數。這等價于下列公式當然，在這個公式中a的選擇對輸出結果有重要影響。a的一種合理的選擇是2的冪，如1 6或1 2 8，這樣乘法可以通過移位來完成。該程序a選16，s i z e 取211。由于在數據結構方面為了實現很方便的進行查找，插入，刪除等操作。我們把它的數據結構設計成一哈稀表結構，哈稀表的查找，插入等操作是飛快的。我們所設計的哈稀結構符號表是參考教科書上P295它的結構如下：符號表的雜湊函數#define SIZE 211#define SHIFT 4int hash ( char * key ) int temp = 0;int i = 0;whil

7、e (keyi != '0') temp = (temp << SHIFT) + keyi) % SIZE;+ + i ;return temp;該符號表完成了插入void st_insert( char * name, int lineno, int loc )、查找int st_lookup ( char * name )工作源程序：symtab.c#include <stdio.h>#include <stdlib.h>#include <string.h>#include "symtab.h"/* 定義

8、哈稀表的最大值 */#define SIZE 211/* SHIFT is the power of two used as multiplier in hash function */#define SHIFT 4/* 哈稀函數結構 */static int hash ( char * key ) int temp = 0; int i = 0; while (keyi != '0') temp = (temp << SHIFT) + keyi) % SIZE; +i; return temp;typedef struct LineListRec int line

9、no; struct LineListRec * next; * LineList;typedef struct BucketListRec char * name; LineList lines; int memloc ; /* memory location for variable */ struct BucketListRec * next; * BucketList;/* 哈稀表*/static BucketList hashTableSIZE; void st_insert( char * name, int lineno, int loc ) int h = hash(name)

10、; BucketList l = hashTableh; while (l != NULL) && (strcmp(name,l->name) != 0) l = l->next; if (l = NULL) /* variable not yet in table */ l = (BucketList) malloc(sizeof(struct BucketListRec); l->name = name; l->lines = (LineList) malloc(sizeof(struct LineListRec); l->lines->

11、lineno = lineno; l->memloc = loc; l->lines->next = NULL; l->next = hashTableh; hashTableh = l; else /* found in table, so just add line number */ LineList t = l->lines; while (t->next != NULL) t = t->next; t->next = (LineList) malloc(sizeof(struct LineListRec); t->next->

12、;lineno = lineno; t->next->next = NULL; int st_lookup ( char * name ) int h = hash(name); BucketList l = hashTableh; while (l != NULL) && (strcmp(name,l->name) != 0) l = l->next; if (l = NULL) return -1; else return l->memloc; void printSymTab(FILE * listing) int i; fprintf(li

13、sting,"Variable Name Location Line Numbersn"); fprintf(listing,"- - -n"); for (i=0;i<SIZE;+i) if (hashTablei != NULL) BucketList l = hashTablei; while (l != NULL) LineList t = l->lines; fprintf(listing,"%-14s ",l->name); fprintf(listing,"%-8d ",l->

14、memloc); while (t != NULL) fprintf(listing,"%4d ",t->lineno); t = t->next; fprintf(listing,"n"); l = l->next; /* printSymTab */symtab.h#ifndef _SYMTAB_H_#define _SYMTAB_H_void st_insert( char * name, int lineno, int loc ); /*插入函數*/int st_lookup ( char * name ); /*查找函數*/v

15、oid printSymTab(FILE * listing); /*用來打印哈稀表內容*/#endif 符號表設計的好壞直接影響到整個程序運行的速度，效率以及準確度。因為接下來的parse工作是基于符號表的，是從符號表里提取token進行語法分析的。為了提高程序運行的的效率，我們把scan直接通過parse來調用。具體的來講就是，程序運行時，首先進入parse部分，當parse要用到token時，調用scan部分掃描原文件生成token儲存在符號表中，并同時提供給parse進行語法分析。這樣就可以一遍完成整個原文件的掃描。第二部分：運用LEX實現cminus詞法分析程序。這一部比較關鍵，設計

16、的正確與否直接影響到在scan過程中token的產生。以及整個程序運行的結果的正確與否。在這里主要定義cminus的基本語法規(guī)則，以及token類型，運算符類型，并且定義cminus關鍵字，便于在程序運行時能對其進行識別。一下為cminus.l文件原代碼：/*定義全局變量、函數及包含文件說明：*/%#include "globals.h "#include "util.h"#include "scan.h "#define MAXTOKENLEN 40char tokenString40;int lineno = 0;%/*有關語法規(guī)

17、則以及token的定義:*/digit 0-9number digit+letter a-zA-Zidentifier letter+newline nwhitespace t+%/*以下為關鍵字定義:*/"if" return IF;"else" return ELSE;"int" return INT;"void" return VOID;"return" return RETURN;"while" return WHILE;/*以下為運算符號定義:*/"=&q

18、uot; return ASSIGN;"<=" return LTEQ;">=" return GTEQ;"<" return LT;">" return GT;"=" return EQ;"!=" return NOTEQ;"+" return PLUS;"-" return MINUS;"*" return TIMES;"/" return OVER;"(&q

19、uot; return LPAREN;")" return RPAREN;"" return LBRACK;"" return RBRACK;"" return LCURL;"" return RCURL;"" return SEMI;"," return COMMA;/*終結符及注釋符號*/number return NUM;identifier return ID;newline lineno+;whitespace /* skip whitespac

20、e */"/*" char c;char d; c = input(); if (c != EOF) do d = c; c = input(); if (c = EOF) break; if (c = 'n') lineno+; while (!(d = '*' && c = '/'); . return ERROR;%/*定義getToken()函數體:*/TokenType getToken(void) static int firstTime = TRUE; TokenType currentToken

21、; if (firstTime) firstTime = FALSE; lineno+; yyin = source; yyout = listing; currentToken = yylex(); strncpy(tokenString,yytext,MAXTOKENLEN); if (TraceScan) fprintf(listing,"t%d: ",lineno); printToken(currentToken,tokenString); return currentToken;說明：以上代碼已經能通過lex工具產生c代碼。cminus.l的設計基本結構是參考t

22、iny.l的結構設計而成，但要注意的是，由于在接下來的cnimus.y中所定義的語法規(guī)則不同，這里的也要稍做修改。比如在這里的getToken函數，要于cminus.y文件里的設計的返回參數要一一對應，否則在編譯的過程中會出現類型不匹配等等的錯誤，修改起來比較麻煩。 第三部分：為C-設計語法樹結構，使之適用于分析器產生語法樹是LALR分析的前提。因此在進行語法分析之前，必須設計語法樹結構，使接下來的語法分析有一個具體的數據結構。其代碼段如下：#define MAXTOKENSIZE 50typedef int TokenType; /*定義語法樹結構*/typedef struct Token

23、Type tok; char * tokString; TokenStruct;typedef enum IfK,WhileK,AssignK,ReturnK,CallK,VarDeclK,FunDeclK,OpK,ConstK,IdK NodeKind; /*枚舉結點類型*/typedef enum Void,Integer,Boolean ExpType; /*枚舉返回變量類型*/#define MAXCHILDREN 3 /*聲明一個結點最多有三個子結點*/typedef struct treeNode /*定義語法樹結點結構*/ struct treeNode * childMAXCH

24、ILDREN; struct treeNode * sibling; int lineno; NodeKind kind; union TokenType op; int val; char * name; attr; ExpType type; TreeNode; 說明：在這里當當只是設計的語法樹的基本數據結構，至于要用到parse過程中還要進行具體的修改，調試。這些工作都已經在程序原代碼調試過程中做好。第四部分：LALR分析。（使用yacc工具）這一部分完成了整個編譯過程中的語法分析，二異性沖突處理，lese懸掛問題的處理，運算符優(yōu)先級處理以及錯誤報告。參考課本P492 29條cminus

25、 BNF。并且通過細心理解體會，寫出了cminus.y文件，并能通過yacc生成c代碼。Cnimus.y代碼以及一些具體功能如下所述：一 YACC源程序的結構說明部分的內容如下：頭文件宏定義數據類型定義全局變量定義語法開始符定義語義值類型定義終結符定義運算符優(yōu)先級及結合性定義%#define YYPARSER /* distinguishes Yacc output from other code files */#include "globals.h"#include "util.h"#include "scan.h"#includ

26、e "parse.h"TreeNode * parseTree; /* stores syntax tree for later return */void yyerror (const char *s);%語法開始符號的定義start 非終結符注：若沒有上述說明，YACC自動將第一條語法規(guī)則左部的非終結符作為語法開始符。 語義值類型的定義%union定義語義值的類型;%union TreeNode * tnode; TokenType tok; %type定義文法符號的語義值類型; %type <tnode> program declaration_list

27、declaration var_declaration%type <tnode> fun_declaration params param_list param compound_stmt %type <tnode> local_declarations statement_list statement %type <tnode> expression_stmt selection_stmt iteration_stmt%type <tnode> return_stmt expression var simple_expression%type

28、<tnode> additive_expression term factor call args arg_list%type <tok> type_specifier relop addop mulop%token在定義終結符號時也可以定義語義值類型。終結符的定義%token <語義值類型> 終結符名 編號%token DIGIT LETTER%token BEGIN 100注： 1.非終結符不需要特別說明，如果需要說明語義值類型則用type語句； 2.文字字符終結符不需要特別說明，它們的編號取其在字符集中的值； 3.在規(guī)則中出現文字字符時用單引號括起來。

29、%token ENDFILE,ERROR,%token IF,ELSE,INT,RETURN,VOID,WHILE,%token ID,NUM,%token ASSIGN,%token EQ,NOTEQ,LTEQ,GTEQ,LT,GT,%token PLUS,MINUS,TIMES,OVER,%token LPAREN,RPAREN,LBRACK,RBRACK,LCURL,RCURL,%token SEMI,COMMA運算符優(yōu)先級和結合性的定義以left和right定義結合性；以排列順序定義優(yōu)先級；在語法規(guī)則中，以prec輔助定義優(yōu)先級消除二義性的兩條規(guī)則： 1.出現移進/歸約沖突時，進行移進

30、； 2.出現歸約/歸約沖突時，用先出現的規(guī)則進行歸約；stat :IF bexp THEN statIF bexp THEN stat ELSE stat ;用結合性和優(yōu)先級解決沖突； 規(guī)則的結合性就是規(guī)則右部最后一個非終結符的優(yōu)先級和結合性； 如果使用了prec子句，則優(yōu)先級和結合性由prec子句決定； 對于無優(yōu)先級和結合性的規(guī)則，用規(guī)則1、2解決； 對于有優(yōu)先級和結合行的規(guī)則，用如下的規(guī)則解決：出現移進/歸約沖突時，輸入符號的優(yōu)先級大于規(guī)則的優(yōu)先級則移進，若輸入符號的優(yōu)先級小于規(guī)則的優(yōu)先級則歸約，若二者的優(yōu)先級相同，左結合則歸約，右結合則移進，無結合則出錯。二 語法規(guī)則program :

31、declaration_list parseTree = $1; YYACCEPT; ;declaration_list: declaration_list declaration TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $2; $ = $1; else $ = $2; | declaration $ = $1;declaration: var_declaration $ = $1; | fun_declarat

32、ion $ = $1; ;程序由聲明的列表(或序列)組成，聲明可以是函數或變量聲明，順序是任意的。至少必須有一個聲明。接下來是語義限制(這些在C中不會出現)。所有的變量和函數在使用前必須聲明(這避免了向后backpatching引用)。程序中最后的聲明必須是一個函數聲明，名字為main。var_declaration: type_specifier ID SEMI $ = (TreeNode *) newNode(VarDeclK); $->attr.op = $1; $->child0 = (TreeNode *) newNode(IdK); $->child0->a

33、 = (char *) copyString(lastid); / add to symbol table | type_specifier ID LBRACK NUM $<tnode>$ = (TreeNode *) newNode(VarDeclK); $<tnode>$->attr.op = $1; $<tnode>$->child0 = (TreeNode *) newNode(IdK); $<tnode>$->child0-> = (char *) copyString(last

34、id); $<tnode>$->child0 = (TreeNode *) newNode(ConstK); $<tnode>$->child0->attr.val = atoi(curToken.tokString); / add to symbol table RBRACK SEMI $ = $<tnode>5; ;type_specifier: INT $ = INT;| VOID $ = VOID;變量聲明或者聲明了簡單的整數類型變量，或者是基類型為整數的數組變量，索引范圍從0到NUM-1。注意，在C中僅有的基本類型是整型和空類型。

35、在一個變量聲明中，只能使用類型指示符int。void用于函數聲明(參見下面)。也要注意，每個聲明只能聲明一個變量。fun_declaration: type_specifier ID $<tnode>$ = (TreeNode *) newNode(FunDeclK); $<tnode>$->attr.op = $1; $<tnode>$->child0 = (TreeNode *) newNode(IdK); $<tnode>$->child0-> = (char *) copyString(lasti

36、d); LPAREN params RPAREN compound_stmt $ = $<tnode>3; $->child1 = $5; $->child2 = $7; ;params: param_list $ = $1; | VOID $ = NULL; ;param_list: param_list COMMA param TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $3; $ = $

37、1; else $ = $3; | param $ = $1; ;param: type_specifier ID $ = (TreeNode *) newNode(VarDeclK); $->attr.op = $1; $->child0 = (TreeNode *) newNode(IdK); $->child0-> = (char *) copyString(lastid); / add to symbol table | type_specifier ID $<tnode>$ = (TreeNode *) newNode(VarDe

38、clK); $<tnode>$->attr.op = $1; $<tnode>$->child0 = (TreeNode *) newNode(IdK); $<tnode>$->child0-> = (char *) copyString(lastid); / add to symbol table LBRACK RBRACK $ = $<tnode>3; ;函數聲明由返回類型指示符、標識符以及在圓括號內的用逗號分開的參數列表組成，后面跟著一個復合語句，是函數的代碼。如果函數的返回類型是void，那么函數

39、不返回任何值(即是一個過程)。函數的參數可以是void(即沒有參數)，或者一列描述函數的參數。參數后面跟著方括號是數組參數，其大小是可變的。簡單的整型參數由值傳遞。數組參數由引用來傳遞(也就是指針)，在調用時必須通過數組變量來匹配。注意，類型“函數”沒有參數。一個函數參數的作用域等于函數聲明的復合語句，函數的每次請求都有一個獨立的參數集。函數可以是遞歸的(對于使用聲明允許的范圍)。compound_stmt: LCURL local_declarations statement_list RCURL TreeNode * t = $2; if (t != NULL) while (t->

40、sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $3; $ = $2; else $ = $3; ;復合語句由用花括號圍起來的一組聲明和語句組成。復合語句通過用給定的順序執(zhí)行語句序列來執(zhí)行。局部聲明的作用域等于復合語句的語句列表，并代替任何全局聲明。local_declarations: local_declarations var_declaration TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *

41、) t->sibling; t->sibling = $2; $ = $1; else $ = $2; | $ = NULL; ;statement_list: statement_list statement TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $2; $ = $1; else $ = $2; | $ = NULL; ;注意聲明和語句列表都可以是空的(非終結符empty表示空字符串，有時寫作)s

42、tatement: expression_stmt $ = $1; | compound_stmt $ = $1; | selection_stmt $ = $1; | iteration_stmt $ = $1; | return_stmt $ = $1; ;expression_stmt: expression SEMI $ = $1; | SEMI $ = NULL; ;表達式語句有一個可選的且后面跟著分號的表達式。這樣的表達式通常求出它們一方的結果。因此，這個語句用于賦值和函數調用。selection_stmt: IF LPAREN expression RPAREN statemen

43、t $ = (TreeNode *) newNode(IfK); $->child0 = $3; $->child1 = $5; | IF LPAREN expression RPAREN statement ELSE statement $ = (TreeNode *) newNode(IfK); $->child0 = $3; $->child1 = $5; $->child2 = $7; ;if語句有通常的語義：表達式進行計算；非0值引起第一條語句的執(zhí)行； 0值引起第二條語句的執(zhí)行，如果它存在的話。這個規(guī)則導致了典型的懸掛else二義性，可以用一種標準的方法

44、解決：else部分通常作為當前i f的一個子結構立即分析(“最近嵌套”非二義性規(guī)則)。iteration_stmt: WHILE LPAREN expression RPAREN statement $ = (TreeNode *) newNode(WhileK); $->child0 = $3; $->child1 = $5; ;while語句是C中唯一的重復語句。它重復執(zhí)行表達式，并且如果表達式的求值為非0，則執(zhí)行語句，當表達式的值為0時結束。return_stmt: RETURN SEMI $ = (TreeNode *) newNode(ReturnK); | RETURN

45、 expression SEMI $ = (TreeNode *) newNode(ReturnK); $->child0 = $2; ;返回語句可以返回一個值也可無值返回。函數沒有說明為void就必須返回一個值。函數聲明為void就沒有返回值。return引起控制返回調用者(如果它在main中，則程序結束)。expression: var ASSIGN expression $ = (TreeNode *) newNode(AssignK); $->child0 = $1; $->child1 = $3; | simple_expression $ = $1; ;var:

46、ID $ = (TreeNode *) newNode(IdK); $-> = (char *) copyString(lastid); | ID $<tnode>$ = (TreeNode *) newNode(IdK); $<tnode>$-> = (char *) copyString(lastid); LBRACK expression RBRACK $ = $<tnode>2; $->child0 = $4; ;表達式是一個變量引用，后面跟著賦值符號(等號)和一個表達式，或者就是一個簡單的表達式

47、。賦值有通常的存儲語義：找到由v a r表示的變量的地址，然后由賦值符右邊的子表達式進行求值，子表達式的值存儲到給定的地址。這個值也作為整個表達式的值返回。v a r是簡單的(整型)變量或下標數組變量。負的下標將引起程序停止(與C不同)。然而，不進行下標越界檢查。simple_expression: additive_expression relop additive_expression $ = (TreeNode *) newNode(OpK); $->attr.op = $2; $->child0 = $1; $->child1 = $3; | additive_exp

48、ression $ = $1; ;relop: EQ $ = EQ; | NOTEQ $ = NOTEQ; | LTEQ $ = LTEQ; | GTEQ $ = GTEQ; | LT $ = LT; | GT $ = GT; ;簡單表達式由無結合的關系操作符組成(即無括號的表達式僅有一個關系操作符)。簡單表達式在它不包含關系操作符時，其值是加法表達式的值，或者如果關系算式求值為t u r e，其值為1，求值為false時值為0。additive_expression: additive_expression addop term $ = (TreeNode *) newNode(OpK); $->attr.op = $2; $-