构造FIRST集、FOLLOW集、 LL(1)预测分析表

构造FIRST集、FOLLOW集、 LL(1)预测分析表

FIRST集构造对于一条产生式:S->…

若右边第一个符号是终结符或者ε,则 将其加入FIRST(S)

若右边第一个符号是非终结符,则将其FIRST集加入FIRST(S)

若右边第一个符号是非终结符,且随后紧跟多个非终结符,这是判断是否有ε

若第i个非终结符有ε集,则可将i+1个非终结符去除ε的FIRST集加入FIRST(S)

若所有非终结符都能够推导出ε,则将ε也加入FIRST(S)

e.g 若给出G(S)如下

12345S->ABCDA->a|εB->b|εC->cD->d

则FIRST(S)= a,b,c

FOLLOW集构造

将所有产生式的候选式的非终结符都找到,定位到求解的FOLLOW集的非终结符的位置,从当前位置挨个检查

先检验这个非终结符的右边有无别的符号,例如A->aBC,求FOLLOW(B)时,其右侧有非终结符C的

将右边符号的FIRST集中非空符号加入当前符号的FOLLOW集,若右边符号FIRST含有ε,则将FOLLOW(A)也加入FOLLOW(B)

若右边没有符号了,例如这里的 C,那么可以将 FOLLOW(A)中的元素全部加入到 FOLLOW(C)中

断当前符号是不是文法的开始符号,比如 G[A] 中的非终结符 A 就是 G[A] 文法的开始符号,如果是的话就将“#”也加入到 FOLLOW集中去

e.g 若给出文法如下

123E->E+T|TF->(E)|iT->F|T*E

FIRST

FOLLOW

E

( i

# ) +

F

( i

# ) + *

T

( i

# ) + *

预测表的构造首先构造出预测分析表的第一行与第一列,第一行为文法出现的所有终结符以及‘#’(注意:没有 ε ,因为 Follow 集不含 ε),第一列为文法出现的所有非终结符

对文法G的每个产生式A->α 执行如下步骤:

对每个a∈First(α),把 A->α 加入M[A,a]

若 ε∈First(α),则对任何b∈Follow(A) ,把 A-> ε加至M[A,b]中

对如下文法

123S->AaS|BbS|dA->aB->ε|c

举个例子,对于第一个产生式,FIRST(AaS)={a},则将S->AaS加入到[S,a]

a

b

c

d

S

S->AaS

A

B

而对于B->ε,计算FOLLOW(B)中的所有元素将其加入。FOLLOW(B) = { b },所以将产生式加入到M[B,b]

a

b

c

d

S

S->AaS

A

B

B->ε

最后得到的完整LL(1)分析表

a

b

c

d

S

S->AaS

S->BbS

S->BbS

S->d

A

A->a

B

B->ε

B->c

相关文章

qq自定义封面怎么设置
下载365App

qq自定义封面怎么设置

📅 08-03 👁️ 5139
使用命令行编译、运行Java程序
office365打不开doc文件

使用命令行编译、运行Java程序

📅 01-10 👁️ 1594