编译原理课程设计语法分析器.doc

《编译原理课程设计语法分析器.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计语法分析器.doc（18页珍藏版）》请在三一办公上搜索。

1、福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：系：计算机专 业：计算机科学与技术年 级：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 算符优先分析

2、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个状态并初

3、始化各个状态间的关系，以及定义一个存储当前状态的变量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_s

4、tr();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|

5、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：NTSNT

6、S_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

7、.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;table

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

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

10、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 分析程序代码

11、#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;case -:return T

12、S_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;tableTS_PLUSTS_MULT

13、IPLY = 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_MINUSTS_R_PARENS

14、= 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 = 2;tableTS_DIVIS

15、IONTS_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;tableTS_L_PARENSTS_

16、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;tableTS_R_PARENST

17、S_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;tableTS_EOSTS_PL

18、US = 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(1)if(lexer(*p)

19、 = 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 Symbols temp;whil

20、e(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 分析程序代码#include #includ

21、e #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;case #:return TS_E

22、OS; / 栈底：#终结符号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 =

23、 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 = R_1;tableS_6TS_A = R_2;tableS_6TS_B = R_2;tableS_6TS_EOS = R_2;/初始化状态栈status.push(S_0);while(1)if(lexer(*p) = TS_INVALID)co

24、ut False endl;goto END;break;switch(tablestatus.top()lexer(*p)case S_0:case S_1:case S_2:case S_3:case S_4:case S_5:case S_6:status.push(tablestatus.top()lexer(*p);+p;break;case S_ACC:cout 是给定LR文法的句子 endl;goto END;break;case R_1:status.pop();status.pop();status.push(tablestatus.top()NTS_S);break;cas

25、e R_2:status.pop();status.pop();status.push(tablestatus.top()NTS_B);break;case R_3:status.pop();status.push(tablestatus.top()NTS_B);break;default:cout 不是给定LR文法的句子 endl;goto END;break;END:;return 0;4.4 程序运行截图4.5 小结此LR分析程序的设计的数据结构与前面的类似，主要在识别算法上修改便可达到预期目的。参考文献：1 杨德芳主编.编译原理实用教程M.北京：中国水利水电出版社，20072 蒋宗礼 姜守旭编著.编译原理M.北京：高等教育出版社，2010