编译原理课程设计、正则表达式、LL(1)分析、算符优先、LR分析

福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓名：陈润铭系：计算机专业：计算机科学与技术年级：11级计升学号：3116013049指导教师：李小林职称：副教授2012~2013学年第一学期福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目录1正则表达式·································································································11.1正则表达式························································································11.2确定化(化简)后的状态转换图································································11.3分析程序代码·····················································································11.4程序运行截图·····················································································21.5小结···································································································22LL(1)分析···································································································32.1LL(1)文法·························································································32.2LL(1)预测分析表················································································32.3分析程序代码·····················································································32.4程序运行截图·····················································································32.5小结·································································································63算符优先分析······························································································73.1算符优先文法·····················································································73.2算符优先关系表··················································································73.3分析程序代码·····················································································73.4程序运行截图·····················································································73.5小结································································································114LR分析·····································································································124.1LR文法····························································································124.2LR分析表·························································································124.3分析程序代码····················································································124.4程序运行截图····················································································154.5小结································································································15参考文献：·····································································································1511正则表达式1.1正则表达式(a|b)*(aa|bb)(a|b)*(注：该正规式为示例，可更改）1.2确定化(化简)后的状态转换图1.3分析程序代码#includeiostream#includestring#includemapusingnamespacestd;//定义一个存储状态转换的类classStatu{public:mapchar,Statu*MAP;};intmain(){//定义4个状态并初始化各个状态间的关系，以及定义一个存储当前状态的变量statusStatuA,B,C,D,*status;A.MAP['a']=&B;A.MAP['b']=&C;B.MAP['a']=&D;B.MAP['b']=&C;C.MAP['a']=&B;C.MAP['b']=&D;D.MAP['a']=&D;D.MAP['b']=&D;while(1){string::size_typesize=0;stringstr;boolflag=true;cout请输入符合(a|b)*(aa|bb)(a|b)*的正则表达式endl;cinstr;status=&A;//刚开始指向初始状态constchar*ch=str.c_str();while(ch[size]){abCBADababab2if(ch[size]!='a'&&ch[size]!='b'){flag=false;break;}status=status-MAP[ch[size++]];//根据输入字符串调整状态}if(status==&D&&flag)//若为终结状态则符合此正则表达式cout√正确endl;elsecout×错误endl;}return0;}1.4程序运行截图1.5小结通过定义各个状态，并生成各个状态间的关系可以方便地表示状态转换图，使用关联容器则可以方便的管理状态。32LL(1)分析2.1LL(1)文法E→TE'(注：该文法为示例，可更改）E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i2.2LL(1)预测分析表i+*()#EE→TE'E→TE'E'E'→+TE'E'→εE'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)2.3分析程序代码#includeiostream#includestring#includemap#includestackusingnamespacestd;enumSymbols{//终结符号Terminalsymbols：TSTS_I,//iTS_PLUS,//+TS_MULTIPLY,//*TS_L_PARENS,//(TS_R_PARENS,//)TS_EOS,//#,'\0'TS_INVALID,//非法字符//非终结符号Noneterminalsymbols：NTSNTS_E,//ENTS_EE,//E'NTS_T,//TNTS_TT,//T'NTS_F//F};4enumSymbolslexer(charc){switch(c){case'i':returnTS_I;case'+':returnTS_PLUS;case'*':returnTS_MULTIPLY;case'(':returnTS_L_PARENS;case')':returnTS_R_PARENS;case'#':returnTS_EOS;//栈底：#终结符号default:returnTS_INVALID;}}intmain(){while(1){cout输入一个以#结束的字符串endl;constchar*p;stringstr;cinstr;p=str.c_str();mapenumSymbols,mapenumSymbols,inttable;stackenumSymbolsss;//设置词法分析表table[NTS_E][TS_I]=1;table[NTS_E][TS_L_PARENS]=1;table[NTS_EE][TS_PLUS]=2;table[NTS_EE][TS_R_PARENS]=3;table[NTS_EE][TS_EOS]=3;table[NTS_T][TS_I]=4;table[NTS_T][TS_L_PARENS]=4;table[NTS_TT][TS_PLUS]=6;table[NTS_TT][TS_MULTIPLY]=5;table[NTS_TT][TS_R_PARENS]=6;table[NTS_TT][TS_EOS]=6;table[NTS_F][TS_I]=8;table[NTS_F][TS_L_PARENS]=7;5//初始化符号栈ss.push(TS_EOS);ss.push(NTS_E);while(ss.size()0){if(lexer(*p)==ss.top()){p++;ss.pop();}else{switch(table[ss.top()][lexer(*p)]){case1://1.E→TE'ss.pop();ss.push(NTS_EE);ss.push(NTS_T);break;case2://2.E'→+TE'ss.pop();ss.push(NTS_EE);ss.push(NTS_T);ss.push(TS_PLUS);break;case3://2.E'→εss.pop();break;case4://4.T→FT'ss.pop();ss.push(NTS_TT);ss.push(NTS_F);break;case5://5.T'→*FT'ss.pop();ss