编译原理实验.docx
- 文档编号:17099547
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:35
- 大小:74.20KB
编译原理实验.docx
《编译原理实验.docx》由会员分享,可在线阅读,更多相关《编译原理实验.docx(35页珍藏版)》请在冰点文库上搜索。
编译原理实验
实验一:
简易扫描器的DFA设计与实现
实验原理:
词法分析器的工作原理
实验内容:
用程序模拟实现一个简易扫描器的工作过程,从输入字符串到分析完以后以(CLASS,VALUE)的标准格式输出
实验要求:
1.源程序设计语言G[<标志符>]:
<标志符>→<标志符><字母>|<标志符><下划线>|<标志符><数字>|<字母>|<下划线>
<常数>→<整数>
<整数>→0|<非零数字><泛整数>
<泛整数>→<数字>|<数字><泛整数>|ε
<关系符>→<|<=|=|>|>=|<>
<字母>
→A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<非零数字>→1|2|3|4|5|6|7|8|9
<数字>→<非零数字>|0
2.能识别下表所列的单词符号:
单词符号
类别编码
类别码的助记符
单词之值
begin
1
BEGIN
end
2
END
if
3
IF
then
4
THEN
else
5
ELSE
标识符
6
ID
整数
7
INT
数字串
<
8
LT
<=
9
LE
=
10
EQ
<>
11
NE
>
12
GT
>=
13
GE
+
14
ADD
-
15
SUB
*
16
MUL
/
17
DIV
;
18
SEM
(
19
LB
)
20
RB
3.能跳过源程序中的空白格:
两个单词之间的任何空格,制表符,回车,换行都是白空格,除了用来分隔单词以外,没有意义;
4.能跳过注释:
1)接连出现的/*到下一次接连出现的*/之间的任何文字都是注释(多行);
2)从某行接连出现的//到该行的结尾的任何文字都是注释(单行)。
实验步骤:
1.DFA及相关语义过程;
2.流程图(或程序的基本框架);
3.根据实验要求编写一个能够完全遍历整个词法分析程序的输入字符串;
4.把课本P81程序3-4的函数编写完整。
1.
OUTSEM””)
OUT(MUL,””)
OUT(SUB””)
其他
9
OUT(ADD,””)
0
2
4
非空格
3
空格
OUT(EQ,””)
C不=0时OUT(c,””)
OUT(GT,””)
OUT(GE,””)
OUT(LT,””)
OUT(NE,””)
OUT(LE,””)
OUT(INT,”TOKEN)
C=0时OUT(ID,TOKEN)
OUT(RB,””)
OUT(DIV,””)
OUT(LB””)
非d
26
非字母和d
+
-
*
)
START
(
1
;
8
*
非=
=
>
=
非=和>
>
=
<
d
d
非/
/
*
非*
字母,d
字母
换行
非换行
非/或非*
/
/
空格
5
22
21
20
18
13
10
6
7
29
28
27
25
24
23
17
16
12
14
19
11
15
DFA及相关语义过程
2.流程图(或程序的基本框架);
开始
是否文件尾
除去空格
换行符合
无意义字符
除去注释
识别ID或标识符
识别数字
识别符号
Y
N
退出
3.代码
#define_CRT_SECURE_NO_WARNINGS
#include
#include
#include
#defineBEGIN1
#defineEND2
#defineIF3
#defineTHEN4
#defineELSE5
#defineID6
#defineINT7
#defineLT8
#defineLE9
#defineEQ10
#defineNE11
#defineGT12
#defineGE13
#defineADD14
#defineSUB15
#defineMUL16
#defineDIV17
#defineSEM18
#defineLB19
#defineRB20
charTOKEN[20];
intlookup(char*);//查找标识符
voidout(int,char*);//输出扫描结果
voidreport_error();//错误信息
//externintlookup(char*);
intlookup(char*temp){
if(strcmp(temp,"begin")==0)returnBEGIN;
elseif(strcmp(temp,"end")==0)returnEND;
elseif(strcmp(temp,"if")==0)returnIF;
elseif(strcmp(temp,"then")==0)returnTHEN;
elseif(strcmp(temp,"else")==0)returnELSE;
elsereturn0;
}
//externvoidout(int,char*);
voidout(inta,char*s){
switch(a)
{
caseBEGIN:
printf("<%s,%s>\n","BEGIN","begin");
break;
caseEND:
printf("<%s,%s>\n","END","end");
break;
caseIF:
printf("<%s,%s>\n","IF","if");
break;
caseTHEN:
printf("<%s,%s>\n","THEN","then");
break;
caseELSE:
printf("<%s,%s>\n","ELSE","else");
break;
caseID:
printf("<%s,%s>\n","ID",s);
break;
caseINT:
printf("<%s,%s>\n","INT",s);
break;
caseLT:
printf("<%s,%s>\n","LT","<");
break;
caseLE:
printf("<%s,%s>\n","LE","<=");
break;
caseEQ:
printf("<%s,%s>\n","EQ","=");
break;
caseNE:
printf("<%s,%s>\n","NE","<>");
break;
caseGT:
printf("<%s,%s>\n","GT",">");
break;
caseGE:
printf("<%s,%s>\n","GE",">=");
break;
caseADD:
printf("<%s,%s>\n","ADD","+");
break;
caseSUB:
printf("<%s,%s>\n","SUB","-");
break;
caseMUL:
printf("<%s,%s>\n","MUL","*");
break;
caseDIV:
printf("<%s,%s>\n","DIV","/");
break;
caseSEM:
printf("<%s,%s>\n","SEM",";");
break;
caseLB:
printf("<%s,%s>\n","LB","(");
break;
caseRB:
printf("<%s,%s>\n","RB",")");
break;
default:
break;
}
}
//externreport_error(void);
voidreport_error(){
printf("未识别字符\n");
}
voidscanner_example(FILE*fp){
charch;
inti=0,c;
ch=fgetc(fp);
if(ch==''||ch=='\n'||ch==-1)return;//略掉空格,换行符和无意义字符
if(ch=='/')//如果扫描到/
{
charch2=fgetc(fp);//取下一个字符
if(ch2=='/')//判断这个字符是不是/
{
printf("//");//条件成立构成//注释
while(ch2=fgetc(fp))
{
printf("%c",ch2);//输出信息调试用,要跳过,注释这行即可
if(ch2=='\n'){break;}//到了行尾跳出
}
}
elseif(ch2=='*')//判断是否多行注释
{
printf("/*");
while(ch2=fgetc(fp))
{
if(ch2=='*'){//如果遇到*
ch2=fgetc(fp);
if(ch2=='/')break;//切下一个为/跳出
}
else
{
printf("%c",ch2);//输出信息调试用,要跳过,注释这行即可
}
}
printf("*/\n");
return;
}
fseek(fp,-1,1);//没成立的话、文件指针回退1
}
if(isalpha(ch)){//扫描字母
TOKEN[i]=ch;i++;
while(isalnum(ch)){//字母后面带数字的也是合法ID
TOKEN[i]=ch;i++;
ch=fgetc(fp);
}
TOKEN[i]='\0';//给串打上结束符
fseek(fp,-1,1);
strncpy(TOKEN,TOKEN+1,i);//剪切字串,不要头个字符
c=lookup(TOKEN);//查找是否关键字并得到返回值
if(c==0){
out(ID,TOKEN);//不是关键字则输出ID
}
else{out(c,"");}//否则则输出关键字
}
else
if(isdigit(ch)){//扫描数字
TOKEN[0]=ch;
ch=fgetc(fp);i=1;
while(isdigit(ch))
{
TOKEN[i]=ch;i++;
ch=fgetc(fp);
}
TOKEN[i]='\0';
fseek(fp,-1,1);
out(INT,TOKEN);
}
else//前面都不成立的话、则查看是不是符号
switch(ch){
case'<':
ch=fgetc(fp);
if(ch=='=')out(LE,"");
elseif(ch=='>')out(NE,"");
else
{
fseek(fp,-1,1);
out(LT,"");
}
break;
case'=':
out(EQ,"");break;
case'>':
ch=fgetc(fp);
if(ch=='=')out(GE,"");
elseif(ch=='>')out(NE,"");
else
{
fseek(fp,-1,1);
out(GT,"");
}
break;
case'+':
out(ADD,"");break;
case'-':
out(SUB,"");break;
case'*':
out(MUL,"");break;
case'/':
out(DIV,"");break;
case'(':
out(LB,"");break;
case')':
out(RB,"");break;
case';':
out(SEM,"");break;
break;
default:
report_error();//报错
break;
}
return;
}
intmain(){
FILE*fp;
fp=fopen("d:
\\test.txt","r");
inttt;
while(!
feof(fp))//如果文件没到行尾则循环
{
scanner_example(fp);
}
return0;
}
测试文件:
结果:
心得:
经过这次实验,虽然在课堂上写的程序有许多缺陷,但回去后,我认真的重写了一遍,实现了要求的功能,并通过这次的实验,加深了对扫描器的理解。
实验二:
自顶向下分析:
LL
(1)分析方法
实验原理:
语法分析器的工作原理
实验内容:
1、了解语法分析的其中一种自顶向下分析方式LL
(1);
2、学会构造LL
(1)分析表;
3、上机实现课本P120预测分析器的工作流程。
实验要求:
要求能对下列文法所产生的符号串进行语法分析:
①EE+T|E-T|T
②TT*F|T/F|F
③F(E)|num|id
对输入的符号在分析完之后,如果正确就报告,有误就停止。
实验步骤:
1、消除文法的左递归(①、②产生式);
2、对消除左递规后的文法分别求出各FIRST集和FOLLOW集,再构造相应的LL
(1)分析表;
3、根据参考程序(见程序设计指导),实现预测分析器的工作流程。
程序设计指导:
1、本次实验要完成的程序功能为:
用程序实现预测分析器的工作流程,根据不断地查找指定文法得出的LL
(1)分析表,最终判断输入串是否符合该文法的语法要求;
2、首先,在本次实验的预习报告中要先完成实验步骤中的前面两条;
3、参考程序:
charstack[50];//分析栈
chara[100];//输入器
gettop(stack);//自己定义
is_nonterminal(x);//自己定义
is_terminal(x);//自己定义
pop
(1);//自己定义
push();//自己定义
intLL1driver(void)
{
stack[0]='#';
stack[1]='E';//把初始符号移入空栈
/*输入指示器指向输入器的初始位置*/
while(!
stack_empty())
{
x=gettop(stack);/*取当前栈顶的符号x*/
/*取当前指示器指向的位置*/
if(is_nonterminal(x))
{
/*查LL
(1)分析表,对应有产生式:
xày1…y2*/if(查表成功)
{pop
(1);//栈顶x出栈
push();/*把产生式右部的侯选式反序(y2…y1)压入分析栈*/
}
elseprintf("语法分析过程有误!
");//查表不成功
}//endif
else
if(is_terminal(x)&&x=ai)
{pop
(1);//栈顶x出栈
/*输入指示器向前推进一个位置*/
}
else
if(x=ai=#)
printf("success!
");
elseprintf("error!
");
}//endwhile
}//endLL1driver
1.消除文法的左递归(①、②产生式);
①EE+T|E-T|T
ETE’
E’+TE’|-TE’|ε
②TT*F|T/F|F
TFT’
T’*FT’|/FT’|ε
③F(E)|num|id
2.对消除左递规后的文法分别求出各FIRST集和FOLLOW集,再构造相应的LL
(1)分析表;
FIRST
FLOLLOW
E
{(,num,id}
{),#}
E’
{+,-,ε}
{),#}
T
{(,num,id}
{+,-,),#}
T’
{*,/,ε}
{+,-,),#}
F
{(,num,id}
{*,/,+,-,),#}
num
id
+
-
*
/
(
)
#
E
EETE’
ETE’
ETE’
E’
E’+TE’
E’-TE’
E’ε
E’ε
T
TFT’
TFT’
TFT’
T’
Tε
Tε
T*FT’
T/FT’
Tε
Tε
F
Fnum
Fid
F(E)
3.根据参考程序(见程序设计指导),实现预测分析器的工作流程。
#define_CRT_SECURE_NO_WARNINGS
#include
#include
structanlysis
{
charvn;
charvt;
charrs[20];
}productions[19]={
{'E','n',"TX"},
{'E','i',"TX"},
{'E','(',"TX"},
{'X','+',"+TX"},
{'X','-',"-TX"},
{'X',')',""},
{'X','#',""},
{'T','n',"FY"},
{'T','i',"FY"},
{'T','(',"FY"},
{'Y','*',"*FY"},
{'Y','/',"/FY"},
{'Y','+',""},
{'Y','-',""},
{'Y',')',""},
{'Y','#',""},
{'F','n',"n"},
{'F','i',"i"},
{'F','(',"(E)"},
};
charstack[50],a[50],token[20];
chargettop()
{
chartop;
intj=strlen(stack)-1;
top=stack[j];
returntop;
}
intis_vn(charx)
{
inti,c;
for(i=0;i<19;i++)
{
if(productions[i].vn==x)
{
c=1;
returnc;
}
}
c=0;
returnc;
}
voidpop()
{
intj;
j=strlen(stack)-1;
stack[j]='\0';
}
voidpush()
{
strcat(stack,token);
}
voidinv()
{
chartemp;
intn=strlen(token);
inti,j,m=(n-2)/2;
for(i=0;i<=m;i++)
{
j=n-1-i;
temp=token[i];
token[i]=token[j];
token[j]=temp;
}
}
voidLL1driver(chara[])
{
stack[0]='#';
stack[1]='E';
printf("\nstack=%s,a=%s",stack,a);
intk=0;
charx;
do
{
start:
x=gettop();
if(is_vn(x))
{
for(inti=0;i<=19;i++)
{
if((productions[i].vt==a[k])&&(productions[i].vn==x))
{
for(intj=0;j<20;j++)
{
token[j]=productions[i].rs[j];
}
inv();
pop();
push();
printf("\nstack=%s,a[k]=%c",stack,a[k]);
gotostart;
}
}
printf("\nerror");
return;
}
else
if(x!
='#')
{
if(a[k]==x)
{
pop();
printf("\nstack=%s,a[k]=%c",stack,a[k+1]);
}
else
{
printf("\nerror");
return;
}
}
else
if(a[k]=='#'&&x=='#')
{
printf("\nsuccess");
return;
}
elseprintf("error");
k++;
}while(strlen(stack)!
=0);
}
voidmain()
{
printf("pleaseinputstring:
");
scanf("%s",a);
LL1driver(a);
getchar();
getchar();
}
运行截图:
心得:
通过这次的实验、我学会了如何构造消除文法的左递归、并构造LL
(1)分析表、为程序的编写做好预先准备、并加
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 实验
![提示](https://static.bingdoc.com/images/bang_tan.gif)