编译原理实验报告.docx

《编译原理》实验报告

软件131 陈万全 132852

一、 需求分析
通过对一个常用高级程序设计语言的简单语言子集编译系统中词法分析、语法分析、语义处理模块的设计、开发，掌握实际编译系统的核心结构、工作流程及其实现技术，获得分析、设计、实现编译程序等方面的实际操作能力，增强设计、编写和调试程序的能力。
通过开源编译器分析、编译过程可视化等扩展实验，促进学生增强复杂系统分析、设计和实现能力，鼓励学生创新意识和能力。
实验项目
实 验 内 容
1、词法分析程序设计与实现
构造具有关键字、运算符、标识符、无符号常数等单词的词法分析程序。输入由符合及不符合规定单词类别结构的各类单词组成的源程序。输出单词串的二元式编码（CLASS，VALUE）。
2、语法分析程序设计与实现
将词法分析程序输出的单词串作为输入，针对常见的表达式、赋值语句、条件语句、循环语句等语法成分，选择有代表性的语法分析方法，如递归下降法、算符优先分析、LL(1)、LR等方法之一，设计实现相应的语法分析程序。
3、语义分析程序设计与实现
对各语法单位增加语义子程序，将表达式或可执行语句翻译为四元式序列输出，并能进行错误检查与处理，将错误信息输出。

1、 词法分析程序设计与实现
假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序。
输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。
输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。
2、 语法分析程序设计与实现
选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。
G2[<算术表达式>]：
<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <运算对象> | (<算术表达式>)
若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i代表，则G2可写成：
G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E)
输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID ······
输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。
3、语义分析程序设计与实现
对文法G2[<算术表达式>]中的产生式添加语义处理子程序，完成运算对象是简单变量（标识符）和无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。
输入：包含测试用例（由标识符、无符号数和+、−、*、/、(、)构成的算术表达式）的源程序文件。
输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息
二、 设计思路
1、 词法分析程序设计与实现
1)单词分类
为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。

表1 语言中的各类单词符号及其分类码表
单词符号
类别编码
类别码的助记符
单词值
begin
1
BEGIN

end
2
END

if
3
IF

then
4
THEN

else
5
ELSE

标识符
6
ID
字母打头的字母数字串
无符号常数
7
UCON
机内二进制表示
<
8
LT

<=
9
LE

=
10
EQ

<>
11
NE

>
12
GT

>=
13
GE

:=
14
IS

+
15
PL

-
16
MI

*
17
MU

/
18
DI

2） 词法分析器的设计
函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。
字符数组TOKEN：用来依次存放一个单词词文中的各个字符。
函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。
函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。
函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。
函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。

图1 识别表I所列语言中的部分单词的DFA及相关的语义过程

3）词法分析程序的实现
编写的扫描器:
char TOKEN[20],TOKEND[20],TOKENDO[20];
int lookup (char*);
void out (int, char*);
void report_error (void);
//extern void LEX(void);
int siagn=0;//标志位
FILE *fp1;

char *KeyWordTable[MAX_KEY_NUMBER]={"begin","end", "if", "then", "else", KEY_WORD_END};
/* 查保留字表，判断是否为关键字 */
int lookup (char *token)
{
int n=0;
while (strcmp(KeyWordTable[n], KEY_WORD_END)) /*strcmp比较两串是否相同，若相同返回0*/
{
if (!strcmp(KeyWordTable[n], token)) /*比较token所指向的关键字和保留字表中哪个关键字相符*/
{
return n+1; /*根据单词分类码表I，设置正确的关键字类别码，并返回此类别码的值*/
break;
}
n++;
}
return 0;
}

