編譯原理課程設計--語法分析器

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：17 大?。?13.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計報告　　2011~2012學年第一學期　課程名稱：編譯原理　課程設計題目：語法分析器　姓名：　系：計算機　專

2、業(yè)：計算機科學與技術　年級：2009計科　學號：　指導教師：　職稱：副教授　　目錄　　1 正則表達式1<p&g

3、t;　　1.1 正則表達式1　　1.2 確定化(化簡)后的狀態(tài)轉換圖1　　1.3 分析程序代碼1　　1.4 程序運行截圖1　　1.5 小結1　　2 LL(1)分析2<

4、;/p>　　2.1 LL(1)文法2　　2.2 LL(1)預測分析表2　　2.3 分析程序代碼2　　2.4 程序運行截圖2　　2.5 小結2

5、3 算符優(yōu)先分析3　　3.1 算符優(yōu)先文法3　　3.2 算符優(yōu)先關系表3　　3.3 分析程序代碼3　　3.4 程序運行截圖3　　3.5 小結3&

6、lt;p>　　4 LR分析4　　4.1 LR文法4　　4.2 LR分析表4　　4.3 分析程序代碼4　　4.4 程序運行截圖4　　4.5 小結4

7、　　參考文獻：4　　1 正則表達式　　1.1 正則表達式　　(a|b)*(aa|bb)(a|b)* (注：該正規(guī)式為示例，可更改）<p&g

8、t;　　1.2 確定化(化簡)后的狀態(tài)轉換圖　　1.3 分析程序代碼　　#include <iostream>　　#include <string>　　#include <map>　　usi

9、ng namespace std;　　//定義一個存儲狀態(tài)轉換的類　　class Statu　　{　　public:　　map<char, Stat

10、u *> MAP;　　};　　int main()　　{　　//定義4個狀態(tài)并初始化各個狀態(tài)間的關系，以及定義一個存儲當前狀態(tài)的變量status

11、Statu A, B, C, D, *status;　　A.MAP['a'] = &B;　　A.MAP['b'] = &C;　　B.MAP['a'] = &D;　　B.MAP['b']

12、 = &C;　　C.MAP['a'] = &B;　　C.MAP['b'] = &D;　　D.MAP['a'] = &D;　　D.MAP['b'] = &D;</p

13、>　　while(1)　　{　　string::size_type size=0;　　string str;　　bool flag = true;

14、　　cout<<"請輸入符合(a|b)*(aa|bb)(a|b)* 的正則表達式"<<endl;　　cin >> str;　　status = &A;//剛開始指向初始狀態(tài)　　const char *ch = str.c_str(

15、);　　while(ch[size])　　{　　if(ch[size] != 'a' && ch[size] != 'b')　　{

16、;　　flag = false;　　break;　　}　　status = status->MAP[ch[size++]];//根據(jù)輸入字符串調(diào)整狀態(tài)

17、　　}　　if(status == &D && flag)//若為終結狀態(tài)則符合此正則表達式　　cout<<"√正確"<<endl;　　else

18、　cout<<"×錯誤"<<endl;　　}　　return 0;　　}　　1.4 程序運行截圖<

19、;/p>　　1.5 小結　　通過定義各個狀態(tài)，并生成各個狀態(tài)間的關系可以方便地表示狀態(tài)轉換圖，使用關聯(lián)容器則可以方便的管理狀態(tài)。　　2 LL(1)分析　　2.1 LL(1)文法　　E→TE'

