1、編譯原理課程設(shè)計(jì)報(bào)告slr(1)分析的實(shí)現(xiàn)學(xué) 院 計(jì)算機(jī)科學(xué)與技術(shù) 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué) 號(hào) 學(xué) 生 姓 名 指導(dǎo)教師姓名 2015年12月 26日目錄1設(shè)計(jì)的目的與內(nèi)容11.1課程設(shè)計(jì)的目的11.2設(shè)計(jì)內(nèi)容11.3設(shè)計(jì)要求11.4理論基礎(chǔ)12算法的基本思想22.1主要功能函數(shù)22.2算法思想3slr文法構(gòu)造分析表的主要思想：3解決沖突的方法：3slr語法分析表的構(gòu)造方法：43主要功能模塊流程圖53.1主函數(shù)功能流程圖54系統(tǒng)測試65 結(jié)論11附錄 程序源碼清單121 設(shè)計(jì)的目的與內(nèi)容1.1課程設(shè)計(jì)的目的編譯原理課程設(shè)計(jì)是計(jì)算機(jī)專業(yè)重要的教學(xué)環(huán)節(jié)，它為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，將課本

2、上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來，獨(dú)立分析和解決實(shí)際問題的機(jī)會(huì)。 l 進(jìn)一步鞏固和復(fù)習(xí)編譯原理的基礎(chǔ)知識(shí)。 l 培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。 l 提高學(xué)生對(duì)于編程語言原理的理解能力。l 加深學(xué)生對(duì)于編程語言實(shí)現(xiàn)手段的印象。1.2設(shè)計(jì)內(nèi)容構(gòu)造lr(1)分析程序，利用它進(jìn)行語法分析，判斷給出的符號(hào)串是否為該文法識(shí)別的句子，了解lr（k）分析方法是嚴(yán)格的從左向右掃描，和自底向上的語法分析方法。1.3設(shè)計(jì)要求1) slr(1)分析表的生成可以選擇編程序生成，也可選擇手動(dòng)生成；2) 程序要求要配合適當(dāng)?shù)腻e(cuò)誤處理機(jī)制；3) 要打印句子的文法分析過程。1.4理論基礎(chǔ)由于大多數(shù)適用的程序設(shè)

3、計(jì)語言的文法不能滿足lr(0)文法的條件，即使是描述一個(gè)實(shí)數(shù)變量說明這樣簡單的文法也不一定是lr(0)文法。因此對(duì)于lr(0)規(guī)范族中有沖突的項(xiàng)目集(狀態(tài))用向前查看一個(gè)符號(hào)的辦法進(jìn)行處理，以解決沖突。這種辦法將能滿足一些文法的需要，因?yàn)橹粚?duì)有沖突的狀態(tài)才向前查看一個(gè)符號(hào)，以確定做那種動(dòng)作，因而稱這種分析方法為簡單的lr(1)分析法，用slr(1)表示。2算法的基本思想2.1主要功能函數(shù)class wf wf(char s1, char s2, int x, int y) wf(const string& s1, const string& s2, int x, int y) bool ope

4、rator (const wf& a) const bool operator = (const wf& a) const void print();class closure void print(string str) bool operator = (const closure& a) const;void make_item()void dfs(const string& x)void make_first()void append(const string& str1, const string& str2)bool _check(const vector& id, const st

5、ring str)void make_follow()void make_set()void make_v()void make_cmp(vector& cmp1, int i, char ch)void make_go()void make_table()void print(string s1, string s2, string s3, string s4, string s5, string s6, string s7)string get_steps(int x)string get_stk(vector stk)string get_shift(wf& temp)void anal

