編譯原理課程設(shè)計、正則表達(dá)式、LL(1)分析、算符優(yōu)先、LR分析

1、福建農(nóng)林大學(xué)計算機與信息學(xué)院計算機類課程設(shè)計報告課程名稱：編譯原理課程設(shè)計題目：語法分析器姓 名：陳潤銘系：計算機專 業(yè)：計算機科學(xué)與技術(shù)年 級：11級計升學(xué) 號：3116013049指導(dǎo)教師：李小林職 稱：副教授20122013學(xué)年第一學(xué)期福建農(nóng)林大學(xué)計算機與信息學(xué)院計算機類課程設(shè)計結(jié)果評定評語：成績：指導(dǎo)教師簽字：任務(wù)下達(dá)日期：評定日期：目 錄1 正則表達(dá)式11.1 正則表達(dá)式11.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖11.3 分析程序代碼11.4 程序運行截圖11.5 小結(jié)12 LL(1)分析22.1 LL(1)文法22.2 LL(1)預(yù)測分析表22.3 分析程序代碼22.4 程序運行截圖2

2、2.5 小結(jié)23 算符優(yōu)先分析33.1 算符優(yōu)先文法33.2 算符優(yōu)先關(guān)系表33.3 分析程序代碼33.4 程序運行截圖33.5 小結(jié)34 LR分析44.1 LR文法44.2 LR分析表44.3 分析程序代碼44.4 程序運行截圖44.5 小結(jié)4參考文獻(xiàn)：41 正則表達(dá)式1.1 正則表達(dá)式 (a|b)*(aa|bb)(a|b)* (注：該正規(guī)式為示例，可更改）1.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖 1.3 分析程序代碼#include #include #include using namespace std;/定義一個存儲狀態(tài)轉(zhuǎn)換的類class Statupublic:map MAP;int

3、main()/定義4個狀態(tài)并初始化各個狀態(tài)間的關(guān)系，以及定義一個存儲當(dāng)前狀態(tài)的變量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)* 的正則表達(dá)式 str;status = &A;/剛開始指向初始狀態(tài)const cha

4、r *ch = str.c_str();while(chsize)if(chsize != a & chsize != b)flag = false;break;status = status-MAPchsize+;/根據(jù)輸入字符串調(diào)整狀態(tài)if(status = &D & flag)/若為終結(jié)狀態(tài)則符合此正則表達(dá)式cout正確endl;elsecout錯誤endl;return 0;1.4 程序運行截圖1.5 小結(jié)通過定義各個狀態(tài)，并生成各個狀態(tài)間的關(guān)系可以方便地表示狀態(tài)轉(zhuǎn)換圖，使用關(guān)聯(lián)容器則可以方便的管理狀態(tài)。2 LL(1)分析2.1 LL(1)文法 ETE (注：該文法為示例，可更改） E

5、+TE| TFT T*FT| F(E)|i2.2 LL(1)預(yù)測分析表i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)2.3 分析程序代碼#include #include #include #include using namespace std;enum Symbols/ 終結(jié)符號 Terminal symbols：TSTS_I, / iTS_PLUS, / +TS_MULTIPLY,/ *TS_L_PARENS, / (TS_R_PARENS, / )TS_EOS, / #, 0TS_INVALID, / 非法字符/非終結(jié)符號 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; / 棧底：#終結(jié)符號default:return TS_INVALID;int main()while(1)cout 輸入一個以#結(jié)束的

7、字符串 str;p = str.c_str(); map enum Symbols, map table; stack ss;/設(shè)置詞法分析表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 小結(jié)在程序中要跳出多層語句只能用goto語句實現(xiàn)。用枚舉類型表示各個終結(jié)符與非終結(jié)符，再用關(guān)聯(lián)容器生成預(yù)測分析表即可方便地實現(xiàn)此算法。3 算符優(yōu)先分析3.1 算符優(yōu)先文法 ET | E+T | E-T (注：該文法為示例，可更改） TF | T*F | T/F F(E) | i3.2 算符優(yōu)先關(guān)系表+-*/()i#+-*

11、/()i#3.3 分析程序代碼#include #include #include #include using namespace std;enum Symbols / 終結(jié)符號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; / 棧底：#終結(jié)符號default:return TS_INVALID;/初始化算符優(yōu)先關(guān)系表，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();/初始化優(yōu)先關(guān)系表while(1)cout 輸入一個以#結(jié)束的符號串 str;p = str.c_str();stack ss;ss.push(TS_EOS);while

19、(1)if(lexer(*p) = TS_INVALID)/讀取到不在集合中的非法字符cout 不是給定算符優(yōu)先文法的句子 endl;break;if(ss.top() = TS_EOS & lexer(*p) = TS_EOS)/成功規(guī)約cout 是給定算符優(yōu)先文法的句子 endl;break;elseif(tabless.top()lexer(*p) = 1 | tabless.top()lexer(*p) = 0)/繼續(xù)讀入字符，暫不規(guī)約ss.push(lexer(*p);+p;else if(tabless.top()lexer(*p) = 2) /符合規(guī)約要求，開始規(guī)約enum Sy

20、mbols temp;while(1)temp = ss.top();ss.pop();if(tabless.top()temp = 1)break;else/語法錯誤cout 不是給定算符優(yōu)先文法的句子 endl;break;return 0;3.4 程序運行截圖3.5 小結(jié)此方法初始化優(yōu)先關(guān)系法顯得有點繁瑣，有待改進(jìn)。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 / 終結(jié)符號TS_A,/ ATS_B,/ BTS_EOS,/ #, 0TS_INVALID,/ 非法字符/非終結(jié)符號NTS_SS,/SNTS_S,/SNTS_B,/B/狀態(tài)statusS_0,S_1,S_2,S_3,S_4,S_5,S_6,S_ACC,/GOGOG_S,G_B,/規(guī)約式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; / 棧底：#終結(jié)符號default:return TS_INVALID;map enum Symbols, map table; int main()while(1)cout 輸入一個以#結(jié)束的字符串 str;p = str.c_str();stack status;/設(shè)置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