20、 (注：該文法為示例，可更改）　　E'→+TE'|ε　　T→FT'　　T'→*FT'|ε　　F→

21、(E)|i　　2.2 LL(1)預測分析表　　2.3 分析程序代碼　　#include <iostream>　　#include <string>　　#include <map

22、>　　#include <stack>　　using namespace std;　　enum Symbols　　{　　// 終結符號 Terminal symbols：TS

23、　　TS_I, // i　　TS_PLUS, // +　　TS_MULTIPLY,// *　　TS_L_PARENS, // (　　TS_R_PARENS, // )</p&g

24、t;　　TS_EOS, // #, '\0'　　TS_INVALID, // 非法字符　　//非終結符號 None terminal symbols：NTS　　NTS_E, //E　　NTS_

25、EE,//E'　　NTS_T,//T　　NTS_TT,//T'　　NTS_F//F　　};　　enum Symbols lexer(char c)<

26、;/p>　　{　　switch(c)　　{　　case 'i':　　retu

27、rn TS_I;　　case '+':　　return TS_PLUS;　　case '*':　　return TS_MULTIPLY;&l

28、t;p>　　case '(':　　return TS_L_PARENS;　　case ')':　　return TS_R_PARENS;

29、case '#':　　return TS_EOS; // 棧底：#終結符號　　default:　　return TS_INVALID;　　}

30、　　}　　int main()　　{　　while(1)　　{<p&

31、gt;　　cout << "輸入一個以#結束的字符串" << endl;　　const char *p;　　string str;　　cin >> str;　　p = str.c_str();

32、　　map< enum Symbols, map<enum Symbols, int> > table; 　　stack<enum Symbols> ss;　　//設置詞法分析表　　table[NTS_E][TS_

33、I] = 1;　　table[NTS_E][TS_L_PARENS] = 1;　　table[NTS_EE][TS_PLUS] = 2;　　table[NTS_EE][TS_R_PARENS] = 3;　　table[NTS_EE][TS_EOS] = 3;</p&

34、gt;　　table[NTS_T][TS_I] = 4;　　table[NTS_T][TS_L_PARENS] = 4;　　table[NTS_TT][TS_PLUS] = 6;　　table[NTS_TT][TS_MULTIPLY] = 5;　　t

35、able[NTS_TT][TS_R_PARENS] = 6;　　table[NTS_TT][TS_EOS] = 6;　　table[NTS_F][TS_I] = 8;　　table[NTS_F][TS_L_PARENS] = 7;　　//初始化符號棧&l

36、t;/b>　　ss.push(TS_EOS);　　ss.push(NTS_E);　　while(ss.size() > 0)　　{　　if(lexer(*p) == ss.top(

37、))　　{　　p++;　　ss.pop();　　}　　els

38、e　　{　　switch(table[ss.top()][lexer(*p)])　　{　　case 1://1.E→TE'&l

39、t;b>　　ss.pop();　　ss.push(NTS_EE);　　ss.push(NTS_T);　　break;　　case 2://2.E'→+TE'<p&

40、gt;　　ss.pop();　　ss.push(NTS_EE);　　ss.push(NTS_T);　　ss.push(TS_PLUS);　　break;

41、　case 3://2.E'→ε　　ss.pop();　　break;　　case 4://4.T→FT'　　ss.pop();</p&

42、gt;　　ss.push(NTS_TT);　　ss.push(NTS_F);　　break;　　case 5://5.T'→*FT'　　ss.pop();&l

43、t;/p>　　ss.push(NTS_TT);　　ss.push(NTS_F);　　ss.push(TS_MULTIPLY);　　break;　　case 6://6.T'→ε

44、　　ss.pop();　　break;　　case 7://7.F→(E)　　ss.pop();　　ss.push(TS_R_PARENS

45、);　　ss.push(NTS_E);　　ss.push(TS_L_PARENS);　　break;　　case 8://7.F→i　　ss.pop();

46、　　ss.push(TS_I);　　break;　　default:　　cout << "錯誤的句子" << endl;<

47、p>　　goto END;　　break;　　}　　}　　}</p&g

48、t;　　cout << "正確的句子" << endl;　　END:　　;　　}<b&

49、gt;　　return 0;　　}　　2.4 程序運行截圖　　2.5 小結　　在程序中要跳出多層語句只能用goto語句實現(xiàn)。　　用

