编译原理课程设计实验报告Word格式文档下载.docx
《编译原理课程设计实验报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计实验报告Word格式文档下载.docx（34页珍藏版）》请在冰点文库上搜索。
E02620106
马培良：
编写cminus.y文件，并用yacc工具生成可执行代码）；
E02620121丘廷：
（进行程序的测试）
以下为具体实验分步报告以及过程：
第一部分：
设计cminus符号表
符号表是编译器中的主要继承属性，并且在语法树之后，形成了主要的数据结构。
符号表主要的操作有插入、查找和删除。
杂凑表（hash表）通常为符号表的实现提供了最好的选择，因为所有3种操作都能在几乎恒定的时间内完成，在实践中也是最常使用。
该课程设计所用的C-符号表采用建立杂凑表的方法。
杂凑表是一个入口数组，称作“桶（bucket）”，使用一个整数范围的索引，通常从0到表的尺寸减1。
杂凑函数（hashfuction）把索引键（在这种情况下是标识符名，组成一个字符串）转换成索引范围内的一个整数的杂凑值，对应于索引键的项存储在这个索引的“桶”中。
每个“桶”实际上又是一个线性表，通过把新的项插入到“桶”表中来解决冲突在任何情况下，“桶”数组的实际大小要选择一个素数，因为这将使一般的杂凑函数运行得更好。
杂凑函数。
在符号表实现中使用的杂凑函数将字符串（标识符名）转换成0...size-1范围内的一个整数。
一般这通过3步来进行。
首先，字符串中的每个字符转换成一个非负整数。
然后，这些整数用一定的方法组合形成一个整数。
最后，把结果整数调整到0...size-1范围内。
冲突的一个好的解决办法是，当加上下一个字符的值时，重复地使用一个常量作为乘法因子。
因此，如果ci是第i个字符的数字值，hi是在第i步计算的部分杂凑值，那么hi根据下面的递归公式计算，h0=0，hi－1=ahi－ci，最后的杂凑值用h=hnmodsize计算。
这里n是杂凑的名字中字符的个数。
这等价于下列公式当然，在这个公式中a的选择对输出结果有重要影响。
a的一种合理的选择是2的幂，如16或128，这样乘法可以通过移位来完成。
该程序a选16，size取211。
由于在数据结构方面为了实现很方便的进行查找，插入，删除等操作。
我们把它的数据结构设计成一哈稀表结构，哈稀表的查找，插入等操作是飞快的。
我们所设计的哈稀结构符号表是参考教科书上P295
它的结构如下：
符号表的杂凑函数
#defineSIZE211
#defineSHIFT4
inthash（char*key）
{inttemp=0;
inti=0;
while（key[i]!
='
\0'
）
{temp=（（temp<
<
SHIFT）+key[i]）%SIZE;
++i;
}
returntemp;
该符号表完成了插入[voidst_insert（char*name,intlineno,intloc）]、查找[intst_lookup（char*name）]工作
源程序：
symtab.c
#include<
stdio.h>
stdlib.h>
string.h>
#include"
symtab.h"
/*定义哈稀表的最大值*/
/*SHIFTisthepoweroftwousedasmultiplier
inhashfunction*/
/*哈稀函数结构*/
staticinthash（char*key）
++i;
typedefstructLineListRec
{intlineno;
structLineListRec*next;
}*LineList;
typedefstructBucketListRec
{char*name;
LineListlines;
intmemloc;
/*memorylocationforvariable*/
structBucketListRec*next;
}*BucketList;
/*哈稀表*/
staticBucketListhashTable[SIZE];
voidst_insert（char*name,intlineno,intloc）
{inth=hash（name）;
BucketListl=hashTable[h];
while（（l!
=NULL）&
&
（strcmp（name,l->
name）!
=0））l=l->
next;
if（l==NULL）/*variablenotyetintable*/
{l=（BucketList）malloc（sizeof（structBucketListRec））;
l->
name=name;
l->
lines=（LineList）malloc（sizeof（structLineListRec））;
lines->
lineno=lineno;
memloc=loc;
next=NULL;
next=hashTable[h];
hashTable[h]=l;
}
else/*foundintable,sojustaddlinenumber*/
{LineListt=l->
lines;
while（t->
next!
=NULL）t=t->
t->
next=（LineList）malloc（sizeof（structLineListRec））;
t->
next->
intst_lookup（char*name）
=0））
l=l->
if（l==NULL）return-1;
elsereturnl->
memloc;
voidprintSymTab（FILE*listing）
{inti;
fprintf（listing,"
VariableNameLocationLineNumbers\n"
）;
fprintf（listing,"
---------------------------------\n"
for（i=0;
i<
SIZE;
++i）
{if（hashTable[i]!
=NULL）
{BucketListl=hashTable[i];
while（l!
%-14s"
l->
name）;
%-8d"
memloc）;
while（t!
{fprintf（listing,"
%4d"
t->
lineno）;
t=t->
\n"
}/*printSymTab*/
symtab.h
#ifndef_SYMTAB_H_
#define_SYMTAB_H_
voidst_insert（char*name,intlineno,intloc）;
/*插入函数*/
intst_lookup（char*name）;
/*查找函数*/
voidprintSymTab（FILE*listing）;
/*用来打印哈稀表内容*/
#endif
符号表设计的好坏直接影响到整个程序运行的速度，效率以及准确度。
因为接下来的parse工作是基于符号表的，是从符号表里提取token进行语法分析的。
为了提高程序运行的的效率，我们把scan直接通过parse来调用。
具体的来讲就是，程序运行时，首先进入parse部分，当parse要用到token时，调用scan部分扫描原文件生成token储存在符号表中，并同时提供给parse进行语法分析。
这样就可以一遍完成整个原文件的扫描。
第二部分：
运用LEX实现cminus词法分析程序。
这一部比较关键，设计的正确与否直接影响到在scan过程中token的产生。
以及整个程序运行的结果的正确与否。
在这里主要定义cminus的基本语法规则，以及token类型，运算符类型，并且定义cminus关键字，便于在程序运行时能对其进行识别。
一下为cminus.l文件原代码：
/*定义全局变量、函数及包含文件说明：
*/
%{
globals.h"
util.h"
scan.h"
#defineMAXTOKENLEN40
chartokenString[40];
intlineno=0;
%}有关语法规则以及token的定义:
digit[0-9]number{digit}+letter[a-zA-Z]identifier{letter}+newline\nwhitespace[\t]+
%%
/*以下为关键字定义:
"
if"
{returnIF;
else"
{returnELSE;
int"
{returnINT;
void"
{returnVOID;
return"
{returnRETURN;
while"
{returnWHILE;
}以下为运算符号定义:
="
{returnASSIGN;
{returnLTEQ;
>
{returnGTEQ;
{returnLT;
{returnGT;
=="
{returnEQ;
!
{returnNOTEQ;
+"
{returnPLUS;
-"
{returnMINUS;
*"
{returnTIMES;
/"
{returnOVER;
}"
（"
{returnLPAREN;
）"
{returnRPAREN;
["
{returnLBRACK;
]"
{returnRBRACK;
{"
{returnLCURL;
{returnRCURL;
;
{returnSEMI;
"
{returnCOMMA;
}终结符及注释符号*/
{number}{returnNUM;
{identifier}{returnID;
{newline}{lineno++;
{whitespace}{/*skipwhitespace*/}
/*"
{charc;
chard;
c=input（）;
if（c!
=EOF）
{
do
d=c;
if（c==EOF）break;
if（c=='
\n'
）lineno++;
}while（!
（d=='
*'
&
c=='
/'
））;
.{returnERROR;
%%定义getToken（）函数体:
TokenTypegetToken（void）
{staticintfirstTime=TRUE;
TokenTypecurrentToken;
if（firstTime）
{firstTime=FALSE;
lineno++;
yyin=source;
yyout=listing;
currentToken=yylex（）;
strncpy（tokenString,yytext,MAXTOKENLEN）;
if（TraceScan）{
\t%d:
"
lineno）;
printToken（currentToken,tokenString）;
returncurrentToken;
说明：
以上代码已经能通过lex工具产生c代码。
cminus.l的设计基本结构
是参考tiny.l的结构设计而成，但要注意的是，由于在接下来的cnimus.y中所定义的语法规则不同，这里的也要稍做修改。
比如在这里的getToken函数，要于cminus.y文件里的设计的返回参数要一一对应，否则在编译的过程中会出现类型不匹配等等的错误，修改起来比较麻烦。
第三部分：
为C-设计语法树结构，使之适用于分析器产生
语法树是LALR分析的前提。
因此在进行语法分析之前，必须设计语法树结构，使接下来的语法分析有一个具体的数据结构。
其代码段如下：
#defineMAXTOKENSIZE50
typedefintTokenType;
/*定义语法树结构*/
typedefstruct
TokenTypetok;
char*tokString;
}TokenStruct;
typedefenum{IfK,WhileK,AssignK,ReturnK,CallK,VarDeclK,FunDeclK,OpK,ConstK,IdK}NodeKind;
/*枚举结点类型*/
typedefenum{Void,Integer,Boolean}ExpType;
/*枚举返回变量类型*/
#defineMAXCHILDREN3/*声明一个结点最多有三个子结点*/typedefstructtreeNode/*定义语法树结点结构*/
{structtreeNode*child[MAXCHILDREN];
structtreeNode*sibling;
intlineno;
NodeKindkind;
union{TokenTypeop;
intval;
char*name;
}attr;
ExpTypetype;
}TreeNode;
在这里当当只是设计的语法树的基本数据结构，至于要用到parse过程中还要进行具体的修改，调试。
这些工作都已经在程序原代码调试过程中做好。
第四部分：
LALR分析。
（使用yacc工具）
这一部分完成了整个编译过程中的语法分析，二异性冲突处理，lese悬挂问题的处理，运算符优先级处理以及错误报告。
参考课本P49229条cminusBNF。
并且通过细心理解体会，写出了cminus.y文件，并能通过yacc生成c代
码。
Cnimus.y代码以及一些具体功能如下所述：
一．YACC源程序的结构
说明部分的内容如下：
％{
头文件
宏定义
数据类型定义
全局变量定义
％}
语法开始符定义
语义值类型定义
终结符定义
运算符优先级及结合性定义
#defineYYPARSER/*distinguishesYaccoutputfromothercodefiles*/
globals.h"
scan.h"
parse.h"
TreeNode*parseTree;
/*storessyntaxtreeforlaterreturn*/
voidyyerror（constchar*s）;
%}
语法开始符号的定义
％start非终结符
注：
若没有上述说明，YACC自动将第一条语法规则左部的非终结符作为语法开始符。
语义值类型的定义
%union定义语义值的类型;
%union{TreeNode*tnode;
%type定义文法符号的语义值类型;
%type<
tnode>
programdeclaration_listdeclarationvar_declaration
fun_declarationparamsparam_listparamcompound_stmt%type<
local_declarationsstatement_liststatement
expression_stmtselection_stmtiteration_stmt
return_stmtexpressionvarsimple_expression
additive_expressiontermfactorcallargsarg_list
tok>
type_specifierrelopaddopmulop
%token在定义终结符号时也可以定义语义值类型。
终结符的定义
%token<
语义值类型>
终结符名编号
%tokenDIGITLETTER
%tokenBEGIN100
1.非终结符不需要特别说明，如果需要说明语义值类型则用％type语句；
2.文字字符终结符不需要特别说明，它们的编号取其在字符集中的值；
3.在规则中出现文字字符时用单引号括起来。
%tokenENDFILE,ERROR,
%tokenIF,ELSE,INT,RETURN,VOID,WHILE,
%tokenID,NUM,
%tokenASSIGN,
%tokenEQ,NOTEQ,LTEQ,GTEQ,LT,GT,
%tokenPLUS,MINUS,TIMES,OVER,
%tokenLPAREN,RPAREN,LBRACK,RBRACK,LCURL,RCURL,
%tokenSEMI,COMMA
运算符优先级和结合性的定义
以％left和％right定义结合性；
以排列顺序定义优先级；
在语法规则中，以％prec辅助定义优先级
消除二义性的两条规则：
•1.出现移进/归约冲突时，进行移进；
•2.出现归约/归约冲突时，用先出现的规则进行归约；
stat:
IFbexpTHENstat
IFbexpTHENstatELSEstat;
用结合性和优先级解决冲突；
•规则的结合性就是规则右部最后一个非终结符的优先级和结合性；
•如果使用了％prec子句，则优先级和结合性由％prec子句决定；
•对于无优先级和结合性的规则，用规则1、2解决；
•对于有优先级和结合行的规则，用如下的规则解决：
出现移进/归约冲突时，输入符号的优先级大于规则的优先级则移进，若输入符号的优先级小于规则的优先级则归约，若二者的优先级相同，左结合则归约，右结合则移进，无结合则出错。
二．
语法规则
program:
declaration_list
{parseTree=$1;
YYACCEPT;
declaration_list:
declaration_listdeclaration
{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_specifierIDSEMI
{$$=（TreeNode*）newNode（VarDeclK）;
$$->
attr.op=$1;
child[0]=（TreeNode*）newNode（IdK）;
child[0]->
attr.name=（char*）copyString（la
升级会员 