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

福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：陈润铭系：计算机专 业：计算机科学与技术年 级：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 程序运行截图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 <iostream>#include <string>#include <map>using namespace std;/定义一个存储状态转换的类class Statupublic:map<char, Statu *> MAP;int main()/定义4个状态并初始化各个状态间的关系，以及定义一个存储当前状态的变量statusStatu A, 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_type size=0;string str;bool flag = true;cout<<"请输入符合(a|b)*(aa|bb)(a|b)* 的正则表达式"<<endl;cin >> 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+*()#EETE'ETE'E'E'+TE'E'E'TTFT'TFT'T'T'T'*FT'T'T'FFiF(E)2.3 分析程序代码#include <iostream>#include <string>#include <map>#include <stack>using namespace std;enum Symbols/ 终结符号 Terminal symbols：TSTS_I, / iTS_PLUS, / +TS_MULTIPLY,/ *TS_L_PARENS, / (TS_R_PARENS, / )TS_EOS, / #, '0'TS_INVALID, / 非法字符/非终结符号 None terminal symbols：NTSNTS_E, /ENTS_EE,/E'NTS_T,/TNTS_TT,/T'NTS_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 << "输入一个以#结束的字符串" << endl;const char *p;string str;cin >> str;p = str.c_str(); map< enum Symbols, map<enum Symbols, int> > table; stack<enum Symbols> 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.ETE'ss.pop();ss.push(NTS_EE);ss.push(NTS_T);break;case 2:/2.E'+TE'ss.pop();ss.push(NTS_EE);ss.push(NTS_T);ss.push(TS_PLUS);break;case 3:/2.E'ss.pop();break;case 4:/4.TFT'ss.pop();ss.push(NTS_TT);ss.push(NTS_F);break;case 5:/5.T'*FT'ss.pop();ss.push(NTS_TT);ss.push(NTS_F);ss.push(TS_MULTIPLY);break;case 6:/6.T'ss.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 <iostream>#include <string>#include <map>#include <stack>using namespace std;enum Symbols / 终结符号TS_PLUS,/ +TS_MINUS,/ -TS_MULTIPLY, / *TS_DIVISION,/ /TS_L_PARENS,/ (TS_R_PARENS, / )TS_I,/ iTS_EOS,/ #, '0'TS_INVALID,/ 非法字符;map< enum Symbols, map<enum Symbols, int> > table; enum Symbols lexer(char c)switch(c)case '+':return TS_PLUS;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;tableTS_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_MINUSTS_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 = 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;tableTS_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;tableTS_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;tableTS_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 << "输入一个以#结束的符号串" << endl;const char *p;string str;cin >> str;p = str.c_str();stack<enum Symbols> ss;ss.push(TS_EOS);while(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 Symbols 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) S'S (注：该文法为示例，可更改） (1) SBB (2) BaB (3) Bb4.2 LR分析表ACTIONGOTOab#SB0S3S4121acc2S3S453S3S464r3r3r35r1r1r16r2r2r24.3 分析程序代码#include <iostream>#include <string>#include <map>#include <stack>using namespace std;enum Symbols / 终结符号TS_A,/ ATS_B,/ BTS_EOS,/ #, '0'TS_INVALID,/ 非法字符/非终结符号NTS_SS,/S'NTS_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_EOS; / 栈底：#终结符号default:return TS_INVALID;map< enum Symbols, map<enum Symbols, enum Symbols> > table; int main()while(1)cout << "输入一个以#结束的字符串" << endl;const char *p;string str;cin >> str;p = str.c_str();stack<enum Symbols> 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 = 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)cout << "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;case 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