50、枚舉類型表示各個終結符與非終結符，再用關聯(lián)容器生成預測分析表即可方便地實現(xiàn)此算法。　　3 算符優(yōu)先分析　　3.1 算符優(yōu)先文法　　E→T | E+T | E-T (注：該文法為示例，可更改）　　T→F | T*F | T/F&l

51、t;/p>　　F→(E) | i　　3.2 算符優(yōu)先關系表　　3.3 分析程序代碼　　#include <iostream>　　#include <string></p&g

52、t;　　#include <map>　　#include <stack>　　using namespace std;　　enum Symbols {　　// 終結符號

53、　　TS_PLUS,// +　　TS_MINUS,// -　　TS_MULTIPLY, // *　　TS_DIVISION,// /　　TS_L_PARENS,// (　　TS_R_PAR

54、ENS, // )　　TS_I,// i　　TS_EOS,// #, '\0'　　TS_INVALID,// 非法字符　　};　　map< enum

55、Symbols, map<enum Symbols, int> > table; 　　enum Symbols lexer(char c)　　{　　switch(c)<b&

56、gt;　　{　　case '+':　　return TS_PLUS;　　case '-':　　return TS_MINUS;

57、;　　case '*':　　return TS_MULTIPLY;　　case '/':　　return TS_DIVISION;<b&

58、gt;　　case '(':　　return TS_L_PARENS;　　case ')':　　return TS_R_PARENS;　　case 'i&#

59、39;:　　return TS_I;　　case '#':　　return TS_EOS; // 棧底：#終結符號　　default:

60、　　return TS_INVALID;　　}　　}　　//初始化算符優(yōu)先關系表，0、1、2分別表示=、〈、〉，-1表示不存在　　void setup()

61、　　{　　table[TS_PLUS][TS_PLUS] = 2;　　table[TS_PLUS][TS_MINUS] = 2;　　table[TS_PLUS][TS_MULTIPLY] = 1;　　table[T

62、S_PLUS][TS_DIVISION] = 1;　　table[TS_PLUS][TS_L_PARENS] = 1;　　table[TS_PLUS][TS_R_PARENS] = 2;　　table[TS_PLUS][TS_I] = 1;　　table[TS_PLUS]

63、[TS_EOS] = 2;　　table[TS_MINUS][TS_PLUS] = 2;　　table[TS_MINUS][TS_MINUS] = 2;　　table[TS_MINUS][TS_MULTIPLY] = 1;　　table[TS_MINUS][TS_DIVI

64、SION] = 1;　　table[TS_MINUS][TS_L_PARENS] = 1;　　table[TS_MINUS][TS_R_PARENS] = 2;　　table[TS_MINUS][TS_I] = 1;　　table[TS_MINUS][TS_EOS] =

65、2;　　table[TS_MULTIPLY][TS_PLUS] = 2;　　table[TS_MULTIPLY][TS_MINUS] = 2;　　table[TS_MULTIPLY][TS_MULTIPLY] = 2;　　table[TS_MULTIPLY][TS_DIV

66、ISION] = 2;　　table[TS_MULTIPLY][TS_L_PARENS] = 1;　　table[TS_MULTIPLY][TS_R_PARENS] = 2;　　table[TS_MULTIPLY][TS_I] = 1;　　table[TS_MULTIPL

67、Y][TS_EOS] = 2;　　table[TS_DIVISION][TS_PLUS] = 2;　　table[TS_DIVISION][TS_MINUS] = 2;　　table[TS_DIVISION][TS_MULTIPLY] = 2;　　table[TS_DIV

68、ISION][TS_DIVISION] = 2;　　table[TS_DIVISION][TS_L_PARENS] = 1;　　table[TS_DIVISION][TS_R_PARENS] = 2;　　table[TS_DIVISION][TS_I] = 1;　　tab

69、le[TS_DIVISION][TS_EOS] = 2;　　table[TS_L_PARENS][TS_PLUS] = 1;　　table[TS_L_PARENS][TS_MINUS] = 1;　　table[TS_L_PARENS][TS_MULTIPLY] = 1;

70、　table[TS_L_PARENS][TS_DIVISION] = 1;　　table[TS_L_PARENS][TS_L_PARENS] = 1;　　table[TS_L_PARENS][TS_R_PARENS] = 0;　　table[TS_L_PARENS][TS_I] = 1;&

71、lt;p>　　table[TS_L_PARENS][TS_EOS] = -1;　　table[TS_R_PARENS][TS_PLUS] = 2;　　table[TS_R_PARENS][TS_MINUS] = 2;　　table[TS_R_PARENS][TS_MULTIPLY] = 2;</p&g

72、t;　　table[TS_R_PARENS][TS_DIVISION] = 2;　　table[TS_R_PARENS][TS_L_PARENS] = -1;　　table[TS_R_PARENS][TS_R_PARENS] = 2;　　table[TS_R_PARENS][TS_I] =

73、-1;　　table[TS_R_PARENS][TS_EOS] = 2;　　table[TS_I][TS_PLUS] = 2;　　table[TS_I][TS_MINUS] = 2;　　table[TS_I][TS_MULTIPLY] = 2;&l

74、t;p>　　table[TS_I][TS_DIVISION] = 2;　　table[TS_I][TS_L_PARENS] = -1;　　table[TS_I][TS_R_PARENS] = 2;　　table[TS_I][TS_I] = -1;　　table[TS

75、_I][TS_EOS] = 2;　　table[TS_EOS][TS_PLUS] = 1;　　table[TS_EOS][TS_MINUS] = 1;　　table[TS_EOS][TS_MULTIPLY] = 1;　　table[TS_EOS][TS_DIVISION]

76、 = 1;　　table[TS_EOS][TS_L_PARENS] = 1;　　table[TS_EOS][TS_R_PARENS] = -1;　　table[TS_EOS][TS_I] = 1;　　table[TS_EOS][TS_EOS] = 0;

77、　　}　　int main()　　{　　setup();//初始化優(yōu)先關系表　　while(1)

78、;　　{　　cout << "輸入一個以#結束的符號串" << endl;　　const char *p;　　string str;　　cin >> str;

79、　　p = str.c_str();　　stack<enum Symbols> ss;　　ss.push(TS_EOS);　　while(1)　　{</p&

80、gt;　　if(lexer(*p) == TS_INVALID)//讀取到不在集合中的非法字符　　{　　cout << "×不是給定算符優(yōu)先文法的句子" << endl;　　brea

81、k;　　}　　if(ss.top() == TS_EOS && lexer(*p) == TS_EOS)//成功規(guī)約　　{　　cout << &qu

82、ot;√是給定算符優(yōu)先文法的句子" << endl;　　break;　　}　　else　　{<

83、;/p>　　if(table[ss.top()][lexer(*p)] == 1 || table[ss.top()][lexer(*p)] == 0)　　{　　//繼續(xù)讀入字符，暫不規(guī)約　　ss.push(lexer(*p));

84、;　　++p;　　}　　else if(table[ss.top()][lexer(*p)] == 2) //符合規(guī)約要求，開始規(guī)約　　{

85、;　　enum Symbols temp;　　while(1)　　{　　temp = ss.top();　　ss.pop();<

86、p>　　if(table[ss.top()][temp] == 1)　　break;　　}　　}　　else//語法錯誤<

87、p>　　{　　cout << "×不是給定算符優(yōu)先文法的句子" << endl;　　break;　　}<p&g

88、t;　　}　　}　　}　　return 0;　　}<

