自顶向下语法分析.pptx

S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序错误处理符号表管理

知识结构

任务：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。两大类分析方法：自顶向下分析自底向上分析语法分析的任务

自顶向下分析算法的基本思想为：+若x?S则x?L(G[S])否则x?L(G[S])G[S]存在主要问题:回溯问题,左递归问题主要方法：递归子程序法、LL分析法自底向上分析算法的基本思想为：+若x?S则x?L(G[S])否则x?L(G[S])G[S]存在主要问题:“可归约串”的识别问题主要方法：算符优先分析法、LR分析法

5.1自顶向下分析法自顶向下分析的一般过程从S出发采用最左推导，试图逐步推出输入串α,α?L(G[S])?S作为语法树的根，试图自上而下地为α构造一棵语法树若叶结点从左向右排列恰好α，则表示α是文法的句子，而这棵语法树就是句子α的语法结构若构造不出语法树，则α不是文法的句子

自顶向下分析方法分类确定的不确定的回溯

S→pA|qBA→cAd|aB→dB|c识别输入串w=pccadd是否是G1[S]的句子【例】G1[S]:SpApcAdpccAddpccadd试探成功试探推导过程：每个产生式的右部都由终结符号开始如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始这个文法的特点：

S→Ap|BqA→a|cAB→b|dB识别输入串w=ccap是否是G2[S]的句子【例】G2[S]:SApcApccApccap试探成功试探推导过程：产生式的右部不全是由终结符开始如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始文法中无空产生式这个文法的特点：

1.FIRST集FIRST(α)：从α可能推导出的所有开头终结符号或ε对于文法G的所有非终结符的每个候选式?，其终结首符号集称为FIRST集，定义如下：?，则规定?∈FIRST(?)若?【例】S→aAbA→cd|ca…，a∈VTFIRST(?)={a|?FIRST(aAb)={a}FIRST(cd)={c}FIRST(c)={c}【例】S→AaA→a|?FIRST(a)={a}FIRST(?)={?}FIRST(Aa)={a}FIRST(S)={a}FIRST(A)={c}FIRST(S)={a}FIRST(A)={a,?}

（1）若α=aβ，且a∈VT，则a∈FIRST(α)；例：FIRST(i)={i}FIRST(+TE)={+}E→TEE→+TE|?T→FTT→*FT|?F→(E)|i构造FIRST集的算法（2）若α=Xβ，X∈VN，且有产生式X→b…，则把b加入到FIRST(α)中；例：FIRST(FT)={(,i}??

（3）若α=X1X2…Xn，其中Xi∈VN,1≤i≤n；①将FIRST(X1)中的一切非ε的终结符加进FIRST(α)；②若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α)；③若ε∈FIRST(X1)且ε∈FIRST(X2),则将FIRST(X3)中的一切非ε的终结符加进FIRST(α)；④依此类推，若对于一切1≤i≤n,ε∈FIRST(Xi)，则将ε加进FIRST(α)。E→TEE→+TE|?T→FTT→*FT|?F→(E)|i例：FIRST(FT)=注意：要顺序往下做，一旦不满足条件，过程就要中断进行FIRST(F)-{ε}={(,i}

【例】G2[S]:S→Ap|BqA→a|cAB→b|dB识别输入串w=ccap是否是G2[S]的句子试探推导过程：SApcApccApccap试探成功FIRST（Ap）＝｛a，c｝FIRST（Bq）＝｛b，d｝

FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(,i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(,i}【例】G[E]E→TEE→+TE|?T→FTT→*FT|?F→(E)|i计算文法中非终结符的First集合

【例】G3[S]:S→aA|dA→bAS|ε识别输入串w=abd是否是G3[S]的句子试探推导过程：SaAabASabSabd试探成功这个文法的特点：1、含有空产生式2、非空产生式右部首符号集合两两不相交3、紧跟该非终结符右边可