实验二 基于预测方法的语法分析程序的设计
一、实验目的
了解预测分析器的基本构成及用自顶向下的预测法对表达式进行语法分析的方法,掌握预
测语法分析程序的手工构造方法。
二、实验内容
1、了解编译程序的基于预测方法的语法分析过程。
2、根据预测分析原理设计一个基于预测方法的语法分析程序。
三、实验要求
对给定文法 G[S]:
S->AT
A->BU
T->+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#;
输出:
Step Stack
String
Rule
Step Stack
String
Rule
用预测分析法分析符号串 m+m*m#的过程
1
2
3
4
5
6
7
8
9
#S
#TA
#TUB
#TUm
#TU
#T
#TA+
#TA
#TUB
m+m*m#
m+m*m#
S->AT
A->BU
m+m*m#
B->m
m+m*m#
M 匹配
+m*m#
+m*m#
+m*m#
m*m#
m*m#
U->$
T->+AT
+匹配
A->BU
B->m
10
11
12
13
14
15
16
17
#TUm
#TU
#TUB*
#TUB
#TUm
#TU
#T
#
m*m#
*m#
*m#
m#
m#
#
#
#
M 匹配
U->*BU
*匹配
B->m
M 匹配
U->$
T->$
接受
五、提示
本实验重点有两个:一是如何用适当的数据结构实现预测分析表存储和使用;二是如何
实现各规则右部串的逆序入栈处理。
建议:使用结构体数组。
六、分析与讨论
1、若输入串不是指定文法的句子,会出现什么情况?
2、总结预测语法分析程序的设计和实现的一般方法。
代码:
#include
#include
#include
#include
struct stack1
{
char stack[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","$"
};
//struct stack *head;
char stack_1[10]={'\0'},stack_2[10]={'\0'},stack_3[10]={'\0'};
int i,j,k,len_1,len_2,len_3,mark=0;
void main()
{
// void c_stack();
void analyze_stack();
void surplus_str();
int rules();
//
//
printf("%s\t",sta[0][1].stack);
printf("\n");
while(1)
{
//
mark=0;
system("cls");
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;
}
}
}
}
void analyze_stack()//分析栈
{
printf("#%-15s",stack_1);
len_1=strlen(stack_1);
}
void surplus_str()//剩余串//注意拼写的正确性,写成 surlpus_str()报
错,unresolved sxternal symbol_surplus_str;
{
printf("%-48s",stack_3);
}
int rules()//所用规则
{
int p,q,h;
char temp;
// 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';
}
else if(stack_1[len_1-1]<'A'||stack_1[len_1-1]>'Z')
{
printf("报错\n");
mark=1;
return 0;
}
else if(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;
return 0;
}
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;
return 0;
}
if(sta[p][q].stack[0]=='\0')
{
printf("报错\n");
mark=1;
return 0;
}
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