FIRST集、FOLLOW集和SELECT集 |
您所在的位置:网站首页 › first集的计算 › FIRST集、FOLLOW集和SELECT集 |
*一:什么是终结符和非终结符。* 终结符:通俗的说就是不能单独出现在推导式左边的符号,也就是说终结符不能再进行推导。 非终结符:不是终结符的都是非终结符。 如:S——>B,则S是非终结符。 (一般书上终结符用小写,非终结符用大写。) 二:文法产生语言句子的基本思想:从识别符号(开始符)开始,把当前产生的符号串中的非终结符替换为相应规则右部的符号串,直到全部由终结符组成。 三:什么是FIRST集 FIRST集的定义: 如果α是任意的文法符号串,则我们定义FIRST(α)是从α推导出的串的开始符号的终结符集合,即 FIRST(α)={a|α 四:FIRST集求法 First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的First集合。 \1. 直接收取:对形如U->a…的产生式(其中a是终结符),把a收入到First(U)中 \2. 反复传送:对形入U->P…的产生式(其中P是非终结符),应把First§中的全部内容传送到First(U)中【意思就是只需要把第一个非终结符的First集传过去~这个地方是要注意的地方,也是难点】。 五:什么是FOLLOW集 设A是一个非终结符,则定义FOLLOW(A)是包含所有在句型中紧跟在A后面的终结符a的集合,即FOLLOW(A)={a|S 六:FOLLOW集的求法 Follow集合是针对非终结符而言的,Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合,特别地,“#”是识别符号的后随符。注意Follow集合是从开始符号S开始推导。 \1. 直接收取:注意产生式右部的每一个形如“…Ua…”的组合,把a直接收入到Follow(U)中。因a是紧跟在U后的终结符。 2.直接收取:对形如“…UP…”(P是非终结符)的组合,把First§直接收入到Follow(U)中【在这里,如果First(P)中有空字符,那么就要把左部(假设是S)的Follow(S)送入到Follow(U)中。还有就是Follow集中是没有空字符的】。 \3. 直接收取:若S->…U,即以U结尾,则#∈Follow(U) 4.*反复传送:对形如U->…P的产生式(其中P是非终结符),应把Follow(U)中的全部内容传送到Follow§中。 另外,比较正式的说明如下: FIRST集的计算: 首先,为了计算单个文法符号X的FIRST(X),可以应用下列规则,直到没有终结符或ε可加到某个FIRST集合为止: \1. 如果X是终结符,则FIRST(X)是 { X }。 \2. 如果X –> ε 是一个产生式,则将ε加到FIRST(X)中。 \3. 如果X是非终结符,且X –> Y1Y2…Yk是一个产生式,其中k≥1。则当某终结符a∈FIRST(Yi),(1αBβ,那么将集合FIRST(β)中除ε外的所有元素加入到FOLLOW(B)当中。 \3. 如果有一个产生式 A->αB , 或者A->αBβ且FIRST(β)中包含ε , 那么将集合FOLLOW(A)中的所有元素 加入到集合FOLLOW(B)中。 另一种描述: 计算FIRST集 对每一文法符号X∈V , 计算FIRST(X) (a) 若X∈VT,则FIRST(X)={X} (b) 若X∈VN,且有产生式 X→ a… , a∈VT ,则 a∈FIRST(X) 即把a加入到FIRSR(X)中 © 若X∈VN,且有产生式 X→ε,则ε∈FIRST(X) (d) 若X∈VN, 且有产生式X→Y1 Y2 …Yi-1 Yi … Yn,当Y1 Y2 … Yi-1都能推出ε时, 则 FIRST(Y1)-{ε} FIRST(Y2)-{ε} … FIRST(Yi-1)-{ε} FIRST(Yi) 都包含在FIRST(X)中。 (e) 当(d)中X→Y1 Y2 … Yn 所有Yj 都可以推出ε,(j=1,2,…n) , 则 FIRST(Y1) FIRST(Y2) … FIRST(Yn) 都包含在FIRST(X)中 反复使用上述(b)~(e)步直到每个符号的FIRST集合不再增大为止。 求一个符号串α的FIRST集合 若符号串α∈V*,α=X1 X2 … Xi-1 Xi … Xn, 1.若X1不能推导出ε, 则 FIRST(α)= FIRST(X1) 2.若对任何j (1≤j≤i-1, 2≤i≤n) ε∈FIRST(Xj) 3.若对任何j (1≤j≤n) ε∈FIRST(Xj), 七:例子 有如下文法, S->AaBb|BbBa A->ε B->ε 我们求FIRST集。 FIRST(S) = FIRST(AaBb) ∪ FIRST(BbBa) 我们看到 FIRST(A) = ε FIRST(B) = ε 于是,根据我们的规则,要向下看, FIRST(a) = a FIRST(b)= b 没有ε 于是结束,并且在FIRST(AaBb)中不加入ε。 那么我们的结果就是,FIRST(S) = FIRST(AaBb) ∪ FIRST(BbBa) = {A,B} 例:判断该文法是不是LL(1)文法,说明理由 S→ABc A→a|ε B→b|ε First集合求法就是:能由非终结符号推出的所有的开头符号或可能的ε,但要求这个开头符号是终结符号。如此题A可以推导出a和ε,所以FIRST(A)={a,ε};同理FIRST(B)={b,ε};S可以推导出aBc,还可以推导出bc,还可以推导出c,所以FIRST(S)={a,b,c}。 Follow集合的求法是:紧跟随其后面的终结符号或#。但文法的识别符号包含#,在求的时候还要考虑到ε。具体做法是把所有包含你要求的符号的产生式都找出来,再看哪个有用。 Follow(S)={#} 如求A的,产生式:S→ABc A→a|ε ,但只有S→ABc 有用。跟随在A后年的终结符号是FIRST(B)={b,ε},当FIRST(B)的元素为ε时,跟随在A后的符号就是c,所以 Follow(A)={b,c} 同理Follow(B)={c}。 补充: SELECT集 选择集合 给定上下文无关文法的产生式A→α, A∈VN, α∈V*, 若α不能 小结: 因为编译原理对求First集、Follow集和Select集有要求,所以在网上找到了这篇博客,课本上有几个小的知识点补充一下 (1)X->Y1Y2···Yk并且Y1Y2···Yk都能->ε,则FIRST(Yk)∈FIRST(X) (2)如果A->αBβ,则FIRST(β)中除ε之外的所有符号都在FOLLOW(B)中; 小结: 因为编译原理对求First集、Follow集和Select集有要求,所以在网上找到了这篇博客,课本上有几个小的知识点补充一下 (1)X->Y1Y2···Yk并且Y1Y2···Yk都能->ε,则FIRST(Yk)∈FIRST(X) (2)如果A->αBβ,则FIRST(β)中除ε之外的所有符号都在FOLLOW(B)中; 如果A->αB,或A->αBβ,且FIRST(β)包含ε,那么FOLLOW(A)∈FOLLOW(B). |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |