编译基本知识实验3算符优先分析

编译原理实验3 算符优先分析一、实验目的通过设计编制调试构造FIRSTVT集、LASTVT集和构造算符优先表、对给定符号串进行分析的程序，了解构造算符优先分析表的步骤，对文法的要求，生成算符优先关系表的算法，对给定的符号串进行分析的方法。

二、实验内容1. 给定一文法G，输出G的每个非终结符的FIRSTVT集和LASTVT集。

2. 构造算符优先表。

3. 对给定的符号串进行分析，包含符号栈，符号栈栈顶符号和输入串当前符号的优先级，最左素短语和使用的产生式和采取的动作。

三、程序思路在文法框内输入待判断文法产生式，格式E->a|S,注意左部和右部之间是“->”，每个产生式一行，ENTER键换行。

文法结束再输入一行G->#E#1. 先做文法判断，即可判断文法情况。

2. 若是算符优先文法，则在优先表栏显示优先表。

3. 写入要分析的句子，按回车即可。

4. 在分析过程栏，可以看到整个归约过程情况四、实验结果FunctorFirst.h#include<afx.h>#include<iostream>#include<fstream>#include<string>using namespace std;#define rightlength 20#define product_num 20 // 产生式最多个数#define num_noterminal 26 // 非终结符最多个数#define num_terminal 26 // 终结符最多个数struct Production{char Left;char Right[rightlength];int num;};struct VT{bool vt[num_noterminal][num_terminal];};struct Stack{char P;char a;};class CMyDlg{public:CMyDlg();void InputRule();CString showLastVT();CString showFirstVT();CString shownoTerminal(char G[]);CString showTerminal(char g[]);CString showLeftS(char S[], int j, int k);void InitAll();CString showSentence(CString sen, int start);CString showStack(char S[], int n);void Initarry(char arry[], int n);CString ProdtoCStr(Production prod);int selectProd(int i, int j, char S[]);void preFunctor(CString sen);void insertFirstVT(Stack S[], int &sp, char P, char a);void insertLastVT(Stack S[], int &sp, char P, char a); void ShowPreTable();void createPreTable();char pretable[num_terminal][num_terminal];bool like_Q(Production prod, char Q);void createLastVT();bool likeQ_(Production prod, char Q);bool likeQa_(Production prod);bool like_aQ(Production prod);bool like_a(Production prod);bool likea_(Production prod);bool Dignose(char c);int findg(char c);int findG(char c);void createFirstVT();void createTerminal();void createnoTerminal();void buildProduction(CString s);bool test(CString s);void parse(); // 语法分析CString gram; // 存放文法；Production production[product_num];VT FirstVT;VT LastVT;int locProduct; // 已有产生式个数char G[num_noterminal];char g[num_terminal];int i_G;int i_g;CString m_sen;};FunctorFirst.cpp#include"FunctorFirst.h"CMyDlg::CMyDlg(){}bool CMyDlg::test(CString s) // 测试是否是算符优先文法{bool t = 1;for (int i = 0;i < s.GetLength() - 1;i++)if (s[i] > 64 && s[i] < 91 && s[i + 1]>64 && s[i + 1] < 91){t = 0;break;}return t;}void CMyDlg::InputRule(){string infile;string line;cout <<" 请输入语法文件的路径：";cin >> infile;cout << endl;ifstream input(infile.c_str());if (!input){cout << endl <<"###打不开文件，请确认输入的路径有效###"<< endl;cout <<"!!!请再次运行本程序!!!"<< endl << endl;}while (getline(input, line)){if (test(line.c_str()) == 0){cout << endl <<"这不是算符优先文法！"<< endl;exit(0);}buildProduction(line.c_str());}cout << endl <<"这是算符优先文法！"<< endl;input.close();}void CMyDlg::buildProduction(CString s){int j = 0;int k = 0;for (k = 0;k < s.GetLength();k++) // 得到左部{if (s[k] != ' '){production[locProduct].Left = s[k];break;}}for (i = k + 1;i < s.GetLength();i++){if (s[i - 1] == '-'&&s[i] == '>')break;}int temp = i;for (i = temp + 1;i < s.GetLength();i++){if (s[i] != '|'){if (s[i] != ' '){production[locProduct].Right[j] = s[i];j++;production[locProduct].num = j;}}else{locProduct++;production[locProduct].Left = production[locProduct - 1].Left;j = 0;}}locProduct++;}void CMyDlg::createnoTerminal() // 建立非终结符索引{i_G = 0; // 最后一个位置的下一个下标int j = 0;for (int i = 0;i < locProduct;i++){for (j = 0;j < i_G;){if (production[i].Left != G[j])j++;elsebreak;}if (j > i_G - 1){G[i_G] = production[i].Left;i_G++;}}}void CMyDlg::createTerminal() // 建立终结符索引{i_g = 0; // 最后一个位置的下一个下标int j = 0;for (int i = 0;i < locProduct;i++){for (int k = 0;k < production[i].num;k++){char temp = production[i].Right[k];if (Dignose(temp)){for (j = 0;j < i_g;){if (temp != g[j])j++;elsebreak;}if (j > i_g - 1){g[i_g] = temp;i_g++;}}}}}void CMyDlg::createFirstVT() // production已完成，创建FirstVT {int i, j;Stack S[100];int sp = 0;for (i = 0;i < i_G;i++) // 初始化FirstVTfor (j = 0;j < i_g;j++)FirstVT.vt[i][j] = false;for (i = 0;i < locProduct;i++){if (likea_(production[i]))insertFirstVT(S, sp, production[i].Left, production[i].Right[0]);if (likeQa_(production[i]))insertFirstVT(S, sp, production[i].Left, production[i].Right[1]);}while (sp > 0){sp--;char Q = S[sp].P;char a = S[sp].a;for (i = 0;i < locProduct;i++){if (likeQ_(production[i], Q))insertFirstVT(S, sp, production[i].Left, a);}}}void CMyDlg::createLastVT() // 创建Last集{int i, j;Stack S[100];int sp = 0;for (i = 0;i < i_G;i++) // 初始化FirstVT for (j = 0;j < i_g;j++)LastVT.vt[i][j] = false;for (i = 0;i < locProduct;i++){if (like_a(production[i]))insertLastVT(S, sp, production[i].Left, production[i].Right[production[i].num - 1]);if (like_aQ(production[i]))insertLastVT(S, sp, production[i].Left, production[i].Right[production[i].num - 2]);}while (sp > 0){sp--;char Q = S[sp].P;char a = S[sp].a;for (i = 0;i < locProduct;i++){if (like_Q(production[i], Q))insertLastVT(S, sp, production[i].Left, a);}}}* * int CMyDlg::findG(char c) // 定位c在G中的下标{int i = 0;for (i = 0;i < i_G;i++)if (c == G[i])break;return i;}int CMyDlg::findg(char c) // 定位c在g中的下标{int i = 0;for (i = 0;i < i_g;i++)if (c == g[i])break;return i;}bool CMyDlg::Dignose(char c) // 判断c 是终结符还是非终结符，终结符true，非终结符falseif (c > 64 && c < 91)return false;elsereturn true;}bool CMyDlg::likea_(Production prod){if (Dignose(prod.Right[0]))return true;elsereturn false;}bool CMyDlg::like_a(Production prod) // 形如P->…a型产生式{if (Dignose(prod.Right[prod.num - 1]))return true;elsereturn false;bool CMyDlg::like_aQ(Production prod) // 形如P->…aQ型产生式{if (prod.num < 1)return false;else{if (Dignose(prod.Right[prod.num - 2]) && (!Dignose(prod.Right[prod.num - 1])))return true;elsereturn false;}}bool CMyDlg::likeQa_(Production prod){if (prod.num < 1)return false;else{if (Dignose(prod.Right[1]) && (!Dignose(prod.Right[0]))) return true;elsereturn false;}}bool CMyDlg::likeQ_(Production prod, char Q){if (prod.Right[0] == Q)return true;elsereturn false;}bool CMyDlg::like_Q(Production prod, char Q){if (prod.Right[prod.num - 1] == Q)return true;elsereturn false;}void CMyDlg::createPreTable() // 创建优先表{// 初始化优先表pretableint i, j;for (i = 0;i < i_g;i++)for (j = 0;j < i_g;j++)pretable[i][j] = ' '; // 表错误for (j = 0;j < locProduct;j++){for (i = 0;i < production[j].num - 1;i++){char xi, xi1, xi2;xi = production[j].Right[i];xi1 = production[j].Right[i + 1];xi2 = production[j].Right[i + 2];if (Dignose(xi) && Dignose(xi1))pretable[findg(xi)][findg(xi1)] = '=';if (i < production[j].num - 2 && Dignose(xi) && Dignose(xi2) && (!Dignose(xi1)))pretable[findg(xi)][findg(xi2)] = '=';if (Dignose(xi) && (!Dignose(xi1))){int N = findG(xi1);for (int k = 0;k < i_g;k++)if (FirstVT.vt[N][k] == true)pretable[findg(xi)][k] = '<';}if ((!Dignose(xi)) && Dignose(xi1)){int N = findG(xi);for (int k = 0;k < i_g;k++)if (LastVT.vt[N][k] == true)pretable[k][findg(xi1)] = '>';}}}}void CMyDlg::ShowPreTable() // 显示相关集合和优先表{CString str = "";str = str +"终结符"+ showTerminal(g) +"\r\n";str = str +"非终结符"+ shownoTerminal(G) +"\r\n";str = str +"First集合：\r\n"+ showFirstVT();str = str +"Lasst集合：\r\n"+ showLastVT();str = str +" | ";int i, j;for (i = 0;i < i_g;i++)str = str + g[i] +" | ";str = str +"\r\n";for (j = 0;j < i_g;j++)str = str +"…………";str +="\r\n";for (i = 0;i < i_g;i++){str = str + g[i] +" | ";for (j = 0;j < i_g;j++)str = str + pretable[i][j] +" | ";str +="\r\n";for (j = 0;j < i_g;j++)str = str +"…………";str +="\r\n";}cout << str.GetBuffer(1000);}void CMyDlg::insertFirstVT(Stack S[], int &sp, char P, char a) {if (FirstVT.vt[findG(P)][findg(a)] == false){FirstVT.vt[findG(P)][findg(a)] = true;S[sp].P = P;S[sp].a = a;sp++;}}void CMyDlg::insertLastVT(Stack S[], int &sp, char P, char a) {if (LastVT.vt[findG(P)][findg(a)] == false){LastVT.vt[findG(P)][findg(a)] = true;S[sp].P = P;S[sp].a = a;sp++;}}void CMyDlg::preFunctor(CString sen) // 算符优先分析过程实现{bool tagbreak = true;char S[100];int k = 0;S[k] = '#';int i = 0; // 表下次读入位置int j = 0;//char a;CString show = "";CString temp = "";temp.Format("%-15s %s %15s %-15s%-10s%-15s\r\n\r\n", "符号栈", "关系", "输入串", "最左素短语", "使用产生式", "下步动作");show = show + temp;temp ="";CString s_stack, s_sentence, s_lefts, s_prod, s_action;char s_presymbol;do{a = sen[i];if (Dignose(S[k]))j = k;elsej = k - 1;while (pretable[findg(S[j])][findg(a)] == '>'){s_stack = showStack(S, k);s_presymbol = pretable[findg(S[j])][findg(a)];s_sentence = showSentence(sen, i);char Q;do{Q = S[j];if (Dignose(S[j - 1]))j = j - 1;elsej = j - 2;} while (pretable[findg(S[j])][findg(Q)] == '>' || pretable[findg(S[j])][findg(Q)] == '=');int n = selectProd(j + 1, k, S);if (n > -1 && n < locProduct){s_lefts = showLeftS(S, j + 1, k);k = j + 1;S[k] = production[n].Left;s_prod = ProdtoCStr(production[n]);s_action ="归约";temp.Format("%-15s %c %15s %-15s %-10s %-15s\r\n", s_stack, s_presymbol, s_sentence, s_lefts, s_prod, s_action);show = show + temp;s_stack ="";s_sentence ="";s_lefts ="";s_prod ="";s_action ="";s_presymbol = ' ';}else{s_stack = showStack(S, k);s_presymbol = 'n';s_prod ="出错";s_sentence = showSentence(sen, i);s_action ="无法归约";temp.Format("%-15s %c %15s %-15s %-10s %-15s\r\n", s_stack, s_presymbol, s_sentence, s_lefts, s_prod, s_action);show = show + temp;s_stack ="";s_sentence ="";s_lefts ="";s_prod ="";s_action ="";s_presymbol = ' ';tagbreak = false;break;}}if (!tagbreak)break;if (pretable[findg(S[j])][findg(a)] == '<' || pretable[findg(S[j])][findg(a)] == '='){s_stack = showStack(S, k);s_presymbol = pretable[findg(S[j])][findg(a)];s_sentence = showSentence(sen, i);s_action ="入栈";temp.Format("%-15s %c %15s %-15s %-10s %-15s\r\n", s_stack, s_presymbol, s_sentence, s_lefts, s_prod, s_action);show = show + temp;k = k + 1;S[k] = a;s_stack ="";s_sentence ="";s_lefts ="";s_prod ="";s_action ="";s_presymbol = ' ';}else{s_stack = showStack(S, k);s_presymbol = 'n';s_prod ="出错";s_sentence = showSentence(sen, i);s_action ="出错";temp.Format("%-15s %c %15s %-15s %-10s %-15s\r\n", s_stack, s_presymbol, s_sentence, s_lefts, s_prod, s_action);show = show + temp;s_stack ="";s_sentence ="";s_lefts ="";s_prod ="";s_action ="";s_presymbol = ' ';break;}i++;} while (a != '#');show = show +"完成";cout << show.GetBuffer(1000) << endl << endl; }void CMyDlg::parse(){string sen;cout << endl << endl <<" 请输入分析的句子：";cin >> sen;cout << endl << endl;m_sen = sen.c_str();}int CMyDlg::selectProd(int i, int j, char S[]) // 查找产生式{int n = -1;int k = 0;for (k = 0;k < locProduct;k++){if (j - i == production[k].num - 1){int si = i;for (int m = 0;m < production[k].num;m++){if (S[si] == production[k].Right[m] || ((!Dignose(S[si])) && (!Dignose(production[k].Right[m]))))si++;elsebreak;}if (si == j + 1){n = k;break;}}}return n;}CString CMyDlg::ProdtoCStr(Production prod) {CString str = "";str = str +prod.Left +"->";for (int i = 0;i < prod.num;i++)str = str +prod.Right[i];return str;}void CMyDlg::Initarry(char arry[], int n)//初始化数组{for (int i = 0;i < n;i++)arry[i] = ' ';}CString CMyDlg::showStack(char S[], int n)//显示符号栈，n表栈大小{CString str = "";for (int i = 0;i <= n;i++)str = str +S[i];return str;}CString CMyDlg::showSentence(CString sen, int start){CString str = "";for (int i = start;i < sen.GetLength();i++)str = str +sen[i];return str;}void CMyDlg::InitAll()gram ="";i_G = 0;i_g = 0;locProduct = 0;}// 以下是为了便于显示，将数组型转换成CString型CString CMyDlg::showLeftS(char S[], int j, int k) {CString str = "";for (int i = j;i <= k;i++)str = str +S[i];return str;}CString CMyDlg::showTerminal(char g[]){CString str = "{";for (int i = 0;i < i_g;i++)str = str +g[i] +" ";return str +"}";CString CMyDlg::shownoTerminal(char G[]) {CString str = "{";for (int i = 0;i < i_G;i++)str = str +G[i] +" ";return str +"}";}CString CMyDlg::showFirstVT(){CString str = "";for (int i = 0;i < i_G;i++){str = str +"FirstVT( "+ G[i] +" )={ ";for (int j = 0;j < i_g;j++){if (FirstVT.vt[i][j])str = str + g[j] +' ';}str = str +" }\r\n";}return str;}CString CMyDlg::showLastVT(){CString str = "";for (int i = 0;i < i_G;i++){str = str +"LastVT( "+ G[i] +" )={ ";for (int j = 0;j < i_g;j++){if (LastVT.vt[i][j])str = str + g[j] +' ';}str = str +" }\r\n";}return str;}FFmain.cpp#include"FunctorFirst.h"void main(){CMyDlg ff;ff.gram ="";ff.locProduct = 0; // 已有产生式个数ff.InputRule();ff.createnoTerminal(); // 建立非终结符索引ff.createTerminal(); // 建立终结符索引ff.createFirstVT(); // 建立FirstVTff.createLastVT(); // 建立LastVTff.createPreTable(); // 建立优先表ff.ShowPreTable();ff.parse();if (ff.m_sen[ff.m_sen.GetLength() - 1] != '#')ff.m_sen = ff.m_sen +'#';ff.preFunctor(ff.m_sen);}。