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

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

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

3、main()/定義4個(gè)狀態(tài)并初始化各個(gè)狀態(tài)間的關(guān)系，以及定義一個(gè)存儲(chǔ)當(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請(qǐng)輸入符合(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錯(cuò)誤endl;return 0;1.4 程序運(yùn)行截圖1.5 小結(jié)通過(guò)定義各個(gè)狀態(tài)，并生成各個(gè)狀態(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ù)測(cè)分析表i+*()#eeteeteee+teeettfttftttt*ftttffif(e)2.3 分析程序代碼#include #include #include #include using namespace std;enum symbols/ 終結(jié)符號(hào) terminal symbols：tsts_i, / its_plus, / +ts_multiply,/ *ts_l_parens, / (ts_r_parens, / )ts_eos, / #, 0ts_invalid, / 非法字符/非終結(jié)符號(hào) 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é)符號(hào)default:return ts_invalid;int main()while(1)cout 輸入一個(gè)以#結(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;/初始化符號(hào)棧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 錯(cuò)誤的句子 endl;goto end;break;cout 正確的句子 endl;end:;return 0;2.4 程序運(yùn)行截圖2.5 小結(jié)在程序中要跳出多層語(yǔ)句只能用goto語(yǔ)句實(shí)現(xiàn)。用枚舉類型表示各個(gè)終結(jié)符與非終結(jié)符，再用關(guān)聯(lián)容器生成預(yù)測(cè)分析表即可方便地實(shí)現(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é)符號(hào)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é)符號(hào)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 輸入一個(gè)以#結(jié)束的符號(hào)串 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/語(yǔ)法錯(cuò)誤cout 不是給定算符優(yōu)先文法的句子 endl;break;return 0;3.4 程序運(yùn)行截圖3.5 小結(jié)此方法初始化優(yōu)先關(guān)系法顯得有點(diǎ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é)符號(hào)ts_a,/ ats_b,/ bts_eos,/ #, 0ts_invalid,/ 非法字符/非終結(jié)符號(hào)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é)符號(hào)default:return ts_invalid;map enum symbols, map table; int main()while(1)cout 輸入一個(gè)以#結(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