自顶向下语法分析方法.pptxVIP

确定的自顶向下分析不确定的语法分析算法优先分析（第六章）自底向上分析LR分析（第七章）语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子分类:自顶向下的基本思想: 从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.5.1 确定的自顶向下分析思想5.2 LL(1)文法的判别5.3 某些非LL(1)文法到LL(1)文法的等价变换5.4 不确定的自顶向下分析思想5.5 确定的自顶向下分析方法5.1 确定的自顶向下分析思想1 确定分析的条件2 开始符号集FIRST(α)的定义3 后跟符号集FOLLOW(A)的定义4 选择集合SELECT(A→α)的定义5 LL(1)文法的定义1 确定分析的条件 从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。pAcAdcAda例1 设有文法G1[S]: S→pA|qB A→cAd|a B→dB|b 若输入串W=pccadd。自顶向下的推导过程为:G1[S]有如下特点： (1) 每个产生式的右部由终结符开头; (2) 同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。SS=pA=pcAd=pccAdd=pccaddpAcAcAa例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dB若输入串W=ccap,自顶向下的推导过程为：该例说明，当(1) 产生式右部以终结符或非终结符开头（无空产生式）；(2) 同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定SS=Ap=cAp=ccAp=ccapaAbASεd例3：设有文法G3[S]S→aA|dA→bAS| ε若输入串W=abd，自顶向下的推导过程为：S文法的特点是:包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。=abAS=abS=abd S=aA要进行确定的自顶向下的分析，文法要满足一定的限制——即文法是LL(1)文法。先研究三个定义 开始符号集FIRST 后跟符号集FOLLOW 选择集合SELECT2 开始符号集FIRST(α)的定义定义:设G=(VN, VT, P, S)是上下文无关文法， ??(VN?VT)* FIRST(?) = { a ?VT | ??* a......} 若??* ε 则规定ε ∈FIRST(?) 直观上说文法符号串? 的开始符号集是由?推导出的开头的终结符（包括ε）组成。 例文法G2[S]: S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)={a,c}FIRST(Bq)={b,d}FIRST(a)={a }FIRST(cA)={c}FIRST(b)={b}FIRST(dB)={d}由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析3 后跟符号集FOLLOW(A)的定义定义 设G=(VT, VN, P, S)是上下文无关文法，A∈VN ， FOLLOW(A)={a|S=*…Aa…，a ∈VT}， 若有S=* …A，则规定 # ∈FOLLOW(A) （注： # 输入串#，‘#’做为输入串的结束符） 直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。例 文法G3[S]: S→aA|d A→bAS|ε由S=* aA 得 # ∈FOLLOW(A) 由S=* abAS=* abAaA 得 a ∈FOLLOW(A) … =* abAd 得 d ∈FOLLOW(A) FOLLOW(A)={#,a,d}由 S=* S 得 # ∈FOLLOW(S) 由S=aA=abAS=abbASS=abbASaA …=abbASd FOLLOW(S)={#,a,d}说明：对于非终结符A的两个产生式 A→bAS 和 A→ε，当输入符号∈FIRST(bAS)={b}时，选A→bAS推导，当输入符号∈FOLLOW(A)={#,a,d }时，选A→ε推导。由于FIRST(bAS)∩FOLLOW(A)=ф，所以可进行确定的自顶向下分析。4 选择集合SELECT(A→α)的定义定义 对给定的上下文无关文法的产生式A→α，A∈VN，α∈V*，若α≠*ε,则SELECT(A→α)=FIRST(α)若α=*ε, 则SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A) 解释 当A面对应输入符a，在自顶向下的分析中应选择这