FIRST、FOLLOW、SELECT

LL(1)文法

    遍历所有表达式，取具有相同左部的表达式的select集合，将这些具有相同左部表达式的select集合取交集。
    只要有一组相同左部表达式交集不为空，则该文法非LL1文法。
    只有所有相同左部表达式交集都不为空，则为LL1文法。

FIRST

S->AB|bC
A->ε|b
B->ε|aD
C->AD|b
D->aS|c

FIRST(S)= (FIRST(A)-{ε})∪(FIRST(B)- {ε})∪{ε}∪{b}={a,b,ε}
因为A的first有ε，B的first有ε，S->AB，所以是(FIRST(A)-{ε})∪(FIRST(B)- {ε})，然后S->bC，所以再加一个b，就是(FIRST(A)-{ε})∪(FIRST(B)- {ε})∪{b}。

First(A)= {b, ε}
没什么好解释的

First(B)={a,ε}
ε不用解释，就是B->ε，所以有它，a就是因为B->aD，第一个非终结符是a所以有a，那要不要加上D的first呢，就是a和c，答案是不用，就只要aD里面的a就可以。

First(C)={a,b,c}
C->AD这一句，AD都是非终结符，所以要找A和D的first集。D的是a，c。A的是b，ε。因为不是AD同时都能推出ε，所以C的first是A和D的first的并集减去ε，还要加上b，因为有C->b这一句。

First(D)={a,c}

First(AB)={a,b,ε}
AB同时能够推出ε，所以First(AB)就是A和B的First的并集减去ε再并上ε。

两个非终结符的要看是不是他们两个同时能推出ε，能就有ε；要是有一个不能推出ε，那First集就没有ε。

FOLLOW

从开始符号S开始推导，开始符号的follow里面一定要有#。
所以开始符号的S的follow集要有#。
follow是找->后面的。

比如找S的follow，就要看谁的->后面有S。
D->aS里面有S，然后再看D->aS的S后面有没有别的符号，没有就加上D的follow集。如果有，就加上后面那个字母的first集里面除了ε以外的符号，再看这个字母能不能推出ε，如果能，就再加上->左边的那个字母的follow。
Follow(S)->Follow(D)={#}

Follow(A)={a,c,#}
看A的follow，首先找所有->后面有A的，找到了S->AB，C->AD。先看S->AB，A后面有B，所以要加上B的first集里面除了ε的其他符号，再看B能不能在有限的步骤里推出ε，有B->ε这句，所以能，就要再加上->左边的S的follow集，所以目前的A的follow集里面有a,和follow(S)，再看C->AD这一句，A后面有D，所以要加上D的first集里面除了ε的其他的，再看D能不能在有限的步骤里推出ε，D不能，所以不用加->左边的C的follow，所以A的follow就是a,Follow(S),a,c，但是如果有重复的，就只要一个，所以最终就是a,c,follow(S)，这个follow(S)到后面还有算出来，不能就这么写。

Follow(B)={#}
看B的follow，找所有->后面有B的，找到了S->AB，看B后面有字母吗？没有，就加上->左边的S的follow，所以Follow(B)=Follow(S)

Follow(C)={#}
看C的follow，找所有->后面有C的，找到了S->bC，看C后面有字母吗？没有，就加上->左边的S的follow集，所以Follow(C)=Follow(S)

Follow(D)={#}
看D的follow，找所有->后面有D的，找到了B->aD，C->AD，这两句D后面都没有字母，所以加上->左边的B和C的follow，所以Follow(D)=Follow(B)∪Flollow(C)

Follow(S)={#}∪Follow(D)，Follow(D)=Follow(B)+ Follow(C)，所以Follow(S)={#}∪Follow(B)∪Follow(C)，Follow(B)= Follow(S)，Follow(C)= Follow(S)，所以Follow(S)={#}，Follow(B)={#}，Follow(C)={#}，Follow(D)={#}，Follow(A)={a,c,#}。

SELECT

SELECT(S->AB)，AB都能推出ε，所以SELECT(S->AB)=First(AB)-ε+Follow(S)，所以SELECT(S->AB)={a,b,#}

SELECT(S->bC)，bC不能推出ε，所以是First(bC)，结果是{b}

SELECT(A->ε)，A能推出ε所以是First(ε)-ε+Follow(A)，结果是{a,c,#}

SELECT(A->b)，这里的A是推出ｂ，不是ε所以是first(b)，结果是{b}

SELECT(B->ε)，B能推出ε，所以是First(ε)-ε+Follow(B)，结果是{#}

SELECT(B->aD)，这里B不能推出ε，所以是First(aD)，结果是{a}

SELECT(C->AD)，这里D不能推出ε，所以算AD不能推出ε，就是First(AD)，结果是{a,b,c}

SELECT(C->b)，C推不出ε，所以是First(b)，结果是{b}

SELECT(D->aS)，这里不能推出ε，所以是First(aS)，结果是{a}

SELECT(D->c)，这里D不能推出ε，所以是First(c)，结果是{c}