编译原理课件第3章.pptVIP

定义3.10 文法符号序列α的FIRST集合定义如下: FIRST(α) = { a|α a...，a∈T}，若α ε，则ε∈FIRST(α)。 * * 定义3.11 非终结符A的FOLLOW集合定义如下: FOLLOW(A) = { a |S ...Aa...，a∈T}，若A是某句型的最右符号， 则#∈FOLLOW(A)。 * 非形式地讲，文法符号序列α的FIRST集合，就是从α开始可以推导出的所有以终结符开头的序列中的开头终结符。而一个非终结符A的FOLLOW集合，就是从文法开始符号可以推导出的所有含A序列中紧跟A之后的终结符。 算法3.5 计算X的FIRST集合 输入 文法符号X 输出 X的FIRST集合 方法 应用下述规则： ① 若X是终结符，则FIRST(X)={X}； ② 若X 是非终结符且有X→ε，则加入ε到FIRST(X)； ③ 若X 是非终结符且有X→Y1Y2...Yk，并令Y0=ε，Yk+1=ε，则对所有j(0≤j≤k)，若a∈FIRST(Yj+1)且ε∈FIRST(Yj)，加入a到FIRST(X)。 对任意文法符号序列X1X2...Xn，FIRST(X1X2...Xn)的计算方法与算法3.5中规则③类似，即：FIRST(X1X2...Xn)是所有FIRST(Xi)(i=1,2,..,k)的并集。其中k为第一个具有性质ε不属于FIRST(Xk)或kn的文法符号，若kn，则ε∈FIRST(X1X2...Xn)。 算法3.6 计算所有非终结符的FOLLOW集合 输入 文法G 输出 G中所有非终结符的FOLLOW集合 方法 应用下述规则: ① 加入#到FOLLOW(S)，其中，S是开始符号，#是输入结束标记； ② 若有产生式A→αBβ，则除ε外，FIRST(β)的全体加入到FOLLOW(B)； ③ 若有产生式A→αB或A→αBβ而ε∈FIRST(β)，则FOLLOW(A)的全体加入到FOLLOW(B)。 对于算法3.6中的规则③，可以这样来理解：如果从文法的开始符号S经过若干步推导后得到任意句型δAa，应用规则③中的产生A→αB直接推导，可以得到句型δαBa，或者应用产生A→αBβ再加若干步推导，也可得到句型δαBa(注意ε∈FIRST(β))，即两种情况下均有S δ Aa δαBa。显然任何a∈FOLLOW(A)，均有a∈FOLLOW(B)。 * * 例3.22 文法G3.9中非终结符的FIRST集合与FOLLOW集合，可计算如下。其中FIRST集合的计算可以是自底向上的(从远离文法开始符号的非终结符开始)，FOLLOW集合的计算可以是自顶向下的(从文法的开始符号开始)。 FIRST(F) = {(，id, num} FIRST(T) = {*，/，mod，ε} FIRST(T) = FIRST(F) = {(，id, num} FIRST(E) = {+，–，ε} FIRST(E) = FIRST(T) = FIRST(F) = {(，id, num} FIRST(L) = {ε}∪FIRST(E) = {ε，(，id, num} FOLLOW(L)= {#} FOLLOW(E)=FOLLOW(E)= {?)，;} FOLLOW(T)=FOLLOW(T)= {+，–, ；，)} FOLLOW(F)= {+，–，*，/，mod，)，；} 算法3.7 构造预测分析表 输入 文法G 输出 分析表M 方法 应用下述规则： ① 对文法的每个产生式A→α，执行②和③； ② 对FIRST(α)的每个终结符a，加入α到M[A，a]； ③ 若ε在FIRST(α)中，则对FOLLOW(A)的每个终结符b(包括#)，加入α到M[A，b]； ④ M中其他没有定义的条目均是error。 结合驱动器的动作和FIRST、FOLLOW定义，可以看出M[A，a]是如何指导下一步动作的： ① 若当前栈顶为A，当前输入为a，则规则②表示下一步动作是展开A→α，因为a∈FIRST(α)，所以展开后下一次正好匹配a；