《编译原理》课程设计报告
—SLR(1)分析的实现
学 院 计算机科学与技术
专 业 计算机科学与技术奉献英文
学 号
学 生 姓 名
指导教师姓名
2015年12月 26日
1． 设计的目的与内容 1
1.1课程设计的目的 1
1.2设计内容 1
1.3设计要求 1
1.4理论基础 1
2算法的基本思想 2
2.1主要功能函数 2
2.2算法思想 3
SLR文法构造分析表的主要思想： 3
解决冲突的方法： 3
SLR语法分析表的构造方法： 4
3主要功能模块流程图 5
3.1主函数功能流程图 5
4系统测试 6
5 结论 11
附录 程序源码清单 12
1．设计的目的与内容
1.1课程设计的目的
编译原理课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。
●进一步巩固和复习编译原理的基础知识。
●培养学生结构化程序、模块化程序设计的方法和能力。
●提高学生对于编程语言原理的理解能力。
●加深学生对于编程语言实现手段的印象。
1.2设计内容
构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
1.3设计要求
1)SLR(1)分析表的生成可以选择编程序生成，也可选择手动生成；
2)程序要求要配合适当的错误处理机制；
3)要打印句子的文法分析过程。
数学基础知识1.4理论基础
由于大多数适用的程序设计语言的文法不能满足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, 4笔画的字有哪些const string& s2, int x, int y)
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<int>& id, const string str)
void make_follow()
void make_t()
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(int x)
string get_stk(vector<T> stk)
string get_shift(WF& temp)
void analy(string src)
2.2算法思想
SLR文法构造分析表的主要思想：
许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决。
解决冲突的方法：
解决冲突的方法是分析所有含A和B的句型，考察集合FOLLOW(A)和FOLLOW(B)，如果这两个集合不相交，而且也不包含b，那么当状态I面临输入符号a时，我们可以使用如下策略：
若a=b，则移进。
若a∈FOLLOW(A)，则用产生式A→α进行归约；
若a∈FOLLOW(B)，则用产生式B→α进行归约；
此外，报错* SLR的基本算法：
假定LR(0)规范族的一个项目集I中含有m个移进项目
A1→α•a1β1，A2→α•a2β2，…，Am→α•amβm；
同时含有n个归约项目
B1→α•，B2→α•，…，B3→α•，
如果集合{ a1,…, am}，FOLLOW(B1)，…，FOLLOW(Bn)两两不相交（包括不得有两个FOLLOW集合有#），则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1个集合中的哪个集合而活的解决：
若a是某个ai，i=1,2,…,m，则移进。
若a∈FOLLOW(Bi)，i=1,2,…,m，则用产生式Bi→α进行归约；
此外，报错
这种冲突的解决方法叫做SLR(1)解决办法。
SLR语法分析表的构造方法：
首先把G拓广为G’，对G’构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO。函数ACTION和GOTO可按如下方法构造：
若项目A→α•bβ属于Ik，GO(Ik,a)= Ij,a为终结符，置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”；
若项目A→α•属于Ik，那么，对任何非终结符a，a∈FOLLOW(A)，置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”；其中，假定A→α为文法G’的第j个产生式
若项目S’→S•属于Ik，则置ACTION[k,#]为可“接受”，简记为“acc”；
若GO(Ik, A)= Ij，A为非终结符，则置GOTO[k, A]=j；
分析表中凡不能用规则1至4填入信息的空白格均填上“出错标志”。
语法分析器的初始状态是包含S’ →•S的项目集合的状态 盘扣型脚手架
SLR解决的冲突只是移进-规约冲突和规约-规约冲突
3主要功能模块流程图
3.1主函数功能流程图
图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是指构造最右推倒的逆工程。
这种分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。
