精华内容
下载资源
问答
  • 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合
  • 题目:First集和Follow集生成算法模拟 【问题描述】 设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。(算法参见教材) 【基本要求】 动态模拟算法的基本功能是: (1) 输入一个文法G; (2) ...
  • 编译原理的FIRST集和FOLLOW集~~有兴趣的可以看一下,有漏了一个条件,不过注明出来了~~
  • 编译原理------C++实现求First集和Follow集

    千次阅读 多人点赞 2019-12-06 20:39:54
    First集算法描述 1.若X->a…,则将终结符a放入First(X)中 2.若X->ε,则将ε放入First(X)中 3.若有X->Y1Y2Y3…Yk,则 (1)把First(Y1)去掉 ε后加入First(X) (2)如果First(Y1)包含ε,则...

    First集算法描述

    1.若X->a…,则将终结符a放入First(X)中
    2.若X->ε,则将ε放入First(X)中
    3.若有X->Y1Y2Y3…Yk,则
    (1)把First(Y1)去掉 ε后加入First(X)
    (2)如果First(Y1)包含ε,则把First(Y2)也加入到First(X)中,以此类推,直到某一个非终结符Yn的First集中不包含ε
    (3)如果First(Yk)中包含ε,即Y1~Yn都有ε产生式,就把ε加入到First(X)中

    Follow集算法描述

    1.对于文法开始符号S,把$加入到Follow(S)中
    2.若有A->aBC,则将First(C)中除了ε之外的元素加入到Follow(B)(此处a可以为空)
    3.若有A->aB或者A->aBC且ε属于first(C),则将Follow(A)加入到follow(B)中(此处a可以为空)
    4.若有A->Bc,则直接将c加入follow(B)中
    follow集中不含有空串ε

    代码

    代码说明

    1.原产生式存于文件中
    2.终结符只能用一个小写字母表示
    3.产生式内不可以有空格
    4.ε用#代替
    5.代码没有实现消除左递归和二义性,所以产生式必须为消除左递归和二义性的
    6.暂时看来代码没什么问题(可以准确求出first集和follow集),有问题请指正。

    #include<iostream>
    #include<string>
    #include<set>
    #include<map>
    #include <Windows.h>
    #include <fstream>
    
    using namespace std;
    
    /*
    所有非终结符均为单个字符,#代表空串
    E->TE'
    E'->+TE'|#
    T->FT'
    T'->*FT'|#
    F->(E)|i
    */
    
    class FF {
    public:
    	string fileName = "productions.txt";
    	set<string> productions;//产生式集合
    	map<string, set<string>> split_productions;//分解后的产生式集合
    	set<string> Vt;//终结符集合
    	set<string> Vn;//非终结符集合
    	map<string, set<string>> first;//First集
    	map<string, set<string>> follow;//Follow集
    
    	void init();//从文件读取产生式
    	void splitProductions();//分解产生式
    	void findVtAndVn();//获得终结符和非终结符
    	bool isVn(string s);
    	bool isVt(string s);
    	set<string> getOneFirst(string s);//获得单个非终结符first集
    	void getFirst();//获得所有非终结符first集
    	void getFollow();//获得所有非终结符follow集
    	void SSS();//求folloe集的步骤3
    };
    
    void FF::init() {
    	string line;
    	ifstream in(fileName);
    	if (in) {
    		//文法开始符号的follow集中放入$
    		getline(in, line);
    		productions.insert(line);
    		follow[line.substr(0, 1)].insert("$");
    		cout << line << endl;
    		while (getline(in, line)) {
    			productions.insert(line);
    			cout << line << endl;
    		}
    	}
    }
    void FF::splitProductions() {
    	int position = 0;
    	for (set<string>::iterator it = productions.begin(); it != productions.end(); it++) {
    		string temp = *it;
    		for (int i = 0; i < temp.length(); i++) {
    			position = temp.find("->");
    			string s = temp.substr(0, position);
    			string ss = temp.substr(position + 2);
    			set<string>sss;
    			string t;
    			for (int j = 0; j < ss.length(); j++) {
    				if (ss[j] == '|') {
    					sss.insert(t);
    					t = "";
    				}
    				else
    				{
    					t.append(ss.substr(j,1));
    				}
    				
    			}
    			sss.insert(t);
    			split_productions.insert(pair<string, set<string>>(s, sss));
    		}
    	}
    	for (map<string, set<string>>::iterator it = split_productions.begin(); it != split_productions.end(); it++) {
    		cout << it->first << "    ";
    		for (set<string>::iterator ii = it->second.begin(); ii != it->second.end(); ii++) {
    			cout << *ii << "    ";
    		}
    		cout << endl;
    	}
    
    
    }
    void FF::findVtAndVn() {
    	for (set<string>::iterator it = productions.begin(); it != productions.end(); it++) {
    		string temp = *it;
    		for (int i = 0; i < temp.length(); i++) {
    			if (temp[i] == '-' || temp[i] == '>' || temp[i] == '|')
    				continue;
    			//是大写字母
    			if (temp[i] >= 'A' && temp[i] <= 'Z') {
    				//后面带'
    				if (temp[i + 1] == '\'') {
    					Vn.insert(temp.substr(i, 2));
    					i++;
    				}
    				else {
    					Vn.insert(temp.substr(i, 1));
    				}
    			}
    			//是终结符
    			else
    			{
    				Vt.insert(temp.substr(i, 1));
    			}
    		}
    	}
    
    	cout << "非终结符" << endl;
    	for (set<string>::iterator it = Vn.begin(); it != Vn.end(); it++) {
    		cout << *it << endl;
    	}
    
    	cout << "终结符" << endl;
    	for (set<string>::iterator it = Vt.begin(); it != Vt.end(); it++) {
    		cout << *it << endl;
    	}
    }
    bool FF::isVn(string s) {
    	if (Vn.find(s) != Vn.end()) {
    		return true;
    	}
    	return false;
    }
    bool FF::isVt(string s) {
    	if (Vt.find(s) != Vt.end()) {
    		return true;
    	}
    	return false;
    }
    set<string> FF::getOneFirst(string s) {
    	if (split_productions.count(s)>0) {
    		set<string>temp = split_productions[s];
    		for (set<string>::iterator it = temp.begin(); it != temp.end(); it++) {
    			string stemp = *it;
    			if (stemp == "#") {
    				first[s].insert("#");
    			}
    			else {
    				int flagAll = 0;//所有的非终结符的first集都有#;
    				for (int i = 0; i < stemp.length(); i++) {
    					int flag = 0;//当前的非终结符的first集有#;
    					if (stemp[i+1] == '\'') {//带'的非终结符
    						set<string>t1 = getOneFirst(stemp.substr(i, 2));
    						for (set<string>::iterator ii = t1.begin(); ii !=  t1.end(); ii++) {
    							if (*ii == "#") {//此时空串不可插入
    								flag = 1;
    							}
    							else {
    								first[s].insert(*ii);
    							}
    						}
    						i++;
    					}
    					else if(isVn(stemp.substr(i,1)))//单个非终结符
    					{
    						set<string>t2 = getOneFirst(stemp.substr(i, 1));
    						for (set<string>::iterator ii = t2.begin(); ii != t2.end(); ii++) {
    							if (*ii == "#") {//此时空串不可插入
    								flag = 1;
    							}
    							else {
    								first[s].insert(*ii);
    							}
    						}
    					}
    					else {//终结符
    						first[s].insert(stemp.substr(i, 1));
    					}
    					if (i == stemp.length() - 1 && flag==1) {
    						flagAll = 1;
    					}
    					if (flag == 0)
    						break;
    
    				}
    				if (flagAll == 1) {
    					first[s].insert("#");
    				}
    			}
    		}
    	}
    	return first[s];
    }
    void FF::getFirst() {
    	for (map<string, set<string>>::iterator it = split_productions.begin(); it != split_productions.end(); it++) {
    		getOneFirst(it->first);
    	}
    	cout << "First集" << endl;
    	for (map<string, set<string>>::iterator it = first.begin(); it != first.end(); it++) {
    		cout << it->first << "  :  "  ;
    		for (set<string>::iterator ii = it->second.begin(); ii != it->second.end(); ii++)
    		{
    			cout << *ii << "    ";
    		}
    		cout << endl;
    	}
    
    }
    void FF::getFollow() {
    	for (map<string, set<string>>::iterator it = split_productions.begin(); it != split_productions.end(); it++) {
    		string left = it->first;
    		set<string>right = it->second;
    		for (set<string>::iterator ii = right.begin(); ii != right.end(); ii++) {
    			string temp = *ii;
    			
    			for (int i = 0; i < temp.length(); i++) {
    				if (isVt(temp.substr(i, 1))) {//终结符
    					continue;
    				}
    				else if (i+1<temp.length()&&temp[i + 1] == '\'') {//带有’的非终结符
    					if (isVt(temp.substr(i + 2, 1))) {//非终结符后面是终结符
    						follow[temp.substr(i, 2)].insert(temp.substr(i + 2, 1));
    						i++;
    					}
    					else {//非终结符后面是非终结符s
    						//把后面非终结符的first集ff加入follow集中
    						string s;
    						if (i+3<temp.length()&& temp[i + 3] == '\'') {
    							s = temp.substr(i + 2, 2);
    						}
    						else {
    							s = temp.substr(i + 2, 1);
    						}
    						set<string> ff = first[s];
    						for (set<string>::iterator nn = ff.begin(); nn != ff.end(); nn++) {
    							if (*nn != "#")
    								follow[temp.substr(i, 2)].insert(*nn);
    						}
    					}
    				}
    				else {//不带’的非终结符
    					
    					if (i+1<temp.length() && isVt(temp.substr(i + 1, 1))) {//非终结符后面是终结符
    						follow[temp.substr(i, 1)].insert(temp.substr(i + 1, 1));
    						i++;
    					}
    					else {//非终结符后面是非终结符s
    						//把后面非终结符的first集ff加入follow集中
    						string s;
    						if (i+2<temp.length() && temp[i + 2] == '\'') {
    							s = temp.substr(i + 1, 2);
    						}
    						else {
    							s = temp.substr(i + 1, 1);
    						}
    						set<string> ff = first[s];
    						for (set<string>::iterator nn = ff.begin(); nn != ff.end(); nn++) {
    							if (*nn != "#")
    								follow[temp.substr(i, 1)].insert(*nn);
    						}
    					}
    				}
    			}
    		}
    	}
    	//这一个需要多进行几次,因为follow是不断增长的
    	SSS();
    	SSS();
    
    	cout << "Follow集" << endl;
    	for (map<string, set<string>>::iterator it = follow.begin(); it != follow.end(); it++) {
    		cout << it->first << "  :  ";
    		for (set<string>::iterator ii = it->second.begin(); ii != it->second.end(); ii++)
    		{
    			cout << *ii << "    ";
    		}
    		cout << endl;
    	}
    }
    void FF::SSS() {
    	for (map<string, set<string>>::iterator it = split_productions.begin(); it != split_productions.end(); it++) {
    		string left = it->first;
    		set<string>right = it->second;
    		for (set<string>::iterator ii = right.begin(); ii != right.end(); ii++) {
    			string temp = *ii;
    			for (int j = temp.length() - 1; j > 0; j--) {
    				string now;
    				if (temp[j] == '\'') {
    					now = temp.substr(j - 1, 2);
    					j--;
    				}
    				else now = temp.substr(j, 1);
    				if (isVt(now)) {//产生式最后是终结符
    					break;
    				}
    				else {//产生式最后是非终结符
    					set<string>aa = follow[left];
    					for (set<string>::iterator pp = aa.begin(); pp != aa.end(); pp++) {
    						follow[now].insert(*pp);
    					}
    				}
    				if (first[now].find("#") == first[now].end())
    					break;
    			}
    		}
    	}
    }
    int main() {
    	FF ff;
    	ff.init();
    	ff.splitProductions();
    	ff.findVtAndVn();
    	ff.getFirst();
    	ff.getFollow();
    }
    展开全文
  • 对文法中的非终结符,求first集和follow集
  • 编译原理:求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页的结果对比,发现是一致的
    展开全文
  • 文法first集和follow集的计算源代码
  • DEV C++ 项目实现 不会建项目的看这个——>如何创建项目 ...提取码:b1qz 使用教程 解压后打开文件夹,直接用Dev c++运行LL1,如图: 即可实现。...一分钱都不要啊, 比那些要C币的都好,点个赞呗亲们!...

    DEV C++ 项目实现 不会建项目的看这个——>如何创建项目


    代码链接:https://pan.baidu.com/s/1VNdrSMXaKu3HI0UQ_TInUQ

    提取码:b1qz


    使用教程

    解压后打开文件夹,直接用Dev c++运行LL1,如图:
    在这里插入图片描述

    即可实现。


    一分钱都不要呀, 比需要C币下载的资源都好,点个赞呗!

    展开全文
  • First集和Follow集的求法

    万次阅读 多人点赞 2018-12-22 16:55:21
    FIRST集FOLLOW集 SELECT集 一、FIRST集 FIRST(A)为A的开始符或者首符号集。 1、定义: 设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*} 特别的,若α能推导...

    FIRST集、FOLLOW集 和 SELECT集

    一、FIRST集

    FIRST(A)为A的开始符或者首符号集。

    1、定义:

    设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*}   

    特别的,若α能推导出ε,则规定ε∈FIRST(α).

    2、根据定义求解FIRST集(对每一文法符号X∈V 计算FIRST(X)):

    ①. 若X∈VT,则FIRST(X)={X}。(简单讲,终结符的FIRST集就是它本身)

    ②. 若X∈VN,且有产生式X→a…,a∈VT, 则 a∈FIRST(X)X→ε,则ε∈FIRST(X)。 (简单讲,若是非终结符X,能推导出以终结符a开头的串,那么这个终结符a属于FIRST(X),若X能够推导出空符号串ε,那么空符号串ε也属于X的FIRST集)

    ③. X→Y…是一个产生式且Y ∈VN  则把FIRST(Y)中的所有非空符号串ε元素都加入到FIRST(X)中。(这个可以理解吧)

    ④.若X∈VN;Y1,Y2,…,Yi∈VN,且有产生式X→Y1 Y2 … Yn;当Y1 Y2 … Yn-1都能推导出ε时,则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yn-1)的所有非空元素和FIRST(Yn) 包含在FIRST(X)中。

    即: FIRST(X)=(FIRST(Y1)-{ε} )∪(FIRST(Y2)-{ε} )∪…∪(FIRST(Yn-1)-{ε})∪{FIRST(Yn)}

    ⑤.当(4)中所有Yi 能够推导出ε,(i=1,2,…n),则

    FIRST(X)=(FIRST(Y1)-{ε})∪(FIRST(Y2)- {ε}∪…∪(FIRST(Yn) -{ε})∪{ε}

    反复使用上述②~⑤步直到每个符号的FIRST集合不再增大为止。

     

     

     

    3、求解示例

    1、文法G [S]为:
      S→AB
      S→bC
      A→ε
      A→b
      B→ε
    B→aD
    C→AD
    C→b
    D→aS
    D→c

    求每个非终结符的First集?

    解:对于非终结符S,S的开始符有终结符b和非终结符A,根据上面定义②把b加入FIRST(S),由上面的定义③把FIRST(A)中的所有非空符号串ε元素都加入到FIRST(S)中,而且因为S→AB符合上面的定义④和⑤,所以FIRST(S)=(FIRST(A)-{ε})∪(FIRST(B) -{ε})∪{ε}那么先求FIRST(A)和FIRST(B),A的开始符有终结符b和空符号串ε,由定义①和定义②全部加入FIRST(A),也就是FIRST(A)={ε,b},同理,FIRST(B)={a,ε},这样FIRST(S)也就求出来了,FIRST(S)={b,a,ε},其实回过头来看之所以要反复调用定义②~⑤,是因为开始符中A可能为空字符串ε,所以要考虑A后面的情况。

    再求,FIRST(C),由定义①,把b加入FIRST(C),再由定义④,FIRST(C)=(FIRST(A)-{ε} )∪{FIRST(D)},先求FIRST(D),易知,FIRST(D)={a,c},所以FIRST(C)={b,a,c}

     

    4、小结:

    1、对于终结符而言,FIRST集中的元素只有它本身

    2、对于非终结符而言,如果开始符是终结符或者空符号串ε,则加入其FIRST集中;若开始符是非终结符,则要加入它的不含ε的FIRST集,并考虑其为ε时的情况。

     

     

    二、FOLLOW集

            FOLLOW(A)={a|S能推导出μAβ,且a∈VT,a∈FIRST(β),μ∈VT* ,β∈V+},若S能推导出μAβ,且β能推导出ε, 则#∈FOLLOW(A)。 也可定义为:FOLLOW(A)={a|S能推导出…Aa…,a ∈VT} ,若有S能推导出…A,则规定#∈FOLLOW(A) ,这里我们用‘#’作为输入串的结束符,或称为句子括号, 
        如:   #输入串#。

    FOLLOW(A)为非终结符A的后跟符号集合。

    1、定义:

    设G=(VT,VN,S,P)是上下文无关文法,A∈VN,S是开始符号  

     

    需要注意的是,FOLLOW(A)集是针对非终结符A的,集合中的元素是终结符,是A的全部后跟符号的集合,当A是文法G的开始符(识别符)时,把‘#也加入其中’

     

     
     

    2、根据定义求解FOLLOW集(对每一文法符号S∈VN 计算FOLLOW(S)):

    ①. 设S为文法中开始符号,把{#}加入FOLLOW(S)中(这里“#”  为句子括号)。

    ②. 若A→αBβ是一个产生式,则把FIRST(β)的非空元素加入

      FOLLOW(B)中。如果β能够推导出ε则把FOLLOW(A)也加入FOLLOW(B)中。

     
    ③.反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。

     

    3、求解示例

    1、文法G [E]为:
     
    E   →  TE'
     
    E'  →  +TE' |  ε
     
    T   →  FT'
     
    T'  →  *FT' |  ε
    F  →  (E) | i

    求每个非终结符的FOLLOW集?

     
     

     

    解:先给出它们的FIRST集:(求解方法见上面FIRST集的求解)

     

    FIRST(F)={ (,i }

     

    FIRST(T’)={ *,ε }

     

    FIRST(T) ={ (,i }

     

    FIRST(E’)={ +,ε }

    FIRST(E)={ (,i }
    FOLLOW集的求解:因为E是文法的识别符所以把#加入FOLLOW(E),又由规则F  →  (E) | i 得E的后跟符号),所以,FOLLOW(E)={ #,) };
    FOLLOW(E’)={ #,) }    ∵E → TE’   ∴FOLLOW(E)加入 FOLLOW(E’)
    FOLLOW(T)={+,),#}      ∵E'→ +TE’  ∴FIRST(E’)-{ε}加入FOLLOW(T); 又E’→ε,     ∴ FOLLOW(E’)加入FOLLOW(T)
    FOLLOW(T’)= FOLLOW(T)= {+,),#}      ∵T → FT’   ∴ FOLLOW(T)加入FOLLOW(T’)
    FOLLOW(F)={*,+,),#}    ∵T → FT’   ∴ FOLLOW(F)=FIRST(T’)-{ε} ; 又T’→ε ∴ FOLLOW(T)加入FOLLOW(F)

     

     

     

    4、小结:

    1、FOLLOW集对于非终结符而言,是非终结符的全部后跟符号的集合,如果后跟终结符则加入,如果后跟非终结符,则加入该非终结符的不含空符号串的FIRST集,特别地,文法的识别符的FOLLOW集需要额外的加入‘#’。

     

     

    三、SELECT集

    1、定义:

    给定上下文无关文法的产生式A→α, A∈VN,α∈V*, 若α不能推导出ε,则SELECT(A→α)=FIRST(α)   

    如果α能推导出ε则:SELECT(A→α)=(FIRST(α) –{ε})∪FOLLOW(A)

    需要注意的是,SELECT集是针对产生式而言的。

     

     

    2、LL(1)文法

    ① 一个上下文无关文法是LL(1)文法的充分必要条件是:对每个非终结符A的两个不同产生式,A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=空集  其中α,β不同时能推导出ε。

    ② LL(1)文法的含义:
            第一个L    从左到右扫描输入串
            第二个L    生成的是最左推导
             1         向右看一个输入符号便可决定选择哪个产生式。

    ③LL(1)文法的判别:当我们需选用自顶向下分析技术时,首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合,进而判别文法是否为LL(1)文法。

     

    3、求解示例

    1、文法G [S]为:
      S→AB
      S→bC
      A→ε
      A→b
      B→ε
    B→aD
    C→AD
    C→b
    D→aS
    D→c

    求每个产生式的SELECT集,并判断文法G是否为LL(1)文法?

    解:SELECT(S→AB)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}   

        SELECT(S→bC)=FIRST(bC)={b}   

        SELECT(A→ε)=(FIRST(ε) -{ε})∪FOLLOW(A)={a,c,#}   

        SELECT(A→b)=FIRST(b)={b}   

        SELECT(B→ε)=(FIRST(ε) -{ε})∪FOLLOW(B)={#}   

        SELECT(B→aD)=FIRST(aD)={a}   

        SELECT(C→AD)=FIRST(AD)={a,b,c}   

        SELECT(C→b)=FIRST(b)={b}   

        SELECT(D→aS)=FIRST(aS)={a}   

        SELECT(D→c)=FIRST(c)={c}

     

        由以上计算结果可得相同左部产生式的SELECT交集为:   

    SELECT(S→AB)∩SELECT(S→bC)={b,a,#}∩{b}={b}≠ф      

    SELECT(A→ε)∩SELECT(A→b)={a,c,#}∩{b}=ф       

    SELECT(B→ε)∩SELECT(B→aD)={#}∩{a}=ф       

    SELECT(C→AD)∩SELECT(C→b)={b,a,c}∩{b}={b}≠ф       

    SELECT(D→aS)∩SELECT(D→c)={a}∩{c}=ф       
    由LL(1)文法定义知该文法不是LL(1)文法,因为具有相同左部其产生式的SELECT集的交集不为空。

     

    4、小结:

    1、Select集的作用是将first集和follow集进行合并,如果两个文法的左端都是A,若他们的select集交集为空,表明他们是两个无关的,不会产生不确定性的文法,反之,则表明文法不是LL(1)文法。

    展开全文
  • 文章目录计算文法符号X的FIRST(X)计算非终结符A的FOLLOW(A)表达式文法各产生式的SELECT预测分析表LL(1)文法的分析方法==预测分析法实现步骤== 计算文法符号X的FIRST(X) FIRST ( X ):可以从X推导出的所有串首终结...
  • FIRST集和FOLLOW集的计算

    千次阅读 2019-04-26 17:05:58
    文章目录`FIRST`集的计算计算`FIRST(x)`具体算法计算`$X_21,X_2,X_3,...,X_n$`的`FIRST`集FOLLOW集的计算算法 FIRST集的计算 计算FIRST(x) FIRST(X):可以从X中推导出的所有串首终结符构成的结合。 若$X\Rightarrow...
  • LL文法First集和Follow集通俗讲解

    千次阅读 多人点赞 2020-10-11 17:00:05
    编译原理FIRST集和FOLLOW集 一、FIRST集 定义: 设 G=(VT,VN,S,P)G=(V_T,V_N,S,P)G=(VT​,VN​,S,P)是上下文无关文法,则 FIRST(α)=a∣α⇒a...,a∈VTFIRST(\alpha)= { a\vert \alpha\Rightarrow a...,a \in V_T }...
  • 编译原理FIRST集和FOLLOW集的求法以及构建LL(1)分析表

    万次阅读 多人点赞 2019-07-01 10:57:57
    文章目录FIRST集的求法FOLLOW集的计算生成预期分析表算法例题 FIRST集的求法 FIRST集是一个文法符号串所可能推导出的符号串的第一个终结符的集合 对于文法G的任一符号串α\alphaα = x1x2…xnx_{1}x_{2} \ldots x_{n...
  • 这是这道题的SELECT集 first集和follow集理解了 select集看图就很容易理解了 将文法的合起来的产生式都分开变成单独的一条 没有遇到ε空产生式的就用对应的first集 遇到ε空产生式就用对应的follow集 ok 完美 看到...
  • 本资源用C#开发,集成了first集和follow集 正规式到NFA转换 等
  • 如何计算FIRST集和FOLLOW集

    千次阅读 2020-02-14 15:33:22
    编译原理之计算FIRST集合和FOLLOW集合 原创 ...
  • 编译原理FIRST集和FOLLOW集的求法

    千次阅读 多人点赞 2019-06-18 17:16:41
    编译原理FIRST集和FOLLOW集的求法 由于最近要期末考试了,所以要从头到尾复习(预习)一遍了。陈意云老师写的课本比较抽象,看不太懂,最后又找了中科大的编译原理课,可能听的时候太困了没有集中精力,又跑去看了...
  • 编译原理速成大法FIRST集和FOLLOW集构造法速成FIRSTFOLLOW FIRST集和FOLLOW集构造法速成 例:对于文法G(E) 首先像E,T,E’,F这样的就是非终结符 +,*, ε,(,)这样的就是终结符 构造每个非终结符的FIRST集和FOLLOW集 ...
  • 给出了FIRST集和FOLLOW集的详细计算方法,比原始方法更好理解,更清晰。
  • FIRST集定义如下: 对于α可以有两种表达式: 下面开始构造每个文法符号的FIRST集合 对于每一个X∈VT∪VN,连续使用下面规则,知道每个集合的FIRST不再增大为止: 1.X∈VT,则有FIRST(X)={X}。 2.X∈VN,且有产生式...
  • 文章目录 深入理解 FIRST集的定义 FIRST集的实际意义 FIRST集的计算方法 FOLLOW集的定义 FOLLOW集的实际意义 FOLLOW集的计算方法 预测分析表的实质 LL(1)文法的判断 深入理解 在哈工大的陈老师讲这个的时候(也就是...
  • 【编译原理】First集和Follow集

    千次阅读 2017-05-19 22:06:43
    编译原理课上实验first集和follow集求法:First集合:First集合顾名思义就是求一个文法符号串所可能推导出的符号串的第一个终结符的集合。First(X)就是求X所有推导出的符号串的第一个符号的集合。求First集合可分...
  • FIRST集和FOLLOW集的求法FIRST集步骤FOLLOW集步骤 FIRST集 步骤 若X->a…,则将终结符a加入FIRST(X)中; 若X->e ,则将终结符e加入FIRST(X)中(e表示空集); 若 X->BC…D,则将First(B)所有元素(除了空集...
  • 编译原理 First集和Follow集的求法

    千次阅读 2018-11-19 13:17:56
    FIRST集求法 &nbsp;&nbsp;&nbsp;&nbsp;First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可...
  • 编译原理 求解first集和follow集步骤(附例子)

    万次阅读 多人点赞 2020-03-14 21:07:41
    First集 定义:对于任意文法符号串α ,FIRST(α)是可从α推导得到的串的首符号的集合 如果αε,则ε也在FIRST(α)中( 即α可空) FIRST(α)={t|α-->tβ, t∈T}U{ε|α-->ε} 做法:首先明确FIRST...
  • LL(1)文法系列(一)first集和follow集 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 已知文法G[S]的表达式,计算文法中终结符的first集和follow集。在文法G[S]中使用’@’代表空。 现在我们规定...
  • 学编译原理的时候,印象最深的莫过于这四个...首先要知道First和Follow是一对,而FirstvtLastvt是一对。 然后要知道这两对都是干什么的。 First和Follow是为了画预测分析表的(在LL(1)分析法处)。 而Firstvt...
  • First集和Follow集生成算法模拟

    热门讨论 2010-05-08 11:04:36
    编译原理课程设计First集和Follow集生成算法模拟 【问题描述】 设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟 【基本要求】 动态模拟算法的基本功能是: (1) 输入一个文法G; (2) 输出由...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,467
精华内容 5,386
关键字:

first集和follow集