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

1、福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：陈润铭系：计算机专 业：计算机科学与技术年 级：11级计升学 号：3116013049指导教师：李小林职 称：副教授20122013学年第一学期福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目 录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 程序运行截图2

2、2.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

3、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 cha

4、r *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

5、+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 termina

6、l 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 输入一个以#结束的

7、字符串 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_P

8、ARENS = 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);s

9、s.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

10、_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#+-*

11、/()i#3.3 分析程序代码#include #include #include #include using namespace std;enum Symbols / 终结符号TS_PLUS,/ +TS_MINUS,/ -TS_MULTIPLY, / *TS_DIVISION,/ /TS_L_PARENS,/ (TS_R_PARENS, / )TS_I,/ iTS_EOS,/ #, 0TS_INVALID,/ 非法字符;map enum Symbols, map table; enum Symbols lexer(char c)switch(c)case +:return TS_PLUS;

12、case -:return TS_MINUS;case *:return TS_MULTIPLY;case /:return TS_DIVISION;case (:return TS_L_PARENS;case ):return TS_R_PARENS;case i:return TS_I;case #:return TS_EOS; / 栈底：#终结符号default:return TS_INVALID;/初始化算符优先关系表，0、1、2分别表示=、，-1表示不存在void setup()tableTS_PLUSTS_PLUS = 2;tableTS_PLUSTS_MINUS = 2;tabl

13、eTS_PLUSTS_MULTIPLY = 1;tableTS_PLUSTS_DIVISION = 1;tableTS_PLUSTS_L_PARENS = 1;tableTS_PLUSTS_R_PARENS = 2;tableTS_PLUSTS_I = 1;tableTS_PLUSTS_EOS = 2;tableTS_MINUSTS_PLUS = 2;tableTS_MINUSTS_MINUS = 2;tableTS_MINUSTS_MULTIPLY = 1;tableTS_MINUSTS_DIVISION = 1;tableTS_MINUSTS_L_PARENS = 1;tableTS_MI

14、NUSTS_R_PARENS = 2;tableTS_MINUSTS_I = 1;tableTS_MINUSTS_EOS = 2;tableTS_MULTIPLYTS_PLUS = 2;tableTS_MULTIPLYTS_MINUS = 2;tableTS_MULTIPLYTS_MULTIPLY = 2;tableTS_MULTIPLYTS_DIVISION = 2;tableTS_MULTIPLYTS_L_PARENS = 1;tableTS_MULTIPLYTS_R_PARENS = 2;tableTS_MULTIPLYTS_I = 1;tableTS_MULTIPLYTS_EOS =

15、2;tableTS_DIVISIONTS_PLUS = 2;tableTS_DIVISIONTS_MINUS = 2;tableTS_DIVISIONTS_MULTIPLY = 2;tableTS_DIVISIONTS_DIVISION = 2;tableTS_DIVISIONTS_L_PARENS = 1;tableTS_DIVISIONTS_R_PARENS = 2;tableTS_DIVISIONTS_I = 1;tableTS_DIVISIONTS_EOS = 2;tableTS_L_PARENSTS_PLUS = 1;tableTS_L_PARENSTS_MINUS = 1;tabl

16、eTS_L_PARENSTS_MULTIPLY = 1;tableTS_L_PARENSTS_DIVISION = 1;tableTS_L_PARENSTS_L_PARENS = 1;tableTS_L_PARENSTS_R_PARENS = 0;tableTS_L_PARENSTS_I = 1;tableTS_L_PARENSTS_EOS = -1;tableTS_R_PARENSTS_PLUS = 2;tableTS_R_PARENSTS_MINUS = 2;tableTS_R_PARENSTS_MULTIPLY = 2;tableTS_R_PARENSTS_DIVISION = 2;ta

17、bleTS_R_PARENSTS_L_PARENS = -1;tableTS_R_PARENSTS_R_PARENS = 2;tableTS_R_PARENSTS_I = -1;tableTS_R_PARENSTS_EOS = 2;tableTS_ITS_PLUS = 2;tableTS_ITS_MINUS = 2;tableTS_ITS_MULTIPLY = 2;tableTS_ITS_DIVISION = 2;tableTS_ITS_L_PARENS = -1;tableTS_ITS_R_PARENS = 2;tableTS_ITS_I = -1;tableTS_ITS_EOS = 2;t

18、ableTS_EOSTS_PLUS = 1;tableTS_EOSTS_MINUS = 1;tableTS_EOSTS_MULTIPLY = 1;tableTS_EOSTS_DIVISION = 1;tableTS_EOSTS_L_PARENS = 1;tableTS_EOSTS_R_PARENS = -1;tableTS_EOSTS_I = 1;tableTS_EOSTS_EOS = 0;int main()setup();/初始化优先关系表while(1)cout 输入一个以#结束的符号串 str;p = str.c_str();stack ss;ss.push(TS_EOS);while

19、(1)if(lexer(*p) = TS_INVALID)/读取到不在集合中的非法字符cout 不是给定算符优先文法的句子 endl;break;if(ss.top() = TS_EOS & lexer(*p) = TS_EOS)/成功规约cout 是给定算符优先文法的句子 endl;break;elseif(tabless.top()lexer(*p) = 1 | tabless.top()lexer(*p) = 0)/继续读入字符，暂不规约ss.push(lexer(*p);+p;else if(tabless.top()lexer(*p) = 2) /符合规约要求，开始规约enum Sy

20、mbols temp;while(1)temp = ss.top();ss.pop();if(tabless.top()temp = 1)break;else/语法错误cout 不是给定算符优先文法的句子 endl;break;return 0;3.4 程序运行截图3.5 小结此方法初始化优先关系法显得有点繁琐，有待改进。4 LR分析4.1 LR文法 (0) SS (注：该文法为示例，可更改） (1) SBB (2) BaB (3) Bb4.2 LR分析表ACTIONGOTOab#SB0S3S4121acc2S3S453S3S464r3r3r35r1r1r16r2r2r24.3 分析程序代码#

21、include #include #include #include using namespace std;enum Symbols / 终结符号TS_A,/ ATS_B,/ BTS_EOS,/ #, 0TS_INVALID,/ 非法字符/非终结符号NTS_SS,/SNTS_S,/SNTS_B,/B/状态statusS_0,S_1,S_2,S_3,S_4,S_5,S_6,S_ACC,/GOGOG_S,G_B,/规约式R_1,R_2,R_3,;enum Symbols lexer(char c)switch(c)case a:return TS_A;case b:return TS_B;cas

22、e #:return TS_EOS; / 栈底：#终结符号default:return TS_INVALID;map enum Symbols, map table; int main()while(1)cout 输入一个以#结束的字符串 str;p = str.c_str();stack status;/设置LR分析表tableS_0TS_A = S_3;tableS_0TS_B = S_4;tableS_0NTS_S = S_1;tableS_0NTS_B = S_2;tableS_1TS_EOS = S_ACC;tableS_2TS_A = S_3;tableS_2TS_B = S_4;tableS_2NTS_B = S_5;tableS_3TS_A = S_3;tableS_3TS_B = S_4;tableS_3NTS_B = S_6;tableS_4TS_A = R_3;tableS_4TS_B = R_3;tableS_4TS_EOS = R_3;tableS_5TS_A = R_1;tableS_5TS_B = R_1;tableS_5TS_EOS