**

算符优先分析程序(NCWU慎用)

**
1．实验要求
⑴ 选择算符优先分析方法；
⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句或表达式或控制流语句等作为分析对象，并且与所选语法分析方法要比较贴切。
⑶ 实验时间为6学时。

2．实验内容及要求
（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表 输出到显示器或者输出到文件）；
（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）
（3）假如给定表达式文法为：
G(E’): E’→#E#
E→E+T | T
T→T*F |F
F→(E)|i
(4) 分析的句子可为:
(i+i)*i和i+i)*i
3.运行结果：


4.源代码：

// Exper2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。#include <iostream>
#include <string>
#include <fstream>
using namespace std;static char Vn[50];//记录非终结符
static int len_vn;
static char Vt[50];//记录终结符
static int len_vt;
static string AftSource[50][50];//处理后的产生式，一行一个产生式
static int num[50];//每个产生式有用部分的个数
static int Len_Source;//产生式的个数
static char firstvt[50][50];//记录firstvt集 
static int len_first[50];
static char lastvt[50][50];//记录lastvt集
static int len_last[50];
static char Vt_[50];//加入#号的
static char table[50][50];//记录生成的算符优先关系表bool IsVn(char c) {//判断该字符为非终结符for (int i = 0; i < len_vn; i++) {if (c == Vn[i]) {return true;}}return false;
}
bool IsVt(char c) {//判断该字符是否为终结符if (c == '#') {return true;}for (int i = 0; i < len_vt; i++) {if (c == Vt[i]) {return true;}}return false;
}void Pretreatment(string arr[], int n) {//预处理，将产生重新存储，并且将终结符和非终结符分开存放for (int i = 0; i < n; i++) {Vn[len_vn++] = arr[i][0];AftSource[i][num[i]++] = arr[i].substr(0, 1);//将第一个字符存入处理后的数组int npc = 3;for (int j = 3; j < arr[0].length(); j++) {if (arr[i][j] == '|' || arr[i][j] == ';') {AftSource[i][num[i]++] = arr[i].substr(npc, j - npc);npc = j + 1;}}}for (int i = 0; i < Len_Source; i++) {for (int j = 1; j < num[i]; j++) {for (int k = 0; k < AftSource[i][j].length(); k++) {if (!IsVn(AftSource[i][j][k])) {Vt[len_vt++] = AftSource[i][j][k];}}}}
}int RepeatFirst(int n, char c) {//判断即将加入的终结符是否已经在firstvt集中了for (int i = 0; i < len_first[n]; i++) {if (firstvt[n][i] == c) {return 0;}}return 1;
}
int RepeatLast(int n, char c) {//判断即将加入的终结符是否已经在lastvt集中了for (int i = 0; i < len_last[n]; i++) {if (lastvt[n][i] == c) {return 0;}}return 1;
}void FirstVT() {//构造firstvt集for (int i = 0; i < len_vn; i++) {//对非终结符进行逐个判断string temp = "";temp += Vn[i];firstvt[i][len_first[i]++] = Vn[i];for (int j = 0; j < Len_Source; j++) {if (temp._Equal(AftSource[j][0])) {//找出当前非终结符对应的产生式所对应的行for (int k = 1; k < num[j]; k++) {int len = AftSource[j][k].length();if (IsVt(AftSource[j][k][0]) || (IsVn(AftSource[j][k][0]) && AftSource[j][k][0] != Vn[i])) {//开头是终结符   p->a....||  p->Q....则a，Q加入这里Q不是当前非终结符if (RepeatFirst(i, AftSource[j][k][0])) {firstvt[i][len_first[i]++] = AftSource[j][k][0];}}if (len >= 2 && IsVn(AftSource[j][k][0]) && IsVt(AftSource[j][k][1])) {//p->Qa...   a加入if (RepeatFirst(i, AftSource[j][k][1])) {firstvt[i][len_first[i]++] = AftSource[j][k][1];}}}}}}int flag = 1;while (flag) {flag = 0;for (int i = 0; i < len_vn; i++) {char str[50];int p = 0;for (int j = 1; j < len_first[i]; j++) {if (IsVt(firstvt[i][j])) {//当前符号是终结符str[p++] = firstvt[i][j];}else {         //当前符号是非终结符for (int k = 0; k < len_vn; k++) {//找出该非终结符的位置if (Vn[k] == firstvt[i][j]) {   //k为当前非终结符在表中的行下标for (int q = 1; q < len_first[k]; q++) {//将k行中的firstvt集中的元素全部加入i中char ch = firstvt[k][q];int npc = 1;for (int m = 1; m < len_first[i]; m++) {//遍历第i行，去除重复的。if (ch == firstvt[i][m]) {npc = 0;break;}}if (npc == 1) {str[p++] = ch;}}}}}}for (int j = 0; j < p; j++) {//重新写入i行的firstfirstvt[i][j + 1] = str[j];}len_first[i] = p + 1;if (flag == 0) {for (int j = 1; j < len_first[i]; j++) {if (IsVn(firstvt[i][j])) {flag = 1;break;}}}}}}
void LastVT() {for (int i = 0; i < len_vn; i++) {//对非终结符进行逐个判断string temp = "";temp += Vn[i];lastvt[i][len_last[i]++] = Vn[i];for (int j = 0; j < Len_Source; j++) {if (temp._Equal(AftSource[j][0])) {for (int k = 1; k < num[j]; k++) {int len = AftSource[j][k].length();if (len >= 2 && IsVn(AftSource[j][k][len - 1]) && IsVt(AftSource[j][k][len - 2])) {//开头是终结符   p->....a||  p->....Q 则a，Q加入这里Q不是当前非终结符if (RepeatLast(i, AftSource[j][k][len - 2])) {lastvt[i][len_last[i]++] = AftSource[j][k][len - 2];}}else if (IsVt(AftSource[j][k][len - 1]) || (IsVn(AftSource[j][k][len - 1]) && AftSource[j][k][len - 1] != Vn[i])) {//p->...aQ   a加入if (RepeatLast(i, AftSource[j][k][len - 1])) {lastvt[i][len_last[i]++] = AftSource[j][k][len - 1];}}}}}}int flag = 1;while (flag) {flag = 0;for (int i = 0; i < len_vn; i++) {char str[50];int p = 0;for (int j = 1; j < len_last[i]; j++) {if (IsVt(lastvt[i][j])) {//当前符号是终结符str[p++] = lastvt[i][j];}else {         //当前符号是非终结符for (int k = 0; k < len_vn; k++) {//找出该非终结符的位置if (Vn[k] == lastvt[i][j]) {   //k为当前非终结符在表中的行下标for (int q = 1; q < len_last[k]; q++) {//将k行中的firstvt集中的元素全部加入i中char ch = lastvt[k][q];int npc = 1;for (int m = 1; m < len_last[i]; m++) {//遍历第i行，去除重复的。if (ch == lastvt[i][m]) {npc = 0;break;}}if (npc == 1) {str[p++] = ch;}}}}}}for (int j = 0; j < p; j++) {//重新写入i行的firstlastvt[i][j + 1] = str[j];}len_last[i] = p + 1;if (flag == 0) {for (int j = 1; j < len_last[i]; j++) {if (IsVn(lastvt[i][j])) {flag = 1;break;}}}}}
}void PrinFirst() {for (int i = 0; i < len_vn; i++) {cout << "Firstvt(" << firstvt[i][0] << "):";for (int j = 1; j < len_first[i]; j++) {cout << firstvt[i][j] << " ";}cout << endl;}
}
void PrinLast() {for (int i = 0; i < len_vn; i++) {cout << "Lastvt(" << lastvt[i][0] << "):";for (int j = 1; j < len_last[i]; j++) {cout << lastvt[i][j] << " ";}cout << endl;}
}
void PrintTable() {//输出算符优先关系表for (int i = 0; i < len_vt + 1; i++) {cout << "\t" << Vt_[i];}cout << endl;for (int i = 0; i < len_vt + 1; i++) {cout << Vt_[i];for (int j = 0; j < len_vt + 1; j++) {cout << "\t" << table[i][j];}cout << endl;}
}void Init() {//对Vt数组增加# 生成Vt_数组  在构建算符优先分析表中用到int i;for (i = 0; i < len_vt; i++) {Vt_[i] = Vt[i];}Vt_[i] = '#';
}
int FindSub(char c) {//寻找某个终结符在数组里面对应的下标for (int i = 0; i < len_vt + 1; i++) {if (Vt_[i] == c) {return i;}}return -1;//#的下标
}
void CreateTable() {//构建算符优先分析表Init();AftSource[Len_Source][num[Len_Source]++] = "E'";AftSource[Len_Source][num[Len_Source]++] = "#";AftSource[Len_Source][num[Len_Source] - 1] += AftSource[0][0];AftSource[Len_Source][num[Len_Source] - 1] += '#';Len_Source++;for (int i = 0; i < Len_Source; i++) {//遍历每条产生式for (int j = 1; j < num[i]; j++) {//遍历每条产生式中的每个生成式int len = AftSource[i][j].length();for (int k = 0; k < len - 1; k++) {//遍历每个生成式中的每个元素if (IsVt(AftSource[i][j][k]) && IsVt(AftSource[i][j][k + 1])) {//Xi和Xi+1都是终结符P->...ab...int x = FindSub(AftSource[i][j][k]);int y = FindSub(AftSource[i][j][k + 1]);table[x][y] = '=';}if (k <= len - 3 && IsVt(AftSource[i][j][k]) && IsVt(AftSource[i][j][k + 2]) && IsVn(AftSource[i][j][k + 1])) { //P->..aQb..int x = FindSub(AftSource[i][j][k]);int y = FindSub(AftSource[i][j][k + 2]);table[x][y] = '=';}if (IsVt(AftSource[i][j][k]) && IsVn(AftSource[i][j][k + 1])) {//p->..aQ.. 则 a < firstvt(Q)int x = FindSub(AftSource[i][j][k]);for (int m = 0; m < len_vn; m++) {if (firstvt[m][0] == AftSource[i][j][k + 1]) {//找到非终结符Xi+1对应的位置for (int n = 1; n < len_first[m]; n++) {//遍历该firstvt集中的每个元素int y = FindSub(firstvt[m][n]);table[x][y] = '<';}break;}}}if (IsVn(AftSource[i][j][k]) && IsVt(AftSource[i][j][k + 1])) {//p->..Qa..  则lastvt(Q) > aint x = FindSub(AftSource[i][j][k + 1]);for (int m = 0; m < len_vn; m++) {if (lastvt[m][0] == AftSource[i][j][k]) {for (int n = 1; n < len_last[m]; n++) {int y = FindSub(lastvt[m][n]);table[y][x] = '>';}break;}}}}}}
}char Judge(string temp) {for (int r = 0; r < Len_Source; r++) {for (int s = 1; s < num[r]; s++) {if (temp.length() == AftSource[r][s].length()) {//保证可规约串与 产生式里的式子长度相等for (int h = 0; h < temp.length(); h++) {if (temp[h] == AftSource[r][s][h] && IsVt(temp[h])) {return AftSource[r][0][0];}}}}}
}void Analysis(string str) {//算符优先分析int Len = str.length();string stack = "#";int k = 1;//记录栈顶元素char a;//记录输入缓冲区最前面的元素int j;int i = 0;int tap = 0;cout << "步骤\t\t" << "符号栈\t\t" << "输入串\t\t" << "动作\n\n";cout << tap++ << "\t\t" << stack << "\t\t" << str << "\t" << "预备\n";do {a = str[i];if (IsVt(stack[k - 1])) {j = k - 1;}else {j = k - 2;}int x = FindSub(stack[j]);int y = FindSub(a);while (table[x][y] == '>') {//归约int m, n;do {char Q = stack[j];if (IsVt(stack[j - 1])) {j = j - 1;}else {j = j - 2;}m = FindSub(stack[j]);n = FindSub(Q);} while (table[m][n] != '<');string temp = stack.substr(j + 1, k - j - 1);char ch = Judge(temp);//判断归约后的符号stack.erase(j + 1, k - 1);k = j + 1;stack += ch;k++;//入栈后栈的长度还得+1，x = FindSub(stack[j]);//这里的x更换了cout << tap++ << "\t\t" << stack << "\t\t" << str.substr(i, Len - i) << "\t\t" << "归约\n";//cout << stack << endl;}if ((table[x][y] == '<' || table[x][y] == '=') && a != '#') { //移进操作stack += a;k++;i++;cout << tap++ << "\t\t" << stack << "\t\t" << str.substr(i, Len - i) << "\t\t" << "移进\n";}else if (a != '#') {//错误cout << "error" << endl;return;}} while (a != '#');cout << tap++ << "\t\t" << stack << "\t\t" << str.substr(i, Len - i) << "\t\t" << "接受\n";
}int main() {static string BefSource[100];ifstream infile("Source.txt");if (!infile)cout << "error" << endl;int Len = 0;while (infile.good()) {getline(infile, BefSource[Len++]);}cout << "==========从文件中读取到的产生式==========\n" << endl;for (int i = 0; i < Len; i++) {cout << BefSource[i] << endl;}Len_Source = Len;Pretreatment(BefSource, Len);//预处理FirstVT();LastVT();cout << "\n==========firstVt集==========\n" << endl;PrinFirst();cout << "\n==========LastVt集==========\n" << endl;PrinLast();CreateTable();cout << "\n==========算符优先关系表==========\n" << endl;PrintTable();string str;cout << "\n==========请输入要分析的句子：==========" << endl;cin >> str;cout << "\n==========分析步骤==========\n" << endl;Analysis(str);return 0;
}//E->E+T|T;
//T->T*F|F;
//F->P!F|P;
//P->(E)|i;

附件：
文件中的产生式：