自上而下的语法分析：LL(1)文法分析

自上而下的语法分析：LL(1)文法分析

1．实验内容及要求

（1）根据给定文法，先求出First和Follow集合，构造预测分析表
（2）根据预测分析表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）
（3）假如给定表达式文法为：
E->TE’;
E’->+TE’|e;
T->FT’;
T’->*FT’|e;
F->(E)|i;
(4) 分析的句子可为:
(i+i)*i和i+i)*i

2.运行结果


3.实验代码

// QX.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//#include 
#include 
#include 
using namespace std;static int Len = 0;//记录文件中产生式的个数
static string Gen[50][50];//记录消除左递归后的产生式
static int Gen_num[50];//消除左递归后每个产生式中句子的个数static char Vt[50];//记录终结符
static int len_vt = 0;//终结符的个数
static string Vn[50];//非终结符数组，因为存在E‘  所以需要设置为string类型
static int len_vn = 0;//非终结符的个数static string First[50][50];//记录first集
static int len_first = 0;
static int num_Fi[50];static string Follow[50][50];//记录follow集
static int len_follow = 0;
static int num_Fo[50];static string Ana_Table[50][50] = { "" };
static char V[50];static int arrx[50];//follow集中包含的元素static int Mer[50][50];//记录first和follow的表格bool IsVt(char c) {//判断是否为终结符/e(空集)for (int i = 0; i < len_vt; i++) {if (c == Vt[i] || c == 'e') {return true;}}return false;
}
bool IsVn(string s) {//判断是否为非终结符for (int i = 0; i < len_vn; i++) {if (s == Vn[i]) {return true;}}return false;
}
void Pretreatment(string arr[]) {//预处理程序for (int i = 0; i < Len; i++) {//遍历每行产生式int npc = 0;for (int j = 0; j < arr[i].length(); j++) {//遍历一行产生式的每个字符if (arr[i][j] == '-') {Gen[i][Gen_num[i]++] = arr[i].substr(npc, j - npc);Vn[len_vn++] = arr[i].substr(npc, j - npc);//取出非终结符npc = j + 2;}else if (arr[i][j] == '|' || arr[i][j] == ';') {Gen[i][Gen_num[i]++] = arr[i].substr(npc, j-npc);npc = j + 1;}}}//取出终结符for (int i = 0; i < Len; i++) {for (int j = 1; j < Gen_num[i]; j++) {for (int k = 0; k < Gen[i][j].length(); k++) {if (Gen[i][j][k] != '\'' && !IsVt(Gen[i][j][k]) && !IsVn(Gen[i][j].substr(k, 1))) {Vt[len_vt++] = Gen[i][j][k];}}}}
}bool Is(char c, int n) {for (int i = 0; i < num_Fi[n]; i++) {if (First[n][i][0] == c) {return true;}}return false;
}
void Cre_First() {//构建first集for (int i = 0; i < Len; i++) {First[len_first][num_Fi[len_first]++] = Gen[i][0];for (int j = 1; j < Gen_num[i]; j++) {if (Gen[i][j][0] != Gen[i][0][0] && !Is(Gen[i][j][0], i)) {//P->Q.. && Q不在P的first集中First[len_first][num_Fi[len_first]++] += Gen[i][j][0];}}len_first++;}int flag = 1;while (flag) {flag = 0;for (int i = 0; i < len_first; i++) {string arr[50];int len = 0;for (int j = 1; j < num_Fi[i]; j++) {if (IsVt(First[i][j][0])) {arr[len++] = First[i][j];}else {string str = First[i][j];for (int k = 0; k < len_first; k++) {if (str._Equal(First[k][0])) {for (int p = 1; p < num_Fi[k]; p++) {arr[len++] = First[k][p];}break;}}}}num_Fi[i] = 1;for (int j = 0; j < len; j++) {First[i][num_Fi[i]++] = arr[j];}}for (int i = 0; i < len_first; i++) {int npc = 0;for (int j = 1; j < num_Fi[i]; j++) {if (!IsVt(First[i][j][0])) {flag = 1;npc = 1;break;}}if (npc == 1) {break;}}}cout << "\n==========first集合:============\n" << endl;for (int i = 0; i < len_first; i++) {cout << "FIRST(" << First[i][0] << "):";for (int j = 1; j < num_Fi[i]; j++) {cout << First[i][j] << " ";}cout << endl;}
}//=============求解follow用到
int FindSub(string c) {//follow中对应的下标for (int i = 0; i < Len; i++) {if (c._Equal(Gen[i][0])) {return i;}}return -1;
}
int FindSub_Vt(char c) {//找到终结符在终结符数组中的下标if (c == '#') {return len_vt;}for (int i = 0; i < len_vt; i++) {if (c == Vt[i])return i;}return -1;
}
void PrintFollow(bool arry[][50]) {//输出follow集cout << "\n==========follow集合:============\n" << endl;for (int i = 0; i < Len; i++) {cout << "follow(" << Gen[i][0] << "): ";Follow[len_follow][num_Fo[len_follow]++] = Gen[i][0];for (int j = 0; j < len_vt + 1; j++) {if (j == len_vt) {cout << "#" << " ";Follow[len_follow][num_Fo[len_follow]++] = "#";}else if (arry[i][j] == true) {cout << Vt[j] << " ";Follow[len_follow][num_Fo[len_follow]++] = Vt[j];}}len_follow++;cout << endl;}for (int i = 0; i < Len; i++) {for (int j = 0; j < len_vt + 1; j++) {if (arry[i][j] == true) {arrx[j] = 1;}}}
}
bool Exit_Fi(int n, char c) {string str(1, c);for (int i = 1; i < num_Fi[n]; i++) {if (str == First[n][i]) {return true;}}return false;
}
bool Exit_F0(int n, char c) {string str(1, c);for (int i = 1; i < num_Fo[n]; i++) {if (str == Follow[n][i]) {return true;}}return false;
}void Print(bool arry[][50]) {cout << "\n\n=================First集 & Follow集=================\n";cout << "\t\t";char arr[50];for (int i = 0; i < len_vt; i++) {arr[i] = Vt[i];}arr[len_vt] = '#';arr[len_vt + 1] = 'e';//上表头有len+2元素for (int i = 0; i < len_vt + 2; i++) {cout << arr[i] << "\t";}cout << endl;for (int i = 0; i < len_first; i++) {cout << "First(" << First[i][0] << ")" << "\t";for (int j = 0; j < len_vt + 2; j++) {if (Exit_Fi(i, arr[j])) {cout << 1 << "\t";}else {cout << "-" << "\t";}}cout << endl;}for (int i = 0; i < len_first; i++) {cout << "Follow(" << First[i][0] << ")" << "\t";for (int j = 0; j < len_vt + 2; j++) {if (Exit_F0(i, arr[j])) {cout << 1 << "\t";}else {cout << "-" << "\t";}}cout << endl;}
}void Cre_Follow() {//2020-5-27 终于写出来了，bool arry[50][50];for (int i = 0; i < Len; i++) {for (int j = 0; j < len_vt + 1; j++) {arry[i][j] = false;}}arry[0][len_vt] = true;for (int i = 0; i < Len; i++) {for (int j = 1; j < Gen_num[i]; j++) {int len = Gen[i][j].length();for (int k = 1; k < len; k++) {if (IsVt(Gen[i][j][k]) && !IsVt(Gen[i][j][k - 1])) {   //p->Qa   a加入follow(Q)string str = "";if (len > 2 && Gen[i][j][k - 1] == '\'') {str = Gen[i][j].substr(k - 2, 2);}else {str += Gen[i][j][k - 1];}int x = FindSub(str);int y = FindSub_Vt(Gen[i][j][k]);arry[x][y] = true;}}}}for (int i = 0; i < Len; i++) {for (int j = 1; j < Gen_num[i]; j++) {int len = Gen[i][j].length();for (int k = 0; k < len - 1; k++) {if (!IsVt(Gen[i][j][k]) && !IsVt(Gen[i][j][k + 1]) && Gen[i][j][k + 1] != '\'') {//P->..QW   first(W)-"e"  --->follow(Q)string str = "";if (k < len - 2 && Gen[i][j][k + 2] == '\'') {str = Gen[i][j].substr(k + 1, 2);}else {str += Gen[i][j][k + 1];}int y = FindSub(str);//  W  在消除左递归后的数组中所在的行下标str = "";if (k > 0 && Gen[i][j][k] == '\'') {str = Gen[i][j].substr(k - 1, 2);}else {str += Gen[i][j][k];}int x = FindSub(str);//  Q  在消除左递归后的数组中所在的行下标 for (int w = 1; w < num_Fi[y]; w++) {if (!First[y][w]._Equal("e")) {int m = FindSub_Vt(First[y][w][0]);arry[x][m] = true;}}}}}}for (int i = 0; i < Len; i++) {for (int j = 1; j < Gen_num[i]; j++) {int len = Gen[i][j].length();for (int k = 0; k < len; k++) {if (k == len - 1 && !IsVt(Gen[i][j][k])) {//最后一个元素   P->....Q||P->....Q'   follow(P)入follow(Q)string str = "";if (Gen[i][j][k] == '\'') {str = Gen[i][j].substr(k - 1, 2);}else {str += Gen[i][j][k];}int x = FindSub(str);//Q所在行int y = FindSub(Gen[i][0]);//P所在行for (int p = 0; p < len_vt + 1; p++) {if (arry[y][p]) {arry[x][p] = true;}}}else if (k < len - 1) {if (!IsVt(Gen[i][j][k]) && !IsVt(Gen[i][j][k + 1])) {string str = "";if (k < len - 2 && Gen[i][j][k + 2] == '\'') {str = Gen[i][j].substr(k + 1, 2);}else {str += Gen[i][j][k];}int t = FindSub(str);int flag = 0;for (int w = 1; w < num_Fi[t]; w++) {//判断是否包含空集if (First[t][w]._Equal("e")) {flag = 1;break;}}if (flag) {//包含空集str = "";if (Gen[i][j][k] == '\'') {str = Gen[i][j].substr(k - 1, 2);}else {str += Gen[i][j][k];}int x = FindSub(str);//Q所在行int y = FindSub(Gen[i][0]);//P所在行for (int p = 0; p < len_vt + 1; p++) {if (arry[y][p]) {arry[x][p] = true;}}}}}}}}PrintFollow(arry);Print(arry);
}void Print_Table() {cout << "\n\n" << "\t";for (int i = 0; i < len_vt + 1; i++) {cout << V[i]<<"\t\t";}cout << endl;for (int i = 0; i < len_first; i++){cout << First[i][0] << "\t";for (int j = 0; j < len_vt + 1; j++) {if (Ana_Table[i][j] != "") {cout << Ana_Table[i][j] << "\t\t";}else {cout << ""<<"\t\t";}}cout << endl;}
}int FindSub_V(char c) {for (int i = 0; i < len_vt + 1; i++) {if (c == V[i]) {return i;}}return -1;
}void Cre_AnaTable() {for (int i = 0; i < len_vt; i++) {V[i] = Vt[i];}V[len_vt] = '#';for (int i = 0; i < len_first; i++) {for (int j = 1; j < num_Fi[i]; j++) {if (First[i][j][0] != 'e') {//该终结符  不为空int y = FindSub_V(First[i][j][0]);//该终结符所在的下标if (Gen_num[i] == 2) {//只有一个产生式后件Ana_Table[i][y] = Gen[i][0] + "->" + Gen[i][1];}else {//有多个产生式后件for (int k = 1; k < Gen_num[i]; k++) {if (Gen[i][k][0] == First[i][j][0]) {Ana_Table[i][y] = Gen[i][0] + "->" + Gen[i][k];break;}}}}else {//该终结符  为空for (int k = 1; k < num_Fo[i]; k++) {int y = FindSub_V(Follow[i][k][0]);Ana_Table[i][y] = Gen[i][0] + "->" + "e";}}}}Print_Table();
}void Analysis(string str) {cout << "\n\n==========预测分析过程==========\n";string stack = "";stack += str[0]; stack += Gen[0][0];str=str.substr(1, str.length() - 1);char a = str[0];bool flag = true;int npc = 0;cout << "步骤\t\t" << "符号栈\t\t" << "输入串\t\t" << "所用产生式" << endl;cout << npc << "\t\t" << stack << "\t\t" << str << "\t\t" << "" << "\n";while (flag) {npc++;char x = stack[stack.length() - 1];stack.erase(stack.length() - 1);if (IsVt(x)) {//栈顶元素为终结符if (x == a) {str=str.substr(1, str.length() - 1);a = str[0];cout << npc << "\t\t" << stack << "\t\t" << str << "\t\t" << "" << "\n";}else {cout << "error" << endl;break;}}else if (x == '#') {//栈顶元素位#if (x == a) {flag = false;}else {cout << "error" << endl;break;}}else{string s="";if (x == '\'') {s += stack[stack.length() - 1];s += x;stack.erase(stack.length() - 1);}else {s += x;}int m;for (int i = 0; i < Len; i++) {if (s == Gen[i][0]) {m = i;break;}}int n = FindSub_V(a);int len = Ana_Table[m][n].length();if (len == 0) {cout << "error" << endl;}else if (Ana_Table[m][n][len-1] != 'e') {for (int k = len - 1; k >= 0; k--) {if (Ana_Table[m][n][k] == '>') {break;}else if (Ana_Table[m][n][k] == '\'') {stack += Ana_Table[m][n].substr(k - 1, 2);k--;}else {stack += Ana_Table[m][n][k];}}cout << npc << "\t\t" << stack << "\t\t" << str << "\t\t" << Ana_Table[m][n] << "\n";}else {cout << npc << "\t\t" << stack << "\t\t" << str << "\t\t" << Ana_Table[m][n] << "\n";}}//cout << npc << "\t\t" << stack << "\t\t" << str << "\t\t" << "" << "\n";}
}int main()
{string Pri[100];ifstream infile("Source.txt");if (!infile)cout << "error" << endl;int len = 0;//文件中产生式的个数while (infile.good()) {getline(infile, Pri[len++]);}//len=5cout << "==========从文件中读取到的产生式==========\n" << endl;for (int i = 0; i < len; i++) {cout << Pri[i] << endl;}Len = len;Pretreatment(Pri);Cre_First();Cre_Follow();Cre_AnaTable();string str;cout << "==========请输入产生式==========" << endl;cin >> str;//       #i*i+i#Analysis(str);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！