SLR(1)文法分析實驗報告

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

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

3、計語言的文法不能滿足LR(0)文法的條件，即使是描述一個實數(shù)變量說明這樣簡單的文法也不一定是LR(0)文法。因此對于LR(0)規(guī)范族中有沖突的項目集(狀態(tài))用向前查看一個符號的辦法進行處理，以解決沖突。這種辦法將能滿足一些文法的需要，因為只對有沖突的狀態(tài)才向前查看一個符號，以確定做那種動作，因而稱這種分析方法為簡單的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)

4、bool operator < (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)b

5、ool _check(const vector<int>& id, const string str)void make_follow()void make_set()void make_V()void make_cmp(vector<WF>& 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(i

6、nt x)string get_stk(vector<T> stk)string get_shift(WF& temp)void analyse(string src)2.2算法思想SLR文法構造分析表的主要思想：許多沖突性的動作都可能通過考察有關非終結符的FOLLOW集而獲解決。 解決沖突的方法：解決沖突的方法是分析所有含A和B的句型，考察集合FOLLOW(A)和FOLLOW(B)，如果這兩個集合不相交，而且也不包含b，那么當狀態(tài)I面臨輸入符號a時，我們可以使用如下策略：若a=b，則移進。若aFOLLOW(A)，則用產(chǎn)生式A進行歸約；若aFOLLOW(B)，則用產(chǎn)生式B進

7、行歸約；此外，報錯* SLR的基本算法：假定LR(0)規(guī)范族的一個項目集I中含有m個移進項目 A1a11，A2a22，Amamm； 同時含有n個歸約項目 B1，B2，B3，如果集合 a1, am，F(xiàn)OLLOW(B1)，F(xiàn)OLLOW(Bn)兩兩不相交（包括不得有兩個FOLLOW集合有#），則隱含在I中的動作沖突可以通過檢查現(xiàn)行輸入符號a屬于上述n+1個集合中的哪個集合而活的解決： 若a是某個ai，i=1,2,m，則移進。若aFOLLOW(Bi)，i=1,2,m，則用產(chǎn)生式Bi進行歸約；此外，報錯這種沖突的解決方法叫做SLR(1)解決辦法。SLR語法分析表的構造方法： 首先把G拓廣為G，對G構造L

8、R(0)項目集規(guī)范族C和活前綴識別自動機的狀態(tài)轉換函數(shù)GO。函數(shù)ACTION和GOTO可按如下方法構造：若項目Ab屬于Ik，GO(Ik,a)= Ij,a為終結符，置ACTIONk,a為“把狀態(tài)j和符號a移進棧”，簡記為“sj”；若項目A屬于Ik，那么，對任何非終結符a，aFOLLOW(A)，置ACTIONk,a為“用產(chǎn)生式A進行歸約”，簡記為“rj”；其中，假定A為文法G的第j個產(chǎn)生式若項目SS屬于Ik，則置ACTIONk,#為可“接受”，簡記為“acc”；若GO(Ik, A)= Ij，A為非終結符，則置GOTOk, A=j；分析表中凡不能用規(guī)則1至4填入信息的空白格均填上“出錯標志”。 語法

9、分析器的初始狀態(tài)是包含S S的項目集合的狀態(tài) SLR解決的沖突只是移進-規(guī)約沖突和規(guī)約-規(guī)約沖突3主要功能模塊流程圖出錯接受產(chǎn)生Follow合集產(chǎn)生First合集產(chǎn)生項目表輸入分析串WF開始(初始化分析表及棧)3.1主函數(shù)功能流程圖退出程序，并告知用戶分析結果構造LR(0)分析表圖3.1 程序主要流程4系統(tǒng)測試圖4.1 輸入圖4.2 項目表圖4.3 FIRST集圖4.4 FOLLOW集圖4.5 CLOSURE表圖4.6 EDGE表圖4.7 LR(0)表圖4.8 文法分析步驟5 結論LR分析法是一種自下而上進行規(guī)范歸約的語法分析方法。這里L是指從左到右掃描輸入符號串。R是指構造最右推倒的逆工程。

10、這種分析法比遞歸下降分析法、預測分析法和算符優(yōu)先分析法對文法的限制要少得多。附錄 程序源碼清單#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cctype>#include <vector>#include <string>#include <queue>#include <map>#include <set>#include <sstream>

11、#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, const string& s2, int x, int y) left = s1; right = s2; back = x

12、; id = y; bool operator < (const WF& a) const if (left = a.left) return right < a.right; return left < a.left; bool operator = (const WF& a) const return (left = a.left) && (right = a.right); void print() printf("%s->%sn", left.c_str(), right.c_str(); ;class Clo

13、surepublic: vector<WF> element; void print(string str) printf("%-15s%-15sn", "", str.c_str(); for (int i = 0; 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 <

14、; a.element.size(); i+) if (elementi = a.elementi) continue; else return false; return true; ;struct Content int type; int num; string out; Content() type = -1; Content(int a, int b) :type(a), num(b) ;vector<WF> wf;map<string, vector<int> > dic;map<string, vector<int> >

15、 VN_set;map<string, bool> vis;string start = "S"vector<Closure> collection;vector<WF> items;char CH = '$'int goMAXMAX;int toMAX;vector<char> V;bool usedMAX;Content actionMAXMAX;int GotoMAXMAX;map<string, set<char> > first;map<string, set<ch

16、ar> > follow;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(it

17、ems.size(); if (j) toitems.size() - 1 = items.size(); items.push_back(WF(wfi.left, temp, i, items.size(); #ifdef DEBUG puts("-項目表-"); for (int i = 0; i < items.size(); i+) printf("%s->%s back:%d id:%dn", itemsi.left.c_str(), itemsi.right.c_str(), itemsi.back, itemsi.id); pu

18、ts("-");#endifvoid dfs(const string& x) if (visx) return; visx = 1; vector<int>& id = VN_setx; for (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

19、(j, 1); set<char>& temp = firstright.substr(j, 1); set<char>:iterator it = temp.begin(); bool flag = true; for (; it != temp.end(); it+) if (*it = '') flag = false; firstleft.insert(*it); if (flag) break; else firstleft.insert(rightj); break; void make_first() vis.clear(); ma

20、p<string, vector<int> >:iterator it2 = dic.begin(); for (; it2 != dic.end(); it2+) if (visit2->first) continue; else dfs(it2->first);#ifdef DEBUG puts("*FIRST集*"); map<string, set<char> >:iterator it = first.begin(); for (; it != first.end(); it+) printf("

21、;FIRST(%s)=", it->first.c_str(); set<char> & temp = it->second; set<char>:iterator it1 = temp.begin(); bool flag = false; for (; it1 != temp.end(); it1+) if (flag) printf(","); printf("%c", *it1); flag = true; puts(""); #endif void append(cons

22、t string& str1, const string& str2) set<char>& from = followstr1; set<char>& to = followstr2; set<char>:iterator it = from.begin(); for (; it != from.end(); it+) to.insert(*it);bool _check(const vector<int>& id, const string str) for (int i = 0; i < id.

23、size(); i+) int x = idi; if (wfx.right = str) return true; return false;void make_follow() while (true) bool goon = false; map<string, vector<int> >:iterator it2 = VN_set.begin(); for (; it2 != VN_set.end(); it2+) vector<int>& id = it2->second; for (int i = 0; i < id.size

24、(); i+) bool flag = true; WF& tt = wfidi; string& left = tt.left; const string& right = tt.right; for (int j = right.length() - 1; j >= 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, 1).si

25、ze(); 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<char>& from = firstidd; set<char>& to = followright.substr(j, 1); set<char>:iterator it1 =

26、from.begin(); int tx = followright.substr(j, 1).size(); for (; 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.sub

27、str(j, 1).insert(rightk); int tx1 = followright.substr(j, 1).size(); if (tx1 > tx) goon = true; break; else flag = false; if (!goon) break; #ifdef DEBUG puts("*FOLLOW集*"); map<string, set<char> >:iterator it = follow.begin(); for (; it != follow.end(); it+) printf("FOLL

28、OW(%s)=", it->first.c_str(); set<char> & temp = it->second; temp.insert('#'); set<char>:iterator it1 = temp.begin(); bool flag = false; for (; it1 != temp.end(); it1+) if (flag) printf(","); printf("%c", *it1); flag = true; puts(""); #

29、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<WF>& element = temp.element; element.push_back(itemsi); size_t x = 0; for (x = 0; x < str.length(

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

31、t0 = 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<int, Closure> temp; for (size_t j = 0; j < collectioni.element.size(); j+) str

32、ing str = collectioni.elementj.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

33、= 0; k < items.size(); k+) if (itemsk = cmp) ii = k; break; memset(has, 0, sizeof(has); vector<WF>& element = tempy.element; element.push_back(itemsii); hasii = 1; x+; if (x != str.length() - 1) queue<string> q; q.push(str.substr(x + 1, 1); while (!q.empty() string u = q.front();

34、q.pop(); vector<int>& id = dicu; for (size_t j = 0; j < id.size(); j+) int 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<int, Closure>:iterator it = temp.begin(); fo

35、r (; it != temp.end(); it+) collection.push_back(it->second); for (size_t i = 0; i < collection.size(); i+) sort(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 = colle

36、ctionj) collection.erase(collection.begin() + j); #ifdef DEBUG puts("-CLOSURE-"); stringstream sin; for (size_t i = 0; i < collection.size(); i+) sin.clear(); string out; sin << "closure-I" << i; sin >> out; collectioni.print(out); puts("");#endif v

37、oid 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); string& str1 = wfi.right; for (size_t j = 0; j < str1.length(); j+) if (usedstr1

38、j) continue; usedstr1j = 1; V.push_back(str1j); sort(V.begin(), V.end(); V.push_back('#');void make_cmp(vector<WF>& cmp1, int i, char ch) for (size_t j = 0; j < collectioni.element.size(); j+) string str = collectioni.elementj.right; size_t k; for (k = 0; k < str.length(); k+

39、) 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(go); int m = collection.size(); f

40、or (size_t t = 0; t < V.size(); t+) char ch = Vt; for (int i = 0; i < m; i+) vector<WF> 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<WF> 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) cmp2.push_back(WF(collectionj.elementk.left, str, -1