《SLR(1)文法分析实验报告.doc》由会员分享，可在线阅读，更多相关《SLR(1)文法分析实验报告.doc（35页珍藏版）》请在三一文库上搜索。
1、.编译原理课程设计报告SLR(1)分析的实现学 院 计算机科学与技术 专 业 计算机科学与技术 学 号 学 生 姓 名 指导教师姓名 2015年12月 26日精品.目录1设计的目的与内容11.1课程设计的目的11.2设计内容11.3设计要求11.4理论基础12算法的基本思想22.1主要功能函数22.2算法思想3SLR文法构造分析表的主要思想：3解决冲突的方法：3SLR语法分析表的构造方法：43主要功能模块流程图53.1主函数功能流程图54系统测试65 结论11附录 程序源码清单12精品.1 设计的目的与内容1.1课程设计的目的编译原理课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手
2、又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 l 进一步巩固和复习编译原理的基础知识。 l 培养学生结构化程序、模块化程序设计的方法和能力。 l 提高学生对于编程语言原理的理解能力。l 加深学生对于编程语言实现手段的印象。1.2设计内容构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。1.3设计要求1) SLR(1)分析表的生成可以选择编程序生成，也可选择手动生成；2) 程序要求要配合适当的错误处理机制；3) 要打印句子的文法分析过程。1.4理论基础由于大多
3、数适用的程序设计语言的文法不能满足LR(0)文法的条件，即使是描述一个实数变量说明这样简单的文法也不一定是LR(0)文法。因此对于LR(0)规范族中有冲突的项目集(状态)用向前查看一个符号的办法进行处理，以解决冲突。这种办法将能满足一些文法的需要，因为只对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称这种分析方法为简单的LR(1)分析法，用SLR(1)表示。精品.2算法的基本思想2.1主要功能函数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)bool _check(const vector& id
5、, const string 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
6、)void analyse(string src)精品.2.2算法思想SLR文法构造分析表的主要思想：许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决。 解决冲突的方法：解决冲突的方法是分析所有含A和B的句型，考察集合FOLLOW(A)和FOLLOW(B)，如果这两个集合不相交，而且也不包含b，那么当状态I面临输入符号a时，我们可以使用如下策略：若a=b，则移进。若aFOLLOW(A)，则用产生式A进行归约；若aFOLLOW(B)，则用产生式B进行归约；此外，报错* SLR的基本算法：假定LR(0)规范族的一个项目集I中含有m个移进项目 A1a11，A2a22，Amamm；
7、同时含有n个归约项目 B1，B2，B3，如果集合 a1, am，FOLLOW(B1)，FOLLOW(Bn)两两不相交（包括不得有两个FOLLOW集合有#），则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1个集合中的哪个集合而活的解决： 若a是某个ai，i=1,2,m，则移进。若aFOLLOW(Bi)，i=1,2,m，则用产生式Bi进行归约；此外，报错这种冲突的解决方法叫做SLR(1)解决办法。精品.SLR语法分析表的构造方法： 首先把G拓广为G，对G构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO。函数ACTION和GOTO可按如下方法构造：若项目Ab属于Ik，G
8、O(Ik,a)= Ij,a为终结符，置ACTIONk,a为“把状态j和符号a移进栈”，简记为“sj”；若项目A属于Ik，那么，对任何非终结符a，aFOLLOW(A)，置ACTIONk,a为“用产生式A进行归约”，简记为“rj”；其中，假定A为文法G的第j个产生式若项目SS属于Ik，则置ACTIONk,#为可“接受”，简记为“acc”；若GO(Ik, A)= Ij，A为非终结符，则置GOTOk, A=j；分析表中凡不能用规则1至4填入信息的空白格均填上“出错标志”。 语法分析器的初始状态是包含S S的项目集合的状态 SLR解决的冲突只是移进-规约冲突和规约-规约冲突3主要功能模块流程图出错接受产
9、生Follow合集产生First合集产生项目表输入分析串WF开始(初始化分析表及栈)3.1主函数功能流程图精品.退出程序，并告知用户分析结果构造LR(0)分析表图3.1 程序主要流程4系统测试精品.图4.1 输入图4.2 项目表图4.3 FIRST集图4.4 FOLLOW集精品.图4.5 CLOSURE表精品.图4.6 EDGE表图4.7 LR(0)表精品.图4.8 文法分析步骤精品.5 结论LR分析法是一种自下而上进行规范归约的语法分析方法。这里L是指从左到右扫描输入符号串。R是指构造最右推倒的逆工程。这种分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。精品.附录 程
10、序源码清单#include #include #include #include #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 =
11、 x; id = y; WF(const string& s1, const 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(%-
12、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 a.element.size(); i+) if (elementi = a.elementi) continue; else return false; return true; ;struct Cont
13、ent int type; int num; string out; Content() 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 GotoMA
14、XMAX;mapstring, set first;mapstring, set 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.le
15、ft.push_back(items.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 %s back:%d id:%dn, itemsi.left.c_str(), itemsi.right.c_str(), itemsi.back, itemsi.id); puts(-);#endifvoid dfs(const string& x)精品. if (v
16、isx) return; visx = 1; vector& 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(j, 1); set& temp = firstright.substr(j, 1); set:iterator it = temp.begin(); bool flag = tru
17、e; 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(); mapstring, vector :iterator it2 = dic.begin(); for (; it2 != dic.end(); it2+) if (visit2-first) continue; else dfs(it2-first);#if
18、def DEBUG puts(*FIRST集*); mapstring, set :iterator it = 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; p
19、uts(); #endif void append(const string& str1, const 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
20、= str) return true; return false;void make_follow() while (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(); appe
21、nd(left, right.substr(j, 1); int tx1 = followright.substr(j, 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 =
22、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.substr(j, 1).insert(rightk); i
23、nt tx1 = followright.substr(j, 1).size(); if (tx1 tx) goon = 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(#);
24、 set:iterator it1 = temp.begin(); bool flag = false; for (; it1 != 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.rig
25、ht; vector& element = temp.element; element.push_back(itemsi); size_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
26、; 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); collection.push_back(temp); for (size_t i = 0; i collection.size(); i+) map temp; for (size_t j =
27、 0; j collectioni.element.size(); j+) string 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.element
28、j.left, str, -1, -1); for (size_t k = 0; k items.size(); k+) if (itemsk = 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+) 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);