编译原理 第四章 语法分析—自上而下分析
构造算法：
1、对文法开始符号S，将“#”臵于FOLLOW(S)中。 即FOLLOW(S) = ? # ?。
2、若A →?B? 是一个产生式，则把FIRST（β）-{ε}加至 FOLLOW(B)中。
3、若A →?B是一个产生式，或A→?B? 是一个产生式，而 ???（即??FIRST（?））；则把FOLLOW(A)加至FOLLOW(B)中。
例 文法G
E →TE` E`→+TE`|ε T →FT` T`→*FT`|ε F→（E）|i
求FOLLOW（E）：
因为 F→（E） ，所以FIRST（））加入FOLLOW(E)中， FOLLOW(E) = ? ) ? ；
又因为E→TE`,E是文法的开始符号，则#加至FOLLOW(E)中，所以
FOLLOW(E)= ? # ? U FOLLOW(E)=? #,) ?。 求FOLLOW（E`）：
因为E→TE`, 满足算法(3)若A →?B是一个产生式，则 把FOLLOW(A)加至FOLLOW(B)中，所以
制作人：李明新 共28页第11页 13-3-24
编译原理 第四章 语法分析—自上而下分析
FOLLOW(E`)= FOLLOW(E)U FOLLOW(E)
= ? #，) ?
求FOLLOW（T）：
因为E→TE`, 满足算法⑵若A →?B? 是一个产生式，则把 FIRST（β）\\{ε}加至FOLLOW(B)中，所以
FOLLOW(T) = FOLLOW(T) U FIRST（E`）\\{ε}
= {+}
又因为E`??，满足算法(3)若A→?B? 是一个产生式，而 ???，则把FOLLOW(A)加至FOLLOW(B)中。所以
FOLLOW(T) = FOLLOW(E) U FOLLOW(T)
= ? #，) ?U ?+? = ? #，)，+?
求FOLLOW（T`）：
因为T→FT`,满足算法(3)若A →?B是一个产生式，则 把FOLLOW(A)加至FOLLOW(B)中，所以
FOLLOW(T) = FOLLOW(T) U FOLLOW(T`)
= ? #，)，+?
求FOLLOW（F）：
因为T→FT`, 满足算法⑵若A →?B? 是一个产生式，则把 FIRST（β）\\{ε}加至FOLLOW(B)中，所以
FOLLOW(F) = FOLLOW(F) U FIRST（T`）\\{ε}= {*} 又因为T`??，满足算法(3)若A→?B? 是一个产生式，而
制作人：李明新 共28页第12页 13-3-24
编译原理 第四章 语法分析—自上而下分析
???，则把FOLLOW(A)加至FOLLOW(B)中。所以
FOLLOW(F) = FOLLOW(T) U FOLLOW(F)
= ? #，)，+? U ?*? = ? #，)，+，* ?
连续使用上述三条规则，直到每个FOLLOW不再增大为止。 FOLLOW(E)= FOLLOW(E?)= ? #，) ? FOLLOW(T)= FOLLOW(T?)= ? #，)，+ ?
FOLLOW(F)= ? #，)，+，* ? 七、证明上述文法是否为LL(1)文法
对于产生式A????:
1、若? ? ?，证明侯选式?，?的首字符集是否相交。
FIRST（?）∩FIRST（?）= Ф 例：F?（E）?i
FIRST（（）∩FIRST（i）= Ф
2、若?＝ε，证明FIRST（A）和FOLLOW（A）是否相交。
FIRST（A）∩FOLLOW（A）=φ 例：E`?+TE`??
FIRST（E`）∩FOLLOW（E`） =? +，? ?∩? ），# ?=φ
八、构造分析表的算法
1、对文法G的每个产生式A→α执行第二步和第三步； 2、对每个终结符a?FIRST(?),把A→α加至M[A,a]中；
制作人：李明新 共28页第13页 13-3-24
编译原理 第四章 语法分析—自上而下分析
3、若ε?FIRST（α），则对任何b?FOLLOW(A)把A→α（或A??）加至M[A,b]中；
4、把所有无定义的M[A，a]标上“出错标志” 例： E→TE` ， E`→+TE`′|ε
T→FT` ， T`→*FT`′|ε
F→（E）|i
求其FIRST的集合:
FIRST（E）=FIRST（T）=FIRST（F）={（，i ）} FIRST（E?）={ +，ε}，FIRST（T?）={ *，ε} 求其FOLLOW的集合:
FOLLOW(E)= FOLLOW(E?)= ? #，) ? FOLLOW(T)= FOLLOW(T?)= ? #，)，+ ?
FOLLOW(F)= ? #，)，+，* ? 根据算法构造LL（1）的分析表:
终结符 非终结符 i + * （ ） # E TE` TE` E` +TE` ? ? T FT` FT` T` ? *FT` ? ? F i (E) 九、LL（1）分析器的逻辑结构与分析程序 1、LL（1）分析器的逻辑结构
LL（1）分析法，由总控程序控制输入字符串，在一张LL（1）分析表和一个分析工作栈上运行，而完成语法分析任务的。
制作人：李明新 共28页第14页 13-3-24
编译原理 第四章 语法分析—自上而下分析
输入字符串 a1 a2 ? ai ? an
X 总控程序 分析栈 分析表 # 其中：
①分析表，实现相应的分析动作，即对[Ai，aj]，设Ai??表示当前分析工作栈顶为Ai，输入字符为aj时，应选用Ai??进行推导。
②分析工作栈，用于存放分析过程中的文法符号。分析工作栈初始化时，在工作栈顶写入一个“#”，再写入文法开始符号。
③总控程序，依据分析工作栈和分析表联合控制输入串的识别和分析。
2、分析程序的工作原理
⑴把“＃”和文法开始符号推入分析工作栈；设臵指示器的初始值，用第一个输入符号（终结符号）与分析工作栈顶文法符号进行匹配。
⑵设在某一步的分析工作栈与输入串的当前工作状态： X1X2?Xm-1Xm为分析工作栈中的当前状态；aiai+1?#为输入串的当前状态。
①若Xm?VN，则以Xm及ai组成符号对（Xm，ai）查分析表M[Xm，ai]，设Xm?UVW，将Xm从分析工作栈顶退出，并将UVW按反向写
制作人：李明新 共28页第15页 13-3-24