构造FIRST集和FOLLOW集的方法

构造FIRST集和FOLLOW集的方法1、构造FIRST集的算法(1)对于G中的每个文法符号X,为求FIRST(X),反复应用如下规则,直到集合不再增大:①若X∈VT，则FIRST(X)是{X}②若X∈VN,且X→aα(a∈VT)，则{a}FIRST(X)X→ε，则{ε}FIRST(X)③若X-Y1Y2…Yi-1Yi…YK∈P,Y1∈VN,则FIRST(Y1)-{ε}FIRST(X)而对所有的j(1≤j≤i-1),Yj∈VN，且Yj∗⇒ε，则令FIRST(Yj)-{ε}FIRST(X)(1≤j≤i)特别，当ε∈FIRST(Yj)(1≤j≤k)时，令ε∈FIRST(X)(2)对文法G的任何符号串=X1X2…Xn构造集合FIRST()①置FIRST(X1)-{}FIRST()②若对任何1ji-1，FIRST(Xj)，则FIRST(Xi)-{}FIRST()特别是，若所有的FIRST(Xj)均含有，1jn，则{}FIRST()。显然，若＝则FIRST()＝{}。2、构造FOLLOW集的算法对于G中的每一A∈VN，为构造FOLLOW(A)，可反复使用如下的规则，直到每个FOLLOW集不再增大为止:①对于文法的开始符号S，令#∈FOLLOW(S)。②对于每一A→αBβ∈P，令FIRST(β)-{ε}FOLLOW(B)。③对于每一A→αB∈P，或A→αBβ∈P，且ε∈FIRST(β)，则令FOLLOW(A)FOLLOW(B)。