已知文法G 表达式 :: 项 | 表达式项 项 :: 因子 | 项*因子 因子 :: (表达式) | i 试给出下列表达式的推导。 (1) i (2) (i) (3) i*i (4) i*ii (5) i(ii) (6) ii*i (7) (ii)*i (8) ii (9) i*ii*i (10)i*i*i3. 算法思想描述的是大概的过程具体实现的细节见代码注释。1定义输入字符串E保存需要推导的句子定义输出字符串out”E”和kout”E”out用于输出主推导不是括号中表达式的推导 时的推导过程kout用于输出括号推导时的推导过程定义栈S用于保存括号中待推导的表达式。2定义推导阶段标志kflag0kflag0表示为主推导kflag≠0表示为从右向左第kflag个括号推导。定义输出函数print()根据kflag的值选择性输出推导过程具体实现可见源代码3中输出均为调用print()函数。3推导方法如下① 扫描字符串E计算E中除去括号中的符号外“”的个数记录每个“()”的位置位置相对每个“()”为一个整体来看保存到数组pos同时将“()”中的符号串压入栈S。② E中除去括号中的符号外有多少个“”就在E的末尾添加几次“I”E→EI最后将E用I替换EI…→II…同时输出。如果没有“”用I替换EE→I同时输出。③ 倒序从右向左扫描E以“”为分割点分成若干区间从右向左依次扫描每个区间计算区间内除去括号中的符号外有几个“*”从右向左扫描out不重复扫描每次接着上次的位置继续向左扫描记录“I”的位置Ipos有几个“*”就在out中Ipos位置的‘I’的后面插入“*T”I→I*T同时输出。④ 倒序扫描E将位置ipos[]pos数组中任意某个值的字符“I”或“T”替换成“E”I→TT→(E)同时输出。⑤当栈S不空令ES.top()S栈顶出栈推导阶段标志kflag重复②⑤过程。直到S栈空结束。4. 不足之处① 对于文法并没有用相应的数据结构去存储推导过程仅仅只是依据输入的表达式中的算符来判断并且只针对2.中给定的文法推导。②输入检测不够严谨仅仅只对输入能够接受的字符进行了限制并没有检查句子合法性。③推导过于依赖“*()”符号所以整体不是最左推导也不是最右推导并且对应存在嵌套括号括号中还有括号的表达式不能推导能够推导大部分的多级括号式中有多个括号但每个括号中无括号但也有少部分不能推导。#includeiostream #includestring #includestack using namespace std; int kflag0;//推导阶段标志0为主推导非0表示从右向左第几个括号推导 string out,kout;//保存括号推导过程保存全部推导过程 void shift()//存储的字母输出为汉字 { cout →; if(kflag0)//主推导直接输出out { coutout; for(int j0;j30-out.length();j) cout ; cout| →; for(int i0;iout.length();i) { if(out[i]E) cout表达式; else if(out[i]I) cout项; else if(out[i]T) cout因子; else coutout[i]; } coutendl; } else//括号推导输出kout { coutkout; for(int j0;j30-kout.length();j) cout ; cout| →; for(int i0;ikout.length();i) { if(kout[i]E) cout表达式; else if(kout[i]I) cout项; else if(kout[i]T) cout因子; else coutkout[i]; } coutendl; } } void print()//输出函数输出推导过程 { int kk,knum,kpos1,kpos2; if(kflag0)//主推导 shift();//输出 else//括号推导 { knum0;//第几个括号 for(kkkout.length()-1;kk0;kk--) { if(kout[kk])) { knum;//遇到)加1 if(knumkflag)//当遇到第kflag个)时 { kpos2kk;//记录右括号位置 while(kout[kk]!() kk--; kpos1kk;//记录左括号位置 } } } kout.replace(kpos11,kpos2-kpos1-1,out);//将括号中字符替换为当前的括号推导 shift();//输出 } } int main() { string P[3][3]; P[0][0]E; P[0][1]I; P[0][2]EI; P[1][0]I; P[1][1]T; P[1][2]I*T; P[2][0]T; P[2][1](E); P[2][2]i; coutendl文法如下endl;//输出文法 for(int i0;i3;i) { cout P[i][0] → P[i][1]|P[i][2] | ; for(int j0;j3;j) { for(int m0;mP[i][j].length();m) if(P[i][j][m]E) cout表达式; else if(P[i][j][m]I) cout项; else if(P[i][j][m]T) cout因子; else coutP[i][j][m]; if(j0) cout →; if(j1) cout | ; } coutendl; } stackstring S; //保存括号中的句子栈顶到栈底依次保存的是E中从右向左每对括号中的内容 int n[20];//括号内串长度,下标默认为第几个括号 int pos[20];//记录表达式中所有(位置 string E;//保存输入的文法 koutE;//输出总的推导过程 string choose1; while(choose1) //选择是否继续的循环 { coutendl★说明无法推导括号嵌套“(())”或“(()())”的句子只能推导多个单级括号“()()()”的句子!endl; int error1; while(error1)//输入句子简单判错 { cout请输入该文法的句子endl; cinE; for(int i0;iE.length();i) { if(E[i]!i E[i]! E[i]!* E[i]!( E[i]!)) { cout输入有误请重新输入表达式应只含有“i,,*,(,)”等字符endl; error1; break; } else error0; } } coutendl句子 E 的推导过程如下endl; coutendl E; for(int j0;j30-1;j) cout ; cout | 表达式endl;//输出开始符 K: int k0;//访问pos数组 int add0;//括号外加号个数 outE;//保存括号中内容推导过程 for(int i0;iE.length();i) { if(E[i]()//未考虑括号嵌套情况 { if(k!0)//保存(的相对位置 { pos[k]i;//一对()看成一个位置 for(int j0;jk;j) pos[k]-n[j]; pos[k]-k; } else pos[k]i; k;//查找下一个( i;//跳过( n[k-1]0;//计算括号内字符长度 while(E[i]!))//跳过括号中的字符并计算长度 { n[k-1]; i; } S.push(E.substr(i-n[k-1],n[k-1]));//括号中符号串内容入栈如果括号很多栈底为靠左括号内容 } if(E[i]) add;//计数个数 } for(int i0;iadd;i) { out.append(I);//几个就输出几个I print(); } if(add0)//无时 { outI; print(); } else//有时 { out[0]I;//E用I替换 print(); } int mul;//两个之间的括号之外乘号个数 int pos1E.length()-1,pos2; //两个的位置 int Ipos;//I的位置 char str[2]{*,T};//“*T” str[2]\0; int iE.length()-1; int mout.length()-1; while(i!-1)//倒序遍历输入的句子E { for(;i0;i--)//未考虑括号嵌套情况 { if(E[i]))//遇到 { i--;//跳过) while(E[i]!()//跳过括号中的字符 i--; } if(E[i]) break; } pos2pos1;//记录区间以为分界点末端位置 是上一个区间的开始位置 pos1i;//记录区间开始位置 if(i!-1)//保证循环能够结束 i--; mul0; for(int jpos11;jpos2;j)//扫描此区间 { if(E[j]()//遇到( { j;//跳过( while(E[j]!))//跳过括号中的字符 j; } if(E[j]*) mul; //记录*个数 } for(;m0;m--)//倒序遍历out字符 { if(out[m]I) { Iposm;//记录I的位置 mm-1;//下次从下一个位置开始遍历 break; } } if(mul!0)//有乘号 { for(int j0;jmul;j) { outout.insert(Ipos1,str);//I位置之后插入*T print(); } } } for(iout.length()-1;i0;i--)//倒序遍历out字符串 { for(int j0;jk;j)//查询pos数组即括号(位置 { if(ipos[j])//(位置与i相等时 { if(out[i]I)//推导路线为I-T-(E) { out[i]T; print(); } if(out[i]T) { out.replace(i,1,(E)); print(); } } } } for(iout.length()-1;i0;i--)//倒序遍历out { if(out[i]I)//将IT推导至i { out[i]T; print(); } if(out[i]T) { out[i]i; print(); } } if(kflag0)//如果是主推导 koutout;//保存总输出 if(!S.empty())//当S栈不空说明句子中有括号 { ES.top();//栈顶为最右侧括号 S.pop();//出栈 kflag;//表示当前正在推导第几个括号中的内容 goto K; } else coutendl推导完毕endlendl; cout输入 1 继续推导其他句子输入其他退出。endl; cinchoose; kflag0;//kflag清零继续推导其他句子 } return 0; }1.i2.(i)3.i*i4.i*ii5.i(ii)6.ii*i