计算first集follow集

编辑原理实验报告实验名称计算first集合和follow集合实验时间2016年6月8日医院计算机科学技术类计算机科学技术(1)类学号姓氏1.测试目的：输入：所有上下文无关语法。输出：输入的上下文无关语法所有非终结器的first集合和follow集合。实验原理：当设定语法g s=(VN，VT，p，s)时，第一组字元为：First ()=a | a ，a-vt，-v * 。 ，-first()拉面。定义表明，FIRST()表示符号字符串可以派生的所有符号字符串中字符串开头的结束符号集。因此，FIRST组也称为第一组符号。=x1x2.xn，FIRST()可以按以下方式获得：First ()=，I=1；(1)对于Xivt，为Xifirst()；(2)对于XiVN；如果是FIRST(xi)，则FIRST(Xi)如果是first (Xi)，则first(Xi)-first()；(3) I=I 1，Xi/vt，(I=2，3，重复(1)、(2)，直到、n)或Xi/VN、FIRST(xi)或in为止。如A，语法中有产生的时候，要知道哪些符号可以合法出现在非终结符a之后，才能知道选择a 产生式。由这些合法出现在非终结器a后面的符号组成的集合称为FOLLOW集合。下面提供了语法的FOLLOW集的定义。设定语法g s=(VN，VT，p，s)的步骤Follow (a)=a | s.aa.a-vt 。s.a，# 871 follow (a)。定义表明，在语法GS的所有语句模式中，FOLLOW(A)表示紧跟在终结器A之后的终结器的集合。可以通过以下方式获取FOLLOW集：(1)语法GS的起始符号S的# 871 follow(S)；(2)如果语法GS有BxAy等规则，其中x，y/v *，则first(y)-(3)如果语法GS中有BxA之类的规则或BxAy之类的规则，其中x，y/v *是follow(B)forst(y)实验代码和结果：输入格式：每行输入一个生产表达式。左右中间的替换为空间。非终结器等于大写表示为空输入到文件结尾或以0结尾。编译原理5.6的典型示例和答案示例(第96页):#include#include#include#include#includeUsing namespace STDchar l；字串r；Multimap sentence/保存内部版本Multimap senRever/反转生产布景；布景。/非终结器集合MaptoEmpty/非终止符可以为空吗Bool flagfir设置；/存储单个元素的first集Set follow/存储单个元素的follow集Vector rightSide/右侧Char BeginBool capL(char c) /字符是否为大写If(c=Z c=A)Return trueReturn falseBool CapLString(string s) /大写字符串for(int I=0)；I :3360 iterator miter=sentence . find(ch)；int CNT=sentence . count(ch)；for(int I=0)；I second=)Return trueElse if (capl string (miter-second)字串s(次要)；Bool flag2=truefor(int j=0)；J First)/查找单个元素的First集multimap 33603360 iterator imul=sentence . find(ch)；If(imul=sentence.end()Returnint sum=sentence . count(imul-first)；for(int I=0)；isecond)；for(int j=0)；j=0；I-)If(ch=si)Return trueIf(！capl(sI)| | toemptysI=false)Return falseReturn falseVoid get FOLLOW (charch，set follow)/查找单个元素的FOLLOW集If(！CapL(ch)Returnfor(vector 33603360 iterator ITER=right side . begin()；Iter！=right side . end()；Iter) for(int I=0)；I(*iter)。size()；I) If(ch=(*iter)i I！=(*iter)。size()-1) If(！capl(* ITER)I 1)follow . insert(* ITER)I 1)；Elseget first(* ITER)I 1，follow)；If (ch=(* ITER) I I=(* ITER)。判断是否为size ()-1) /右侧的最后一个非终结器follow #Follow.insert(#)Else if (ch=(* ITER) I I (* ITER)。size ()-1) /不是最后一个，但之后都是非结束符，因此为null follow #Bool flag1=truefor(int j=I 1；J(*iter)。size()；J) _If(！capl(* ITER)j| | toempty(* ITER)j=false)Flag1=falseIf(！capl(* ITER)j)follow . insert(* ITER)j)；BreakIf(flag1=true) Follow.insert(#)If(isLast(*iter，ch) /ch是*iter的最后一个符号(直接或间接)int n=se NR never . count(* ITER)；multimap 33603360 iterator miter=senr . find(* ITER)；for(int I=0)；Isecond！=ch)GetFollow(mIter-second，follow)；Int main()int CNT=0；While(cinlr) If(cnt=0) begin=l；CntIf(l=0)BreakSentence.insert(make_pair(l，r)；/表达式Senr.insert (make _ pair (r，l)；ter . insert(l)；/非终结器集合(左)right side . push _ back(r)；/右侧集合for(set 336360 iterator siter=ter . begin()；SIter！=ter . end()；SIter) /确定是否有非终结器-。If (isto empty (* siter)ToEmpty* sIter=true；ElseToEmpty* sIter=false；for(set 33603360 iterator ITER=ter . begin()；Iter！=ter . end()；Iter) Flag=falseCout*iter第一集：；冷杉。clear()；Getfirst (* ITER，杉树)；For (set :3360iterator