实验二预测分析
一、实验目的
预测分析表的实现
二、实验
设有文法G:
E→TE’
E’→+TE’|ε
T→FT’
T’→*FT’|ε
F→(E)|i;
根据文法编写预测表分析总控程序,分析句子是否为该文法的句型。
当输入字符串: +i时,分析字符串是否为文法的句型
三、实验步骤(详细的实验步骤)
(1)文法
E→TE’
E’→+TE’|ε
T→FT’
T’→*FT’|ε
F→(E)|i;
(2)FIRST集
FIRST(E)={(,i};
FIRST(E’)={+,ε};
FIRST(T)={(,i};
FIRST(T’)={*,ε};
FIRST(F)={(,i};
(3)FALLOW集
FOLLOW(E)={),#};
FOLLOW(E’)={),#};
FOLLOW(T)={+,),#};
FOLLOW(T’)={+,),#};
FOLLOW(F)={*,+,),#};
(4)预测分析表
i
+
*
(
)
#
E
E->TE’
E->TE’
E’
E’->+TE’
E’->ε
E’->ε
T
T->FT’
T->FT’
T’
T’->ε
T’->*FT’
T’->ε
T’->ε
F
F->i
F->(E)
(5)分析过程
步骤
符号栈
输入串
应用句型
0
#E
i1*i2+i3#
1
#E’T
i1*i2+i3#
E->TE’
2
#E’T’F
i1*i2+i3#
E->TE’
3
#E’T’i
i1*i2+i3#
F->i
4
# E’T’
i1*i2+i3#
5
# E’T’F*
*i2+i3#
T’->*FT’
6
# E’T’F
*i2+i3#
7
#E’T’i
i2+i3#
F->i
8
# E’T’
i2+i3#
9
#E’
+i3#
T’->ε
10
# E’T+
+i3#
E’->+TE’
11
#E’T
+i3#
12
# E’T’F
i3#
T->FT’
13
# E’T’i
i3#
F->i
14
# E’T’
i3#
15
# E’
#
T’->ε
16
#
#
E’->ε
(6)程序伪代码
BEGIN
首先把‘#’然后把文法开始符号推进STACK栈;
把第一个输入符号读进a;
FLAG:=TRUE;
WHILE FLAG DO
BEGIN
把STACK栈顶符号托出去并放在X中;
IF X属于VTTHEN
IF X=aTHEN把下一输入符号读进a;
ELSE ERROR;
ELSE IF X=’#’ THEN
IF X=a THEN FLAG:=FALSE ELSE ERROR;
ELSE IF M[A,a]={X->X1X2…Xk} THEN
把Xk,X(k-1),…,X1一一推进栈
ELSE ERROR;
END OF WHILE
STOP
END
(7)运行结果截图
注:为了将E和E’区分开,所以就有e来表示E’,因为在处理中E’会被当成两个字符来处理,所以就简化的表示了。对于T’是同样的道理,用t来表示。
四、
此次的实验是对预测分析表程序的实现,先通过给定文法写出FIRST集FOLLOW集以及预测分析表,根据预测分析表,编写程序分析句子。此次的实验之中,存储非终结符使用的是栈来存储,存储输入串则用到的是数组来存储。对于分析表,用函数的形式来存储相应的产生式。本次的实验加强了对预测分析程序的知识应用,对于预测分析程序的运行机制有了更进一步的认识和掌握。最重要的是通过本次的实验对
本的知识进一步的掌握了。
五、源程序
// analyze.cpp : 定义控制台应用程序的入口点。
//程序可以运行 VS2015里能完全运行。
#include"stdafx.h"
#include
#include
usingnamespacestd;
//typedefstruct {
// char *base;
// char *top;
// int size;
//}SqStack; //定义栈
charstack[13];
int base = 0;
int top = 1;
char VT[5] = { 'i','+','*','(',')' }; /*用来存放5个终结符*/
charinputString[13]; /*用来存储用户输入的字符串,最长为20个字符*/
charchanShengShi[13]; /*用来存放预测分析表M[A,a]中的一条产生式*/
intfirstCharIntex = 0; /*如果a匹配产生式,则每次firstCharIntex自增 1 */ /*firstCharIntex用来存放用户输入串的第一个元素的下标*/
int M(char A, char a); /* 若预测分析表M[A,a]中存在产生式,
则将该产生式赋给字符数组chanShengShi[10],并返回 1。若M[A,a]中无定义产生式则返回 0 */
intyuCeFenXi();//预测分析主函数
voidprintStack(); /*打印栈内元素 */
voidprintinputString(); /*打印用户输入串 */
voidinit() {
inti;
for (i = 0; i<13; i++) {
inputString[i] = NULL; /*初始化数组inputString[10] */
stack[i] = NULL;
chanShengShi[i] = NULL; /*初始化数组chanShengShi[10]*/
}
}
char pop() { /*弹出栈顶元素,用topChar返回*/
chartopChar;
topChar = stack[--top];
returntopChar;
}
intpush(charch) {
if (top>12) {
cout<<" 栈溢出! "; /*栈空间溢出*/
return 0;
}
else {
stack[top] = ch; /*给栈顶空间赋值*/
top++;
return 1;
}
}
int M(charA, chara) { /*该函数模拟预测分析表中的二维数组 */
if (A == 'E'&&a == 'i') {
strcpy_s(&chanShengShi[0], 4, "Te$");
cout<<" E->TE'";
return 1;
}
if (A == 'E'&&a == '(') {
strcpy_s(&chanShengShi[0], 4, "Te$");
cout<<" E->TE'";
return 1;
}
if (A == 'e'&&a == '+') {
strcpy_s(&chanShengShi[0], 5, "+Te$");
cout<<" E'->+TE'";
return 1;
}
if (A == 'e'&&a == ')') {
strcpy_s(&chanShengShi[0], 2, "$");
cout<<" E'->ε";
return 1;
}
if (A == 'e'&&a == '#') {
strcpy_s(&chanShengShi[0], 2, "$");
cout<<" E'->ε";
return 1;
}
if (A == 'T'&&a == 'i') {
strcpy_s(&chanShengShi[0], 4, "Ft$");
cout<<" T->FT'";
return 1;
}
if (A == 'T'&&a == '(') {
strcpy_s(&chanShengShi[0], 4, "Ft$");
cout<<" T->FT'";
return 1;
}
if (A == 't'&&a == '+') {
strcpy_s(&chanShengShi[0], 2, "$");
cout<<" T'->ε";
return 1;
}
if (A == 't'&&a == '*') {
strcpy_s(&chanShengShi[0], 5, "*Ft$");
cout<<" T'->*FT'";
return 1;
}
if (A == 't'&&a == ')') {
strcpy_s(&chanShengShi[0], 2, "$");
cout<<" T'->ε";
return 1;
}
if (A == 't'&&a == '#') {
strcpy_s(&chanShengShi[0], 2, "$");
cout<<" T'->ε";
return 1;
}
if (A == 'F'&&a == 'i') {
strcpy_s(&chanShengShi[0], 3, "i$");
cout<<" F->i";
return 1;
}
if (A == 'F'&&a == '(') {
strcpy_s(&chanShengShi[0], 5, "(E)$");
cout<<" F->(E)";
return 1;
}
else
return 0; /*没有定义产生式则返回0*/
}
intsearch(chartemp) {
inti, flag = 0; /*flag变量做为标志,若找到temp则赋1,否则赋0*/
for (i = 0; i<5; i++) {
if (temp == VT[i]) {/*终结符集合中存在temp*/
flag = 1;
break;
}
}
if (flag == 1)
return 1; /*flag==1说明已找到等于temp的元素*/
else
return 0;
}
voidprintinputString() { /*输出用户输入的字符串*/
int temp = firstCharIntex;
cout<<" "; /*该句控制输出格式*/
do {
cout<记录语法分析的步骤数*/
cout<<"输入一个字符串以“#”结尾:"; /*提示用户输入将要测试的字符串*/
//scanf_s("%s", inputString);
cin>>inputString;
push('#');
push('E');
/*while循环为语法分析主功能语句块*/
cout<<" 步骤栈输入字符串所用产生式 "; /*输出结果提示语句*/
while (1) {
cout<<" "<
= 0) {
push(chanShengShi[i]); /*将当前产生式逆序压入栈内*/
i--;
}
}
else {
cout<<" 语法错误!!"; /*若预测分析表M[A,a]不存在产生式,说明语法错误*/
return 0;
}
}
}
else { /*说明X为终结符*/
if (X == inputString[firstCharIntex]) { /*如果X等于a,说明a匹配*/
firstCharIntex++; /*输入串的第一个元素被约去,下一个元素成为新的头元素*/
}
else {
cout<<" error!! ";
return 0;
}
}
counter++;
}
}
intmain()
{
yuCeFenXi(); /*调用语法预测分析函数*/
//return 0;
system("pause");
}