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

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

实验目的：

这个实验的目的是构造C minus语言的编译器，要求能够编译C minus语言的程序并且生成中间代码。在实验的过程中，学会使用flex/bison这两个重要的工具。

实验内容：

参见教材

p491 appendix A.

设计一cminus语言编译器 语言介绍。

Decaf（cminus）语言的关键字：

int while if else return void

运算符：+ - * / > < = , . != { } [ ] <= >= == () C minus语言的限制。

数字：支持10进制整数。小数可以采用科学记数法，如1E3也是合法的。 字符串：字符串内部不允许出现换行，即字符串变量必须在同一行内。

注释：C minus语言允许采用/*…*/注释，并且注释不可以嵌套，即下面的注释是不合法的： /*This is /*a valid */comment*/

程序流程图

开始 词法分析 语法分析 语法树 代码生成 类型检查 建立符号表 符号表 结束 程序的流程参照了书本TINY编译器的实例程序：语法分析器(Parser)调用词法分析器得到符合词法的字，建立语法树；符号表通过对语法树的分析，建立符号表，同时检查变量未定义等错误；类型检查包括检查表达式两边是否匹配，函数参数是否匹配等等；经由上述步骤而未出错的源程序被认为是合法程序，然后代码生成通过语法树和符号表生成P Code中间代码，并将变量地址存入符号表。

其中类型检查和代码生成不要求实现。

本次实验要求分组，一组五人，一人完成一个部分。

本组实验分组成员以及分工介绍：

汪晨风：（设计并实现cminus符号表）；E02620105 蔡其星：（编写cminus.l文件，并用lex工具生成c代码）；E02620107 赵婷：（设计cminus语法树结构）；E02620106

马培良：编写cminus.y文件，并用yacc工具生成可执行代码）；E02620121 丘廷：（进行程序的测试）

以下为具体实验分步报告以及过程：

第一部分：设计cminus符号表

符号表是编译器中的主要继承属性，并且在语法树之后，形成了主要的数据结构。符号表主要的操作有插入、查找和删除。杂凑表（hash表）通常为符号表的实现提供了最好的选择，因为所有3种操作都能在几乎恒定的时间内完成，在实践中也是最常使用。该课程设计所用的C-符号表采用建立杂凑表的方法。杂凑表是一个入口数组，称作“桶( b u c k e t )”，使用一个整数范围的索引，通常从0到表的尺寸减1。杂凑函数(hash fuction)把索引键(在这种情况下是标识符名，组成一个字符串)转换成索引范围内的一个整数的杂凑值，对应于索引键的项存储在这个索引的“桶”中。每个“桶”实际上又是一个线性表，通过把新的项插入到“桶”表中来解决冲突在任何情况下，“桶”数组的实际大小要选择一个素数，因为这将使一般的杂凑函数运行得更好。

杂凑函数。在符号表实现中使用的杂凑函数将字符串(标识符名)转换成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计算。这里n 是杂凑的名字中字符的个数。这等价于下列公式当然，在这个公式中a的选择对输出结果有重要影响。a的一种合理的选择是2的幂，如1 6或1 2 8，这样乘法可以通过移位来完成。该程序a选16，s i z e 取211。

由于在数据结构方面为了实现很方便的进行查找，插入，删除等操作。我们把它的数据结构设计成一哈稀表结构，哈稀表的查找，插入等操作是飞快的。我们所设计的哈稀结构符号表是参考教科书上P295

它的结构如下：

符号表的杂凑函数 #define SIZE 211 #define SHIFT 4 int hash ( char * key ) { int temp = 0; int i = 0;

while (key[i] != '\\0')

{ temp = ((temp << SHIFT) + key[i]) % SIZE; + + i ; }

return temp; }

该符号表完成了插入[void st_insert( char * name, int lineno, int loc )]、查找[int st_lookup ( char * name )]工作

源程序： symtab.c

#include #include #include #include \

/* 定义哈稀表的最大值 */ #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 (key[i] != '\\0')

{ temp = ((temp << SHIFT) + key[i]) % SIZE; ++i; }

return temp; }

typedef struct LineListRec { int lineno;

struct LineListRec * next; } * LineList;

typedef struct BucketListRec { char * name; LineList lines;

int memloc ; /* memory location for variable */ struct BucketListRec * next; } * BucketList;

/* 哈稀表*/

static BucketList hashTable[SIZE];

void st_insert( char * name, int lineno, int loc ) { int h = hash(name);

BucketList l = hashTable[h];

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->lineno = lineno; l->memloc = loc;

l->lines->next = NULL; l->next = hashTable[h];

hashTable[h] = 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->lineno = lineno; t->next->next = NULL; } }

int st_lookup ( char * name ) { int h = hash(name);

BucketList l = hashTable[h];

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(listing,\ Location Line Numbers\\n\ fprintf(listing,\ -------- ------------\\n\ for (i=0;i

{ if (hashTable[i] != NULL) { BucketList l = hashTable[i]; while (l != NULL) { LineList t = l->lines;

fprintf(listing,\ fprintf(listing,\ \ while (t != NULL)

{ fprintf(listing,\ t = t->next; }

fprintf(listing,\ l = l->next; } } }

} /* printSymTab */ symtab.h

#ifndef _SYMTAB_H_ #define _SYMTAB_H_

void st_insert( char * name, int lineno, int loc ); /*插入函数*/

本文来源：https://www.bwwdw.com/article/kqzt.html