【实验目的】
掌握算符优先分析法的原理，利用算符优先分析法将赋值语句进行语法分析。
【实验内容】
（1）输入一个文法根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否为算符优先文法
(2)输入一个句子进行分析
【实验要求】
1、根据文法求FIRSTVT集和LASTVT集
给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的FirstVT 集和LastVT 集。
可参考算法描述如下：
/*求 FirstVT 集的算法*/
PROCEDURE insert(P,a);
IF not F[P,a] then
begin
F[P,a] = true; //(P,a)进栈
end;
Procedure FirstVT;
Begin
for 对每个非终结符 P和终结符 a do
F[P,a] = false
for 对每个形如 P a…或 P→Qa…的产生式 do
Insert(P,a)
while stack 非空
begin
栈顶项出栈，记为(Q,a)
for 对每条形如 P→Q…的产生式 do
insert(P,a)
end;
end.
同理，可构造计算LASTVT的算法。
2、构造算符优先分析表
依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。
参考算法描述如下：
for 每个形如 P->X1X2…Xn的产生式 do
for i =1 to n-1 do
begin
if Xi和Xi+1都是终结符 then
Xi = Xi+1
if i<= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then
Xi = Xi+2
if Xi为终结符, Xi+1为非终结符 then
for FirstVT 中的每个元素 a do
Xi < a ;
if Xi为非终结符, Xi+1为终结符 then
for LastVT 中的每个元素 a do
a > Xi+1 ;
end
3、构造控制程序
参考 算法描述如下：
stack S;
k = 1; //符号栈S的使用深度
S[k] = ‘#’
REPEAT
把下一个输入符号读进a中；
If S[k] VT then j = k else j = k-1;
While S[j] > a do
Begin
Repeat
Q = S[j];
if S[j-1] VT then j = j-1 else j = j-2
until S[j] < Q;
把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号；
K = j+1;
S[k] = N;
end of while
if S[j] < a or S[j] = a then
begin k = k+1; S[k] = a end
else error //调用出错诊察程序
until a = ‘#’
4、对给定的表达式，给出准确与否的分析过程
5、给出表达式的计算结果。
【实验结果】
图为参考，要求包含firstvt和lastvt集，算符优先表或优先函数表及句子分析过程。
#include<iostream> #include<fstream> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; char str1[50][50]; //存放优先表 struct csc{ //用结构体数组来存放产生式 char Left; //存放产生式的左部 char Right[100]; //存放产生式的右部 }G[100]; struct db{ char VN; //用于存放 FIRSTVT(P) 和 LASTVT(P) 的非终结符 char VtoT[100]; //用于存放 FIRSTVT(P) 和 LASTVT(P) 的终结符 }firstvt[100], lastvt[100]; int Capital(char ch) // 判断是否是非终结符，默认大写字母为非终结符，其他为终结符 { if (ch >= 'A'&&ch <= 'Z') return 1; else return 0; } void Issfwf(csc G[], int length) //判断文法是否为算符文法 { int i, j; int flag = 0; for (i = 0; i<length; i++) { for (j = 0; j<strlen(G[i].Right) - 1; j++) if (Capital(G[i].Right[j]) == 1 && Capital(G[i].Right[j + 1]) == 1) { flag = 1; break; } } if (flag == 1) { cout << " 该文法不是算符文法 !" << endl; return; } else cout << " 该文法是算符文法 !" << endl; } void Clean(db VNT[], int length1) //去掉集合中重复部分 { char str1[20]; char str2[20][100]; int i, j, k, t; int length; int flag; for (i = 0; i<length1; i++) { str1[i] = VNT[i].VN; strcpy_s(str2[i], VNT[i].VtoT); } for (i = 0; i<length1; i++) memset(VNT[i].VtoT, 0, sizeof(VNT[i].VtoT)); for (i = 0; i<length1; i++) { t = 0; length = strlen(str2[i]); for (j = 0; j<length; j++) { flag = 1; for (k = 0; k<t; k++) if (VNT[i].VtoT[k] == str2[i][j]) flag = 0; if (flag == 1) VNT[i].VtoT[t++] = str2[i][j]; } length = strlen(VNT[i].VtoT); } } void FIRSTVT(csc G[], db firstvt[], int length) //求各非终结符的 FIRSTVT 集合 { int flag = 0, length1 = 0; int i, j, k; for (i = 0; i<100; i++) memset(firstvt[i].VtoT, 0, sizeof(firstvt[i].VtoT)); while (flag<length) { j = 0; firstvt[length1].VN = G[flag].Left; while (firstvt[length1].VN == G[flag].Left) { if (Capital(G[flag].Right[0]) == 0) //P->a...则将 a加入 firstvt(P) 中 firstvt[length1].VtoT[j++] = G[flag].Right[0]; else if (Capital(G[flag].Right[0]) == 1 && Capital(G[flag].Right[1]) == 0) //P->Qa...则将 a加入 firstvt(P) 中 firstvt[length1].VtoT[j++] = G[flag].Right[1]; flag++; } length1++; } for (i = length - 1; i >= 0; i--) //P->Q...，则将 Q 中的终结符加入 P 中 if (Capital(G[i].Right[0]) == 1 && G[i].Left != G[i].Right[0]) { for (j = 0; j<length1; j++) if (firstvt[j].VN == G[i].Right[0]) break; for (k = 0; k<length1; k++) if (firstvt[k].VN == G[i].Left) break; strcat_s(firstvt[k].VtoT, firstvt[j].VtoT); } Clean(firstvt, length1); for (i = 0; i<length1; i++) //集合输出 { cout << "FIRSTVT("; cout << firstvt[i].VN << ")" << "=" << "{"; cout << firstvt[i].VtoT[0]; for (j = 1; j<strlen(firstvt[i].VtoT); j++) cout << "," << firstvt[i].VtoT[j]; cout << "}" << endl; } } void LASTVT(csc G[], db lastvt[], int length) //求各非终结符的 FIRSTVT 集合 { int flag = 0, length1 = 0; int i, j, k, t; for (i = 0; i<100; i++) memset(lastvt[i].VtoT, 0, sizeof(lastvt[i].VtoT)); while (flag<length) { j = 0; lastvt[length1].VN = G[flag].Left; while (lastvt[length1].VN == G[flag].Left) { t = strlen(G[flag].Right) - 1; if (Capital(G[flag].Right[t]) == 0) //P->...a 则将 a加入 lastvt(P)中 lastvt[length1].VtoT[j++] = G[flag].Right[t]; else if (Capital(G[flag].Right[t]) == 1 && Capital(G[flag].Right[t - 1]) == 0) //P->...aQ 则将 a 加入 lastvt(P)中 lastvt[length1].VtoT[j++] = G[flag].Right[t - 1]; flag++; } length1++; } for (i = length - 1; i >= 0; i--) //P->...Q，则将 Q 中的终结符加入 P 中 { t = strlen(G[flag].Right) - 1; if (Capital(G[i].Right[t]) == 1 && G[i].Left != G[i].Right[t]) { for (j = 0; j<length1; j++) if (lastvt[j].VN == G[i].Right[t]) break; for (k = 0; k<length1; k++) if (lastvt[k].VN == G[i].Left) break; strcat_s(lastvt[k].VtoT, lastvt[j].VtoT); } } Clean(lastvt, length1); for (i = 0; i<length1; i++) //集合输出 { cout << "LASTVT("; cout << lastvt[i].VN << ")" << "=" << "{"; cout << lastvt[i].VtoT[0]; for (j = 1; j<strlen(lastvt[i].VtoT); j++) cout << "," << lastvt[i].VtoT[j]; cout << "}" << endl; } } void StructureTable(csc G[], db firstvt[], db lastvt[], int length) //返回非终结符个数 { char str[50]; //存放终结符 int i, j, k, flag, i1, i2, length1; int t = 0; for (i = 0; i<50; i++) memset(str1[i], 0, sizeof(str1[i])); memset(str, 0, sizeof(str)); for (i = 0; i<length; i++) //求所有非终结符 { j = strlen(G[i].Right); flag = 1; for (k = 0; k<j; k++) if (Capital(G[i].Right[k]) == 0) { for (i1 = 0; i1<t; i1++) if (G[i].Right[k] == str[i1]) flag = 0; if (flag == 1) str[t++] = G[i].Right[k]; } } for (i = 0; i<strlen(str); i++) // 与习惯保持一致，将 #置于最后一个 if (str[i] == '#') break; swap(str[i], str[strlen(str) - 1]); for (i = 1; i <= strlen(str); i++) { str1[0][i] = str[i - 1]; str1[i][0] = str[i - 1]; } for (i = 0; i<length; i++) { length1 = strlen(G[i].Right); for (j = 0; j<length1 - 1; j++) { if (Capital(G[i].Right[j]) == 0 && Capital(G[i].Right[j + 1]) == 0) { for (i1 = 0; i1 <= strlen(str); i1++) for (i2 = 0; i2 <= strlen(str); i2++) if (str1[0][i1] == G[i].Right[j] && str1[i2][0] == G[i].Right[j + 1]) { if (str1[i1][i2] != 0) { cout << "该文法不是算符优先文法！ " << endl; return; } else str1[i1][i2] = '='; } } if (j<length1 - 2 && Capital(G[i].Right[j]) == 0 && Capital(G[i].Right[j + 2]) == 0 && Capital(G[i]. Right[j + 1]) == 1) { for (i1 = 0; i1 <= strlen(str); i1++) for (i2 = 0; i2 <= strlen(str); i2++) if (str1[0][i1] == G[i].Right[j] && str1[i2][0] == G[i].Right[j + 2]) { if (str1[i1][i2] != 0) { cout << "该文法不是算符优先文法！ " << endl; return; } else str1[i1][i2] = '='; } } if (Capital(G[i].Right[j]) == 0 && Capital(G[i].Right[j + 1]) == 1) { for (i1 = 0; str1[0][i1] != G[i].Right[j]; i1++); for (k = 0; firstvt[k].VN != G[i].Right[j + 1]; k++); for (i2 = 0; i2 <= strlen(str); i2++) for (t = 0; t<strlen(firstvt[k].VtoT); t++) if (str1[i2][0] == firstvt[k].VtoT[t]) { if (str1[i1][i2] != 0) { cout << "该文法不是算符优先文法！ " << endl; return; } else str1[i1][i2] = '<'; } } if (Capital(G[i].Right[j]) == 1 && Capital(G[i].Right[j + 1]) == 0) { for (t = 0; lastvt[t].VN != G[i].Right[j]; t++); for (k = 0; k<strlen(lastvt[t].VtoT); k++) for (i1 = 0; i1 <= strlen(str); i1++) for (i2 = 0; i2 <= strlen(str); i2++) if (str1[0][i1] == lastvt[t].VtoT[k] && str1[i2][0] == G[i].Right[j + 1]) { if (str1[i1][i2] != 0) { cout << " 该文法不是算符优先文法！ " << endl; return; } else str1[i1][i2] = '>'; } } } } for (i = 0; i <= strlen(str); i++) { for (j = 0; j <= strlen(str); j++) cout << str1[i][j] << " "; cout << endl; } } char GetRalation(char a, char b) //找到 a，b 对应的关系 { int i, j; for (i = 0; str1[0][i] != a; i++); for (j = 0; str1[j][0] != b; j++); return str1[i][j]; } void Judge(char *str, csc G[]) { char Q; char a; char str2[100]; char S[100]; int flag = 0; int i = 0; int j, k; int s = 0, step = 1; int length; cout.width(5); // 输出表头 cout.setf(ios::left); cout << "步骤 "; cout.width(15); cout.setf(ios::left); cout << "符号栈 "; cout.width(15); cout.setf(ios::left); cout << "输入串 "; cout.width(15); cout.setf(ios::left); cout << "动作 " << endl; memset(S, 0, sizeof(S)); a = str[0]; k = 1; S[k] = '#'; while (a != '#') { a = str[flag++]; if (Capital(S[k]) == 0) j = k; else j = k - 1; while (GetRalation(S[j], a) == '>') { Q = S[j]; while (GetRalation(S[j], Q) != '<') { Q = S[j]; if (Capital(S[j - 1]) == 0) j = j - 1; else j = j - 2; } cout.width(5); cout.setf(ios::left); cout << step++; cout.width(15); cout << S + 1; cout.width(15); cout.setf(ios::left); cout << str + flag - 1; cout.width(15); cout.setf(ios::left); cout << " 规约 " << endl; for (i = j + 2; i <= k; i++) S[i] = 0; k = j + 1; S[k] = 'N'; } if (GetRalation(S[j], a) == '<' || GetRalation(S[j], a) == '=') { cout.width(5); cout.setf(ios::left); cout << step++; cout.width(15); cout << S + 1; cout.width(15); // cout.setf(ios::right); cout << str + flag - 1; if (a != '#') { cout.width(15); cout.setf(ios::left); cout << "移进 " << endl; } k = k + 1; S[k] = a; } else { cout << " 抱歉，输入的句子有误 " << endl; return; } } cout << "接受 " << endl; cout << "恭喜你！分析成功！ " << endl; } void main() { char str3[100]; // 用于存放一个产生式子 char str2[100]; // 用于存放待检测的字符串 char filename[10];// 文件名 int length = 0; // 记录产生式个数 int s = 0; cout << "请输入文件名： "; cin >> filename; memset(str1, 0, sizeof(str1)); //置空字符串 ifstream fin1(filename); if (!fin1) { cout << "Cannot open the file. "; //未找到对应文件名的文件 exit(1); } while (fin1) { fin1.getline(str3, 100); //读出一个产生式 cout << str3 << endl; G[length].Left = str3[0]; //产生式的左部 strcpy_s(G[length].Right, str3 + 3); length++; } length -= 1; Issfwf(G, length); cout << "各非终结符的 FIRSTVT 集合如下： " << endl; FIRSTVT(G, firstvt, length); cout << "各非终结符的 LASTVT 集合如下： " << endl; LASTVT(G, lastvt, length); cout << "构造分析表如下： " << endl; StructureTable(G, firstvt, lastvt, length); cout << "请任意输入一个输入串 (以#号键结束 )：" << endl; cin >> str2; Judge(str2, G); }
