预测分析法编译原理.doc
《预测分析法编译原理.doc》由会员分享,可在线阅读,更多相关《预测分析法编译原理.doc(5页珍藏版)》请在冰点文库上搜索。
![预测分析法编译原理.doc](https://file1.bingdoc.com/fileroot1/2023-4/30/88a1bb83-664c-499e-92ad-cf755c5ea7de/88a1bb83-664c-499e-92ad-cf755c5ea7de1.gif)
实验二 基于预测方法的语法分析程序的设计
一、实验目的
了解预测分析器的基本构成及用自顶向下的预测法对表达式进行语法分析的方法,掌握预测语法分析程序的手工构造方法。
二、实验内容
1、了解编译程序的基于预测方法的语法分析过程。
2、根据预测分析原理设计一个基于预测方法的语法分析程序。
三、实验要求
对给定文法G[S]:
S->ATA->BUT->+AT|$U->*BU|$B->(S)|m
其中,$表示空串。
1、判断上述文法G[S]是否LL
(1)文法,若不是,将其转变为LL
(1)文法;
2、对转变后的LL
(1)文法建立预测分析表;
3、根据清华大学出版编译原理教材教材第五章P94的图5.11手工构造预测分析程序;
4、用预测分析程序对任意给定的键盘输入串m+m*m#进行语法分析,并根据栈的变化状态输出给定串的具体分析过程。
四、运行结果
从任意给定的键盘输入串:
m+m*m#;
输出:
用预测分析法分析符号串m+m*m#的过程
Step
Stack
String
Rule
Step
Stack
String
Rule
1
#S
m+m*m#
S->AT
10
#TUm
m*m#
M匹配
2
#TA
m+m*m#
A->BU
11
#TU
*m#
U->*BU
3
#TUB
m+m*m#
B->m
12
#TUB*
*m#
*匹配
4
#TUm
m+m*m#
M匹配
13
#TUB
m#
B->m
5
#TU
+m*m#
U->$
14
#TUm
m#
M匹配
6
#T
+m*m#
T->+AT
15
#TU
#
U->$
7
#TA+
+m*m#
+匹配
16
#T
#
T->$
8
#TA
m*m#
A->BU
17
#
#
接受
9
#TUB
m*m#
B->m
五、提示
本实验重点有两个:
一是如何用适当的数据结构实现预测分析表存储和使用;二是如何实现各规则右部串的逆序入栈处理。
建议:
使用结构体数组。
六、分析与讨论
1、若输入串不是指定文法的句子,会出现什么情况?
2、总结预测语法分析程序的设计和实现的一般方法。
代码:
#include
#include
#include
#include
structstack1
{
charstack[10];
}sta[][7]=
{
"\0","+","*","(",")","m","#",
"S","\0","\0","AT","\0","AT","\0",
"A","\0","\0","BU","\0","BU","\0",
"T","+AT","\0","\0","$","\0","$",
"B","\0","\0","(S)","\0","m","\0",
"U","$","*BU","\0","$","\0","$"
};
//structstack*head;
charstack_1[10]={'\0'},stack_2[10]={'\0'},stack_3[10]={'\0'};
inti,j,k,len_1,len_2,len_3,mark=0;
voidmain()
{
//voidc_stack();
voidanalyze_stack();
voidsurplus_str();
intrules();
//printf("%s\t",sta[0][1].stack);
//printf("\n");
while
(1)
{
// system("cls");
mark=0;
printf("请输入串:
\n");
gets(stack_3);
if(stack_3[0]=='0')
break;
stack_1[0]='S';
len_3=strlen(stack_3);
if(stack_3[len_3-1]!
='#')
{
printf("字符串输入错误,字符串不以#号结束!
\n");
continue;
}
printf("分析栈\t\t剩余串\t\t\t\t\t\t规则\n");
for(i=0;i<=100;i++)
{
analyze_stack();
surplus_str();
rules();
if(mark==1)
break;
if(stack_1[0]=='\0'&&stack_3[0]=='#')
{
printf("#\t\t#\t\t\t\t\t\t成功接受\n");
break;
}
}
}
}
voidanalyze_stack()//分析栈
{
printf("#%-15s",stack_1);
len_1=strlen(stack_1);
}
voidsurplus_str()//剩余串//注意拼写的正确性,写成surlpus_str()报错,unresolvedsxternalsymbol_surplus_str;
{
printf("%-48s",stack_3);
}
intrules()//所用规则
{
intp,q,h;
chartemp;
//printf("%d",len_1);
if(stack_1[len_1-1]==stack_3[0])
{
printf("%c匹配\n",stack_3[0]);
stack_1[len_1-1]='\0';
for(h=1;h<=len_3-1;h++)
stack_3[h-1]=stack_3[h];
stack_3[len_3-1]='\0';
}
elseif(stack_1[len_1-1]<'A'||stack_1[len_1-1]>'Z')
{
printf("报错\n");
mark=1;
return0;
}
elseif(stack_1[len_1-1]>='A'&&stack_1[len_1-1]<='Z')
{
for(j=1;j<=5;j++)
{
if(stack_1[len_1-1]==sta[j][0].stack[0])
{
p=j;
break;
}
}
if(j>=6)
{
printf("报错\n");
mark=1;
return0;
}
for(k=1;k<=6;k++)
{
if(stack_3[0]==sta[0][k].stack[0])
{
q=k;
break;
}
}
if(k>=7)
{
printf("报错\n");
mark=1;
return0;
}
if(sta[p][q].stack[0]=='\0')
{
printf("报错\n");
mark=1;
return0;
}
strcpy(stack_2,sta[p][q].stack);
len_2=strlen(stack_2);
printf("%c->%s\n",stack_1[len_1-1],stack_2);
stack_1[len_1-1]='\0';
if(stack_2[0]=='$')
{
}
else
{
for(h=0;h{
temp=stack_2[h];
stack_2[h]=stack_2[len_2-1-h];
stack_2[len_2-1-h]=temp;
}
strcat(stack_1,stack_2);
}
}
return0;
}