編譯原理課程設(shè)計(jì)語法分析器

1、福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院計(jì)算機(jī)類課程設(shè)計(jì)報(bào)告課程名稱：編譯原理課程設(shè)計(jì)題目：語法分析器姓 名：系：計(jì)算機(jī)專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年 級：2009計(jì)科學(xué) 號(hào)：指導(dǎo)教師：職 稱：副教授20112012學(xué)年第一學(xué)期福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院計(jì)算機(jī)類課程設(shè)計(jì)結(jié)果評定評語：成績：指導(dǎo)教師簽字：任務(wù)下達(dá)日期：評定日期：目 錄1 正則表達(dá)式11.1 正則表達(dá)式11.2 確定化(化簡)后的狀態(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ù)測分析表22.3 分析程序代碼22.4 程序運(yùn)行截圖22.5 小結(jié)23 算符優(yōu)先分析

2、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 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖 1.3 分析程序代碼#include <iostream>#include <string>#include <map>using namespace std;/定義一個(gè)存儲(chǔ)狀態(tài)轉(zhuǎn)換的類clas

3、s statupublic:map<char, statu *> map;int main()/定義4個(gè)狀態(tài)并初始化各個(gè)狀態(tài)間的關(guān)系，以及定義一個(gè)存儲(chǔ)當(dāng)前狀態(tài)的變量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' = &

4、d;d.map'b' = &d;while(1)string:size_type size=0;string str;bool flag = true;cout<<"請輸入符合(a|b)*(aa|bb)(a|b)* 的正則表達(dá)式"<<endl;cin >> str;status = &a;/剛開始指向初始狀態(tài)const char *ch = str.c_str();while(chsize)if(chsize != 'a' && chsize != 'b')f

5、lag = 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é)通過定義各個(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&

6、#39; (注：該文法為示例，可更改） e'+te'| tft' t'*ft'| f(e)|i2.2 ll(1)預(yù)測分析表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>us

7、ing namespace std;enum symbols/ 終結(jié)符號(hào) terminal symbols：tsts_i, / its_plus, / +ts_multiply,/ *ts_l_parens, / (ts_r_parens, / )ts_eos, / #, '0'ts_invalid, / 非法字符/非終結(jié)符號(hào) 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

8、9;: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é)束的字符串" << endl;const

9、char *p;string str;cin >> str;p = str.c_str(); map< enum symbols, map<enum symbols, int> > table; stack<enum symbols> 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_tt

10、s_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;/初始化符號(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.et

11、e'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

12、.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 << "錯(cuò)誤的句子" << endl;goto end;break;cout << "正確的句子" << endl;en

13、d:;return 0;2.4 程序運(yùn)行截圖2.5 小結(jié)在程序中要跳出多層語句只能用goto語句實(shí)現(xiàn)。用枚舉類型表示各個(gè)終結(jié)符與非終結(jié)符，再用關(guān)聯(lián)容器生成預(yù)測分析表即可方便地實(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#+-*/()i#3.3 分析程序代碼#include <iostream>#include <string>#include <map>#include <stack>using na

14、mespace std;enum symbols / 終結(jié)符號(hào)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

15、'-':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表示不存在

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

17、lets_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_multiplyt

18、s_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

19、= 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;t

20、ablets_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;

21、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();/初始化優(yōu)先關(guān)系表while(1)cou

22、t << "輸入一個(gè)以#結(jié)束的符號(hào)串" << 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 << "×不是給定算符優(yōu)先文法的句子" << endl;break;if(ss.top() = ts_eos && l

23、exer(*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 symbols temp;while(1)temp = ss.top();ss.pop();if(tabless.top()temp =

24、1)break;else/語法錯(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) s's (注：該文法為示例，可更改） (1) sbb (2) bab (3) bb4.2 lr分析表actiongotoab#sb0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r24.3 分析程序代碼#include <iostream>#i

25、nclude <string>#include <map>#include <stack>using namespace std;enum symbols / 終結(jié)符號(hào)ts_a,/ ats_b,/ bts_eos,/ #, '0'ts_invalid,/ 非法字符/非終結(jié)符號(hào)nts_ss,/s'nts_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(

26、c)case 'a':return ts_a;case 'b':return ts_b;case '#':return ts_eos; / 棧底：#終結(jié)符號(hào)default:return ts_invalid;map< enum symbols, map<enum symbols, enum symbols> > table; int main()while(1)cout << "輸入一個(gè)以#結(jié)束的字符串" << endl;const char *p;string str;cin

27、>> str;p = str.c_str();stack<enum symbols> 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