编译原理消除回溯.ppt

编译原理 主讲教师：于永彦 FIRST集合 引入FIRST集概念是为了在当前输入的条件下，观察哪个产生式的右部能够导出输入符号，进而决定采用哪个产生式来进行推导。 显然，我们关心的是产生式右部符号串的FIRST集，即文法符号串的FIRST。这个符号串可以是任意的终结符和非终结符的组合。 FIRST集合 【定义】 假定?是文法G的任一符号串，即??(VN∪VT)*，则?的首符号集定义为： 可见，所谓符号串?的FIRST，就是指?的所有可能推导的开头终结符或?的集合。 由定义，不难得出下面的结论： 若 ，则 ； 若?=aA，其中A代表非终结符，则 ； 若?=Aa，则 ； 若? ?，则 。 FIRST集合 一、关系图法求解FIRST 【例】已知文法G[S]如下： S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|c 求所有非终结符的FIRST。 【解】关系图法求解FIRST集，分为三步进行。 （1）求出能推出ε的非终结符 首先建立一个以文法非终结符为元素的一维数组X，对应每个非终结符设置一个标志位，以记录能否推出ε。其值有三种情况：“未定”、“是”、“否”。 其次，按下述步骤逐步更新标志位： FIRST集合 ① 依次扫描文法每一条产生式 I．删除所有右部含终结符的产生式。若使得以某非终结符为左部的所有产生式都被删除，则置该非终结符的标记为“否”，例“D”。 II．若某非终结符存在一条右部为ε的产生式，则置该非终结符的标志为“是”，并删除该非终结符的所有产生式，如“A”、“B”。见表的第2行。 ② 扫描产生式右部的每一符号 I．若某非终结符标志为“是”，则删去该非终结符，若进而使得某产生式右部为空，则置该式左部的非终结符标志为“是”，并删除该非终结符为左部的所有产生式，如“S”。 II．若某非终结符标志为“否”，则删去该产生式，若使得左部为该非终结符的产生式都被删去，则置该非终结符标志为“否”，例如“C”。 ③ 重复上述步骤，直到扫描完一遍文法的产生式，非终结符标志位不再改变为止。 FIRST集合 结合本例，由①中(I)、(II)得知例中对应非终结符D的标志改为“否”，对应非终结符A、B的标志改为“是”。经过①中(I)、(II)两步后文法中的产生式只剩下：S→AB和C→AD，也就是只剩下右部全是非终结符串的产生式。再由②中的(I)步扫描到产生式S→AB时，在数组中A、B对应的标志都为“是”，删去后S的右部变为空，所以S对应标志置为“是”。最后由②中的(II)扫描到产生式C→AD时，其中A对应的标志为“是”，D对应的标志是“否”，删去该产生式后，再无左部为C的产生式，所以C的对应标志改为“否”。结果如下表。 FIRST集合 （2）绘制文法关系图 按下述步骤绘制文法关系图。 ① 每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符A的结点用其FIRST(A)标记。 ② 若有产生式A→αXβ，且α ε，则从对应A的结点到对应X的结点连一条箭弧。 FIRST集合 （3）求解FIRST 按下述步骤从关系图求解FIRST。 ① 凡是从FIRST(A)结点有路径可到达的终结符点所标记的终结符为FIRST(A)的成员。 ② 若某非终结符能够 ε，则将ε加入该非终结符的FIRST集中。 至此，可以求得本例的结果： FIRST(S)={b,a,ε} FIRST(A)={b,ε} FIRST(B)={a,ε} FIRST(C)={a,b,c} FIRST(D)={a,c} FIRST集合 二、根据通用算法构造FIRST （1）文法符号的FIRST 对于文法中的每一个符号X?（VN∪VT），构造FIRST（X）时，只要连续使用下列步骤，直至FIRST集不再扩大为止。 步骤1．若X?VT，则FIRST（X）＝{X}； 步骤2．若X?VN，则考查以X为左部的每一条产生式： ① 若X→?是一条产生式，则??FIRST（X）； ② 若X→Y1Y2…Yn是产生式： (I) 若Y1, …, Yi-1都?VN且都能 ?（其中1≤i≤n），则FIRST(Y1)-{?}，FIRST(Y2)-{?}，…，FIRST(Yi-1)-{?}和FIRST(Yi)都包含在FIRST(X)中； (II) 若所有的FIRST(Yi)均能 ?，i＝1, 2, …, k，则把?加到FIRST(X)中。 FIRST集合 FIRST集合 【例】已知文法G[S]如下： S→aAd A→BC B→b |ε C→c |ε 求各个非终结符的FIRST集。 【解】由上述算法，容易求各个FIRST集： FIRST(S)={