编译原理消除回溯

《编译原理消除回溯》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理主讲教师：于永彦计算机科学与技术专业最重要的学科基础课程淮阴工学院电话:15996198961信箱:shanshan_yyy@163.comFIRST集合引入FIRST集概念是为了在当前输入的条件下，观察哪个产生式的右部能够导出输入符号，进而决定采用哪个产生式来进行推导。显然，我们关心的是产生式右部符号串的FIRST集，即文法符号串的FIRST。这个符号串可以是任意的终结符和非终结符的组合。2FIRST集合【定义】假定是文法G的任一符号串，即(VN∪VT)*，则的首符号集定义为：可见，所谓符号串的FIRST

2、，就是指的所有可能推导的开头终结符或的集合。由定义，不难得出下面的结论：若，则；若=aA，其中A代表非终结符，则；若=Aa，则；若，则。3FIRST集合一、关系图法求解FIRST【例】已知文法G[S]如下：S→AB

3、bCA→b

4、εB→aD

5、εC→AD

6、bD→aS

7、c求所有非终结符的FIRST。【解】关系图法求解FIRST集，分为三步进行。（1）求出能推出ε的非终结符首先建立一个以文法非终结符为元素的一维数组X，对应每个非终结符设置一个标志位，以记录能否推出ε。其值有三种情况：“未定”、“是”、“否”。其次，按下述

8、步骤逐步更新标志位：4FIRST集合①依次扫描文法每一条产生式I．删除所有右部含终结符的产生式。若使得以某非终结符为左部的所有产生式都被删除，则置该非终结符的标记为“否”，例“D”。II．若某非终结符存在一条右部为ε的产生式，则置该非终结符的标志为“是”，并删除该非终结符的所有产生式，如“A”、“B”。见表的第2行。②扫描产生式右部的每一符号I．若某非终结符标志为“是”，则删去该非终结符，若进而使得某产生式右部为空，则置该式左部的非终结符标志为“是”，并删除该非终结符为左部的所有产生式，如“S”。II．若某非终结符标志为“否

9、”，则删去该产生式，若使得左部为该非终结符的产生式都被删去，则置该非终结符标志为“否”，例如“C”。③重复上述步骤，直到扫描完一遍文法的产生式，非终结符标志位不再改变为止。5FIRST集合结合本例，由①中(I)、(II)得知例中对应非终结符D的标志改为“否”，对应非终结符A、B的标志改为“是”。经过①中(I)、(II)两步后文法中的产生式只剩下：S→AB和C→AD，也就是只剩下右部全是非终结符串的产生式。再由②中的(I)步扫描到产生式S→AB时，在数组中A、B对应的标志都为“是”，删去后S的右部变为空，所以S对应标志置为“是

10、”。最后由②中的(II)扫描到产生式C→AD时，其中A对应的标志为“是”，D对应的标志是“否”，删去该产生式后，再无左部为C的产生式，所以C的对应标志改为“否”。结果如下表。SABCD初值未定未定未定未定未定扫描产生式是是否扫描文法符号是否6FIRST集合（2）绘制文法关系图按下述步骤绘制文法关系图。①每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符A的结点用其FIRST(A)标记。②若有产生式A→αXβ，且αε，则从对应A的结点到对应X的结点连一条箭弧。7FIRST集合（3）求解FIRST按下述

11、步骤从关系图求解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}8FIRST集合二、根据通用算法构造FIRST（1）文法符号的FIRST对于文法中的每一个符号X（VN∪VT），构造FIRST（X）时，只要连续使用下列步骤，直至FIRST集不

12、再扩大为止。步骤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)中。9FIRST集合10FIRST集合【例】已知

13、文法G[S]如下：S→aAdA→BCB→b

14、εC→c

15、ε求各个非终结符的FIRST集。【解】由上述算法，容易求各个FIRST集：FIRST(S)={a}FIRST(B)={b,ε}FIRST(C)={c,ε}FIRST(A)={b,c,ε}11FIRST集合（2）文法符号串的FIRST对文