第四章自顶向下的语法分析.ppt

第四章 自顶向下的语法分析 * * 预测分析程序的总控程序 算法4.5 预测分析程序的总控程序。 输入：输入串w和文法G=(V, T, P, S)的分析表M; 输出：如果w属于L(G)，则输出w的最左推导，否则报告错误; 步骤： 1．将栈底符号#和文法开始符号S压入栈中; 2．repeat 3． X:=当前栈顶符号; 4． a:=当前输入符号; 5． if X∈T∪{#} then 6． if X=a then 7． {if X≠# then begin 8． 将X弹出栈; 9． 前移输入指针 10． end} * * 预测分析程序的总控程序 11． else error 12． else 13． if M[X, a]=Y1Y2…Yk then begin 14． 将X弹出栈; 15． 依次将Yk，…，Y2，Y1压入栈; 16． 输出产生式X→Y1Y2…Yk 17． end 18． else error 19．until X=# * * FOLLOW( E)={ ), # } FOLLOW( T)={ +, ), # } FIRST(TE)={(,id} FIRST(+TE)={+} FIRST(FT)={(,id} FIRST(*FT)={*} FIRST((E))={(} FIRST(id)={id} E→TE E→+TE’|ε T→FT T→*FT’|ε F→(E)|id 例4.10 考虑简单算术表达式文法的实现 * * 简单算术表达式文法的预测分析表 * * 对输入串id+id*id进行分析的过程（在黑板上同时画出语法树） 栈 输入缓冲区 输出 #E id+id*id# #ET id+id*id# E→TE #ETF id+id*id# T→FT #ETid id+id*id# F→id #ET +id*id# #E +id*id# T→ε #ET+ +id*id# E→+TE #ET id*id# * * #ETF id*id# T→FT #ETid id*id# F→id #ET *id# #ETF* *id# T→*FT #ETF id# #ETid id# F→id #ET # #E # T→ε # # E→ε 输出的产生式序列形成了最左推导对应的分析树 #ET id*id# * * 4.3.2 预测分析表的构造算法 算法4.6 预测分析表(LL(1)分析表)的构造算法。 输入：文法G; 输出：分析表M; 步骤： 1．对G中的任意一个产生式A→α, 执行第2步和第3步; 2． for ?a?FIRST(α), 将A→α填入M[A, a]; 3． if ε?FIRST(α) then ?a?FOLLOW(A),将A→α填入M[A, a]; if ε?FIRST(α)#?FOLLOW(A) then将A→α填入M[A, #]; 4．将所有无定义的M[A, b]标上出错标志。 * * 预测分析法的实现步骤 1. 构造文法 2. 改造文法：消除二义性、消除左递归、提取左因子 3. 求每个候选式的FIRST集和变量的FOLLOW集 4. 检查是不是 LL(1) 文法 若不是 LL(1),说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息” 5. 构造预测分析表 6. 实现预测分析器 * * 4.3.3 预测分析中错误的处理 对语法变量A，如果M[A,a]无定义，并且a属于FOLLOW(A)，则增加M[A,a]为“同步点”(synch), 同步记号选择方法如下： 把FOLLOW(A)的所有符号放入语法变量A的同步记号集合中。 把高层结构的开始符号加到低层结构的同步记号集合中。 把FIRST(A)的符号加入A的同步记号集合。 如果语法变量可以产生空串，若出错时栈顶是这样的语法变量，则可以使用产生空串的产生式。 如果符号在栈顶而不能匹配，则弹出此符号。 * * 4.4 递归下降分析法—一个设想 1. 对应每个变量设置一个处理子程序： A→X1