算符优先文法

编译原理实验代码：对于任意给定的文法，判断其是否是算符优先文法。代码如下：#include#include#include #define row 50#define col 50#define SIZE 50using namespace std;/两个重要结构体的定义/FIRSTVT表或LASTVT表中一个表项（A,a）结构体的初始化typedef structchar nonterm; /非终结符char term; /终结符StackElement;/存放（A,a）的栈的初始化typedef struct StackElement *top;StackElement *bottom;int stacksize;stack;/初始化（A,a）栈void InitStack(stack &S) S.bottom = new StackElementSIZE; if(!S.bottom) cout存储空间分配失败！=S.stacksize) cout栈已满，无法插入！nonterm=e.nonterm;S.top-term=e.term;S.top+;/弹出栈顶（A,a）元素StackElement Pop(stack &S)StackElement e;e.nonterm = 0;e.term = 0;if(S.top=S.bottom) cout栈为空，无法进行删除操作！nonterm;e.term=S.top-term;return e;/终结符与非终结符的判断函数（布尔类型）bool TerminalJud(char c) if(c=A&c=a&c=z) return false;else return true; /终结符返回true/判断非终结符在first表中是否已存在bool ItemJud(char firstcol,int frist_len,char C)for(int i=0;ifrist_len;i+) if(firsti0=C) return true; /如果first表中已存在此非终结符，则返回true return false;/读文件函数int readfile(char sencol) char addr50; cout请输入要读文件的地址（用表示）：addr; ifstream fin; fin.open(addr,ios:in); if(!fin) coutCannot open file!nDi; coutDiendl; k=0; /couti iiiiendl; /coutkendl; /for(j=0;ji;j+) /coutDjgggendl; for(z=0;zi;z+) mm=0; l=0; for(j=0;j; l=3; j+; if(mm=0) senkl=Dzj; l+ ; if(mm=1) senkl=Dzj; l+ ; k+; /coutk kkkkkkendl; /for(i=0;ik;i+) /coutseniendl; return k;/FIRSTVT表和LASTVT表中表项（非终结符）的初始化void ItemInit(char sencol,char firstcol,char lastcol,int sen_len,int &frist_len)int i;frist_len=1;first00=sen00;last00=sen00;for(i=1;isen_len;i+) if(TerminalJud(seni0)=false & ItemJud(first,frist_len,seni0)=false) /k是当前first和last表的长度 firstfrist_len0=seni0; lastfrist_len0=seni0; frist_len+; void FirstVt(char sencol,char firstcol,int sen_len,int frist_len) / frist_len 是 first 表的行数 sen_len是产生式的个数StackElement DFS,recordSIZE;/StackElement char nonterm; /非终结符 char term; /终结符stack Operator; /创建存放（A，a）的栈 StackElement *top; StackElement *bottom; int stacksize;InitStack(Operator); int i,j,r=0;for(i=0;isen_len;i+) /第一次扫描，将能直接得出的first（A，a）放进栈中 for(j=3;senij!=0;j+) if(TerminalJud(senij)=true) /遇到的第一个终结符压入 int exist=0; DFS.nonterm=seni0; DFS.term=senij; for(int i1=0;ir;i+) if(recordi1.nonterm=seni0&recordi1.term=senij) exist=1; break; recordr.nonterm=seni0; recordr.term=senij; if(exist=0) Insert(Operator,DFS);/A-aB A-aC (A,a)压栈两次? recordr.nonterm=seni0; recordr.term=senij; r+; break; int locationcol; /辅助数组，用来记录first表中放入终结符的位置for(i=0;ifrist_len;i+) locationi=1;while(!ifEmpty(Operator) int exist=0; /标志位，记录即将入栈的元素是否已经存在 StackElement IDElement,DElement; DElement=Pop(Operator); /弹出栈顶元素 for(i=0;ifrist_len;i+) if(firsti0=DElement.nonterm) int n=locationi; firstin=DElement.term; /将终结符填入相应的first表中 locationi+; break; for(j=0;jsen_len;j+) if(senj3=DElement.nonterm) /找出能推出当前非终结符的产生式的左部 IDElement.nonterm=senj0; IDElement.term=DElement.term; /判断将要放进栈里的元素曾经是否出现过，若没有，才压入栈 for(int r0=0;r0r;r0+) /r记录record数组中的元素个数 if(recordr0.nonterm=IDElement.nonterm & recordr0.term=IDElement.term) exist=1; break; if(exist=0) Insert(Operator,IDElement); recordr.nonterm=IDElement.nonterm; recordr.term=IDElement.term; r+; void LastVt(char sencol,char lastcol,int sen_len,int frist_len) /firstvt表与lastvt表行数一样 first_len表示last 表的行数int i,j,i1,j1;char c,recordrowcol=0; for(i=0;isen_len;i+) for(j=0;senij!=0;j+) recordij=senij; j=j-1; for(i1=3,j1=j;i1j1;i1+,j1-) /做翻转，就可以用求first的方法求last c=recordii1; recordii1=recordij1; recordij1=c; /forFirstVt(record,last,sen_len,frist_len);/判断非终结符在term表中是否已存在bool TermTableJud(char termcol,int term_len,char C) for(int i=0;iterm_len;i+) if(termi=C) return true; /如果first表中已存在此非终结符，则返回1 return false;/构造算符优先关系表bool OpPriotable(char sencol,char firstcol,char lastcol,char opTablecol,int sen_len,int first_len,int &opTable_len) int i,j,term_len=0;int i2,i3,opr,opc;char c1,c2,c3;char termSIZE=0;for(i=0;isen_len;i+) /一维数组term记录关系表中存在的所有终结符 for(j=3;senij!=0;j+) if(TerminalJud(senij)=true) if(TermTableJud(term,term_len,senij)=false) /term_len记录term表的长度 termterm_len=senij; term_len+; /得到终结符表for(i=0;iterm_len+1;i+) /给优先关系表赋初值，都等于空 for(j=0;jterm_len+1;j+) opTableij= ;for(i=1;iterm_len+1;i+) /设置优先关系表的表头 opTablei0=termi-1; opTable0i=termi-1; opTablei0=$; opTable0i=$; for(i=0;isen_len;i+) /找等于关系 for(j=4;senij!=0;j+) if(TerminalJud(senij-1)=true&TerminalJud(senij)=true) c1=senij-1; c2=senij; for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的行标opr if(opTableopr0=c1) break; for(opc=1;opcterm_len+1;opc+) /在opTable表中找到该存入的列标j2 if(opTable0opc=c2) break; if(opTableopropc!= ) if(opTableopropc!=) cout不是算符优先文法！endl; return false; else opTableopropc=; for(j=5;senij!=0;j+) if(TerminalJud(senij-2)=true&TerminalJud(senij-1)=false&TerminalJud(senij)=true) c1=senij-2; c2=senij; for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的行标opr if(opTableopr0=c1) break; for(opc=1;opcterm_len+1;opc+) /在opTable表中找到该存入的列标opc if(opTable0opc=c2) break; if(opTableopropc!= ) /表示存在多种关系不满足条件 if(opTableopropc!=) cout不是算符优先文法！endl; return false; else opTableopropc=; /if /for(j)/for(i) for(i=0;isen_len;i+) /找小于关系 for(j=3;senij!=0;j+) if(TerminalJud(senij)=true&TerminalJud(senij+1)=false) c1=senij; /c1记录终结符 c2=senij+1; /c2记录非终结符 for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的行标opr if(opTableopr0=c1) break; for(opc=0;opcfirst_len;opc+) /找出非终结符在first表中的列标opc if(firstopc0=c2) break; for(i2=1;firstopci2!=0;i2+) c3=firstopci2; for(i3=1;i3term_len+1;i3+) if(opTable0i3=c3) if(opTableopri3!= ) if(opTableopri3!=) cout不是算符优先文法！endl; return false; else opTableopri3=; break; for(i=0;isen_len;i+) /找大于关系 for(j=3;senij!=0;j+) if(TerminalJud(senij)=false&senij+1!=0&TerminalJud(senij+1)=true) c1=senij; /c1记录非终结符 c2=senij+1; /c2记录终结符 for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的列标j1 if(opTable0opr=c2) break; for(opc=0;opcfirst_len;opc+) /找出非终结符在last表中的行标j2 if(lastopc0=c1) break; for(i2=1;lastopci2!=0;i2+) c3=lastopci2; for(i3=1;i3) cout不是算符优先文法！; break; opTable_len=term_len+1;return true;/判断两算符优先关系并给出类型供构造分析表int RelationshipJud(char c1,char c2,char opTablecol,int opTable_len)int i,j;for(i=1;iopTable_len;i+) if(opTablei0=c1) break;for(j=1;jopTable_len;j+) if(opTable0j=c2) break;if(opTableij=) return 3;else return 4;/判断输入串是不是优先文法bool PrioGramJud(char sencol,int sen_len)int i,j;for(i=0;isen_len;i+) for(j=4;senij!=0;j+)/gfhgfhgggggggggggggggggggggggggggggggggggggggggggggggggggg if(TerminalJud(senij-1)=false&TerminalJud(senij)=false) cout输入的不是算符文法!endl; return false; return true;/开始分析输入串void InputAnalyse(char opTablecol,char stringcol,int opTable_len) /opTable_len是opTable表的长度char a,Q,SSIZE=0; /S是分析栈 char cho1,cho2;int i,j,relation;int k=0;Sk=#;cho2=y;couttttt分析过程如下：endl;cout-endl;/cout 栈t当前字符t优先关系t移进或规约endl;/cout分析过程如下：endl;cout.width(10);cout栈;cout.width(15);cout当前字符;cout.width(20);cout剩余符号串;cout.width(15);cout优先关系;cout.width(15);cout移进或规约a /cout St att; cout.setf(ios:left); cout.width(10); coutS; cout.unsetf(ios:left); cout.width(15); couta; cout.width(20); coutp; cout.width(15); cout; do Q=Sj; if(TerminalJud(Sj-1)=true) j=j-1; else j=j-2; while(RelationshipJud(Sj,Q,opTable,opTable_len)!=1); /cout Sj归约endl; cout.width(11); coutSj; cout.width(4); cout归约endl; k=j+1; Sk=N; for(int l=k+1;lSIZE;l+) Sl=0; else if(relation=1) /Sja cho1=y; /cout St att tt 移进endl; cout.setf(ios:left); cout.width(10); coutS; cout.unsetf(ios:left); cout.width(15); couta; cout.width(20); coutp; cout.width(15); cout; cout.width(15); cout移进endl; k=k+1; Sk=a; else if(relation=2) /Sj=a cho1=y; /cout St att =tt; cout.setf(ios:left); cout.width(10); coutS; cout.unsetf(ios:left); cout.width(15); couta; cout.width(20); coutp; cout.width(15); cout=; cout.width(15); if(RelationshipJud(Sj,#,opTable,opTable_len)=2) cout 接受endl; break; else cout 移进endl; k=k+1; Sk=a; else cho1=y; /cout Statt出错endl; coutS a 出错endl; cout对不起！字符串有错！endl; cho2=n; break; /while/for /int main()char choice=y;while(choice=y) system(cls); char senrowcol=0,firstrowcol=0,lastrowcol=0,opTablerowcol=0; char stringcol; int i,k,p,q; p=readfile