FIRST:
官方定义:
(1)若X∈Vt(终结符号),则FIRST(X)={X}。
(2)若X∈Vn(非终结符号),且有产生式X→a...,则把a加入到FIRST(X)中;若X∈ε也是一条产生式,则把ε也加到FIRST(X)中。
(3)若X→Y...是一个产生式且Y∈Vn,则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中;若X→Y1Y2...Yk是一个产生式,Y1,...Yi-1都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有ε,则把FIRST(Yi)中的所有非ε-元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj)均含有ε,j=1,2...k,则把ε加到FIRST(X)中。
个人理解:
FIRST(X)就是表示X这个非终结符号用终结符号表示时候(所有的情况)的第一个终结符号!!!
所以解题时可以先把非终结符号利用文法展开---所有情况!!! 然后取每种情况的第一个 终结符号为一个集合(ε也是一种情况)。
例: S→ABc
A→alε
B→blε
解:A只有两种情况,所以FIRST(A)={a,ε}。
B也只有两种情况,FIRST(B)={b,ε}。
S有4种情况:aBc,_bc,a_c,__c。开头的第一个终结符号分别是a,b,c。
FOLLOW:
官方定义:
(1)对于文法的开始符号S,置#于FOLLOW(S)中;
(2)若A→αBβ是一个产生式,则把FIRST(β)\{ε}加至FOLLOW(B)中;
(3)若A→αB是一个产生式,或A→αBβ是一个产生式而β→ε,则把FOLLOW(A)加至FOLLOW(B)中;
(4)FOLLOW中不允许出现ε。
个人理解:
FOLLOW(X)表示.........暂时还不懂?????????????????????????????????????????????????????
但是知道怎么做题:
当X为开始符号时,{}中加入#,然后看→的右边是否有X,若没有,则为{#}。
若有,找到含有X的那个产生式,看X的右侧,若为空,则FOLLOW(X)等于→左侧。
若有,FOLLOW(X)等于FIRST(***).
一定要找全!!!
例: S→aSelB
B→bBelC
C→cCeld
解:S是开始符号,则{}中加入#,............{#}
右侧有S的产生式...第一个式子
S的右侧的FIRST....FIRST(e)=e..........{e,#}
FOLLOW(B)..不是开始符号,直接找右侧有B的产生式
找到了第一个式子,B的右侧没有符号,则FOLLOW(B)=FOLLOW(S).....{e,#}
继续找右侧含有B的产生式,找到了第二个式子
B的右侧是e,求FIRST(e)={e},已经在集合里面,没有B的产生式了,则FOLLOW(B)={e,#}
FOLLOW(C)同FOLLOW(B).
