福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：系：计算机专 业：计算机科学与技术年 级：2009计科学 号：指导教师：职 称：副教授20112012学年第一学期福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目 录1 正则表达式11.1 正则表达式11.2 确定化(化简)后的状态转换图11.3 分析程序代码11.4 程序运行截图11.5 小结12 LL(1)分析22.1 LL(1)文法22.2 LL(1)预测分析表22.3 分析程序代码22.4 程序运行截图22.5 小结23 算符优先分析33.1 算符优先文法33.2 算符优先关系表33.3 分析程序代码33.4 程序运行截图33.5 小结34 LR分析44.1 LR文法44.2 LR分析表44.3 分析程序代码44.4 程序运行截图44.5 小结4参考文献：41 正则表达式1.1 正则表达式 (a|b)*(aa|bb)(a|b)* (注：该正规式为示例，可更改）1.2 确定化(化简)后的状态转换图 1.3 分析程序代码#include #include #include using namespace std;/定义一个存储状态转换的类class Statupublic:map MAP;int main()/定义4个状态并初始化各个状态间的关系，以及定义一个存储当前状态的变量statusStatu A, B, C, D, *status;A.MAPa = &B;A.MAPb = &C;B.MAPa = &D;B.MAPb = &C;C.MAPa = &B;C.MAPb = &D;D.MAPa = &D;D.MAPb = &D;while(1)string:size_type size=0;string str;bool flag = true;cout请输入符合(a|b)*(aa|bb)(a|b)* 的正则表达式 str;status = &A;/刚开始指向初始状态const char *ch = str.c_str();while(chsize)if(chsize != a & chsize != b)flag = false;break;status = status-MAPchsize+;/根据输入字符串调整状态if(status = &D & flag)/若为终结状态则符合此正则表达式cout正确endl;elsecout错误endl;return 0;1.4 程序运行截图1.5 小结通过定义各个状态，并生成各个状态间的关系可以方便地表示状态转换图，使用关联容器则可以方便的管理状态。2 LL(1)分析2.1 LL(1)文法 ETE (注：该文法为示例，可更改） E+TE| TFT T*FT| F(E)|i2.2 LL(1)预测分析表i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)2.3 分析程序代码#include #include #include #include using namespace std;enum Symbols/ 终结符号 Terminal symbols：TSTS_I, / iTS_PLUS, / +TS_MULTIPLY,/ *TS_L_PARENS, / (TS_R_PARENS, / )TS_EOS, / #, 0TS_INVALID, / 非法字符/非终结符号 None terminal symbols：NTSNTS_E, /ENTS_EE,/ENTS_T,/TNTS_TT,/TNTS_F/F;enum Symbols lexer(char c)switch(c)case i:return TS_I;case +:return TS_PLUS;case *:return TS_MULTIPLY;case (:return TS_L_PARENS;case ):return TS_R_PARENS;case #:return TS_EOS; / 栈底：#终结符号default:return TS_INVALID;int main()while(1)cout 输入一个以#结束的字符串 str;p = str.c_str(); map enum Symbols, map table; stack ss;/设置词法分析表tableNTS_ETS_I = 1;tableNTS_ETS_L_PARENS = 1;tableNTS_EETS_PLUS = 2;tableNTS_EETS_R_PARENS = 3;tableNTS_EETS_EOS = 3;tableNTS_TTS_I = 4;tableNTS_TTS_L_PARENS = 4;tableNTS_TTTS_PLUS = 6;tableNTS_TTTS_MULTIPLY = 5;tableNTS_TTTS_R_PARENS = 6;tableNTS_TTTS_EOS = 6;tableNTS_FTS_I = 8;tableNTS_FTS_L_PARENS = 7;/初始化符号栈ss.push(TS_EOS);ss.push(NTS_E);while(ss.size() 0)if(lexer(*p) = ss.top()p+;ss.pop();elseswitch(tabless.top()lexer(*p)case 1:/1.ETEss.pop();ss.push(NTS_EE);ss.push(NTS_T);break;case 2:/2.E+TEss.pop();ss.push(NTS_EE);ss.push(NTS_T);ss.push(TS_PLUS);break;case 3:/2.Ess.pop();break;case 4:/4.TFTss.pop();ss.push(NTS_TT);ss.push(NTS_F);break;case 5:/5.T*FTss.pop();ss.push(NTS_TT);ss.push(NTS_F);ss.push(TS_MULTIPLY);break;case 6:/6.Tss.pop();break;case 7:/7.F(E)ss.pop();ss.push(TS_R_PARENS);ss.push(NTS_E);ss.push(TS_L_PARENS);break;case 8:/7.Fiss.pop();ss.push(TS_I);break;default:cout 错误的句子 endl;goto END;break;cout 正确的句子 endl;END:;return 0;2.4 程序运行截图2.5 小结在程序中要跳出多层语句只能用goto语句实现。用枚举类型表示各个终结符与非终结符，再用关联容器生成预测分析表即可方便地实现此算法。3 算符优先分析3.1 算符优先文法 ET | E+T | E-T (注：该文法为示例，可更改） TF | T*F | T/F F(E) | i3.2 算符优先关系表+-*/()i#+-*/()i#3.3 分析程序代码#include iostre