编译原理实验.docx
- 文档编号:8872949
- 上传时间:2023-05-15
- 格式:DOCX
- 页数:42
- 大小:222.18KB
编译原理实验.docx
《编译原理实验.docx》由会员分享,可在线阅读,更多相关《编译原理实验.docx(42页珍藏版)》请在冰点文库上搜索。
编译原理实验
实验一词法分析
一、实验目的
编制一个读单词过程,从输入的源程序中,识别出各个具有独立意义的单词,即基本保留字、标识符、常数、运算符、分隔符五大类。
并依次输出各个单词的内部编码及单词符号自身值。
二、实验题目
如源程序为C语言。
输入如下一段:
main()
{
inta=-5,b=4,j;
if(a>=b)
j=a-b;
elsej=b-a;
}
要求输出如下:
(2,”main”)(5,”(”)(5,”)”)
(5,”{”)(1,”int”)(2,”a”)
(4,”=”)(3,”-5”)(5,”,”)
(2,”b”)(4,”=”)(3,”4”)
(5,”,”)(2,”j”)(5,”;”)
(1,”if”)(5,”(”)(2,”a”)
(4,”>=”)(2,”b”)(5,”)”)
(2,”j”)(4,”=”)(2,”a”)
(4,”-”)(2,”b”)(5,”;”)
(1,”else”)(2,”j”)(4,”=”)
(2,”b”)(4,”-”)(2,”a”)
(5,”;”)(5,”}”)
三、实验理论依据
(一)识别各种单词符号
程序语言的单词符号一般分为五种:
关键字(保留字/基本字)if、while、begin…
标识符:
常量名、变量名…
常数:
34、56.78、true、‘a’、…
运算符:
+、-、*、/、〈、and、or、….
界限符:
,;(){}/*…
识别单词:
掌握单词的构成规则很重要
标识符的识别:
字母|下划线+(字母/数字/下划线)
关键字的识别:
与标识符相同,最后查表
常数的识别
界符和算符的识别
大多数程序设计语言的单词符号都可以用转换图来识别,如图1-1
图1-1
词法分析器输出的单词符号常常表示为二元式:
(单词种别,单词符号的属性值)
单词种别通常用整数编码,如1代表关键字,2代表标识符等
关键字可视其全体为一种,也可以一字一种。
采用一字一种得分法实际处理起来较为方便。
标识符一般统归为一种
常数按类型(整、实、布尔等)分种
运算符可采用一符一种的方法。
界符一般一符一种的分法。
(二)超前搜索方法
词法分析时,常常会用到超前搜索方法。
如当前待分析字符串为“a>+”,当前字符为“>”,此时,分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢?
显然,只有知道下一个字符是什么才能下结论。
于是分析器读入下一个字符’+’,这时可知应将’>’解释为大于运算符。
但此时,超前读了一个字符’+’,所以要回退一个字符,词法分析器才能正常运行。
又比如:
‘+’分析为正号还是加法符号
(三)预处理
预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理,及删除注解等。
由一个预处理子程序来完成。
四、词法分析器的设计
1、设计方法:
2、写出该语言的词法规则。
3、把词法规则转换为相应的状态转换图。
4、把各转换图的初态连在一起,构成识别该语言的自动机
5、设计扫描器
6、把扫描器作为语法分析的一个过程,当语法分析需要一个单词时,就调用扫描器。
7、扫描器从初态出发,当识别一个单词后便进入终态,送出二元式
图1-2取单词程序框图
五、程序代码
#include
#include
FILE*fp;
charcbuffer;
char*key[8]={"if","else","for","while","do","return","break","continue"};
intatype,id=4;
intisalpha(charc)
{
if((c<='z')&&(c>='a')||(c<='Z')&&(c>='A'))
return1;
elsereturn0;
}
intisdigit(charc)
{
if(c>='0'&&c<='9')
return1;
elsereturn0;
}
intsearch(charsearchchar[],intwordtype)/*判断单词是保留字还是标识符*/
{
inti=0;
intp;
switch(wordtype)
{
case1:
for(i=0;i<=7;i++)
{
if(strcmp(key[i],searchchar)==0)
{p=i+1;break;}/*是保留字则p为非0且不重复的整数*/
elsep=0;/*不是保留字则用于返回的p=0*/
}
return(p);
}
}
charalphaprocess(charbuffer)
{intatype;/*保留字数组中的位置*/
inti=-1;
charalphatp[20];
while((isalpha(buffer))||(isdigit(buffer))||buffer=='_')
{
alphatp[++i]=buffer;
buffer=fgetc(fp);
}/*读一个完整的单词放入alphatp数组中*/
alphatp[i+1]='\0';
atype=search(alphatp,1);/*对此单词调用search函数判断类型*/
if(atype!
=0)
{printf("(%d,\"%s\")\n",atype-1,alphatp);id=1;}
else
{printf("(2,\"%s\")\n",alphatp);id=2;}
return(buffer);
}
chardigitprocess(charbuffer)
{
inti=-1;
chardigittp[20];
while((isdigit(buffer))||buffer=='.')/*1判断小数*/
{
digittp[++i]=buffer;
buffer=fgetc(fp);
}
digittp[i+1]='\0';
printf("(3,\"%s\")\n",digittp);
id=3;
return(buffer);
}
charotherprocess(charbuffer)
{
charch[20];
ch[0]=buffer;
ch[1]='\0';
if(ch[0]==','||ch[0]==';'||ch[0]=='{'||ch[0]=='}'||ch[0]=='('||ch[0]==')')
{printf("(5,\"%s\")\n",ch);
buffer=fgetc(fp);
id=5;
return(buffer);}
if(ch[0]=='/')
{
buffer=fgetc(fp);
if(buffer=='*')/*2区分注释符号和除号*/
{
ch[1]=buffer;
buffer=fgetc(fp);
while(buffer!
='*')
{
buffer=fgetc(fp);
}
ch[2]=buffer;
buffer=fgetc(fp);
if(buffer=='/')
{
ch[3]=buffer;
ch[4]='\0';
}
printf("(5,\"%s\")\n",ch);
}
else{
printf("(4,\"%s\")\n",ch);
id=4;
return(buffer);
}
buffer=fgetc(fp);
id=5;
return(buffer);
}
if(ch[0]=='*')
{printf("(4,\"%s\")\n",ch);
buffer=fgetc(fp);
id=4;
return(buffer);
}
if(ch[0]=='='||ch[0]=='!
'||ch[0]=='<'||ch[0]=='>')
{buffer=fgetc(fp);
if(buffer=='=')
{ch[1]=buffer;
ch[2]='\0';
printf("(4,\"%s\")\n",ch);
}
else
{printf("(4,\"%s\")\n",ch);
id=4;
return(buffer);
}
buffer=fgetc(fp);
id=4;
return(buffer);
}
if(ch[0]=='+'||ch[0]=='-')
{if(id==4)/*在当前符号以前是运算符,则此时为正负号*/
{buffer=fgetc(fp);
ch[1]=buffer;
ch[2]='\0';
printf("(3,\"%s\")\n",ch);
id=3;
buffer=fgetc(fp);
return(buffer);
}
ch[1]='\0';
printf("(4,\"%s\")\n",ch);
buffer=fgetc(fp);
id=4;
return(buffer);
}
if(ch[0]=='#')/*3识别头文件*/
{
chart[20];
inti=0;
t[0]=ch[0];
buffer=fgetc(fp);
while((isalpha(buffer))||buffer==''||buffer=='<'||buffer=='>')
{
t[++i]=buffer;
buffer=fgetc(fp);
}
t[i+1]='\0';
printf("(6,\"%s\")\n",t);
id=6;
return(buffer);
}
if(ch[0]=='\\')/*4识别转义符号*/
{
buffer=fgetc(fp);
ch[1]=buffer;
printf("(6,\"%s\")\n",ch);
buffer=fgetc(fp);
return(buffer);
}
if(ch[0]=='|'||ch[0]=='&')/*5判断或与*/
{
buffer=fgetc(fp);
if(ch[0]==buffer)
{
ch[1]=buffer;
}
ch[2]='\0';
printf("(4,\"%s\")\n",ch);
buffer=fgetc(fp);
return(buffer);
}
if(ch[0]=='"'||ch[0]=='\'')/*6判断双引号和单引号*/
{
printf("(5,\"%s\")\n",ch);
id=5;
buffer=fgetc(fp);
return(buffer);
}
}
intmain()
{
if((fp=fopen("example.c","r"))==NULL)/*只读方式打开一个文件*/
printf("error");
else
{
cbuffer=fgetc(fp);/*fgetc()函数:
从磁盘文件读取一个字符*/
while(cbuffer!
=EOF)
{
if(cbuffer==''||cbuffer=='\n')/*掠过空格和回车符*/
cbuffer=fgetc(fp);
else
if(isalpha(cbuffer))
cbuffer=alphaprocess(cbuffer);
else
if(isdigit(cbuffer))
cbuffer=digitprocess(cbuffer);
elsecbuffer=otherprocess(cbuffer);
}
}
return0;
}
六、实验结果
程序添加了识别小数,识别注释符,识别自加自减符号,识别头文件,识别转义符号,识别或与符号,识别单引号和双引号,识别中括号,识别格式符,结果如图1-3所示:
图1-3
实验二LL
(1)分析法
一、实验目的:
根据某一文法编制调试LL
(1)分析程序,以便对任意输入的符号串进行分析。
本次实验的目的主要是加深对预测分析LL
(1)分析法的理解。
二、实验题目
实验规定对下列文法,用LL
(1)分析法对任意输入的符号串进行分析:
(1)E:
:
=TG
(2)G:
:
=+TG
(3)G:
:
=ε
(4)T:
:
=FS
(5)S:
:
=*FS
(6)S:
:
=ε
(7)F:
:
=(E)
(8)F:
:
=i
若输入串为i+i*i#,则输出为:
LL
(1)的分析表为:
i
+
*
(
)
#
说明
E
e
e
Select(E→TG)={(,i}
G
g
g1
g1
Select(G→+TG)={+}
Select(G→є)={#,)}
T
t
t
Select(T→FS)={(,i}
S
s1
s
s1
s1
Select(S→*FS)={*}Select(S→є)={#,)+}
F
f1
f
Select(F→(E))={(}
Select(F→i)={i}
三、程序代码
#include
#include
#include
usingnamespacestd;
charA[20];/*分析栈*/
charB[20];/*剩余串*/
charv1[20]={'i','+','*','(',')','#'};/*终结符*/
charv2[20]={'E','G','T','S','F'};/*非终结符*/
intj=0,b=0,top=0,l;/*L为输入串长度*/
typedefstructtype/*产生式类型定义*/
{
charorigin;/*大写字符*/
chararray[5];/*产生式右边字符*/
intlength;/*字符个数*/
}type;
typee,t,g,g1,s,s1,f,f1;/*结构体变量*/
typeC[10][10],cha;/*预测分析表*/
voidprint()/*输出分析栈*/
{
inta;/*指针*/
for(a=0;a<=top+1;a++)
printf("%c",A[a]);
printf("\t\t");
}
voidprint1()/*输出剩余串*/
{
intj;
for(j=0;j
printf("");
for(j=b;j<=l;j++)
printf("%c",B[j]);
printf("\t\t\t");
}
intmain()
{
/*把文法产生式赋值结构体*/
e.origin='E';
strcpy(e.array,"TG");
e.length=2;
t.origin='T';
strcpy(t.array,"FS");
t.length=2;
g.origin='G';
strcpy(g.array,"+TG");
g.length=3;
g1.origin='G';
//g1.array[0]='^';
strcpy(g1.array,"^");
g1.length=1;
s.origin='S';
strcpy(s.array,"*FS");
s.length=3;
s1.origin='S';
//s1.array[0]='^';
strcpy(s1.array,"^");
s1.length=1;
f.origin='F';
strcpy(f.array,"(E)");
f.length=1;
f1.origin='F';
strcpy(f1.array,"i");
f1.length=1;
for(intm=0;m<=4;m++)/*初始化分析表*/
for(intn=0;n<=5;n++)
C[m][n].origin='N';/*全部赋为空*/
cha.origin='N';
/*填充分析表*/
C[0][0]=e;
C[0][3]=e;
C[1][1]=g;
C[1][4]=g1;
C[1][5]=g1;
C[2][0]=t;
C[2][3]=t;
C[3][1]=s1;
C[3][2]=s;
C[3][4]=C[3][5]=s1;
C[4][0]=f1;
C[4][3]=f;
charch;
do/*读入分析串*/
{
scanf("%c",&ch);
if((ch!
='i')&&(ch!
='+')&&(ch!
='*')&&(ch!
='(')&&(ch!
=')')&&(ch!
='#'))
{
printf("输入串中有非法字符\n");
break;
}
B[j]=ch;
j++;
}
while(ch!
='#');
l=j;/*分析串长度*/
ch=B[0];/*当前分析字符*/
A[top]='#';
A[++top]='E';/*'#','E'进栈*/
printf("步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n");
intk=1;
intflag=false;
intfinish=false;
intn,m;
do
{
charx;
x=A[top--];/*x为当前栈顶字符*/
printf("%d",k++);
printf("\t\t");
for(j=0;j<=5;j++)/*判断是否为终结符*/
if(x==v1[j])
{
flag=1;
break;
}
if(flag==1)/*如果是终结符*/
{
if(x=='#'&&ch=='#')
{
finish=1;/*结束标记*/
print();
print1();
printf("acc!
\n");
getchar();;/*接受*/
getchar();
break;
}
if(x==ch)
{
print();
print1();
printf("%c匹配\n",ch);
ch=B[++b];/*下一个输入字符*/
flag=0;/*恢复标记*/
}
else/*出错处理*/
{
print();
print1();
printf("%c出错\n",ch);/*输出出错终结符*/
break;
}
}
else/*非终结符处理*/
{
for(j=0;j<=4;j++)
if(x==v2[j])
{
m=j;/*行号*/
break;
}
for(j=0;j<=5;j++)
if(ch==v1[j])
{
n=j;/*列号*/
break;
}
cha=C[m][n];
if(cha.origin!
='N')/*判断是否为空*/
{
print();
print1();
printf("%c->",cha.origin);/*输出产生式*/
for(j=0;j printf("%c",cha.array[j]); printf("\n"); for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/ A[++top]=cha.array[j]; if(A[top]=='^')/*为空则不进栈*/ top--; } else { print(); print1(); printf("%c出错C表不存在\n",ch);/*输出出错终结符*/ break; } } } while(true); return0; } 四、实验结果 输入字符串i+i*i#进行分析,如图2-1所示: 图2-1 输入字符串i)#进行分析,如图2-2所示: 图2-2 实验三逆波兰式的产生及计算 一、实验目的 将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式,并计算用逆波兰式来表示的算术表达式的值 二、实验题目 如输入如下: 21+((42-2)*15+6)-18# 输出为: 原来表达式: 21+((42-2)*15+6)-18# 后缀表达式: 21&42&2&-15&*6&++18&- 计算结果: 609 三、算法流程图 图3-1生成逆波兰式的程序流程图 图3-2计算逆波兰式的程序流程图 四、程序代码 #include #include #include usingnamespacestd; charch; inttop,length,t; charex[100]; charstr[100]; doublecalculate() { doubled; doublestack[100],xx=0; top=-1; for(intt=0;t { ch=ex[t]; switch(ch) { case'+': stack[top-1]=stack[top-1]+stack[top]; top--; t++; break; case'-': stack[top-1]=stack[top-1]-stack[top]; top--; t++; break; case'*': stack[top-1]=stack[top-1]*stack[top]; top--; t++; break; case'/': if(stack[top]! =0) stack[top-1]=stack[top-1]/stack[top]; else { printf("\n\t除零错误! \n"); break;/*异常退出*/ } top--; t++; break; case'^': //stac
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 实验