程序设计语言编译原理第三版第4章.pptVIP

一、预测分析程序工作过程 1.总控程序算法描述 2.分析过程举例 §4.5 预测分析程序 (1)初始化:依次把’#’和文法开始符号压入分析栈, 将输入串第一个符号读入a; §4.5 预测分析程序 1.总控程序算法描述 (2)若X∈VT ①X＝a≠”#”, 则将X从分析栈顶退掉, a指向下一个输入字符; (3)若X∈VN , 则查分析表. 此时对M[X,a]: ②X＝a＝”#”, 表示分析成功,停止分析过程; ③X≠a ,表示不匹配的出错情况. ①若M[A, a]={ X→X1X2…X k },则 将X从栈中弹出并将Xk,Xk-1,…,X1一一推进栈; ②若M[A, a]中为空白,则表示出错,可调用语法出错处理子程序. 下面用预测分析方法对输入串i+i*i# 进行分析，给出栈的变化过程如下： 步骤 分析栈 剩余输入串 所用产生式 2 #E?T i+i*i# E?TE? T?FT ? 1 #E i+i*i# 2.分析过程举例 §4.5 预测分析程序 3 #E?T?F i+i*i# 4 #E?T?i i+i*i# 5 #E?T? +i*i# 6 #E? +i*i# F?i i匹配 T??ε E??+TE? 步骤 分析栈 剩余输入串 所用产生式 2 #E?T i+i*i# T?FT ? 步骤 分析栈 剩余输入串 所用产生式 7 #E?T+ +i*i# +匹配 8 #E?T i*i# T?FT 9 #E?T?F i*i# F ? i 10 #E?T?i i*i# i匹配 11 #E?T? *i# T? ? *FT? 12 #E?T?F* *i# *匹配 13 #E?T?F i# F ? i 14 #E?T?i i# i匹配 15 #E?T? # T? ? ε 16 #E? # E? ? ε 17 # # 接受 预测分析器模型 §4.5 预测分析程序 §4.5 预测分析程序 二. 预测分析表的构造 1. FIRST集合构造 2. FOLLOW集合构造 3. LL(1)分析表的构造 §4.5 预测分析程序 二. 预测分析表的构造 1.First(X)集合构造，X∈VT∪VN 定义：FIRST(α)={a|α a.....} 特别是，若α ε，则规定ε∈FIRST (α). * * 即: first(α)是α的所有可能推导的开头终结符或可能的?。 1.A→a ...... A→α1| α2|......| αn FIRST(A) 2.A→ε 3.A→X1 X2......XK * a..X2....... FIRST(X1)/{ε} * ε ε X2....... FIRST(X2)/{ε} εε......ε * * (1) (2) (3) §4.5 预测分析程序 1.First(X)集合构造，X∈VT∪VN 例：求下题的FIRST集 E→TEE→+TE|εT →FTT→*FT|εF →(E)|i FIRST(E)= FIRST(E‘)=FIRST(T)=FIRST(T‘)=FIRST(F)= {（，i } {+, ε} {*, ε} {（, i } {（, i } §4.5 预测分析程序 1.First(X)集合构造，X∈VT∪VN 2.Follow(A)集合构造，A∈VN §4.5 预测分析程序 定义: Follow(A)={ a | A?…Aa…,a∈ VT } 若S?…A,则规定#∈follow(A) * * 即: follow(A)是所有句型中出现在紧接A之后的终结符或“＃”。 (2)B→αAβ FOLLOW(A) (3)B→αA * (1)若A是开始符号 # FIRST(β)/ {ε} FOLLOW(B) FIRST(β)/{ε}∪FOLLOW(B) ε §4.5 预测分析程序 2.Follow(A)集合构造，A∈VN E→TEE→+TE|εT→FTT→*FT|εF→(E)|i FIRST(E)= {( ,i } FIRST(E)={+,ε} FIRST(T)={( ,i } FIRST(T)={*,ε} FIRST(F)= {(,i } FOLLOW(E)= FOLLOW (E)=FOLLOW (T)=FOLLOW (T)=FOLLOW (F)= { # , ) } { #, ) } { +,#, ) } { +,#, ) } { *,+,#, )