SELECT集和之前讲过的FIRST集和FOLLOW集有些不同。 给出文法如下： S → ABc A → a|ε B → b|ε 我们可以求FOLLOW(S)或者FOLLOW（ABc），同样也可以求FIRST（S），FIRST(ABc)。 但是不能求SELECT(S)，SELECT(ABc)这种形式，这是不对的。应该写成SELECT（S → ABc）。 所以不同点就是，FOLLOW集和FIRST集是对产生式箭头的左部或右部进行求解；而SELECT集是对整个产生式进行求解。

同样，还是先讲3个概念： 非终结符就是大写字母。 终结符就是非终结符以外的所有符号（注意是符号，而不只局限于字母，终结符包括小写字母，数字，加号，减号，逗号等等）。 代入：对于产生式S → ABc， 箭头两侧是等价的，当箭头右部出现S时，就可以用ABc等价代替，可以方便地称为“代入”，这个做题时很好用。代入是用箭头右部代替左部，不能用左部代替右部。

做题步骤： 1.先将题目中的文法展开，将S → a|∧|(T)展开成S → a和S → ∧和S → (T) ， 全部都要展开； 2.对步骤1展开的所有式子分别求SELECT集； 3.分别对每个式子的整个箭头右部进行分析，分析能不能最终推出ε。

比如我们求SELECT（S → AB），如何判断箭头右部最终能不能推出ε呢，也就是AB最终能不能推出ε？ S → AB A → a|ε B → b|ε 因为A → ε，所以箭头右部变成了B，又因为B → ε，所以箭头右部变成了ε。

注意这里，不能和求FOLLOW集时的弄混了，这是不一样的。FOLLOW集是对箭头左部判断最终能不能推出ε，而箭头左部的非终结符可能对应多个式子，这些式子中可能有的箭头右部能推出ε而有的不能，所以不能一概而论。举例：

S → AB S → ε A → a|ε B → b 对于式子S → AB的右部AB最终是不能推出ε的（SELECT集会用到）。但是对于S却是可以推出ε的（FOLLOW集会用到）。

4.第4步：如果箭头右部最终不能推出ε，求出箭头右部的FIRST集，并将“ 箭头右部的FIRST集 ”写进这个式子的SELECT集，结束对这个式子的分析；如果能，也是先求出箭头右部的FIRST集，并将“ 箭头右部的FIRST集 - ε ”写进这个式子的SELECT集，然后再把箭头左侧符号的FOLLOW写进这个式子的SELECT集。

你可能想问，为什么第4步当箭头右部不能推出ε的情况，就不用把FIRST集中的ε减去呢 ？答案：就是因为不能推出ε，所以FIRST集一定没有符号ε，所以就不用减咯。同理，当箭头右部能推出ε，既然能推出，所以FIRST集中一定有，就要减去。 顺便强调一下，SELECT集和FOLLOW集一样，都不能有符号ε 。

已知文法： S → a | ∧ | (T) T → T , S | S | ε