void scanner_example (FILE *fp)
{
char ch; int i, c, isd,cpoint; double o;
ch=fgetc (fp);//fgetc函数 在文件中读取一个字符
if (isalpha (ch)) /*it must be a identifer! 它必须是一个标识符 判断字符ch是否为英文字母，若为小写字母，返回2，若为大写字母，返回1。若不是字母，返回0*/
{
TOKEN[0]=ch;
ch=fgetc(fp);
i=1;
while (isalnum (ch)||ch=='.')//isalnum函数 判断ch是否为空 当ch为数字0-9或字母a-z及A-Z时，返回非零值，否则返回零
{
if(ch=='.'){
cpoint=-1;//标志字符串中有小数点
}
TOKEN[i]=ch;
i++;
ch=fgetc (fp);
}
TOKEN[i]= '\0';
if(ch=='<'||ch=='>'||ch=='='||ch==':') {
fseek (fp,-2,1);
siagn=1;
}
else fseek (fp,-1,1);
//fseek(fp,-1,1); /* retract fseek函数 每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）*/

i=0;
if(TOKEN[i]=='o'||TOKEN[i]=='O')
{ i++;
if(TOKEN[i]=='x'||TOKEN[i]=='X')
{
i++;
while(TOKEN[i]!='\0')
{
if(!isdigit(TOKEN[i])||TOKEN[i]!='a'||TOKEN[i]!='b'||TOKEN[i]!='c'||TOKEN[i]!='d'||TOKEN[i]!='e'||TOKEN[i]!='f'
||TOKEN[i]!='A'||TOKEN[i]!='B'||TOKEN[i]!='C'||TOKEN[i]!='D'||TOKEN[i]!='E'||TOKEN[i]!='F'||TOKEN[i]!='.')
{
isd=-1;
}
isd=16;//标志字符串十六进制
i++;
}
}
else if(TOKEN[i]=='0'||TOKEN[i]=='1'||TOKEN[i]=='2'||TOKEN[i]=='3'||TOKEN[i]=='4'||TOKEN[i]=='5'||TOKEN[i]=='6'||TOKEN[i]=='7'||TOKEN[i]=='.')
{
isd=8;//标志字符串八进制
i++;
while(TOKEN[i]!='\0')
{
if(TOKEN[i]!='0'||TOKEN[i]!='1'||TOKEN[i]!='2'||TOKEN[i]!='3'||TOKEN[i]!='4'||TOKEN[i]!='5'||TOKEN[i]!='6'||TOKEN[i]!='7'||TOKEN[i]!='.')
{
isd=-1;
}
isd=8;
i++;
}
}
}

if(isd==8){
strncpy(TOKEND,TOKEN+1,strlen(TOKEN)-1);//拷贝函数
//printf("%o",atof(TOKEND));
o=octal(TOKEND);
//printf("%g",o);
sprintf(TOKENDO, "%g",octal(TOKEND));
out(OCTAL,TOKENDO);
}
else if(isd==16){
strncpy(TOKEND,TOKEN+2,strlen(TOKEN)-2);//拷贝函数
o=octal(TOKEND);
//printf("%g",o);
sprintf(TOKENDO, "%g",hex(TOKEND));
out(HEX,TOKENDO);
}
else
{
if(cpoint==-1)
report_error();//当字符串中有小数点时，为错误
else{
c=lookup (TOKEN);//looup查询函数 查找保留字
if (c==0)
out (ID,TOKEN);
else
out (c," ");//out函数 输出功能
}
}
}
else

if(isdigit(ch))//isdigit函数 检查参数c是否为阿拉伯数字0到9。
{
/*TOKEN[0]=ch;
ch=fgetc(fp);
i=1;
while(isdigit(ch)||ch=='-'||ch=='E'||ch=='e'||ch=='.')
{
TOKEN[i]=ch;
i++;
ch=fgetc(fp);
}
TOKEN[i]= '\0';*/
int Class;
fseek (fp,-1,1);
Class=LEX(fp);
if(Class==1){
char pi[30] = "";
itoa(ICON,pi,10);
out(INT,pi);
}
else if(Class==2){

char pd[30] = "";
sprintf(pd, "%g",FCON);
out(DOUBLE,pd);
}
else
report_error( );

//fseek(fp,-1,1);
if(chf=='<'||chf=='>'||chf=='='||chf==':'||chf=='+'||chf=='-'||chf=='*'||chf=='/') {
fseek (fp,-2,1);
siagn=1;
}
else
{
fseek (fp,-1,1);
siagn=1;
}
}

else
switch(ch)
{
case '<':
ch=fgetc(fp);
if(ch=='='){
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1); //如果符号后面不是空值 则退后一步 保证符号后可以直接跟数字 也可以跟空格
siagn=1;
out(LE," ");
}
else if(ch=='>') {
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out (NE," ");}
else
{
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out (LT," ");
}
break;
case '=':
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out(EQ, " ");
break;
case '>':
ch=fgetc(fp);
if(ch=='='){
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out(GE," ");
}
else
{
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out(GT," ");
}
break;
case ':':
ch=fgetc(fp);
if(ch=='='){
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out(IS," ");
}
else
report_error();
break;
case'+':
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1); else fseek (fp,-1,1);
siagn=1;
out(PL, " "); break;
case'-':
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out(MI, " "); break;
case'*':
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out(MU, " "); break;
case'/':
ch=fgetc(fp);
if(isalnum (ch)) fseek (fp,-2,1);else fseek (fp,-1,1);
siagn=1;
out(DI, " "); break;
case' ':
break;//当遇到空格时继续向下走
default:
report_error( ); break;//report_error函数 单词错误时输出的内容
}

if(ch==' '||siagn==1){
fseek(fp,1,1); siagn=0;
scanner_example(fp);
}
if(ch==EOF)
return;
// return;
}

