编译原理follow集与first集的计算

下面我将介绍一下我关于LL(1)文法部分的计算文法非终结符First集以及Follow集两个知识点的理解。

首先是First集的计算部分,计算First集首先看我们原文法的左边,原文法左边不重复的都要进行First集的计算,计算时具体有以下三种情况

(1)先看产生式后面的第一个符号,如果是终结符,那就可以直接把它写到这个产生式的First集中,例如:产生式为M->nDc,那在First集中我们就可以直接写上First (M)={ n };

(2)如果产生式后面的第一个符号是非终结符,就看这个非终结符的产生式,看的时候同样利用前面的两种看法;但是当产生式为ε时,则需要把ε带入到待求First集的元素的产生式中再判断。例如:A->Bc; B->aM;B->ε,求First(A)时,我们看到A的第一个产生式中的第一个符号是B,B是一个非终结符,所以我们就要接着看B的产生式,B的第一个产生式的第一个符号为a,a是一个终结符,直接把a写入First(A),B的第二个产生式为ε,把ε带入A->Bc中,A->c(注意:如果将B->ε带入表达式后A的产生式为A->ε,ε不可以忽略),c是终结符,所以把c也写入First(A),最后First (A)={ a,c }。

(3)当产生式右边全为非终结符,且两个非终结符又都可以推出ε时,我们需要把这个产生式的所有情况都列出来,再分析。例如:A->BC;B->b|ε;C->c|ε。我们把A的所有产生式利用上述两种方法列出来就是A->bc,A->b;A->c,A->ε;最后First (A)={b,c, ε}。

接下来介绍一下Follow集的部分,先简单介绍一下计算Follow集的大致规则。比如我们要求Follow(X),文法中多个产生式中含有X,则需要考虑多种情况,以下是具体计算时的三种情况:

(1)文法开始符:所有文法开始符的Follow集中都有一个#。

(2)S->αB的形式:求Follow(B),因为B的后面为空,把Follow(S)写入B的Follow集中。

(3)S->αBβ的形式:求Follow(B),B后部不为空。

①当β是终结符时,直接把β写入Follow(B)。

②当β是非终结符时,将First (β)(如果First(B)中有ε,就把ε删掉)写入Follow(B)中。(需要注意的是:如果β->ε,那么原产生式就变成了S->αB,也就是第二种情况,这两种情况都要算在Follow(B)中)。

郑重声明:本文内容及图片均整理自互联网,不代表本站立场,版权归原作者所有,如有侵权请联系管理员(admin#wlmqw.com)删除。
上一篇 2022年6月14日 21:06
下一篇 2022年6月14日 21:06

相关推荐

联系我们

联系邮箱:admin#wlmqw.com
工作时间:周一至周五,10:30-18:30,节假日休息