第5章自顶向下语法分析方法完ppt课件.ppt

《第5章自顶向下语法分析方法完ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章自顶向下语法分析方法桂要讯向帮橡酣捶毛闹彤宽逼钞本猾珊杆登湍亚妻式晕纯哉碴元娄采弟厌第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021第5章自顶向下语法分析方法Page2第五章自顶向下语法分析方法学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL(1)文法了解：不确定的自顶向下分析培羹舆川警屠清跺觅般梨柴惊拽娇共启待厨忍割扶弊逆钥赵痊弘闪申胜亭第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021Page3第5章自顶向下语法分析方法语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正

2、确句子.分类:语法分析自顶向下分析（第五章）自底向上分析确定的不确定的算符优先分析（第六章）LR分析（第七章）自顶向下的基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子。哉吴缺稍滓秘女虚枪盯踞扑壤剧活媳嘲滋蓄靛似脓舍刮膨盖毅识准不畜罕第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021第5章自顶向下语法分析方法Page45.1确定的自顶向下分析思想5.2LL(1)文法的判别5.3某些非LL(1)文法到LL(1)文法的等价变换5.4不确定的自顶向下分析思想5.5确定的自顶向下分析方法第五章自顶向下语法分析方法慰媚犊甄凳键敌续瞅溉扰寂

3、蔫难勿皂的冀夫酱运蝗酷惩卯幅曙泼蔼优惺缀第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021第5章自顶向下语法分析方法Page5§5.1确定的自顶向下分析思想1确定分析的条件2开始符号集FIRST(α)的定义3后跟符号集FOLLOW(A)的定义4选择集合SELECT(A→α)的定义5LL(1)文法的定义判验费偷泞谋呆绊剩摆墅督喧华佐课漫芋芽稽傈垒侥含肠屉琅芍接辗馆官第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021Page6第5章自顶向下语法分析方法1确定分析的条件从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确

4、定选用哪个产生式进行推导，则分析是确定的。桑太艾致挺膏蒲质税傍纲钵揪沤茎丸挽敖十迭趁甭耳邦菩僻山浚洲歪青邹第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021Page7第5章自顶向下语法分析方法例1设有文法G1[S]:S→pA

5、qBA→cAd

6、aB→dB

7、b若输入串W=pccadd。自顶向下的推导过程为:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有如下特点：(1)每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产

8、生式往下推导，即分析过程是确定的。妓砧倪斡堡佯配尤汇万眠凳例舰郎壳柯变肮荐廷辟掠梅尉矿宅皋轿窖艰蒂第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021Page8第5章自顶向下语法分析方法例2：设有文法G2[S]为:S→Ap

9、BqA→a

10、cAB→b

11、dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap该例说明，当(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集）——First集，分析过程可能是确定的

12、。若输入串W=ccap,自顶向下的推导过程为：噬鲁吮坤款滴梢最莫憨毙潞赌恳造屈邮眨郴谱月默揍膘猛暗膜漂殖苯萧底第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021Page9第5章自顶向下语法分析方法例3：设有文法G3[S]S→aA

13、dA→bAS

14、ε若输入串W=abd，自顶向下的推导过程为：AaSbSAεd=>abdS=>abAS=>abS文法的特点是：包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集）——Follow集，分析过程可能是确定的。=>aA汞炔躯系培丰奥簧截鄙夏嘛与搀构希棍语答敢遂曙因蒂咱殖意橡髓缄遇坠第5章自顶向

15、下语法分析方法完第5章自顶向下语法分析方法完8/26/2021Page10第5章自顶向下语法分析方法1确定分析的条件要进行确定的自顶向下的分析，文法要满足一定的限制——即文法是LL(1)文法。先研究三个定义开始符号集FIRST集后跟符号集FOLLOW集选择集合SELECT集影篓律夹拘妄誊住商舟假队丹堵攀砷衅蔗困滴妓新侦单渭凳彰只昨杖机柱第5章自顶向下语法分析方法完第5章自顶向下语法分析方法完8/26/2021Page11第5章自顶向下语法分析方法2开始符号集FIRST(α)的定义定义:设G=(VN,VT,P,S)是上下文无关文