void report_error(){

printf("error\n");

}

void out(int c, char *vp){
char* cl = NULL;
switch (c)
{
case 1: cl = "BEGIN"; break;
case 2: cl = "END"; break;
case 3: cl = "IF"; break;
case 4: cl = "THEN"; break;
case 5: cl = "ELSE"; break;
case 6: cl = "ID"; break;
case 7: cl = "UCON"; break;
case 8: cl = "LT"; break;
case 9: cl = "LE"; break;
case 10: cl = "EQ"; break;
case 11: cl = "NE"; break;
case 12: cl = "GT"; break;
case 13: cl = "GE"; break;
case 14: cl = "IS"; break;
case 15: cl = "PL"; break;
case 16: cl = "MI"; break;
case 17: cl = "MU"; break;
case 18: cl = "DI"; break;
case 19: cl = "UCON"; break;
case 20: cl = "DOUBLE"; break;
case 21: cl = "OCTAL"; break;
case 22: cl = "HEX"; break;
}
printf("e(%s,%s)\n",cl, vp);

fprintf(fp1,"e(%s,%s)\n",cl, vp);
fseek(fp1,0,1);

}

void main(){
char *fname="test1.txt";//读取为文件fp
FILE *fp;
if((fp1=fopen("asd.txt","w"))==NULL) /*建立文件 写入文件的文件fp1*/{ printf("\nopen file error"); getchar(); exit(1); }
if((fp=fopen(fname,"r"))==NULL)
{
printf("\nSorry, Can't open the file!\n");
getchar();
exit(0);
}
else
{
scanner_example(fp);
}
fclose(fp);
fclose(fp1);
}
本程序从文件test1.txt中读入要分析的单词并把扫描的结果输入asd.txt文件中；
利用gechar（）方法从文件中一个个读入字符，并采用递归的方法对字符多次读入直到读到文件的结尾停止。
字符读入程序后采用图一的方法进行分析解决。

4)无符号常数的识别
针对扫描程序所得到的数字我们可以进行无符号数的处理。
加入了语义过程说明的识别无符号数的状态矩阵，编写词法分析程序，部分实现代码如程序二所示。
表2 包含语义处理过程的识别无符号数的状态矩阵

程序2 单词分类码为UCON的无符号数的识别程序
7 假定无符号常量的类数为7
#define ClassOther 200
#define EndState -1
int w,n,p,e,d;
int Class=-1; //Used to indicate class of the word 用于表示单词的类型 1位int 2为double
int ICON;
double FCON;
static int CurrentState; //Used to present current state, the initial value:0 用于当前状态，初始值：0
int GetChar (FILE *p);
int EXCUTE (int,int);
int LEX (FILE *p);
int HandleOtherWord (void)
{ return ClassOther;
}
int HandleError (void)
{printf ("Error!\n"); return 0;}

int GetChar (FILE *p)
{
chf=fgetc(p);
if(isdigit(chf)) {d=chf-'0';return DIGIT;}
if (chf=='.') return POINT;
if (chf=='E'||chf=='e') return POWER;
if (chf=='+') return PLUS;
if (chf=='-') return MINUS;
return OTHER;
}
int EXCUTE (int state, int symbol)
{
switch (state)
{
case 0:switch (symbol)
{
case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;break;
case POINT: w=0;n=0;p=0;e=1;CurrentState=3;break;
default: HandleOtherWord( );Class=ClassOther;
CurrentState=EndState;
}
break;
case 1:switch (symbol)
{
case DIGIT: w=w*10+d;break; //CurrentState=1
case POINT: CurrentState=2;break;
case POWER: CurrentState=4;break;
default: ICON=w;Class=1;CurrentState=EndState;
}
break;
case 2:switch (symbol)
{
case DIGIT: n++;w=w*10+d;break;
case POWER: CurrentState=4;break;
default: FCON=w*pow(10,e*p-n);Class=2;CurrentState=EndState;
}
break;
case 3:switch (symbol)
{
case DIGIT: n++;w=w*10+d;CurrentState=2;break;
default: HandleError( );CurrentState=EndState;
}
break;
case 4:switch (symbol)
{
case DIGIT: p=p*10+d;CurrentState=6;break;
case MINUS: e=-1;CurrentState=5;break;
case PLUS: CurrentState=5;break;
default: HandleError( );CurrentState=EndState;
}
break;
case 5:switch (symbol)
{
case DIGIT: p=p*10+d;CurrentState=6;break;
default: HandleError( );CurrentState=EndState;
}
break;
case 6:switch (symbol)
{
case DIGIT:p=p*10+d;break;
default: FCON=w*pow(10,e*p-n);Class=2;CurrentState=EndState;
}
break;
}
return CurrentState;
}
int LEX (FILE *p)
{
int ch;
CurrentState=0;
while (CurrentState!=EndState)
{
ch=GetChar(p);
EXCUTE (CurrentState,ch);
}
return Class;
}