89、p>　　3.4 程序運行截圖　　3.5 小結　　此方法初始化優(yōu)先關系法顯得有點繁瑣，有待改進。　　4 LR分析　　4.1 LR文法</p&

90、gt;　　(0) S'→S (注：該文法為示例，可更改）　　(1) S→BB　　(2) B→aB　　(3) B→b　　4.2

91、 LR分析表　　4.3 分析程序代碼　　#include <iostream>　　#include <string>　　#include <map>　　#include <stack&g

92、t;　　using namespace std;　　enum Symbols {　　// 終結符號　　TS_A,// A　　TS_B,// B<p&g

93、t;　　TS_EOS,// #, '\0'　　TS_INVALID,// 非法字符　　//非終結符號　　NTS_SS,//S'　　NTS_S,//S

94、;　　NTS_B,//B　　//狀態(tài)status　　S_0,　　S_1,　　S_2,　　S_

95、3,　　S_4,　　S_5,　　S_6,　　S_ACC,&

96、lt;b>　　//GOGO　　G_S,　　G_B,　　//規(guī)約式　　R_1,

97、;　　R_2,　　R_3,　　};　　enum Symbols lexer(char c)　　{&

98、lt;/p>　　switch(c)　　{　　case 'a':　　return TS_A;　　c

99、ase 'b':　　return TS_B;　　case '#':　　return TS_EOS; // 棧底：#終結符號　　default:&

100、lt;/p>　　return TS_INVALID;　　}　　}　　map< enum Symbols, map<enum Symbols, enum Symbols> > table;

