已知G4=(VTa,’,’,(,),VN=S,L,L’,S,P),其中P为,
S→(L)|a|ξ
L→SL’
L’→,SL’|ξ
FOLLOW(S)是()。
A.’,’,ξ,
B.’,’#,
C.a,’,’ξ,
D.a,’,’,#
参考答案:B
解析:
终结符A的FOLLOW集合定义如下:
FOLLOW(A)={a|S[*]…Aa…,a∈VT,A∈VN},若S[*]…A,则规定#∈FOLLOW(A),约定#为句子结束标记。
给定一个文法,求FOLLOW(A)的算法如下:
① 对于文法的开始符号S,置#于FOLLOW(S)中;
② 若A→αBβ∈P,则把FIRST(β)中的所有非∈—元素都加至FOLLOW(B)中;
③ 若A→αB∈P,或A→αBβ∈P而β[*]ξ,则把FOLLOW(A)加至FOLLOW(B)中。
重复使用上述3条规则,直到每个FOLLOW集合不再增大为止。
非形式地说,一个非终结符的FOLLOW集合,就是从文法开始符号可以推导出的所有含A句型中紧跟在A之后的所有终结符号。
首先,因为S是开始符号,所以,置#于FOLLOW(S)中。根据L→SL’,把FIRST(L’)中的所有非ξ一元素都加至FOLLOW(S)中,即把’,’加至FOLLOW(S)中。又根据L→SL’和 L’[*]ξ,把FOLLOW(L)加至FOLLOW(S)中,即把’)’加至FOLLOW(S)中。最后, FOLLOW(S)为{#,’,’,)}。