5)八进制与十六进制数的处理
在无符号数的处理过程中没有设计八进制与十六进制数转换成十进制的数，但为了方面以后的使用我们进入进制的转换。
设计思路：判断八进制是以0开头，十六进制为0X开头，并且判断后面所跟数字是否超出八进制或十六进制的范围，若超出则错误，如不超出则用8或16转换为相应十进制数字再次读入写个字符循环，直到数字结束。
程序3 单词分类码为八进制的无符号数的识别程序
double octal(char *TP){
int x,y=-1,ypoint=0;//计数 ypoint=-1记录有小数点 y记录是第几位小数
int m=0;
double FINALL=0.0;//放结果
while(*TP!='\0'){
if(*TP=='.'){
ypoint=-1;
}
else{
x=*TP-'0';
if(ypoint!=-1){
FINALL=FINALL*8+x;
}
if(ypoint==-1){
FINALL=FINALL+x*pow(8,y);
y--;
}
}
TP++;
}
return FINALL;

程序4 单词分类码为十六进制的无符号数的识别程序
double hex(char *TP){
int x,y=-1,ypoint=0;//计数 ypoint=-1记录有小数点 y记录是第几位小数
int m=0;
double FINALL=0.0;//放结果
while(*TP!='\0'){
if(*TP=='.'){
ypoint=-1;
}
else{
if(ypoint!=-1){
if(*TP>='0'&&*TP<='9'){
x=*TP-'0';
}
else if(*TP>='a'&&*TP<='f'){
x=*TP-'a'+1;
}
else if(*TP>='A'&&*TP<='F'){
x=*TP-'a'+1;
}
FINALL=FINALL*16+x;
}
if(ypoint==-1){
if(*TP>='0'&&*TP<='9'){
x=*TP-'0';
}
else if(*TP>='a'&&*TP<='f'){
x=*TP-'a'+1;
}
else if(*TP>='A'&&*TP<='F'){
x=*TP-'a'+1;
}
FINALL=FINALL+x*pow(16,y);
y--;
}
}
TP++;
}
return FINALL;
}

2、语法分析程序设计与实现
语法分析，采用的是算符优先文法实现；重点与难点为根据文法求出FirstVt与LastVt集合，构造出算符表。语法分析程序的输入结构为词法分析的输出结果。数字的标志位都设为i 如（i，25.8）；运算符的标志位为其本身如（+， ）其他符号暂不计算，以方便语法分析程序的编写。
算符优先总流程图 图2
开始
初始化FIRSTVT集和LASTVT集
求出文法终结符集
是否为文法
输出非终结符FIRSTVT集和LASTVT集
生成并输出算法分析表
输入需要验证的字符串，以#结束
输出结果
输出结果
结束
输入文法规则和数目
N
Y

1） 判断是否为算符文法
程序5
//judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法
int judge1(int n)
{
int j=3,flag=0;
for(int i=0;i<=n;i++)
while(str[i][j]!='\0')
{
char a=str[i][j];
char b=str[i][j+1];
if(IsLetter(a)&&IsLetter(b))
{flag=1;break;}
else j++;
}
if(flag==1)
return 0;
else
return 1;
}

结果：
输入文件

输入结果

2） 判断是否为算符优先文法
程序5
judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法
void judge2(int n)
{
for(int i=0;i<=n;i++)
if(str[i][3]=='~'||judge1(n)==0||FLAG==1)//'~'代表空字
{cout<<"该文法不是算符优先文法!"<<endl;FF=0;break;}
if(i>n)
cout<<"该文法是算符优先文法!"<<endl;
}

3） 求FristVt( )和LastVt（）集合
程序6
//createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体
void createF(int n)
{
int k=0,i=1;char g;
char t[10];//t数组用来存放非终结符
t[0]=str[0][0];
while(i<=n)
{
if(t[k]!=str[i][0])
{k++;t[k]=str[i][0];g=t[k];i++;}
else i++;
}
kk=0;
char c;
for(i=0;i<=n;i++)
{ int j=3;
while(str[i][j]!='\0')
{
c=str[i][j];
if(IsLetter(c)==0)
{
if(!search1(r,kk,c))
r[kk]=c;kk++;//r数组用来存放终结符
}
j++;
}
}
m=0;
for(i=0;i<k;i++)
for(int j=0;j<kk-1;j++)
{
F[m].R=t[i];
F[m].r=r[j];
F[m].flag=0;
m++;
}
}
//search函数是将在