编译原理---算符优先分析程序设计

编译原理课程设计报告评分：签字：编译原理课程设计二——算符优先分析程序设计实验目的了解掌握算符优先分析的基本方法、内容；学会科学思考并解决问题，提高程序设计能力。实验内容与要求用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中；若存在错误，提示错误相关信息。文法表示：S→v=E|E?|clearE→E+T|E-T|TT→T*F|T/F|FF→(E)|v|c单词种别码设计：=1？2+3-4*5/6（7）8v9c10clear11#12N13实验环境系统环境为windows系统，编译环境为VS2015,编程语言为C++。实验过程过程一：构建firstVT()和lastVT()算法分析：对于firstVT()构建，对于每个非终结符F的产生式，第一个终结符或者‘|’后的第一个终结符应该在其firstVT()集合内，且若非终结符T能推出非终结符F则firstVT(T)包含first（F）。lastVT()的构造类似，对于每个非终结符F的产生式，非终结符后的第一个终结符都属于lastVT（F）,且若非终结符T能推出非终结符F则lastVT(T)包含first（F）。算法实现主要函数：voidget_firstVT()//求firstVT();voidget_lastVT()//求lastVT();结果：FirstVT(S){=,?,l,+,-,*,/,(,v,c,}FirstVT(E){+,-,*,/,(,v,c,}FirstVT(T){*,/,(,v,c,}FirstVT(F){(,v,c,}LastVT(S){=,?,l,+,-,*,/,),v,c,}LastVT(E){+,-,*,/,),v,c,}LastVT(T){*,/,),v,c,}LastVT(F){),v,c,}过程二：构建优先符号表算法分析:（1）在产生式中两个相邻的终结符优先顺序相等（2）对于小于关系，首先扫描终结符a标记flag=1，再扫描到非终结符Q，此时判断若flag=1，则对所有b∈FristVT{Q}，ab.（3）对于大于关系，首先扫描非终结符Q在前标记flag=1，再扫描终结符a在后此时判断若flag=1，对所有b∈LastVT{Q}，ba.算法结果：=?+-*/()vcl#=-2-2-1-1-1-1-1-2-1-1-21?-2-2-2-2-2-2-2-2-2-2-21+-2111-1-1-11-1-1-21--2111-1-1-11-1-1-21*-211111-11-1-1-21/-211111-11-1-1-21(-2-2-1-1-1-1-10-1-1-21)-211111-21-2-2-21v011111-21-2-2-21c-211111-21-2-2-21l-2-2-2-2-2-2-2-2-2-2-21#-1-1-1-1-1-1-1-1-1-1-10其中-2表示不会出现，1表示,-1表示,0表示=.字母l表示clear.过程三：词法分析算法分析：详见课程设计一算法主要函数：intletter()//判断是否为字母intdigit()//判断是否为数字intstr_to_num()//数字字符串转化为整数intreserve(char**k)//处理保留字intsysmbol(identifier*id)//处理标识符，查找符号表并存放位置若没有则添加intconstant(constnumber*con)//存入常数表，并返回它在常数表中的位置voidWordAnalyze(constnumber*con,identifier*id,charsentence[],int&point,int&syn,int&sym_point)//词法分析voidInsert_to_symboltbl(intsyn,intvalue,int&point)//把二元组加入symbol表算法结果：得到语句的所有单词二元组symbolTBL表,存放种别码syn及其值val，其中对于种别码为9的变量val为标志符的入口标志，对于种别码为10的的常量val为存放的值。以及标志符表。过程四：算符优先分析算法分析：1)置栈底及输入串尾为#,并设#VT,VT#;栈顶终结符为θ,输入字为a;2)若θa或θ=a且a≠#,则a移入栈中.重复2);若θa,则在栈中寻找最左素短语,归约为N,并记录N的值重复2);若θ=a=#,且栈中为#N,则分析成功;否则,输入串为非法字串.数据结构设计：构造堆栈结构存储分析句子typedefstruct{SymbolTbl*elem;intn;inttop;}Stack;堆栈相关操作intCreateStack(Stack&s,intn)//初始化voidclearStack(Stack&s)//清空intempty(Stack&s)//判断是否为空voidpush(Stack&s,SymbolTblt)//入栈voidpop(Stack&s)//出栈主要函数：voidClear_Symbol_Tbl()//清空符号表voidprint_(Stack&s,int&point)//打印出堆栈和符号表的情况voidsuanfu_main()//算符优先分析测试分析测试用例a=5b=a+10测试结果#a=5#标识符表：1a-1二元组表:012-119121-13105412-1当前堆栈情况：(12,-1)当前符号表情况：(9,1)(1,-1)(10,5)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,1)当前符号表情况：(1,-1)(10,5)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,1)(1,-1)当前符号表情况：(10,5)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,1)(1,-1)(10,5)当前符号表情况：此处将常量归约为N当前堆栈情况：(12,-1)(9,1)(1,-1)(13,5)当前符号表情况：此处将v=c归约为N当前堆栈情况：(12,-1)(13,5)当前符号表情况：当前堆栈情况：(12,-1)(13,5)当前符号表情况：归约成功结果为5coninue?yorny请输入句子,以#开始并且以#结束#b=a+10#标识符表：1a52b-1二元组表:012-119221-139143-151010612-1当前堆栈情况：(12,-1)当前符号表情况：(9,2)(1,-1)(9,1)(3,-1)(10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,2)当前符号表情况：(1,-1)(9,1)(3,-1)(10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,2)(1,-1)当前符号表情况：(9,1)(3,-1)(10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,2)(1,-1)(9,1)当前符号表情况：(3,-1)(10,10)此处将变量归约为N当前堆栈情况：(12,-1)(9,2)(1,-1)(13,5)当前符号表情况：(3,-1)(10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,2)(1,-1)(13,5)(3,-1)当前符号表情况：(10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1)(9,2)(1,-1)(13,5)(3,-1)(10,10)当前符号表情况：此处将常量归约为N当前堆栈情况：(12,-1)(9,2)(1,-1)(13,5)(3,-1)(13,10)当前符号表情况：此处将N+N归约为N当前堆栈情况：(12,-1)(9,2)(1,-1)(13,15)当前符号表情况：此处将v=c归约为N当前堆栈情况：(12,-1)(13,15)当前符号表情况：归约成功结果为15coninue?yorn结论符合预期结果该赋值语句解释程序符合要求感想与收获赋值语句的词法分析包括了众多过程与步骤，通过完整的完成本次课程设计，我对构建算符优先表以及语法分析过程有了更深的理解与掌握。同时在用代码实现的过程中我程序设计、程序优化、调试程序的能力也有较大提升。代码#includeiostream#includeiomanipusingnamespacestd;//单词种别码intzb_c(chara){switch(a){case'=':return1;case'?':return2;case'+':return3;case'-':return4;case'*':return5;case'/':return6;case'(':return7;case')':return8;case'v':return9;case'c':return10;case'l':return11;case'#':return12;case'N':return13;default:return0;}}charzbc[12]={'=','?','+','-','*','/','(',')','v','c','l','#'};//是否为终结符intISzj_code(charch){if((ch=97&&ch=122)||ch=='+'||ch=='*'||ch=='-'||ch=='/'||ch=='!'||ch=='('||ch==')'||ch=='#'||ch=='\?'||ch=='=')return1;elsereturn0;}charwenfa[4][30]={{S→v=E|E?|l},{E→E+T|E-T|T},{T→T*F|T/F|F},{F→(E)|v|c}};charFirst_VT[4][20];charLast_VT[4][20];charchc[4]={'S','E','T','F'};intFzj(chara){switch(a){case'S':return0;case'E':return1;case'T':return2;case'F':return3;default:return-1;}}//求firstVTvoidget_firstVT(){inti,j;for(i=3;i=0;i--){intk=0,flag=1;for(j=2;wenfa[i][j]!='\0';j++){if(ISzj_code(wenfa[i][j])&&flag==1){if(i==0&&j==3);else{First_VT[i][k++]=wenfa[i][j];flag=0;}}if(wenfa[i][j]=='|')flag=1;}if(i!=3){j=0;while(First_VT[i+1][j]!='\0')First_VT[i][k++]=First_VT[i+1][j++];}First_VT[i][k]='\0';}}voidget_lastVT(){inti,j;for(i=3;i=0;i--){intk=0,flag=0;for(j=3;wenfa[i][j]!='\0';j++){if(ISzj_code(wenfa[i][j])&&flag==1){Last_VT[i][k++]=wenfa[i][j];flag=0;}if(!ISzj_code(wenfa[i][j]))flag=1;}if(i!=3){j=0;while(Last_VT[i+1][j]!='\0')Last_VT[i][k++]=Last_VT[i+1][j++];}}}//打印fistVT与lastVT结果voidprintFistlast(){get_firstVT();for(inti=0;i4;i++){coutFirstVT(chc[i]){;intj=0;while(First_VT[i][j]!='\0')coutFirst_VT[i][j++],;cout'}'endl;}get_lastVT();for(inti=0;i4;i++){coutLastVT(chc[i]){;