精华内容
下载资源
问答
  • 编译原理FIRST和FOLLOW求解,让你一学就会!
  • 编译原理first和follow的计算方法

    千次阅读 多人点赞 2019-12-14 17:40:13
    概括下来,计算的时候,first看产生式的左部,follow看产生式的右部。还是用书上的例子好了: E —> TE' E'-> +TE'|ε T -> FT' T'-> *FT'|ε F -> (E)|id 可能会看得不那么清楚。拆开来看好了: E ...

    书上的定义和计算公式(以及解释)属于太长不看系列……这里试着用更简单的方式来进行表述。

    概括下来,计算的时候,first看产生式的左部,follow看产生式的右部;first看第一个,follow看全部。还是用书上的例子好了:

    E —> TE'
    E'-> +TE'|ε
    T -> FT'
    T'-> *FT'|ε
    F -> (E)|id
    

    可能会看得不那么清楚。拆开来看好了:

    E —> TE'
    E'-> +TE'
    E'-> ε
    T -> FT'
    T'-> *FT'
    T'-> ε
    F -> (E)
    F -> id
    

    计算first的时候,从左部开始,找到需要计算的目标,然后就用产生式一步一步展开,找到第一个终结符即可:

    first(F)  = {(, id}
    first(E') = {+, ε}
    first(T') = {*, ε}
    first(T)  = first(FT')
              = first(F)
              = {(, id}
    first(E)  = first(TE') 
              = first(FT'E') 
              = first(F)
              = {(, id}
    

    相比起follow,first的计算还是比较简单的。需要注意的是,first(FT’) ≠ first(F)∪first(T’),我们求的是这个整体的第一个非终结符,而不是两部分各自的第一个非终结符。

    至于follow,因为follow是要找到目标非终结符后面的第一个终结符,所以需要分类讨论。比如,对于产生式A -> aBb来说,假如我们要求follow(B):

    • 如果b不为空(ε),那么就很好办了,此时follow(B) = first(b)。

      为什么?B后面的第一个不就是b的第一个吗?

    • 如果不为空(ε),但可以推导出空(ε),那么我们要跳过为空的部分,此时follow(B) = first(b) - {ε}。这个应该不用多解释,相当于跳过为空的部分。

    • 如果b为空(ε),那么相当于B后面没有东西了,此时follow(B) = follow(A)。

      为什么?这时候产生式相当于是A -> aB,B后面的第一个不就是A后面的第一个吗?

    在具体计算的时候,为了避免遗漏,个人感觉可以加一些tricky的处理,加一个产生式:

    E -> $E$  // here
    E —> TE'
    E'-> +TE'
    E'-> ε
    T -> FT'
    T'-> *FT'
    T'-> ε
    F -> (E)
    F -> id
    

    添加这个产生式可以有效避免忘记把$加进follow里。计算还是比较简单的,找到右边有目标的,然后按照刚才的流程走一遍就行了。比如,对于follow(E),右边包含E的产生式有E -> $E$F -> (E),而且右边不为空,所以:

    follow(E) = first($) ∪ first()) 
              = {), $}
    

    对于follow(E’),右边包含E’的产生式有E -> TE'E'-> +TE',可以看到E’右边都为空。所以:

    follow(E') = follow(E) ∪ follow(E')
              = {), $}
    

    需要注意的一点是,出现类似于递归的情况的时候,直接去掉就好了;我们只考虑最小的情况。

    对于follow(F),这个稍微复杂一点,右边包含F的产生式有T -> FT'T'-> *FT',F右边第一个是T’,既可以不为空,但是可以推导出空,又可以直接为空,所以需要取个并集:

    follow(F) = follow(T) ∪ follow(T') ∪ (first(T') - {ε})
              = {+, ), $} ∪ {+, ), $} ∪ {*}
              = {*, +, ), $}
    

    可能有一个地方还没有解释,什么叫“first看第一个,follow看全部”?因为按照定义,first是第一个符号,但follow是紧跟在目标后边的终结符的集合,并没有说只有一个。举例来说,对于产生式S -> A a A b | B b B a来说,first(A) = ε,但follow(A) = {a, b},差别就在这了。这也是我觉得非常神秘的一个地方。

    展开全文
  • 之前学习的时候只是知道first和follow集合怎么计算,但是没有很明白背后的原理。想起轮子哥的一句话:要理解一个东西最好的办法就是实现它。所以就心血来潮,写了C++的实现 代码 思路什么的就不说了,都写在代码的...

    前言

    最近在学习微机原理,里面涉及到编译优化的问题,又去重新看了看龙书的语法分析部分。之前学习的时候只是知道first和follow集合怎么计算,但是没有很明白背后的原理。想起轮子哥的一句话:要理解一个东西最好的办法就是实现它。所以就心血来潮,写了C++的实现

    代码

    思路什么的就不说了,都写在代码的注释里面。

    #include<string>
    #include<iostream>
    #include<vector>
    #include <map>
    #include <set>
    #include <regex>
    using namespace std;
    const int MAX_N = 5000;
    //记录总数
    int cnt = 0;
    pair<string,vector<string> > exps[MAX_N];
    set<string> Vns,Vts;//Vns表示非终结符的集合,Vts表示终结符的集合
    //使用set的好处就是可以去掉手工判断重复元素
    map<string,set<string> > first;//计算得到的first集合,同时也包含终结符的(也就是它本身。为了方便起见,往这里加入了)
    map<string,set<string> > follow;//计算得到的follow集合
    
    //判断是否属于终结符
    bool is_terminal_char(const string & s){
        //只要不是大写的我们就认为它属于终结符
        regex nt("[A-Z]*");
        if(regex_match(s,nt)){
            return false;
        }
        return true;
    }
    
    void readExps(){
        string str;
        cout<<"input information (end with #):\n";
    
        while (getline(cin,str)){
            if(str.find("#") != -1) break;//结束的条件,如果是#就直接跳出循环
            //输入的表达式以 -> 作为左右方向的分隔符。所以直接去找这个->的位置
            int mid_pos = str.find("->");
            if(mid_pos == -1){
                cout<<"输入的表达式格式有误,已忽略该表达式\n";
                continue;
            }
            int ls = 0,le = mid_pos;//表示左边的字符串起始位置和结束位置
            while (str[ls] == ' ') ls++;
    
            for(int i = ls;i<mid_pos;i++){
                if(str[i] == ' '){
                    le = i;
                    break;
                }
            }
            //确定表达式左边的非终结符的具体内容
            exps[cnt].first = str.substr(ls,le-ls);
            Vns.insert(exps[cnt].first);//加入到终结符的集合中
            //cout<<"--"<<exps[cnt].first<<"--"<<endl;
            //继续往后读取,把表达式右边的字符全都加入进来
            for(int i = mid_pos + 2; i<(int)str.length();i++){
                //表达式右边把所有的单字符都读入到vector里面
                if(str[i] == ' ') continue;
                exps[cnt].second.push_back(str.substr(i,1));
                string exp_elem = str.substr(i,1);
                if(is_terminal_char(exp_elem)){
                    Vts.insert(exp_elem);
                    first[exp_elem].insert(exp_elem);
                }
            }
            //读取完毕后,把cnt+1
            cnt++;
    //        for(string s : exps[cnt].second){ // 读取测试完成
    //            cout<<s<<" ";
    //        }
        }
    }
    
    
    //计算first集合
    void cal_first(){
        int pre_size = -1,now_size = 0;
        //设置更新的条件
        while(pre_size != now_size){
            pre_size = now_size;
            for(int i = 0;i<cnt;i++){
                string str = exps[i].first;
                vector<string> elements = exps[i].second;
                //如果说表达式右边的第一个字符属于终结符,那么就直接把它加入到first(str)中(规则1)
                if(is_terminal_char(elements[0])){
                    first[str].insert(elements[0]);
                }
                    //规则2
                else {
                    for (int j = 0; j < (int) elements.size(); j++) {
                        if (is_terminal_char(elements[j])) {//用于循环体判断。如果发现已经到达了终结符的位置,就退出
                            break;
                        }
                        //将两个集合进行合并
                        for(string tmp : first[elements[j]]){
                            //注意,空字符不能够加入到str的first集合中
                            if(tmp != "~"){
                                first[str].insert(tmp);
                            }
                            //但是如果发现所有的非终结符都可能推导出空字符,那么就把空字符加进去
                            else if(j == elements.size() - 1){
                                first[str].insert(tmp);
                            }
                        }
                        //如果发现没有空字符集,就直接退出去
                        if (first[elements[j]].find("~") == first[elements[j]].end()) {
                            break;
                        }
                    }
                }
                now_size = 0;
                for(string tmp : Vns){//重新计算now_size的大小
                    now_size += (int)first[tmp].size();
                }
            }
        }
    }
    
    void cal_follow(){
        //使用规则1
        follow["S"].insert("#");//默认S为文法的起始字符
        //这两个标志只用于判断是否已经生成了完全的follow集合
        int pre_size = -1,now_size = 0;
        while (pre_size !=  now_size){
            pre_size = now_size;
            for(int i = 0;i<cnt;i++){
                string str = exps[i].first;
                vector<string> elements = exps[i].second;
                //使用规则2
                for(int j = 0;j<(int)elements.size()-1;j++){
                    if(!is_terminal_char(elements[j])){//如果当前的是非终结符
                        //并且后面的那个单元也是非终结符
                        //就把后面的那个非终结符除~以外的所有first元素都加入进去
                        follow[elements[j]].insert(first[elements[j + 1]].begin(), first[elements[j + 1]].end());
                        //去掉空字符
                        follow[elements[j]].erase("~");
                        //否则就把后面的单个终结符加入进去
                    }
                }
                //如果当前的是终结符,那么规则2就不用了.
                //使用规则3,为了方便起见,从后往向前遍历
                for(int j = elements.size() - 1;j>=0;j--){
                    //如果是非终结符,就把推导式中的follow元素都加入到它对应的follow集合里面
                    if(!is_terminal_char(elements[j])){
                        follow[elements[j]].insert(follow[str].begin(),follow[str].end());
                    }
                    else break;//如果是终结符,就直接退出
    
                    //表明在first集合中没有空字符,这样的话就直接退出
                    if(first[elements[j]].find("~") == first[elements[j]].end()){
                        break;
                    }
                }
            }
            now_size = 0;
            for(string tmp : Vns){//重新计算now_size的大小
                now_size += (int)follow[tmp].size();
            }
        }
    }
    
    /**
     * testData is in test_data.txt
     * @return
     */
    int main(){
        Vts.insert("#");
    
        readExps();
        cal_first();
        cout<<"---first---\n";
        for(string n : Vns){
            cout<<n<<":";
            for(string tmp : first[n]){
                cout<<tmp<<" ";
            }
            cout<<endl;
        }
        cal_follow();
        cout<<"---follow---\n";
        for(string n : Vns){
            cout<<n<<":";
            for(string tmp : follow[n]){
                cout<<tmp<<" ";
            }
            cout<<endl;
        }
        return 0;
    }
    
    

    测试数据:
    输入:

    S->AB
    S->bC
    A->~
    A->b
    B->~
    B->aD
    C->AD
    C->b
    D->aS
    D->c
    

    预计输出:

    ---first---
    A:b ~
    B:a ~
    C:a b c
    D:a c
    S:a b ~
    ---follow---
    A:# a c
    B:#
    C:#
    D:#
    S:#
    
    

    当然设计的还有很多不完善的地方,后续自己优化吧。

    展开全文
  • 编译原理FIRST和FOLLOW集的求法

    千次阅读 多人点赞 2019-06-18 17:16:41
    编译原理FIRST和FOLLOW集的求法 由于最近要期末考试了,所以要从头到尾复习(预习)一遍了。陈意云老师写的课本比较抽象,看不太懂,最后又找了中科大的编译原理课,可能听的时候太困了没有集中精力,又跑去看了...

    编译原理FIRST集和FOLLOW集的求法

    由于最近要期末考试了,所以要从头到尾复习(预习)一遍了。陈意云老师写的课本比较抽象,看不太懂,最后又找了中科大的编译原理课,可能听的时候太困了没有集中精力,又跑去看了以前曾经看过的哈工大的公开课,应该是看懂了,所以就厚颜无耻的来捋一捋,欢迎交流,批评指正。

    废话不多说,直接看怎么计算的吧。
    首先看FIRST集,文字描述如下:

    1.FIRST(X):可以从X推导出的所有串首终结符构成的集合
    如果X=>*ε,那么ε∈FIRST(X)

    举个栗子

    表达式FIRST集FOLLOW集
    E -> TE’{}{}
    E’-> +TE’|ε{}{}
    T-> FT’{}{}
    T’->*FT’|ε{}{}
    F-> (E)|id{}{}

    我是这样做的,首先看有终结符的表达式F-> (E)|id可以得到FIRST(F)={(, id};
    再看有终结符的表达式T’->FT’|ε,得到FIRST(T’)={*, ε}
    再看E’-> +TE’|ε,得到FIRST(E’)={+ , ε},所得得到以下结果:

    表达式FIRST集FOLLOW集
    E -> TE’{}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’{}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    然后再从头看每个表达式可以得到FIRST(E)=FIRST(T),所以去求FIRST(T);
    所以来看表达式T-> FT’,得到FIRST(T)=FIRST(F),又因为F无法推导出ε,所以FIRST(T)=FIRST(F);
    同理可得FIRST(E)=FIRST(T)=FIRST(F)
    所以表就更新为以下结果:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    这时候,我们FIRST集就已经求完了,接下来看FOLLOW集:
    同样先来文字描述:

    FOLLOW(A):可能在某个句型中紧跟在A后边的终结符a的集合
    FOLLOW(A)={a| S=>*αAaβ, a∈VT, α,β∈(VT∪VN)*
    如果A是某个句型的最右符号,则将结束符“$”添加到FOLLOW(A)中。

    还是上面的栗子:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    我是首先找处在句子最右边的非终结符有哪些,由上面的表达式可以看出,分别有E’、T’所以首先把"$"填进去:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$}
    F-> (E)|idFIRST(F)={(, id}{}

    然后从头开始看,首先看E,先直观的看E后面跟有哪些终结符;很容易可以看到有“)”;
    又因为E为开始符号,所以FOLLOW(E)中有“$”符
    再看T,T后面跟的是E’,所以FOLLW(T)要包含FIRST(E’);又由于E’可以推导出空串,所以T也可以是最右符号;
    再看T’,T’首先是最右符号,所以FOLLOW(T)包含结束符;
    最后看F,F后面跟的是T’,所以FOLLOW(F)包含FIRST(T’),又由于T’可以推导出空串,所以F也可以是最右符号
    所以得到以下列表:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $}

    接下来再看有表达式推导得到的FOLLOW集是否发生改变:
    又由于E->TE’,所以FOLLOW(E)=FOLLOW(E’);
    又因为T->FT’,所以FOLLOW(T)=FOLLOW(T’)
    所以有些FOLLOW集需要更新如下所示:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$, )}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$, +}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $}

    再看有些表达式能够推出空串,所以右边非终结符的FOLLW集合需包含左边非终结符的FOLLW集合,如E -> TE’,由于E’能够推导出空串,所以FOLLW(T)要包含FOLLW(E),根据这条规则,对FOLLW集做以下更新:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$, )}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $, )}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$, +, )}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $, +,)}

    总结

    FIRST集没什么问题,很好求,但是FOLLOW集合想对就比较麻烦,需要考虑的地方比较多,在做题目的时候千万不要遗漏!
    欢迎批评指正,交流。

    展开全文
  • 语言为C++,使用了set,map容器,输入格式:S -> Aa | g | e,支持多‘|’ 符号,采用文件输入
  • 编译原理课程设计。。。。简单的FIRSTFOLLOW集求解的程序。。。。压缩文档中ffs.cpp为源程序。。。。使用了bool。。。。所以做了cpp。。。。Production文本是供程序使用的产生式。。。。其余的是过程文件。。。。...
  • 编译原理:求First和Follow

    千次阅读 2018-10-25 22:16:04
    #输入文法求First和Follow集 #要求大写字母表示非终结符,小写字母表示终结符 #最后一个产生式以$结尾或者输入$表示输入结束 #默认第一个产生式的→左边为起始符号 def inputGrammer(): #接收文法输入的函数 ...

    代码

    #输入文法求First集和Follow集
    #要求大写字母表示非终结符,小写字母表示终结符
    #最后一个产生式以$结尾或者输入$表示输入结束
    #默认第一个产生式的→左边为起始符号
    def inputGrammer():  #接收文法输入的函数
        grammer=[]#声明一个文法列表,用来保存该文法的各个产生式
        print('箭头请用符号→')
        print('空串请用符号ε')
        print('____________________________')
        while(True):
            production=input()
            if(production=='$'):
                break;
            elif (production[-1:] == '$'):  # 如果是最后一个产生式,把$去掉加入到文法中,并跳出循环
                grammer.append(production[:-1])
                break;
            else:
                grammer.append(production)
        return grammer
    #print('____________________________')
    def cut(grammer):#把包含选择运算符的产生式,分为两个,如把 F→(E)|id 分成 F→(E) 和 F→id ,这样之后会比较方便
        grammer1 = []
        for i in range(len(grammer)):
            s=grammer[i]
            if '|' in s:
                while True:
                    index = s.find('|')
                    grammer1.append(s[:index])
                    index2 = s.find('→')
                    s1=s[:index2 + 1] + s[index + 1:]
                    if '|' not in s1:
                        grammer1.append(s1)
                        break
                    else:
                        s=s1
            else:
                grammer1.append(grammer[i])
        return grammer1
    #print('____________________________')
    First={}#该文法的First集,以字典形式存储
    Follow={}#该文法的Follow集,以字典形式存储
    def initializeFirstAndFollow(grammer):#找到文法中的非终结符VN,并为其各自建立First集和Follow集
        VN=[]
        for i in range(len(grammer)):
            s=grammer[i]
            for j in range(len(s)):
                if(s[j]>='A' and s[j]<='Z'):
                    if(j<len(s)-1 and s[j+1]=='\''):
                        vn=s[j]+'\''
                        if vn not in VN:
                            VN.append(vn)
                    else:
                        vn = s[j] + ''
                        if vn not in VN:
                            VN.append(vn)
        global First
        global Follow
        for i in range(len(VN)):
            First[VN[i]]=[]
            Follow[VN[i]]=[]
        Follow[VN[0]].append('$')
    # print('____________________________')
    def findFirstVN(s):#找到字符串中的第一个非终结符
        length=len(s)
        for i in range(length):
            if s[i]>='A' and s[i]<='Z':
                if(i<length-1):
                    if(s[i+1]=='\''):
                        return s[i:i+2]
                    else:
                        return s[i]
                else:
                    return s[i]
        return '$'#表示该字符串中没有非终结符
    #print('____________________________')
    def findNextVN(s):#找到字符串中的第二个非终结符
        #判断一下FirstVN的位置,与len(s)比较
        length=len(s)
        vn=findFirstVN(s)
        index=s.find(vn)
        length1=len(vn)
        return findFirstVN(s[index+length1:])
    #print('____________________________')
    def findLastVN(s):#找到字符串中的最后一个非终结符
        length=len(s)
        index=0
        if s[length-1:]<'A' or s[length-1:]>'Z':
            if s[length-1:]!='\'':
                return findFirstVN(s)
        for i in range(length):
            if s[i]>='A' and s[i]<='Z':
                index=i
        if index==length-1:
            return s[index]
        else:
            if s[index+1]=='\'':
                return s[index:index+2]
            else:
                return s[index]
    #print('____________________________')
    def lookVT(grammer):#扫描文法中的每一个产生式,如果产生式右边第一个符号是终结符,则把它加到产生式左边非终结符的First集中去
        global First
        for i in range(len(grammer)):
            s = grammer[i]
            index = s.find('→')
            left = s[:index]
            right= s[index + 1:]
            if right[0]<'A' or right[0]>'Z':
                if right[0]=='i' and 'id' not in First[left]:
                    First[left].append('id')
                else:
                    if right[0] not in First[left]:
                        First[left].append(right[0])
    #print('____________________________')
    def FFirst(grammer):
        '''
            扫描文法中的每一个产生式,对于产生式右边第一个符号不是非终结符的情况,
           把右边非终结符First集中的元素加入到左边非终结符的First集中去
          如果右边非终结符的First集中包含空串ε,则应找到该非终结符之后的一个非终结符
         把这个非终结符First集中的元素加入到左边非终结符的First集中去,此次类推
         '''
        for i in range(len(grammer)):
            s = grammer[i]
            index = s.find('→')
            right = s[index + 1:]
            if right[0]<'A' or right[0]>'Z':
                continue
            vn1 = findFirstVN(s)
            vn2 = findNextVN(s)
            flag=1
            while flag==1 and '$'!=vn2:
                for ss in First[vn2]:
                    if ss not in First[vn1]:
                        First[vn1].append(ss)
                if 'ε' in First[vn2]:
                    flag=1
                    index=s.find(vn2)
                    vn2=findLastVN(s[index:])
                else:
                    flag=0
    #print('____________________________')
    def handleFirst(grammer):#求First集的函数
        lookVT(grammer)
        FFirst(grammer)
        FFirst(grammer)
    #print('____________________________')
    def scanVT(s):#扫描文法中的每一个产生式,如果箭头→右边有终结符的话,找到在它之前紧挨着它的一个非终结符,把该终结符加入到该非终结符的Follow集中去
        #print(s,"In scanVT")
        global Follow
        s1=s
        index=s1.find('→')
        s1=s1[index+1:]
        for i in range(len(s1)):
            if s1[i]<'A' or s1[i]>'Z':
                if s1[i]!='\'':
                    if i>0 and s1[i-1]=='\'':
                        vn=s1[i-2:i]
                    elif i>0:
                        vn=s1[i-1]
                    else:
                        vn='$'
                    if len(s1)==1 or s1=='id':
                        vn='$'
                    if vn!='$':
                        if s1[i] =='i' or s1[i]=='d':
                            if 'id' not in Follow[vn]:
                                Follow[vn].append('id')
                        else:
                            if s1[i] not in Follow[vn]:
                                Follow[vn].append(s1[i])
        vn1=findFirstVN(s1)
        vn2=findNextVN(s1)#产生式右边只有两个非终结符??
        if vn1!='$' and vn2!='$' and vn1+vn2 in s1:
            for si in First[vn2]:
                if si not in Follow[vn1] and si!='ε':
                    Follow[vn1].append(si)
        #print("FOllOW")
        #print(Follow)
        #print("End of FOLLOW")
    
    #print('____________________________')
    def FFollow(grammer):
        '''
              扫描文法的每一个产生式,把第一个非终结符的Follow集去除空串ε加入到最后一个非终结符的Follow集中去
             如果最后一个非终结符的First集中有空串ε,
            则把第一个非终结符的Follow集去除空串ε加入到倒数第二个非终结符的FOllow集中去,依次类推
        '''
        for i in range(len(grammer)):
            s = grammer[i]
            vn1 = findFirstVN(s)
            vn2 = findLastVN(s)
            flag=1
            while flag==1 and vn1!=vn2:
                for ss in Follow[vn1]:
                    if ss not in Follow[vn2]:
                        Follow[vn2].append(ss)
                if 'ε' in First[vn2]:
                    flag=1
                    index=s.find(vn2)
                    vn2=findLastVN(s[:index])
                else:
                    flag=0
    #print('____________________________')
    def handleFollow(grammer):#求Follow集的函数
        global Follow
        for i in range(len(grammer)):
            s=grammer[i]
            scanVT(s)
        FFollow(grammer)
    #print('____________________________')
    def showFirst():#显示First集
        global First
        for i in First.keys():
            print('First(',i,')= ',end="{ ")
            for j in First[i]:
                if j!=First[i][-1]:
                    print(j,end=", ")
                else:
                    print(j, end="")
            print("} ")
    #print('____________________________')
    def showFollow():#显示Follow集
        for i in Follow.keys():
            print('Follow(',i,')= ',end="{ ")
            for j in Follow[i]:
                if j!=Follow[i][-1]:
                    print(j,end=", ")
                else:
                    print(j,end="")
            print("} ")
    
    #print('____________________________')
    if __name__ == '__main__':
        print('____________________________')
        g=inputGrammer()#接收文法输入
        grammer=cut(g)#对产生式作处理
        initializeFirstAndFollow(grammer)#初始化First集和Follow集
        print('____________________________')
        handleFirst(grammer)#求First集
        showFirst()#显示First集
        print('____________________________')
        handleFollow(grammer)#求Follow集
        showFollow()#显示Follow集
        print('____________________________')
    

    输入

    在这里插入图片描述

    输出

    在这里插入图片描述

    检查

    • 和课本55、56页的结果对比,发现是一致的
    展开全文
  • C语音代码。实现功能:1....2.求每个非终结符FIRSTFOLLOWSELECT集模块。3.预测分析表的构建模块。4.文法的检验及消除左公因子左递归模块。5.对输入终结符串的判断,是否为LL1文法,并进一步分析。
  • 编译原理FIRST集合FOLLOW集,超简单

    千次阅读 多人点赞 2020-12-03 19:16:13
    求谁的FIRST集,要找谁在左侧的产生式,拿书上的例子来说(编译原理,陈火旺,第三版) E->TE' E'->+TE'|@ T->FT' T'->*FT'|@ F->(E)|i 然后要看产生式右侧, 1、若产生式右侧以终结符开头,就把这...
  • 编译原理FIRST集与FOLLOW

    千次阅读 2018-12-13 20:06:28
    编译原理FIRST集与FOLLOW集 一、First集合 定义: First集合是对产生式右部的字符串而言的,求取的是非终结符VT(或终结符、空字符、文法符号串)的开始符号集合,集合中包含的是由左部非终结符VT推导得到的...
  • 1.first集合和follow集合都是终结符的集合。 2.first集合是"自己"的开始终结符。 3.follow集合是除开"自己"后面跟着的第一个终结符。 4.first集合和follow集合是对于 非终结符“自己(大写字母)”的首(小写字母) ...
  • 编译原理 First和Follow集的求法

    千次阅读 2018-04-19 19:05:35
    自上而下分析:FIRST集求法 First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的...
  • 编译原理之计算FIRST集合和FOLLOW集合

    万次阅读 多人点赞 2018-04-11 13:24:00
    FIRST集合的求解规则 计算各个文法符号X的FIRST(X)时,不断应用下列规则,直到再没有新的终结符号或者ε可以被加入到任何FIRST集合中为止。 如果X是一个终结符号,那么FIRST(X) = X。 如果X是一个非终结符号...
  • 编译原理之NULL集、firstfollow集C语言实现,实现中句子的转换符号由‘#’代替,数组默认由‘*’作为结束符
  • 刚学first和follow集的时候,如果上课老师没有讲明白或者自己没听明白,自己看的时候还真是有点难理解,不过结合着具体的题目可以理解的更快。 先看一下两种集合的求法:  First集合的求法:  First集合最终...
  • 编译原理FirstFollow集示例 (大写字母非终结符、小写字母终结符) first集各种情况示例: 后面跟终结符 A->aB|ε A->c ..... First(A)={a,ε,c} 后面跟非终结符 A->Ba B->b ..... First(A)={a} ...
  • FIRST集的构造: 计算所有文法符号X的FIRST(X),直到每个FIRST集合不再增大为止...(3) 如果X是非终结符,且X→Y1Y2…Yk是产生式,若对某个i, a属于FIRST(Yi),并且ε属于所有的FIRST(Y1),FIRST(Y2), …,FIRST(Yi-1),即Y1...
  • 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合
  • 编译原理FIRST集合和FOLLOW集合

    千次阅读 多人点赞 2020-06-07 05:03:28
    FIRST集合 定义:可从α推导得到的串的首符号的集合,其中α是任意的文法符号串。 规则:计算文法符号 X 的 FIRST(X),不断运用以下规则直到没有新终结符号或 ε可以被加入为止 : (1)如果 X 是一个终结符号...
  • 编译原理FIRSTFOLLOW、FIRSTVT、LASTVT的求法总结

    千次阅读 多人点赞 2020-04-09 16:35:50
    首先呢First和Follow是一对,而FirstvtLastvt是一对。 First和Follow是为了画预测分析表的(在LL(1)分析法处)。 而FirstvtLastvt是为了画算符优先关系表。 First这里面包含了组成First(A)的两种情况:以...
  • 编译原理FIRSTFOLLOW

    万次阅读 多人点赞 2017-12-01 17:22:29
    编译原理 FIRST,FOLLOW集的求法
  • 详情见本人博客文章“python | 编译原理,语法分析——LL(1)文法实现 上” 详情见本人博客文章“python | 编译原理,语法分析——LL(1)文法实现 上” 详情见本人博客文章“python | 编译原理,语法分析——LL(1)...
  • 怎么求编译原理中的first集,followselec集

    万次阅读 多人点赞 2015-12-09 18:00:15
    所有大写字母代表非终结符,小写字母代表终结符,省略号代表未知数目(可能为0)的不确定...求First集合可分如下几种情况:1、单个符号的First集合:单个终结符的First集合就是它自己。2、单个非终结符的First集合:A
  • 编译原理FIRST和FOLLOW集的求法以及构建LL(1)分析表

    万次阅读 多人点赞 2019-07-01 10:57:57
    文章目录FIRST集的求法FOLLOW集的计算生成预期分析表算法例题 FIRST集的求法 FIRST集是一个文法符号串所可能推导出的符号串的第一个终结符的集合 对于文法G的任一符号串α\alphaα = x1x2…xnx_{1}x_{2} \ldots x_{n...
  • ( 编译原理JAVA求FirstFollow
  • 编译原理学习笔记---FIRST和FOLLOW

    千次阅读 2017-05-07 11:46:22
    FIRST: 官方定义: (1)若X∈Vt(终结符号),则FIRST(X)={X}。 (2)若X∈Vn(非终结符号),且有产生式X→a...,则把a加入到FIRST(X)中;若X∈ε也是一条产生式,则把ε也加到FIRST(X)中。 (3)若X→Y......
  • 编译原理 求解first和follow集步骤(附例子)

    万次阅读 多人点赞 2020-03-14 21:07:41
    First集 定义:对于任意文法符号串α ,FIRST(α)是可从α推导得到的串的首符号的集合 如果αε,则ε也在FIRST(α)中( 即α可空) FIRST(α)={t|α-->tβ, t∈T}U{ε|α-->ε} 做法:首先明确FIRST...
  • 编译原理first集,follow集,select集解析

    万次阅读 多人点赞 2018-04-30 19:30:32
    为了方便自顶向下语法分析,需要求文法对应的first集,follow集,以及select集。本文主要分为两部分,一个是求法解析,还有一个例子详解:第一部分是求法解析将对first集,follow集,select集分为三种讲解方法①定义...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,042
精华内容 4,416
关键字:

编译原理first和follow