编译原理只看书的话还是很难学,上课听老师讲的蛮好,可忘得也很快,再复习看书的时候已然忘记老师当时是怎么讲的了QAQ...
现在只能在网上找教程自学一下喽:先看看为什么要有first集和follow集:
这个很简单了,x是终结符,那它的FIRST集肯定也是x了。
举个栗子::Y->b|ε,那么First (Y)={b, ε}(b是终结符)
举个栗子:Y->b|ε,那么First (Y)={b, ε}(b是终结符),X->Yabcd|ε,则FIRST(X) = (First(Y)--{ε})∪ {ε}(这
里的{ε}是由法则2 推导出来 )
举个栗子:
1、文法G [S]为:
S→AB First(S) =(First(A)-{ε})∪(First (B)-{ε}) ∪{ε}∪{b}
S→bC 因为A的first有ε,B的first有ε,S->AB,所以是First(A)-{ε})∪(First (B)-{ε}) ∪{ε}
A→ε 然后S->bC由法则2得,所以再加一个b就是First(A)-{ε})∪(First(B)-{ε})∪{ε}
A→b ∪{b}
B→ε 由之前的法则:First (A)={b, ε}First (B)={a, ε}所以First(S) ={a,b,ε}
B→aD
C→AD
C→b
D→aS
D→c
FOLLOW集就是找后面有没有能处理这个终结符的非终结符,如果有就继续,没有则报错!所以此处我们的视角和求解first集的视角有所不同,此时我们应该向后看,找后面的。
这个不用多说,初始规定就是这样。
举个栗子:文法G [E]为:
E → TE' 因为E是文法的识别符所以把#加入FOLLOW(E),又由规则F → (E) | i 得E
E' → +TE' | ε 的后跟符号 )( first(')') = {)} ) ,所以,FOLLOW(E)={ #,) };
T → FT'
T' → *FT' | ε
F → (E) | i
举个栗子:文法G [E]为:
E → TE' 先给出它们的FIRST集:(求解方法见上面FIRST集的求解)
E' → +TE' | ε FIRST(F)={ (,i }
T → FT' FIRST(T’)={ *,ε }
T' → *FT' | ε FIRST(T) ={ (,i }
F → (E) | i FIRST(E’)={ +,ε }
FIRST(E)={ (,i }
FOLLOW集的求解:因为E是文法的识别符所以把#加入FOLLOW(E),又由规则F → (E) | i 得E的后跟符号),所以,FOLLOW(E)={ #,) };
FOLLOW(E’)={ #,) } ∵E → TE’ follow集的目的是为了在E'无法处理当前终结符的时候,判断E'之后有没有能处理该终结符的非终结符, ∴FOLLOW(E)加入 FOLLOW(E')
FOLLOW(T)={+,),#} ∵E'→ +TE’ ∴FIRST(E’)-{ε}加入FOLLOW(T); 又E’→ε, ∴ FOLLOW(E’)加入FOLLOW(T)此处如果把E'->+TE'看为A->aBb,b=>ε的话,则Follow(E')加入Follow(E')中,这样没有任何意义。
FOLLOW(T’)= FOLLOW(T)= {+,),#} ∵T → FT’ ∴ FOLLOW(T)加入FOLLOW(T’)
FOLLOW(F)={*,+,),#} ∵T → FT’ ∴ FOLLOW(F)=FIRST(T’)-{ε} ; 又T’→ε ∴ FOLLOW(T)加入FOLLOW(F)
AIEarth是一个由众多领域内专家博主共同打造的学术平台,旨在建设一个拥抱智慧未来的学术殿堂!【平台地址:https://devpress.csdn.net/aiearth】 很高兴认识你!加入我们共同进步!