编译原理实验2语法分析器构造

2018～2019年春季学期《编译原理》课程实验报告实验二语法分析器构造专业班级：学生姓名：学生学号：序号：一、目的和要求借助于词法分析程序提供的分析结果，编写一个算符优先语法分析程序，程序能进行语法结构分析和错误检查，并产生相应的归约信息。同时给出出错信息和错误类型，从而加深对语法分析的理解。二、实验内容给定文法G和算符优先分析法，构造其算符优先分析程序。文法G：语句→赋值语句｜条件语句｜转移语句｜带标号的赋值语句带标号的赋值语句→标号赋值语句赋值语句→变量=算术表达式条件语句→TF布尔表达式THEN语句｜TF布尔表达式THEN语句ELSE语句转移语句→GOTO标号变量→标识符标识符→字母｜标识符数字字母→A｜B｜…｜Z｜a｜b｜…｜z数字→0｜1｜…｜9算术表达式→项｜算术表达式+项｜算术表达式-项项→因子｜项*因子｜项/因子｜因子↑项因子→变量｜常数｜(表达式)布尔表达式→算术表达式关系符算术表达式关系符→｜｜=｜=｜=｜标号→常数常数→数字｜常数数字三、实验的实现1.主要设计思想将算式转化为终结符串，从开始状态开始，按照文法展开式，逐级进行状态分析，直到分析完毕，如果在此期间出现状态不匹配，即语法错误，停止分析。2.实现算法及程序流程图(1)对给定表达式进行拆分以=为界，将等号右边的算式保存(2)将算式另存为终结符串将算式中的数字或字符更换为i运算符不变。(3)对终结符串进行规约(4)结束最高流程图规约过程化为终结符串过程开始判断当前字符是否为‘=’判断上一字符是否为‘’或‘’读入字符读入字符判断当前字符是否为空白符否是否是当前字符写入srcStr字符串否将srcStr串转换为终结符串，存入inputStr是结束，输出inputStr开始将源字符串以等号拆分，将算式转化为终结符串将终结符串进行规约结束开始将#压入符号栈symbols从inputStr读入字符判断symbols最高终结符j的优先级是否高于当前字符，并且符号栈是否不为#N将symbols中所有优先级比当前字符低的弹出栈存入ch直到有一个不低于的判断ch与word[i]是否相等规约为N，将N压入symbols是从inputStr读入字符i++i6?是否判断当前字符优先级是否不低于栈顶字符将当前字符压入symbols报错否是当前字符是否为#结束是否3.主要技术问题的处理方法(1)判断优先级时，原本设置了三个函数，代码过于冗余，提取相同部分后将他们整合为了一个函数，大大减少了代码量(2)最初基本功能全部写在了主函数内，虽然变量的传值十分简单，但是逻辑也极其混乱，优化结构后将大部分功能封装在一个个的函数内部，结构变得十分清晰，逻辑也更为优质。(3)在比较优先级的时候做的还不够完美，需要传入一个数组下标和一个字符才可以比较，进一步的优化可以将其改为直接传入两个字符来进行优先级的比较，代码也更加人性化。4.程序代码：//E-E+T|E-T|T//T-T*F|T/F|F//F-(E)|i////算符优先关系表//----------------------------------//+-*/()i#//+//-//*/////(=?//)??//i??//#?=//----------------------------------/*主函数*/intmain(){fp=fopen(yuchuli.txt,r);charch=fgetc(fp);charpre_ch;printf(\n开始\n\n);while(ch!='#'){formula2VT();prior_analysis();}printf(结束\n);fclose(fp);return0;}/*入栈*/voidpush(charch){symbols[++top]=ch;}/*出栈*/charpop(){chartemp=symbols[top--];symbols[top+1]='\0';returntemp;}/*对应下标*/intindex(charch){switch(ch){case'+':return0;case'-':return1;case'*':return2;case'/':return3;case'(':return4;case')':return5;case'i':return6;case'#':return7;default:return-1;}}/*判断终结符*/intisVT(charch){if(ch=='N')return0;return1;}/*读入终结符*/charreadVT(intk){if(isVT(inputStr[k])){returninputStr[k];}return0;}/*判断优先级*/intpriority(intt,chara){switch(rule[index(symbols[t])][index(a)]){case-1:returnLOW;case0:returnEQUAL;case1:returnHIGH;}return-1;}/*错误处理*/voiderror(intt){if(index(symbols[t])==5||index(symbols[t])==6){printf(\n错误e2:缺少运算符!);}elseif(index(symbols[t])==4){printf(\n错误e1:非法左括号!);}elseprintf(\n错误e3:非法右括号!);}/*打印过程*/voidprint_process(intt,intprior){printf(%4d%12s,step++,symbols);if(prior==HIGH)printf(%10c,'');elseif(prior==EQUAL)printf(%10c,'=');elseprintf(%10c,'');curChar=curChar==0?'':curChar;printf(%12c,curChar);printf(%18s,&inputStr[k]);if(t){printf(%15s\n,归约);No[n++]=step-1;}elseprintf(%15s\n,移进);}/*规约过程*/voidprior_analysis(){inti,j,m;charq,str,ch[20];push('#');print_process(0,LOW);u:curChar=readVT(k++);j=isVT(symbols[top])?top:top-1;do{while((priority(j,curChar)==HIGH)&&strcmp(symbols,#N)!=0){do{q=symbols[j];j=isVT(symbols[j-1])?j-1:j-2;}while(priority(j,q)!=LOW);i=-1;while((top-j)!=0)ch[++i]=pop();ch[i+1]='\0';for(m=0;m=5;m++){if(strcmp(word[m],ch)==0)str='N';}push(str);print_process(1,HIGH);}switch(priority(j,curChar)){caseLOW:push(curChar);print_process(0,LOW);if(symbols[top]!='#')gotou;break;caseHIGH:error(j);curChar='#';break;caseEQUAL:push(curChar);print_process(0,EQUAL);if(symbols[top]!='#')gotou;break;}}while(curChar!='#');printf(\n算术表达式%d的归约产生式步骤号为:,id++);n=0;while(No[n])printf(%d,No[n++]);printf(\n);while(symbols[0]!='\0')pop();while(No[--n])No[n]='\0';top=-1;k=0;n=0;step=1;curChar='\0';}/*导出终结符串*/voidformula2VT(){inti=-1,j=0,m=-1;while(ch!='='&&ch!='#'){pre_ch=ch;ch=fgetc(fp);if((pre_ch==''||pre_ch=='')&&ch=='=')ch=fgetc(fp);}if(ch=='#'){printf(\n------------------------------------------------------------\n);printf(结束\n);fclose(fp);return0;}while(ch!=''&&ch!='#'){ch=fgetc(fp);srcStr[++i]=ch;}srcStr[i]='\0';while(srcStr[j]!='\0'){if(isalnum(srcStr[j])){if(isalnum(srcStr[j-1])==0)inputStr[++m]='i';}elseinputStr[++m]=srcStr[j];j++;}inputStr[m+1]='#';inputStr[m+2]='\0';printf(\n------------------------------------------------------------\n);printf(\n算术表达式%d为:%s\n,id,srcStr);printf(输入字符串:%s\n,inputStr);printf(\n%8s%13s%16s%18s%20s%14s\n,步骤号,符号栈,优先关系,当前分析符,剩余输入串,动作);}5.实验运行结果及分析四、本次实验总结体会本次实验主要遇到的困难及解决方法包括：由于上一次实验打下的良好基础，本次实验较为顺利，没有遇到明显的困难。本程序的优点包括：比较完整地实现了LL(1)分析算法；分析器只需要输入起始符号、产生式、终结符号就可以初始化。本程序还存在可以优化的地方，主要包括：将输入符号串改为由词法分析器生成的二元式从文件中读取，为完整编译器的实现打下良好的基础；本实验中，通过实现LL(1)文法分析表生成算法与LL(1)文法分析算法，加深了我对两个算法的理解，提高了我对问题分析、抽象的能力，为实现完整编译器打下了良好的基础。五、对本实验过程及方法、手段的改进建议语法分析还是比较困难的一次实验，希望老师能在实验前再带领我们大致回顾一下语法分析的过程。