6、yse(string src)2.2算法思想slr文法構(gòu)造分析表的主要思想：許多沖突性的動(dòng)作都可能通過考察有關(guān)非終結(jié)符的follow集而獲解決。 解決沖突的方法：解決沖突的方法是分析所有含a和b的句型，考察集合follow(a)和follow(b)，如果這兩個(gè)集合不相交，而且也不包含b，那么當(dāng)狀態(tài)i面臨輸入符號(hào)a時(shí)，我們可以使用如下策略：若a=b，則移進(jìn)。若afollow(a)，則用產(chǎn)生式a進(jìn)行歸約；若afollow(b)，則用產(chǎn)生式b進(jìn)行歸約；此外，報(bào)錯(cuò)* slr的基本算法：假定lr(0)規(guī)范族的一個(gè)項(xiàng)目集i中含有m個(gè)移進(jìn)項(xiàng)目 a1a11，a2a22，amamm； 同時(shí)含有n個(gè)歸約項(xiàng)目 b1

7、，b2，b3，如果集合 a1, am，follow(b1)，follow(bn)兩兩不相交（包括不得有兩個(gè)follow集合有#），則隱含在i中的動(dòng)作沖突可以通過檢查現(xiàn)行輸入符號(hào)a屬于上述n+1個(gè)集合中的哪個(gè)集合而活的解決： 若a是某個(gè)ai，i=1,2,m，則移進(jìn)。若afollow(bi)，i=1,2,m，則用產(chǎn)生式bi進(jìn)行歸約；此外，報(bào)錯(cuò)這種沖突的解決方法叫做slr(1)解決辦法。slr語法分析表的構(gòu)造方法： 首先把g拓廣為g，對(duì)g構(gòu)造lr(0)項(xiàng)目集規(guī)范族c和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)go。函數(shù)action和goto可按如下方法構(gòu)造：若項(xiàng)目ab屬于ik，go(ik,a)= ij,a為終結(jié)

8、符，置actionk,a為“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡記為“sj”；若項(xiàng)目a屬于ik，那么，對(duì)任何非終結(jié)符a，afollow(a)，置actionk,a為“用產(chǎn)生式a進(jìn)行歸約”，簡記為“rj”；其中，假定a為文法g的第j個(gè)產(chǎn)生式若項(xiàng)目ss屬于ik，則置actionk,#為可“接受”，簡記為“acc”；若go(ik, a)= ij，a為非終結(jié)符，則置gotok, a=j；分析表中凡不能用規(guī)則1至4填入信息的空白格均填上“出錯(cuò)標(biāo)志”。 語法分析器的初始狀態(tài)是包含s s的項(xiàng)目集合的狀態(tài) slr解決的沖突只是移進(jìn)-規(guī)約沖突和規(guī)約-規(guī)約沖突3主要功能模塊流程圖出錯(cuò)接受產(chǎn)生follow合集產(chǎn)生first

9、合集產(chǎn)生項(xiàng)目表輸入分析串wf開始(初始化分析表及棧)3.1主函數(shù)功能流程圖退出程序，并告知用戶分析結(jié)果構(gòu)造lr(0)分析表圖3.1 程序主要流程4系統(tǒng)測試圖4.1 輸入圖4.2 項(xiàng)目表圖4.3 first集圖4.4 follow集圖4.5 closure表圖4.6 edge表圖4.7 lr(0)表圖4.8 文法分析步驟5 結(jié)論lr分析法是一種自下而上進(jìn)行規(guī)范歸約的語法分析方法。這里l是指從左到右掃描輸入符號(hào)串。r是指構(gòu)造最右推倒的逆工程。這種分析法比遞歸下降分析法、預(yù)測分析法和算符優(yōu)先分析法對(duì)文法的限制要少得多。附錄 程序源碼清單#include #include #include #incl

10、ude #include #include #include #include #include #include #include #define max 507/#define debugusing namespace std;#pragma warning(disable:4996)class wfpublic: string left, right; int back; int id; wf(char s1, char s2, int x, int y) left = s1; right = s2; back = x; id = y; wf(const string& s1, cons

