编译原理学习笔记

2020年03月08日更新

Sets

G=(VT，VN，S，P)是上下文无关文法

First sets

• 若X∈VT，则FIRST(X)＝{X}。(简单讲，终结符的FIRST集就是它本身)

• 若X∈VN，且有产生式X→a…，a∈VT， 则 a∈FIRST(X)X→ε,则ε∈FIRST(X)。　（简单讲，若是非终结符X，能推导出以终结符a开头的串，那么这个终结符a属于FIRST（X），若X能够推导出空符号串ε，那么空符号串ε也属于X的FIRST集）

• X→Y…是一个产生式且Y ∈VN 则把FIRST(Y)中的所有 非空符号串ε元素 都加入到FIRST(X)中。

• 若X∈VN；Y1，Y2，…，Yi∈VN，且有产生式X→Y1 Y2 … Yn；当Y1 Y2 … Yn-1都能推导出ε时，则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yn-1)的所有非空元素和FIRST(Yn) 包含在FIRST(X)中。

即: FIRST(X)=(FIRST(Y1)－{ε} ）∪（FIRST(Y2)－{ε} ）∪…∪（FIRST(Yn-1)－{ε}）∪{FIRST(Yn)} ⑤.当(4)中所有Yi 能够推导出ε,(i=1,2,…n)，则 FIRST(X)=(FIRST(Y1)－{ε}）∪（FIRST(Y2)－ {ε}∪…∪（FIRST(Yn) －{ε}）∪{ε}

• 终结符的FIRST就是自己
• 对于产生式，如果最左边的能推导出ϵ
• 则再开始推第二个，并把最左边的FIRST并到自己的FIRST里。

S→AB
S→bC 
A→ε
A→b
B→ε　　
B→aD
C→AD
C→b
D→aS
D→c

FIRST(A)={ε,b} FIRST(B)={a,ε} FIRST(S)={b,a,ε} FIRST(D)={a,c} FIRST(C)={b,a,c} #是因为A中有ε才去看D的

Follow sets

X→AB 则 first(B)∈follow(A) 并且 follow(X) ∈follow(B) B→*ϵ 则follow(X) ∈follow(A)

• 设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里“$” 为开始符号)。
• 若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入 FOLLOW(B)中。如果β能够推导出ε 则把FOLLOW(A)也加入FOLLOW(B)中。

• 反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。

• 产生式的右边如果存在，则把FIRST(右边)中除了ϵ 之外所有的符号加入FOLLOW(自己)
• 如果产生式的右边能推导出ϵ, 或者不存在，则产生式左边的FOLLOW也在自己的里面。 (左右是箭头的左右)

E   →  TE'
E'  →  +TE' | ε
T   →  FT'
T'  →  *FT' | ε
F  →  (E) | i

FIRST(F)={ (,i } FIRST(T’)={ *,ε } FIRST(T) ={ (,i } #F中没有ε, 所以到F为止 FIRST(E’)={ +,ε } FIRST(E)={ (,i }

FOLLOW(E)=｛ $,) }; FOLLOW(E’)={ $,) }
FOLLOW(T)={+,),$}
FOLLOW(T’)= FOLLOW(T)= {+,),$}
FOLLOW(F)={*,+,),$}