题目中的文法等价于： S → a S → ∧ S → (T) T → T,S T → S T → ε 为什么要列举出来呢？因为SELECT集是对每一个产生式进行求解，列举出来不仅方便做题，而且还不容易漏下。 接下来分别对每一个式子求解SELECT集。 SELECT(S → a)：箭头右部有终结符a，一定不能推出ε，SELECT(S → a) = FIRST( a ) = { a } SELECT(S → ∧)：箭头右部有终结符∧，一定不能推出ε，SELECT(S → ∧) = FIRST( ∧ ) = { ∧ } SELECT(S → (T) )：箭头右部有终结符 (，一定不能推出ε，SELECT(S → (T)) = FIRST ( ( T ) ) = { ( } SELECT(T → T,S)：箭头右部有终结符 , ，一定不能推出ε，SELECT(T → T,S) = FIRST(T,S) = { a , ∧ , ( } SELECT(T → S)： 经过分析，箭头右部一定不能推出ε，SELECT(T → S)=FIRST(S) = { a , ∧ , ( } SELECT(T → ε)：右部能够推出ε，而 FIRST(ε)={ ε }, 将FIRST(ε) - ε写入SELECT(T → ε)。再将FOLLOW（T）写进SELECT(T → ε)。最后得到SELECT(T → ε) = { ） , }

判别文法是不是LL（1），如果不是就改写文法。 怎么判断文法是不是LL（1）呢？ 法一：上面已经求出来SELECT集，只要各SELECT集之间没有交集，就说明这个文法是LL（1）的，此时可以直接写预测分析表。如果存在交集，就不是LL（1），就要通过提左公因子或者消左递归改写文法。 法二：如果题目直接给出预测分析表，只要表格中每个格子中都只有0个或1个式子，就是LL（1）文法，否则就不是。下文“4.写预测分析表”那一段有例子。

注意，改写后的文法也不一定是LL（1）文法，仍然要进行判别。

一、消左递归： 左递归的形式： 形式（1）：直接左递归 A → AdDFJ (箭头右部第一个符号与箭头左部相同，为了方便，下文我把这个符号叫做“ 递归符号 ”） 形式（2）：间接左递归 A →Bjcfn B → Acx （将B → Acx代入 A → Bjcfn后变成A → Acxjcfn，也变成了箭头右部第一个符号与箭头左部相同） 怎么消除左递归：

步骤（1）用例：代入之前 A → B B → Aghjj B → trd A → scdbhd

（1）如果间接左递归，代入改写成直接左递归的形式。

步骤（1）用例：代入之后 A → Aghjj A → scdbhd B → trd

（2）然后增加一个新的非终结符，只要不和题目中重复即可，也可以用A’代表。 （3）将箭头左部是“ 递归符号 ”的式子全部列举出来。

步骤（4）用例：之前 A → Aghjj A → scdbhd B → trd

（4） 小步骤1：对于其中是直接左递归的式子将箭头左侧的A改写成你新加的符号，方便起见，这个新加的符号定为H。将箭头右部原来的Aghjj改写成ghjjH。总结，A → Aghjj就变成了H → ghjjH。 小步骤2：对于箭头左侧同样是A，但式子并不是左递归的式子也要改写：箭头左侧不要改，箭头右部的最右侧加上H。比如原来的式子是A → scdbhd，最后将A → scdbhd改成了A → scdbhdH。 小步骤3：最后加上一个产生式：H → ε

步骤（4）用例：之后 H → ghjjH A → scdbhdH B → trd H → ε

（5）消除用不到的式子（孤立的式子） 怎么找孤立的式子呢？ 首先找到只在箭头左侧出现字符，不难发现有A ， B（如果只找出一个只出现在箭头左侧的非终结符，就可以立刻结束这一步，因为这个符号是开始符号，而其他的式子都是有用的） 然后选择一个与文法关联度最低的一个删去，要删去所有以这个符号为产生式头的式子。相比较之下，A比B的关联度更大，因为A的产生式体中还有H，这就与H建立了关联，而B呢，没有与任何其他的非终结符建立关联，所以删去箭头左侧是B的所有式子。 最终，完成了消左递归的过程，文法如下：

H → ghjjH A → scdbhdH H → ε

二、提左公因子 强调一点：只有一个式子，有可能出现左递归，但一定不会出现左公因子。左公因子是针对多个式子，如果有文法中两个及以上式子的箭头右部有相同的前缀，就是左公因子，需要改进文法。 形式（1）：显性左公因子 A → aaadjhvfvbhf A → aaffjvbfdh 公因子：aa 形式（2）：隐式左公因子 A → aaadjhvfvbhf A → Bfdcvbfh B → affjvbfdh 公因子：a 提左公因子步骤： (0).如果是隐式左公因子，先改写成显式的； (1).找出公因子； (2).增加一个非终结符，不能和文法中的重复。为了方便，这个非终结符叫做“公因子符”； (3).用这个公因子符替换公因子； (4).增加一个式子：形如“ 公因子符->公因子 ” （5）消除用不到的式子（孤立的式子） 这个与消除左递归的相应步骤一致。

提左公因子例子： 例1：原始文法： A → aaadjhvfvbhf A → aaffjvbfdh 提左公因子之后的文法： A → Badjhvfvbhf A → Bffjvbfdh B → aa 例2：原始文法： A → aaadjhvfvbhf A → Bfdcvbfh B → affjvbfdh 先改写成显式公因子如下： A → aaadjhvfvbhf A → affjvbfdhfdcvbfh 提公因子之后的文法： A → Daadjhvfvbhf A → Dffjvbfdhfdcvbfh D → a

这一步就很简单了，对照着SELECT表就OK。 步骤如下： 1.将文法中所有的非终结符（大写字母）写在第一列。所有的终结符写在第一行，另外第一行如果没有符号#（或$），要自己加在第一行。 2.这一步主要看SELECT表。就用下面那个SLELCT表举例。从第2行开始分析，先找箭头左部是S，然后找这一行的SELECT集是（。在预测分析表中通过S行，（列共同确定一个格子，将箭头右部(S)A填入这个格子即可（那个箭头填不填根据老师要求）。 接下来看第3行，箭头左部是S，这一行的SELECT是a，就在预测分析表的行S和列a的那一格中填入箭头右部aA。 第4行和第3行类似，来看看第5行。 第5行，箭头左部是A，这一行的SELECT是（ 和 a 。如果SELECT中有多个，我们就按照先后顺序写就行。先用行A和列（找到格子，然后将SA填入。再通过行A和列a找到另一个格子，再将SA写入即可。 剩下的类似，挺简单的，自己练练吧，答案都写在预测分析表里了。

给定一个文法： S → (S)A S → aA A → +SA A → SA A → *A A → ε

SELECT表如下：

预测分析表如下：

这里我们发现，某些格子里面有两个产生式，这就说明这个文法不是LL（1）文法（如果所有的格子都只有0个或1个式子，就是LL（1）文法）。当然也可以在SELECT表中发现不同的行之间有交集，也可以得知这个文法不是LL（1）文法。