Fork me on GitHub

FIRST、FOLLOW、SELECT

LL(1)文法

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

FIRST

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

1
2
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}
1
2
First(A)= {b, ε}
没什么好解释的
1
2
First(B)={a,ε}
ε不用解释,就是B->ε,所以有它,a就是因为B->aD,第一个非终结符是a所以有a,那要不要加上D的first呢,就是a和c,答案是不用,就只要aD里面的a就可以。
1
2
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这一句。
1
First(D)={a,c}
1
2
First(AB)={a,b,ε}
AB同时能够推出ε,所以First(AB)就是A和B的First的并集减去ε再并上ε。

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

FOLLOW

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

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

1
2
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)到后面还有算出来,不能就这么写。
1
2
Follow(B)={#}
看B的follow,找所有->后面有B的,找到了S->AB,看B后面有字母吗?没有,就加上->左边的S的follow,所以Follow(B)=Follow(S)
1
2
Follow(C)={#}
C的follow,找所有->后面有C的,找到了S->bC,看C后面有字母吗?没有,就加上->左边的S的follow集,所以Follow(C)=Follow(S)
1
2
Follow(D)={#}
D的follow,找所有->后面有D的,找到了B->aD,C->AD,这两句D后面都没有字母,所以加上->左边的B和C的follow,所以Follow(D)=Follow(B)∪Flollow(C)
1
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

1
SELECT(S->AB),AB都能推出ε,所以SELECT(S->AB)=First(AB)-ε+Follow(S),所以SELECT(S->AB)={a,b,#}
1
SELECT(S->bC),bC不能推出ε,所以是First(bC),结果是{b}
1
SELECT(A->ε),A能推出ε所以是First(ε)-ε+Follow(A),结果是{a,c,#}
1
SELECT(A->b),这里的A是推出b,不是ε所以是first(b),结果是{b}
1
SELECT(B->ε),B能推出ε,所以是First(ε)-ε+Follow(B),结果是{#}
1
SELECT(B->aD),这里B不能推出ε,所以是First(aD),结果是{a}
1
SELECT(C->AD),这里D不能推出ε,所以算AD不能推出ε,就是First(AD),结果是{a,b,c}
1
SELECT(C->b),C推不出ε,所以是First(b),结果是{b}
1
SELECT(D->aS),这里不能推出ε,所以是First(aS),结果是{a}
1
SELECT(D->c),这里D不能推出ε,所以是First(c),结果是{c}
Your support will encourage me to continue to create!