101、 　　int main()　　{　　while(1)　　{　　cout << "輸入一個以#結

102、束的字符串" << endl;　　const char *p;　　string str;　　cin >> str;　　p = str.c_str();　　stack<enum Symbols

103、> status;　　//設置LR分析表　　table[S_0][TS_A] = S_3;　　table[S_0][TS_B] = S_4;　　table[S_0][NTS_S] = S_1;<p&

104、gt;　　table[S_0][NTS_B] = S_2;　　table[S_1][TS_EOS] = S_ACC;　　table[S_2][TS_A] = S_3;　　table[S_2][TS_B] = S_4;　　table[S_2][NTS_B] = S_5;&l

105、t;/p>　　table[S_3][TS_A] = S_3;　　table[S_3][TS_B] = S_4;　　table[S_3][NTS_B] = S_6;　　table[S_4][TS_A] = R_3;　　table[S_4][TS_

106、B] = R_3;　　table[S_4][TS_EOS] = R_3;　　table[S_5][TS_A] = R_1;　　table[S_5][TS_B] = R_1;　　table[S_5][TS_EOS] = R_1;

107、table[S_6][TS_A] = R_2;　　table[S_6][TS_B] = R_2;　　table[S_6][TS_EOS] = R_2;　　//初始化狀態(tài)棧　　status.push(S_0);&

108、lt;p>　　while(1)　　{　　if(lexer(*p) == TS_INVALID)　　{　　cout << "Fals

109、e" << endl;　　goto END;　　break;　　}　　switch(table[status.top()][lexer(

110、*p)])　　{　　case S_0:　　case S_1:　　case S_2:<p&g

111、t;　　case S_3:　　case S_4:　　case S_5:　　case S_6:　　status.push(

112、table[status.top()][lexer(*p)]);　　++p;　　break;　　case S_ACC:　　cout << "√是給定LR文法的句子"

113、 << endl;　　goto END;　　break;　　case R_1:　　status.pop();<p&g

114、t;　　status.pop();　　status.push(table[status.top()][NTS_S]);　　break;　　case R_2:　　status.pop();</

115、p>　　status.pop();　　status.push(table[status.top()][NTS_B]);　　break;　　case R_3:　　stat

116、us.pop();　　status.push(table[status.top()][NTS_B]);　　break;　　default:　　cout << "×不

117、是給定LR文法的句子" << endl;　　goto END;　　break;　　}　　}<

118、/p>　　END:　　;　　}　　return 0;　　}</b&g

119、t;　　4.4 程序運行截圖　　4.5 小結　　此LR分析程序的設計的數(shù)據(jù)結構與前面的類似，主要在識別算法上修改便可達到預期目的。　　參考文獻：　　[

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

編譯原理課程設計--語法分析器

文檔簡介

溫馨提示

最新文檔

評論

編譯原理課程設計--語法分析器

文檔簡介

溫馨提示

最新文檔

評論

免費下載