编译原理课程设计实验报告Word格式文档下载.docx
- 文档编号:4772781
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:34
- 大小:55.72KB
编译原理课程设计实验报告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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 课程设计 实验 报告