1、E02620106马培良：编写 cminus.y 文件，并用 yacc 工具生成可执行代码）；E02620121 丘廷：（进行程序的测试）以下为具体实验分步报告以及过程：第一部分：设计 cminus 符号表符号表是编译器中的主要继承属性，并且在语法树之后，形成了主要的数据结构。符 号表主要的操作有插入、查找和删除。杂凑表（hash 表）通常为符号表的实现提供了最好 的选择，因为所有 3 种操作都能在几乎恒定的时间内完成，在实践中也是最常使用。该课 程设计所用的 C-符号表采用建立杂凑表的方法。杂凑表是一个入口数组，称作“桶（ b u c k e t ）”，使用一个整数范围的索引，通常从 0 到
2、表的尺寸减 1。杂凑函数（hash fuction）把索引 键（在这种情况下是标识符名，组成一个字符串）转换成索引范围内的一个整数的杂凑值， 对应于索引键的项存储在这个索引的“桶”中。每个“桶”实际上又是一个线性表，通过 把新的项插入到“桶”表中来解决冲突在任何情况下，“桶”数组的实际大小要选择一个素 数，因为这将使一般的杂凑函数运行得更好。杂凑函数。在符号表实现中使用的杂凑函数将字符串（标识符名）转换成 0. . . s i z e- 1 范围内的一个整数。一般这通过 3 步来进行。首先，字符串中的每个字符转换成一个非负 整数。然后，这些整数用一定的方法组合形成一个整数。最后，把结果整数调整
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 取 2
4、11。由于在数据结构方面为了实现很方便的进行查找，插入，删除等操作。我们把它的数 据结构设计成一哈稀表结构，哈稀表的查找，插入等操作是飞快的。我们所设计的哈稀结 构符号表是参考教科书上 P295它的结构如下：符号表的杂凑函数#define SIZE 211#define SHIFT 4int hash （ char * key ） int temp = 0;int i = 0;while （keyi != 0） temp = （temp SHIFT） + keyi） % SIZE;+ + i ;return temp;该符号表完成了插入void st_insert（ char * name,
5、int lineno, int loc ）、查找int st_lookup （ char * name ）工作源程序：symtab.c#include stdlib.hstring.h#include symtab.h/* 定义哈稀表的最大值 */* SHIFT is the power of two used as multiplierin hash function */* 哈稀函数结构 */static int hash （ char * key ）+i;typedef struct LineListRec int lineno;struct LineListRec * next; *
6、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）;BucketList l = hashTableh;while （l !
7、= 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）;lines-lineno = lineno;memloc = loc;next = NULL;next = hashTableh;hashTableh = l; el
8、se /* found in table, so just add line number */ LineList t = l-lines;while （t-next != NULL） t = t-t-next = （LineList） malloc（sizeof（struct LineListRec）; t-next-int st_lookup （ char * name ）= 0）l = l-if （l = NULL） return -1;else return l-memloc;void printSymTab（FILE * listing） int i;fprintf（listing,
9、Variable Name Location Line Numbersn）; fprintf（listing,- - -nfor （i=0;iname）;%-8d memloc）;while （t ! fprintf（listing,%4d ,t-lineno）;t = t-n /* printSymTab */symtab.h#ifndef _SYMTAB_H_#define _SYMTAB_H_void st_insert（ char * name, int lineno, int loc ）; /*插入函数*/int st_lookup （ char * name ）; /*查找函数*/
10、void printSymTab（FILE * listing）; /*用来打印哈稀表内容*/#endif符号表设计的好坏直接影响到整个程序运行的速度，效率以及准确度。因为接下来的 parse 工作是基于符号表的，是从符号表里提取 token 进行语法分析的。为了提高程序运行 的的效率，我们把 scan 直接通过 parse 来调用。具体的来讲就是，程序运行时，首先进入 parse 部分，当 parse 要用到 token 时，调用 scan 部分扫描原文件生成 token 储存在符号表 中，并同时提供给 parse 进行语法分析。这样就可以一遍完成整个原文件的扫描。第二部分：运用 LEX 实
11、现 cminus 词法分析程序。这一部比较关键，设计的正确与否直接影响到在 scan 过程中 token 的产生。 以及整个程序运行的结果的正确与否。在这里主要定义 cminus 的基本语法规则， 以及 token 类型，运算符类型，并且定义 cminus 关键字，便于在程序运行时能 对其进行识别。一下为 cminus.l 文件原代码：/*定义全局变量、函数及包含文件说明：*/%globals.h util.hscan.h #define MAXTOKENLEN 40char tokenString40;int lineno = 0;%有关语法规则以及 token 的定义:digit 0-9n
12、umber 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;以下为运算符号定义:= return ASSIGN; return LTEQ; return GTEQ; return LT; return GT;= return EQ;! return NOTEQ;+ return PLUS;- retu
13、rn MINUS;* return TIMES;/ return OVER;（ 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 whitespace */* char c;char d;c = input（）;if （c != EOF）dod =
14、c;if （c = EOF） break;if （c = n） lineno+; while （!（d = * & c = /）;. return ERROR;%定义 getToken（）函数体:TokenType getToken（void） static int firstTime = TRUE;TokenType currentToken;if （firstTime） firstTime = FALSE;lineno+;yyin = source;yyout = listing;currentToken = yylex（）;strncpy（tokenString,yytext,MAXTO
15、KENLEN）;if （TraceScan） t%d: ,lineno）;printToken（currentToken,tokenString）;return currentToken;说明：以上代码已经能通过 lex 工具产生 c 代码。cminus.l 的设计基本结构是参考 tiny.l 的结构设计而成，但要注意的是，由于在接下来的 cnimus.y 中所 定义的语法规则不同，这里的也要稍做修改。比如在这里的 getToken 函数，要 于 cminus.y 文件里的设计的返回参数要一一对应，否则在编译的过程中会出现 类型不匹配等等的错误，修改起来比较麻烦。第三部分：为 C-设计语法树结
16、构，使之适用于分析器产生语法树是 LALR 分析的前提。因此在进行语法分析之前，必须设计语法树结 构，使接下来的语法分析有一个具体的数据结构。其代码段如下：#define MAXTOKENSIZE 50typedef int TokenType; /*定义语法树结构*/typedef structTokenType tok;char * tokString; TokenStruct;typedef enum IfK,WhileK,AssignK,ReturnK,CallK, VarDeclK,FunDeclK,OpK,ConstK,IdK NodeKind; /*枚举结点类型*/typedef
17、 enum Void,Integer,Boolean ExpType; /*枚举返回变量类型 */#define MAXCHILDREN 3 /*声明一个结点最多有三个子结点*/ typedef struct treeNode /*定义语法树结点结构*/ struct treeNode * childMAXCHILDREN;struct treeNode * sibling;int lineno;NodeKind kind;union TokenType op;int val;char * name; attr;ExpType type; TreeNode;在这里当当只是设计的语法树的基本数据
18、结构，至于要用到 parse 过程中还要进行具体的修改，调试。这些工作都已经在程序原代码调试过程中 做好。第四部分：LALR 分析。（使用 yacc 工具）这一部分完成了整个编译过程中的语法分析，二异性冲突处理，lese 悬挂 问题的处理，运算符优先级处理以及错误报告。参考课本 P492 29 条 cminus BNF。并且通过细心理解体会，写出了 cminus.y 文件，并能通过 yacc 生成 c 代码。Cnimus.y 代码以及一些具体功能如下所述：一 YACC 源程序的结构说明部分的内容如下：头文件宏定义数据类型定义全局变量定义语法开始符定义语义值类型定义终结符定义运算符优先级及结合性
19、定义#define YYPARSER /* distinguishes Yacc output from other code files */globals.hscan.hparse.hTreeNode * parseTree; /* stores syntax tree for later return */void yyerror （const char *s）;%语法开始符号的定义start 非终结符注：若没有上述说明，YACC 自动将第一条语法规则左部的非终结符作为语法开 始符。语义值类型的定义%union 定义语义值的类型;%union TreeNode * tnode;%type
20、 定义文法符号的语义值类型;%type program declaration_list declaration var_declaration fun_declaration params param_list param compound_stmt %type type_specifier relop addop mulop%token 在定义终结符号时也可以定义语义值类型。终结符的定义%token 终结符名 编号%token DIGIT LETTER%token BEGIN 100 1.非终结符不需要特别说明，如果需要说明语义值类型则用type 语句； 2.文字字符终结符不需要特别说明，
21、它们的编号取其在字符集中的值；3.在规则中出现文字字符时用单引号括起来。%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 定义结合性；以排列顺序定义优先级；在语法规则中，以pr
22、ec 辅助定义优先级消除二义性的两条规则： 1.出现移进/归约冲突时，进行移进； 2.出现归约/归约冲突时，用先出现的规则进行归约；stat : IF bexp THEN statIF bexp THEN stat ELSE stat ;用结合性和优先级解决冲突； 规则的结合性就是规则右部最后一个非终结符的优先级和 结合性； 如果使用了prec 子句，则优先级和结合性由prec 子句 决定； 对于无优先级和结合性的规则，用规则 1、2 解决； 对于有优先级和结合行的规则，用如下的规则解决：出现 移进/归约冲突时，输入符号的优先级大于规则的优先级则移进， 若输入符号的优先级小于规则的优先级则归约
23、，若二者的优先级相 同，左结合则归约，右结合则移进，无结合则出错。二语法规则program : declaration_list parseTree = $1;YYACCEPT;declaration_list : declaration_list declaration TreeNode * t = $1;if （t !sibling !t = （TreeNode *） t-sibling;sibling = $2;$ = $1;else $ = $2;| declaration $ = $1;declaration : var_declaration| fun_declaration程序由声明的列表（或序列）组成，声明可以是函数或变量声明，顺序是任意的。至少 必须有一个声明。接下来是语义限制（这些在C中不会出现）。所有的变量和函数在使用前必 须声明（这避免了向后backpatching引用）。程序中最后的声明必须是一个函数声明，名字 为main。var_declaration : type_specifier ID SEMI $ = （TreeNode *） newNode（VarDeclK）;$-attr.op = $1;child0 = （TreeNode *） newNode（IdK）;child0-attr.name = （char *） copyString（la
