编译原理课程设计实验报告

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工具生成可执行代码）；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的基本语法规则，以及token类型，运算符类型，并且定义cminus关键字，便于在程序运行时能对其进行识别。一下为cminus.l文件原代码：/*定义全局变量、函数及包含文件说明：*/%#include "globals.h "#include "util.h"#include "scan.h "#define MAXTOKENLEN 40char tokenString40;int lineno = 0;%/*有关语法规

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中所定义的语法规则不同，这里的也要稍做修改。比如在这里的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悬挂问题的处理，运算符优先级处理以及错误报告。参考课本P492 29条cminus

25、 BNF。并且通过细心理解体会，写出了cminus.y文件，并能通过yacc生成c代码。Cnimus.y代码以及一些具体功能如下所述：一 YACC源程序的结构说明部分的内容如下：头文件宏定义数据类型定义全局变量定义语法开始符定义语义值类型定义终结符定义运算符优先级及结合性定义%#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自动将第一条语法规则左部的非终结符作为语法开始符。 语义值类型的定义%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.在规则中出现文字字符时用单引号括起来。

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运算符优先级和结合性的定义以left和right定义结合性；以排列顺序定义优先级；在语法规则中，以prec辅助定义优先级消除二义性的两条规则： 1.出现移进/归约冲突时，进行移进

30、； 2.出现归约/归约冲突时，用先出现的规则进行归约；stat :IF bexp THEN statIF bexp THEN stat ELSE stat ;用结合性和优先级解决冲突； 规则的结合性就是规则右部最后一个非终结符的优先级和结合性； 如果使用了prec子句，则优先级和结合性由prec子句决定； 对于无优先级和结合性的规则，用规则1、2解决； 对于有优先级和结合行的规则，用如下的规则解决：出现移进/归约冲突时，输入符号的优先级大于规则的优先级则移进，若输入符号的优先级小于规则的优先级则归约，若二者的优先级相同，左结合则归约，右结合则移进，无结合则出错。二 语法规则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; ;复合语句由用花括号围起来的一组声明和语句组成。复合语句通过用给定的顺序执行语句序列来执行。局部声明的作用域等于复合语句的语句列表，并代替任何全局声明。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值引起第一条语句的执行； 0值引起第二条语句的执行，如果它存在的话。这个规则导致了典型的悬挂else二义性，可以用一种标准的方法

44、解决：else部分通常作为当前i f的一个子结构立即分析(“最近嵌套”非二义性规则)。iteration_stmt: WHILE LPAREN expression RPAREN statement $ = (TreeNode *) newNode(WhileK); $->child0 = $3; $->child1 = $5; ;while语句是C中唯一的重复语句。它重复执行表达式，并且如果表达式的求值为非0，则执行语句，当表达式的值为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; $-