自顶向下语法分析方法完.ppt

自顶向下语法分析方法完 2023/3/2第5章 自顶向下语法分析方法Page 2第五章 自顶向下语法分析方法学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解： LL(1)了解：不确定的自顶向下分析 2023/3/2第5章 自顶向下语法分析方法Page 3语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子.分类:语法分析自顶向下分析（第五章）自底向上分析确定的不确定的算符优先分析（第六章）LR分析（第七章）自顶向下的基本思想: 从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子。 2023/3/2第5章 自顶向下语法分析方法Page 45.1 确定的自顶向下分析思想5.2 LL(1)文法的判别5.3 某些非LL(1)文法到LL(1)文法的等 价变换5.4 不确定的自顶向下分析思想5.5 确定的自顶向下分析方法第五章 自顶向下语法分析方法 2023/3/2第5章 自顶向下语法分析方法Page 5§5.1 确定的自顶向下分析思想1 确定分析的条件2 开始符号集FIRST(α)的定义3 后跟符号集FOLLOW(A)的定义4 选择集合SELECT(A→α)的定义5 LL(1)文法的定义 2023/3/2第5章 自顶向下语法分析方法Page 61 确定分析的条件 从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。 2023/3/2第5章 自顶向下语法分析方法Page 7例1 设有文法G1[S]: S→pA|qB A→cAd|a B→dB|b 若输入串W=pccadd。自顶向下的推导过程为:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有如下特点： (1) 每个产生式的右部由终结符开头; (2) 同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。 2023/3/2第5章 自顶向下语法分析方法Page 8例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap若输入串W=ccap,自顶向下的推导过程为： 2023/3/2第5章 自顶向下语法分析方法Page 9例3：设有文法G3[S]S→aA|dA→bAS| ε若输入串W=abd，自顶向下的推导过程为：AaSbSAεd=>abd S=>abAS=>abS=>aA 2023/3/2第5章 自顶向下语法分析方法Page 101 确定分析的条件要进行确定的自顶向下的分析，文法要满足一定的限制——即文法是LL(1)文法。先研究三个定义开始符号集FIRST集后跟符号集FOLLOW集选择集合SELECT集 2023/3/2第5章 自顶向下语法分析方法Page 112 开始符号集FIRST(α)的定义定义: 设G=(VN, VT, P, S)是上下文无关文法，??(VN?VT)* FIRST(?) = { a ?VT | ??* a} 若??* ε 则规定ε ∈FIRST(?) 直观上说，文法符号串? 的开始符号集是由?推导出的开头的终结符（包括ε）组成。 2023/3/2第5章 自顶向下语法分析方法Page 12例文法G2[S]: S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)=FIRST(Bq)=FIRST(a)=FIRST(cA)=FIRST(b)=FIRST(dB)=由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析{a,c}{b,d}{a}{c}{b}{d}First:开始符号集 2023/3/2第5章 自顶向下语法分析方法Page 13例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap若输入串W=ccap,自顶向下的推导过程为： 2023/3/2第5章 自顶向下语法分析方法Page 143 后跟符号集FOLLOW(A)的定义定义 ： 设G=(VT, VN, P, S)是上下文无关文法，A∈VN ， FOLLOW(A)={a|S=>*…Aa…，a ∈VT}， 若有S=>* …A，则规定 # ∈FOLLOW(A) （注： # 输入串#，‘#’做为输入串的结束符） 直观上说，非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。 2023/3/2第5章 自顶向下语法分析方法Page 15例 文法G3[S]: S