11、t string& s2, int x, int y) left = s1; right = s2; back = x; id = y; bool operator (const wf& a) const if (left = a.left) return right a.right; return left %sn, left.c_str(), right.c_str(); ;class closurepublic: vector element; void print(string str) printf(%-15s%-15sn, , str.c_str(); for (int i = 0

12、; i element.size(); i+) elementi.print(); bool operator = (const closure& a) const if (a.element.size() != element.size() return false; for (int i = 0; i a.element.size(); i+) if (elementi = a.elementi) continue; else return false; return true; ;struct content int type; int num; string out; content(

13、) type = -1; content(int a, int b) :type(a), num(b) ;vector wf;mapstring, vector dic;mapstring, vector vn_set;map vis;string start = s;vector collection;vector items;char ch = $;int gomaxmax;int tomax;vector v;bool usedmax;content actionmaxmax;int gotomaxmax;mapstring, set first;mapstring, set follo

14、w;void make_item() memset(to, -1, sizeof(-1); for (int i = 0; i wf.size(); i+) vn_setwfi.left.push_back(i); for (int i = 0; i wf.size(); i+) for (int j = 0; j = wfi.right.length(); j+) string temp = wfi.right; temp.insert(temp.begin() + j, ch); dicwfi.left.push_back(items.size(); if (j) toitems.size

15、() - 1 = items.size(); items.push_back(wf(wfi.left, temp, i, items.size(); #ifdef debug puts(-項(xiàng)目表-); for (int i = 0; i %s back:%d id:%dn, itemsi.left.c_str(), itemsi.right.c_str(), itemsi.back, itemsi.id); puts(-);#endifvoid dfs(const string& x) if (visx) return; visx = 1; vector& id = vn_setx; for

16、(int i = 0; i id.size(); i+) string& left = wfidi.left; string& right = wfidi.right; for (int j = 0; j right.length(); j+) if (isupper(rightj) dfs(right.substr(j, 1); set& temp = firstright.substr(j, 1); set:iterator it = temp.begin(); bool flag = true; for (; it != temp.end(); it+) if (*it = ) flag

17、 = false; firstleft.insert(*it); if (flag) break; else firstleft.insert(rightj); break; void make_first() vis.clear(); mapstring, vector :iterator it2 = dic.begin(); for (; it2 != dic.end(); it2+) if (visit2-first) continue; else dfs(it2-first);#ifdef debug puts(*first集*); mapstring, set :iterator i

18、t = first.begin(); for (; it != first.end(); it+) printf(first(%s)=, it-first.c_str(); set & temp = it-second; set:iterator it1 = temp.begin(); bool flag = false; for (; it1 != temp.end(); it1+) if (flag) printf(,); printf(%c, *it1); flag = true; puts(); #endif void append(const string& str1, const

19、string& str2) set& from = followstr1; set& to = followstr2; set:iterator it = from.begin(); for (; it != from.end(); it+) to.insert(*it);bool _check(const vector& id, const string str) for (int i = 0; i id.size(); i+) int x = idi; if (wfx.right = str) return true; return false;void make_follow() whi

20、le (true) bool goon = false; mapstring, vector :iterator it2 = vn_set.begin(); for (; it2 != vn_set.end(); it2+) vector& id = it2-second; for (int i = 0; i = 0; j-) if (isupper(rightj) if (flag) int tx = followright.substr(j, 1).size(); append(left, right.substr(j, 1); int tx1 = followright.substr(j

21、, 1).size(); if (tx1 tx) goon = true; if (_check(id, ) flag = false; for (int k = j + 1; k right.length(); k+) if (isupper(rightk) string idd = right.substr(k, 1); set& from = firstidd; set& to = followright.substr(j, 1); set:iterator it1 = from.begin(); int tx = followright.substr(j, 1).size(); for

22、 (; it1 != from.end(); it1+) if (*it1 != ) to.insert(*it1); int tx1 = followright.substr(j, 1).size(); if (tx1 tx) goon = true; if (_check(id, ) break; else int tx = followright.substr(j, 1).size(); followright.substr(j, 1).insert(rightk); int tx1 = followright.substr(j, 1).size(); if (tx1 tx) goon

23、= true; break; else flag = false; if (!goon) break; #ifdef debug puts(*follow集*); mapstring, set :iterator it = follow.begin(); for (; it != follow.end(); it+) printf(follow(%s)=, it-first.c_str(); set & temp = it-second; temp.insert(#); set:iterator it1 = temp.begin(); bool flag = false; for (; it1

24、 != temp.end(); it1+) if (flag) printf(,); printf(%c, *it1); flag = true; puts(); #endifvoid make_set() bool hasmax; for (int i = 0; i items.size(); i+) if (itemsi.left0 = s & itemsi.right0 = ch) closure temp; string& str = itemsi.right; vector& element = temp.element; element.push_back(itemsi); siz

25、e_t x = 0; for (x = 0; x str.length(); x+) if (strx = ch) break; memset(has, 0, sizeof(has); hasi = 1; if (x != str.length() - 1) queue q; q.push(str.substr(x + 1, 1); while (!q.empty() string u = q.front(); q.pop(); vector& id = dicu; for (size_t j = 0; j id.size(); j+) int tx = idj; if (itemstx.ri

26、ght0 = ch) if (hastx) continue; hastx = 1; if (isupper(itemstx.right1) q.push(itemstx.right.substr(1, 1); element.push_back(itemstx); collection.push_back(temp); for (size_t i = 0; i collection.size(); i+) map temp; for (size_t j = 0; j collectioni.element.size(); j+) string str = collectioni.elemen

27、tj.right; size_t x = 0; for (; x str.length(); x+) if (strx = ch) break; if (x = str.length() - 1) continue; int y = strx + 1; int ii; str.erase(str.begin() + x); str.insert(str.begin() + x + 1, ch); wf cmp = wf(collectioni.elementj.left, str, -1, -1); for (size_t k = 0; k items.size(); k+) if (item

28、sk = cmp) ii = k; break; memset(has, 0, sizeof(has); vector& element = tempy.element; element.push_back(itemsii); hasii = 1; x+; if (x != str.length() - 1) queue q; q.push(str.substr(x + 1, 1); while (!q.empty() string u = q.front(); q.pop(); vector& id = dicu; for (size_t j = 0; j id.size(); j+) in

29、t tx = idj; if (itemstx.right0 = ch) if (hastx) continue; hastx = 1; if (isupper(itemstx.right1) q.push(itemstx.right.substr(1, 1); element.push_back(itemstx); map:iterator it = temp.begin(); for (; it != temp.end(); it+) collection.push_back(it-second); for (size_t i = 0; i collection.size(); i+) s

30、ort(collectioni.element.begin(), collectioni.element.end(); for (size_t i = 0; i collection.size(); i+) for (size_t j = i + 1; j collection.size(); j+) if (collectioni = collectionj) collection.erase(collection.begin() + j); #ifdef debug puts(-closure-); stringstream sin; for (size_t i = 0; i collec

31、tion.size(); i+) sin.clear(); string out; sin closure-i out; collectioni.print(out); puts();#endif void make_v() memset(used, 0, sizeof(used); for (size_t i = 0; i wf.size(); i+) string& str = wfi.left; for (size_t j = 0; j str.length(); j+) if (usedstrj) continue; usedstrj = 1; v.push_back(strj); s

32、tring& str1 = wfi.right; for (size_t j = 0; j str1.length(); j+) if (usedstr1j) continue; usedstr1j = 1; v.push_back(str1j); sort(v.begin(), v.end(); v.push_back(#);void make_cmp(vector& cmp1, int i, char ch) for (size_t j = 0; j collectioni.element.size(); j+) string str = collectioni.elementj.righ

33、t; size_t k; for (k = 0; k str.length(); k+) if (strk = ch) break; if (k != str.length() - 1 & strk + 1 = ch) str.erase(str.begin() + k); str.insert(str.begin() + k + 1, ch); cmp1.push_back(wf(collectioni.elementj.left, str, -1, -1); sort(cmp1.begin(), cmp1.end();void make_go() memset(go, -1, sizeof

34、(go); int m = collection.size(); for (size_t t = 0; t v.size(); t+) char ch = vt; for (int i = 0; i m; i+) vector cmp1; make_cmp(cmp1, i, ch);#ifdef debug cout cmp1.size() endl;#endif if (cmp1.size() = 0) continue; for (int j = 0; j m; j+) vector cmp2; for (size_t k = 0; k collectionj.element.size(); k+) string& str = collectionj.elementk.right; size_t x; for (x = 0; x str.length(); x+) if (strx = ch) break; if (x & strx - 1 = ch