设有文法G[A]: A→BCc | gDB B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c 计算该文法的每一个非终结符的FIRST集和FOLLOW集。 解:(1)、FIRST集的求解:
时间: 2024-01-05 13:59:30 浏览: 343
首先,我们需要先了解一下什么是FIRST集。对于一个文法符号串,它的FIRST集就是由所有可能的最左终结符组成的集合。具体来说,对于一个文法符号串X,它的FIRST集包含以下内容:
1. 如果X是一个终结符,则FIRST(X)={X}。
2. 如果X可以推导出ε,则ε∈FIRST(X)。
3. 如果X可以推导出Y1Y2...Yk,则将ε加入FIRST(X)中,当且仅当Y1,Y2,...,Yk都可以推导出ε,或者Y1,Y2,...,Yk-1都可以推导出ε并且Yk可以推导出一个不含ε的终结符。
接下来,我们分别求解G[A]的每一个非终结符的FIRST集:
1. FIRST(A)={g,c,d},因为A可以推导出gDB、BCc和ε,其中g、c和d分别是它们的最左终结符。
2. FIRST(B)={b,ε},因为B可以推导出bCDE和ε,其中b是它的最左终结符。
3. FIRST(C)={c,d,a},因为C可以推导出DaB和ca,其中d、a和c分别是它们的最左终结符。
4. FIRST(D)={d,ε},因为D可以推导出dD和ε,其中d是它的最左终结符。
5. FIRST(E)={g,c},因为E可以推导出gAf,其中g和c分别是它们的最左终结符。
(2)、FOLLOW集的求解:
接下来,我们需要求解每一个非终结符的FOLLOW集。对于一个非终结符X,它的FOLLOW集就是由所有可能的紧跟在X后面的终结符组成的集合。具体来说,对于一个非终结符X,它的FOLLOW集包含以下内容:
1. 如果X是文法的开始符号,则将$加入FOLLOW(X)中。
2. 对于每个产生式A→αBβ,将FIRST(β)中除ε以外的所有终结符加入FOLLOW(B)中。
3. 如果存在一个产生式A→αB或者A→αBβ且ε∈FIRST(β),则将FOLLOW(A)加入FOLLOW(B)中。
接下来,我们分别求解G[A]的每一个非终结符的FOLLOW集:
1. FOLLOW(A)={$},因为A是开始符号,所以$紧跟在A后面。
2. FOLLOW(B)={c},因为存在产生式A→BCc,所以c紧跟在B后面。
3. FOLLOW(C)={b,c},因为存在产生式B→bCDE和C→DaB,所以b和c都可能紧跟在C后面。
4. FOLLOW(D)={b,c},因为存在产生式C→DaB,所以b和c都可能紧跟在D后面。
5. FOLLOW(E)={c},因为存在产生式B→bCDE和E→gAf,所以c可能紧跟在E后面。
阅读全文