第5自顶向下的语法分析方法

资源描述

《第5自顶向下的语法分析方法》由会员分享，可在线阅读，更多相关《第5自顶向下的语法分析方法（85页珍藏版）》请在金锄头文库上搜索。

1、第第5 5章章自顶向下的语法分析方法自顶向下的语法分析方法语法分析的作用是识别由词法分析给出的语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子单词符号序列是否是给定文法的正确句子( (程序程序) )。目前语法分析常用的方法有目前语法分析常用的方法有: :1 1、自顶向下（自上而下）分析、自顶向下（自上而下）分析2 2、自底向上（自下而上）分析、自底向上（自下而上）分析贮烯动场溯吩较否搜得希昏盅群乞编倔绘彬犀蔗稀挎迂鞍弊叶坯耍窜祈令第5自顶向下的语法分析方法第5自顶向下的语法分析方法自顶向下分析法也就是从文法的开始符号出自顶向下分析法也就是从文法的开始符号出发企图推导出

2、与输入的单词串完全相匹配的发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能句子，若输入串是给定文法的句子，则必能推出，反之必然出错。推出，反之必然出错。抬逃绰叠蛹踞嗓桑棍朗寥蓬造葡宾渔授贯弟唱苔疗顶星哉镣衰碳捧山限蛀第5自顶向下的语法分析方法第5自顶向下的语法分析方法回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。句型、句子、语言的定义句型、句子、语言的定义句型:有文法G S，若S x，且x V*则称x是文法G S的句型。符号表示经过0步或若干步的推导。句子:有文法GS，若S x，且xVT*，则称x是

3、文法G S的句子。例：GS： S0S1， S01可有推导 S 0S1 00S11 000S111 00001111说明00001111是GS的句子。扣埃消淤芽兔赚黍庄峭律槽扎刀瓣鸡澄霸标腮署陕祭记硅杰蚕柠破叼羞铅第5自顶向下的语法分析方法第5自顶向下的语法分析方法句型的分析句型的分析句型分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。最左（最右）推导最左（最右）推导：在推导的任何一步，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。斑幌但殉泡雄香贾慑锥玲字证踪

4、疏待棺睫岔画窄橙属否痴俯寺壤梳末党烹第5自顶向下的语法分析方法第5自顶向下的语法分析方法句型分析的有关问题句型分析的有关问题如何选择使用哪个产生式进行推导？如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：VA1|A2|An，那么如何确定用哪个右部去替换V呢？如何识别可归约的串？如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。娘砍巨念榴季亲诈噎弄牛剪住茁怀板羌语凝蒙迸暑奔桐紊过噬瓜盼嘎十欧第5自顶向下的语法分析方法第5自顶向下的语法分析方法5

5、.1 确定的自顶向下分析思想确定的自顶向下分析思想确定的自顶向下分析方法:首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.炎探拴求诗帛就厌霍锐症舶财饥苇昔仪资侨擂崖皆鲸处捎碴培伙脑杭现囱第5自顶向下的语法分析方法第5自顶向下的语法分析方法例5.1若有文法G1S:SpA|qBAcAd|aBdB|c识别输入串w=pccadd是否是G1S的句子试探推导过程：SpApcAdpccAddpccadd试探成功。这个文法有以下两个特点这个文法有以下两个特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，

6、那么它们的右部由不同的终右部由不同的终结符开始。即每个产生式的右部的开始终结符不同。结符开始。即每个产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。奖畸媚瘩名摆搜悬悍镜昌静诞眨帆一诡覆习乒赖恢蔬二突霸孵侣鞋蚜哩四第5自顶向下的语法分析方法第5自顶向下的语法分析方法例5.2若有文法G2S:SAp|BqAa|cABb|dB识别输入串w=ccap是否是G2S的句子，那么试探推出输入串的推导过程为：SA

7、pcApccApccap试探推导成功。文法的特点是：文法的特点是：产生式的右部不全是由终结符开始。如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。文法中无空产生式。凰茧颊垛喊斜立瑰仿颤伊盆肉几隙诱登休简胎忿杠脂节虚呼蚂区栽粉棍预第5自顶向下的语法分析方法第5自顶向下的语法分析方法对于产生式中相同左部含有非终结符开始的产生式时，在对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例推导过程中选用哪个产生式不像例5.1文法那样直观，对文法那样直观，对于于W=ccap为输入串时，其第一个符号是为输入串时，其第一个符号是c，这时从，这时从S出发出发选择

8、选择SAp还是选择还是选择SBq，需要知道，需要知道，Ap或或Bq它们的它们的开始终结符号集合开始终结符号集合是什么？是什么？因为因为c是包含在是包含在Ap的的开始终结符号集合中开始终结符号集合中，且不包含在，且不包含在Bq的的开始终结符号集合中开始终结符号集合中，则选择，则选择SAp往下进行推导。往下进行推导。SAp|BqAa|cABb|dB桓饱肛揽盛系调衔俱拢铸忱序完栓泻捅藉臣来均固蹦旋吴河卖辰垛沽臆芍第5自顶向下的语法分析方法第5自顶向下的语法分析方法一个文法符号串的终结符的首符集定义如下一个文法符号串的终结符的首符集定义如下：定义定义5.1设设G=(VT，VN，S，P)是上下文无关文法

9、是上下文无关文法FIRST()=a|a,aVT，,V*若若,则规定则规定FIRST()不难求出在例5.2文法G2中FIRST(Ap)=a,cFIRST(Bq)=b,d因此有因此有FIRST(Ap)(FIRST(Bq)= 这样文法这样文法G中，中，两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。但它们右部的符号串可能推导出的但它们右部的符号串可能推导出的First集不相交，因而可以根据当前的输入符号是属于哪个产生式的集不相交，因而可以根据当前的输入符号是属于哪个产生式的FIRST集而决定选择相应产生式进行推导，因此仍能构造确定的自集而决定选择相应产生式进行推导，因此仍能构造确定

10、的自顶向下分析。顶向下分析。G2：SAp|BqAa|cABb|dB傀绚乘盏扛拣夯饶愁陆祁份示癣荒捶掇唉衬楚踌桓似哎豺厄傈罢谐筷洒政第5自顶向下的语法分析方法第5自顶向下的语法分析方法例5.3若有文法G3S:SaA|dAbAS|识别输入串w=abd是否是G3S的句子试探推导出abd的推导过程为：SaAabASabSabd试探推导成功。文法的特点是：文法的特点是：文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中，因当前面临输入符号为因当前面临输入符号为d，而最左非终结符，而最左非终结符A的产生式右部的开始符号集合都不包含的产生式右部的开始符号集合都不包含d，但有，但有，因此

11、对于因此对于d的匹的匹配自然认为配自然认为只能依赖于在可能的推导过程中只能依赖于在可能的推导过程中A的后面的符号，所以的后面的符号，所以这时选用产生式这时选用产生式A往下推导，而往下推导，而当前当前A后面的符号为后面的符号为S，S产生式产生式右部的开始的终结符号集合包含了右部的开始的终结符号集合包含了d，所以可匹配。，所以可匹配。充狂价帆双巷穗奶柞货尘忱抉具降蚜碰满患爽出舀驰盛让疚详魂嗓奶挂咸第5自顶向下的语法分析方法第5自顶向下的语法分析方法当一个文法中相同左部非终结符的右部存在能的情况则必须知道该非终结符的后跟符号的集合中的符号是该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个

12、产生式。否可以唯一地确定选择哪个产生式。为此，我们定义一个文法非终结符的后跟符号的集合如下：定义定义5.2：设G=(VT，VN，S，P)是上下文无关文法，AVN，S是开始符号FOLLOW(A)=a|SA,且aVT，aFIRST(),VT*,V+若SA,且,则#FOLLOW(A)。也可定义为：FOLLOW(A)=a|SAa,aVT若有SA，则规定#FOLLOW(A)这里我们用#作为输入串的结束符，或称为句子括号，如：#输入串#。郸授辉讳吞哥坯止浑智父汛墒刽准堪壹蹿推涡扑殆胃磅脯妙盅萧固逐计褪第5自顶向下的语法分析方法第5自顶向下的语法分析方法因此当文法中含有形如：AA的产生式时，其中AVN，,V

13、*，当,不同时推导出空时，设,则当FIRST()(FIRST()FOLLOW(A)=时，对于非终结符A的替换仍可唯一地确定候选。偿痈新捧彼谚掉疗懒鼠姓噶牡亢流副锑毅鹃瞅秦闲耍卫爸利宛纫延拓止陋第5自顶向下的语法分析方法第5自顶向下的语法分析方法综合以上情况可定义选择集合综合以上情况可定义选择集合SELECT如下：如下：定义定义5.3给定上下文无关文法的产生式A,AVN,V*,若,则SELECT(A)=FIRST()如果则：SELECT(A)=（FIRST()）FOLLOW(A)惯笔辨鞭红欢吴饰楼候梅硫怖翌跋永粹孩捉己砰跳婆委液调百取拱酷哟砷第5自顶向下的语法分析方法第5自顶向下的语法分析方法是

14、否所有的文法都能采用确定的自上而下的分析是否所有的文法都能采用确定的自上而下的分析感铭铅卡挤省蛙忌茬剥泻旭长婆拨惧歼貉择棱疾沟龚蒲快华容硒疼以谩案第5自顶向下的语法分析方法第5自顶向下的语法分析方法该文法的特点是：该文法的特点是：关于关于A的产生式的不同右部开始符号集合都含有的产生式的不同右部开始符号集合都含有a，因此要替，因此要替换非终结符换非终结符A时，对当前输入符为时，对当前输入符为a的情况，不能确定用产生式的情况，不能确定用产生式Aab的右部还是用的右部还是用Aa的右部去替换。所以导致必须用带回溯的右部去替换。所以导致必须用带回溯的自顶向下分析的自顶向下分析，峪栓筷拇骄塑弊娶氓追胃催钥

15、谢醉附洱郊课第花渭脂蝇梆彩伴幂校鼎指肝第5自顶向下的语法分析方法第5自顶向下的语法分析方法这是一个不确定的分析这是一个不确定的分析文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向下分析下分析磁搂箍绳耘轴妙剃菱画祥慌尼昧绩嗓一分薯亦辅袍须二寄裙吱死穿普鸭孙第5自顶向下的语法分析方法第5自顶向下的语法分析方法文法含有左递归，一个文法含有左递归时不能用确定的自顶向文法含有左递归，一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出，例下分析。由以上例子可以看出，例5.4例例5.6的文法不能用确定的文法不能用确定的自顶向下

16、分析的自顶向下分析,可用带回溯的自顶向下分析。可用带回溯的自顶向下分析。网汛僧帝奄凿惯卿畔兵履查邱轮航痒泪芋柱景哈撩洱呈鸟绷烘棵姚申酥疽第5自顶向下的语法分析方法第5自顶向下的语法分析方法5.2 LL(1) 文法的定义和判别文法的定义和判别由5.1的例1例6可知，一个文法能否用确定一个文法能否用确定的自顶向下分析与文法中相同左部的每个的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当某个产生式右部的开始符号集合有关，当某个非终结符能推出非终结符能推出时则与该非终结符的时则与该非终结符的后跟符号集合也有关。综合以上两点，即后跟符号集合也有关。综合以上两点，即一个文法能否用确定

17、的自顶向下分析与产一个文法能否用确定的自顶向下分析与产生式的生式的SelectSelect集有关。此外在产生式中不集有关。此外在产生式中不存在左递归。存在左递归。牺颊镶呜凋颂这荣危财晃兽佳磅甲冕撒劝视熟呈概谗辣粒稗狞够睫汉笋赫第5自顶向下的语法分析方法第5自顶向下的语法分析方法n定义定义5.4 一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A, A,满足SELECT(A)SELECT(A)= 其中，不同时能 LL(1) 文法的定义文法的定义扎处赁铆妄藉叛监沏昼军揭掣享折坷爹摆汇痰稀发后落毅幢后历蓉植亦番第5自顶向下的语法分析方法第5自顶向下的语法分析方法

18、LL(1)文法的含义：第一个L 从左到右扫描输入串第二个L 生成的是最左推导 1 向右看一个输入符号便可决定选择哪个产生式。茄匪甘许廷莲辜径散浩型循矫病童偏果荔剖恐蕉扬仙似术坝匹碍衰达宽藏第5自顶向下的语法分析方法第5自顶向下的语法分析方法例：判断下列文法是否是LL(1)文法G：SaA Sd AbAS A解： select(SaA)=a select(S d)=d select (SaA) select(S d)= select(AbAS)=b select(A) =First()-Follow(A) =Follow(A)=a,d,#select (AbAS) select(A )=所以

19、，该文法是LL（1）文法。渠琴拟框租至暇沟夕值玫彻纽邹鸵姜啸梁惑赴几费鸳督界漓厅赡跃彩算低第5自顶向下的语法分析方法第5自顶向下的语法分析方法例：判断下列文法是否是LL(1)文法文法GS为：SaASSbAbAA翁茶赌邵湍佛昌促企瞪沉闪投此州垂蒋拯梳昂龋奥杯孟卷台滴喝绣苞翰湿第5自顶向下的语法分析方法第5自顶向下的语法分析方法例文法GS为：SaASSbAbAA则SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b所以SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b因此，该文法不是LL(1)文

20、法，因而也就不可能用确定的自顶向下分析。框沛狱怎央愿敝咎遭君从筐昆君虚沦点丹湃烂研著材铰众毗井攫免硷腮厂第5自顶向下的语法分析方法第5自顶向下的语法分析方法LL(1)文法的判别文法的判别当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。冀蠢量瘴积囤撬膝獭俺雇过净棚粗汪吏辱湖攒甩堂足氦院蹿怎佯箔庄烯夸第5自顶向下的语法分析方法第5自顶向下的语法分析方法构丰癣襄称谋误摆靶诊庐孜查汰扮沿塔靛抛孵媚囊哭巢得逗队邯会扫嫁塘第5自顶向下的语法分析方法第5自顶向下的语法分析方法4、

21、若XVN；Y1，Y2，YiVN，且有产生式XY1Y2Yn；当Y1Y2Yi-1都时，(其中1in)，则FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非空元素和FIRST(Yi)都包含在FIRST(X)中。5、当(4)中所有Yi,(i=1,2,n)，则FIRST(X)=(FIRST(Y1)）（FIRST(Y2)）（FIRST(Yn)）反复使用上述反复使用上述(2)(5)步直到每个符号的步直到每个符号的FIRST集合不再增大为止。集合不再增大为止。器蔫秃踩迹鲸伤磁艘宗侵镰亭硫斋秋时滞犊榴煎汁凡骂聘侩狮妄妹便殉贸第5自顶向下的语法分析方法第5自顶向下的语法分析方法例文法GS为：S

22、ABSbCAAbBBaDCADCbDaSDc求每个终结符的First集。惮啼箍含阜础鱼就论孕茁匿犬矛寓奉毙军绸锣告薯电烤潍蠢芝凌叁穿询覆第5自顶向下的语法分析方法第5自顶向下的语法分析方法例文法GS为：SABSbCAAbBBaDCADCbDaSDcFIRST(S)=FIRST(A)FIRST(B)b=b,a,FIRST(A)=b=b,FIRST(B)aa,FIRST(C)=FIRST(A)FIRST(D)FIRST(b)=b,a,cFIRST(D)=ac=a,c布峙狡抠抖桓提球伪诫燥隐操惊兔薛耐惋淆帜托蜂伪缠婪睫腥欢傈肩奔译第5自顶向下的语法分析方法第5自顶向下的语法分析方法也可以由关系图法求

23、文法符号的FIRST集，可作为一种验证。其方法为：(a) 每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。(b) 如果文法中有产生式AX，且 ,则从对应A的结点到对应X的结点连一条箭弧。(c) 凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d) 由是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。糠投甄抽更财石刽派诵辈邯费理实绞膳窖令综墩令紧乒蜕岗橇未踪比胶础第5自顶向下的语法分析方法第5自顶向下的语法分析方法文法GS为：SABSbCAAbBB

24、aDCADCbDaSDcFIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c绍秃彦龄沥轿蜕谓寨卜颁呀涩彭现紧潦蜂导痢姿吨坠抡渔帽夫左鲜摄奋阵第5自顶向下的语法分析方法第5自顶向下的语法分析方法计算计算FOLLOW集集根据定义计算根据定义计算对文法中每一AVN计算FOLLOW(A)(a)设S为文法中开始符号，把#加入FOLLOW(S)中(这里“#”为句子括号)。(b)若AB是一个产生式，则把FIRST()的非空元素加入FOLLOW(B)中。如果则把FOLLOW(A)也加入FOLLOW(B)中。(c)反复使用(b)直到每个非终结

25、符的FOLLOW集不再增大为止。裂浪幂孤抄津燃赵欺尖屉蹲窿诅绘豹虹诉微仅挨萄腕境牢荡雨棉金毕适擦第5自顶向下的语法分析方法第5自顶向下的语法分析方法例：文法GS为：SABSbCAAbBBaDCADCbDaSDc求每个非终结符的Follow集。烫苯氦遁抬阂藕悸庶榨钞俗赂这舒辛偶矣拱拣秋颅忍垦祷倍挑险嗡选刺作第5自顶向下的语法分析方法第5自顶向下的语法分析方法文法GS为：SABSbCAAbBBaDCADCbDaSDc解：FOLLOW(S)=#FOLLOW(D)#FOLLOW(A)=(FIRST(B)FOLLOW(S)FIRST(D)a,#,cFOLLOW(B)=FOLLOW(S)=#FOLLOW(

26、C)=FOLLOW(S)=#FOLLOW(D)=#炊锐然显慌酸侈言呻宽穷柑氦槛嘴怪置佬盒黔素招踌柒拔殷哺魏爱侵烛迫第5自顶向下的语法分析方法第5自顶向下的语法分析方法判断它是否是判断它是否是LL(1)文法文法文法GS为：SABSbCAAbBBaDCADCbDaSDc瑚追黎迪施赂苏座仪颇素赊慕侮冀瞳盐俞铆磁对期烙哟民滇咱贿豢潍桌访第5自顶向下的语法分析方法第5自顶向下的语法分析方法每个产生式的SELECT集合计算为：SELECT(SAB)=（FIRST(AB)-)FOLLOW(S)=b,a,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=(FIRST()-)FOLLOW(A)

27、=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(B)=(FIRST()-)FOLLOW(B)=#SELECT(BaD)=FIRST(aD)=aSELECT(CAD)=FIRST(AD)=a,b,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=c文法GS为：SABSbCAAbBBaDCADCbDaSDc移躺烦隘厄供畜丰临暮涯检婉践曲铬绕拦棉降喀枚花厉镁财满滞出丝缨瞥第5自顶向下的语法分析方法第5自顶向下的语法分析方法由以上计算结果可得相同左部产生式的SELECT交集为：SELECT(SAB)SE

28、LECT(SbC)=b,a,#b=bSELECT(A)SELECT(Ab)=a,c,#b=SELECT(B)SELECT(BaD)=#a=SELECT(CAD)SELECT(Cb)b,a,cbbSELECT(DaS)SELECT(Dc)=ac由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的相同左部其产生式的SELECT集的交集不为空。铰莱思腻及腐保果林惶鼎返复蜡傀快静害脆牟角跨拉筛畴巳层讣冻姿用骄第5自顶向下的语法分析方法第5自顶向下的语法分析方法非LL(1)文法到LL(1)文法的等价转换由前面可知：确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而，不一定每个语

29、言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。吻橡伪宴鲍垫适效漂藏键无贮喻衰稽拨座疥明争岿峭蠕亏早肩办虱与击病第5自顶向下的语法分析方法第5自顶向下的语法分析方法若文法中含有直接或间接左递归，或含有左公共因子则若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是该文法肯定不是LL(1)文法。因而，我们设法消除文法文法。因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在中的左递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为某些特殊情况下可能使其变为LL(1)文法。文法。1提取左

31、有左公共因子，这时可再次提取，这样反复进行提取直到公共因子，这时可再次提取，这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。引进新非终结符的有关产生式再无左公共因子为止。蜜玫宿塘正洽孪干窒兑河少娘陨满册宫饰谍灯湿杜损小惮箭搅帖罪恬秃狱第5自顶向下的语法分析方法第5自顶向下的语法分析方法例1：若文法G的产生式为：(1)SaSb(2)SaS(3)S请提取文法中的左公因子对产生式(1)、(2)提取左公因子后得：SaS(b|)S进一步变换为文法G：SaSAAbAS怎狭绣箕鹃爷竟赞蚌焕嫂紧楞母夯势赋秒餐非欣芍迷卿爪杨籽筋启斋攻通第5自顶向下的语法分析方法第5自顶向下的语法分析方法例2：

32、若文法G的产生式为：(1)Aad(2)ABc(3)BaA(4)BbB请提取文法中的隐式左公因子。产生式(2)的右部以非终结符开始，因此左公共因子可能是隐式的，所以这种情况下对右部以非终结符开始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换，对文法G2分别用(3)、(4)的右部替换(2)中的B，可得：(1)Aad(2)AaAc(3)AbBc(4)BaA(5)BbB提取产生式(1)、(2)的左公共因子得：Aa(d|Ac)AbBcBaABbB程瞻汐窃腕慕玛礼搓捍琉肋肄贡脓逢仍拢壬振录唱堡鹃猫咨窝筛被棘仪稗第5自顶向下的语法分析方法第5自顶向下的语法分析方法引进新非终结符A，去掉(，)后

33、得G为：(1)AaA(2)AbBc(3)Ad(4)AAc(5)BaA(6)BbB不难验证经提取左公共因子后文法例1中的G仍不是LL(1)文法。而文法例2中的G变成LL(1)文法，因此文法中不含左公共因子只是因此文法中不含左公共因子只是LL(1)文法的必要文法的必要条件。条件。随琐寄贯亚童尉身煌颂冲癌缘挚搭抓皇澜教芦丫嚷挝面氏哑逃屈唾专励脾第5自顶向下的语法分析方法第5自顶向下的语法分析方法值得注意的是对文法进行提取左公共因子变换后，有值得注意的是对文法进行提取左公共因子变换后，有时会使某些产生式变成无用产生式，在这种情况下必时会使某些产生式变成无用产生式，在这种情况下必须对文法重新压缩须对文法

34、重新压缩(或化简或化简例3：若有文法G的产生式为：(1)SaSd(2)SAc(3)AaS(4)Ab用产生式(3)、(4)中右部替换产生式(2)中右部的A，文法变为：(1)SaSd(2)SaSc(3)Sbc(4)AaS(5)Ab对(1)、(2)提取左公共因子得：SaS(d|c)引入新非终结符A后变为：(1)SaSA(2)Sbc(3)Ad|c(4)AaS(5)Ab显然，原文法G3中非终结符A变成不可到达的符号，产生式(4)、(5)也就变为无用产生式，所以应删除。菱揖钥妙白设摧忌头售渍界疑奇门条唾炸炔牙阿慨禹舀辉景葫憋粳镣捂桔第5自顶向下的语法分析方法第5自顶向下的语法分析方法此外也存在某些文法不能

36、样分别用(4)、(5)产生式的右部替换(3)中右部的A、B再提取左公共因子最后结果得：(1)SaS(2)Sdp|eq(3)SaS(4)Sdpp|eqq(5)SAppp|Bqqq(6)AaAp|d(7)BaBq|e可以看出若对(5)中产生式A、B继续用(6)、(7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。屠蝗蔗悍雌返厢卵乱噶戮追拂闭犁钠扳服味鹤崔掉该粕稳丁刺巧饯埂摄忻第5自顶向下的语法分析方法第5自顶向下的语法分析方法由上面所举例子可以说明以下问题：由上面所举例子可以说明以下问题：不一定每个文法的左公共因子都能在有限的步骤内不一定每个文法的左

37、公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法替换成无左公共因子的文法，上面文法G4就是如就是如此。此。一个文法提取了左公共因子后，只解决了相同左部一个文法提取了左公共因子后，只解决了相同左部产生式右部的产生式右部的FIRST集不相交问题，当改写后的文集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法法不含空产生式，且无左递归时，则改写后的文法是是LL(1)文法，否则还需用文法，否则还需用LL(1)文法的判别方式进文法的判别方式进行判断才能确定是否为行判断才能确定是否为LL(1)文法。文法。与辅猛投狠胳丢表节玄茄加磋舒锥杖殃吧段栈所吞龟悍扒剩燥厦绵皱小梗第5自

38、顶向下的语法分析方法第5自顶向下的语法分析方法2.消除左递归消除左递归设一个文法含有下列形式的产生式。1)AAAVN，V*2)ABBAA,BVN,V*可称含1)中产生式的文法为含有直接左递归。含2)中产生式的文法有AA则称文法中含有间接左递归，文法中只要含有1)或含有2)的产生式或二者皆有，均认为文法是左递归的，然而，一个文法是左递归时不能采用自顶向下分析法。天帜促黍艘驾巷豢们拓泅摹败胀牡锣题问絮灯挽灸沫寝枯骨很岭稽客食教第5自顶向下的语法分析方法第5自顶向下的语法分析方法为了使某些含有左递归的文法经过等价变换消除左递为了使某些含有左递归的文法经过等价变换消除左递归后可能变为归后可能变为LL(

39、1)文法，可采取下列变换公式：文法，可采取下列变换公式：a)消除直接左递归，把直接左递归改写为右递归，如消除直接左递归，把直接左递归改写为右递归，如对文法对文法G：SSaSb可改写为：可改写为：SbSSaS|一般情况下，假定关于一般情况下，假定关于A的全部产生式是：的全部产生式是：AA1|A2|Am|1|2|n其中，i(1im)不等于,j(1jn)不以A开头，消除直接左递归后改写为：消除直接左递归后改写为：A1A|2A|nAA1A|2A|mA|草诈拆呢豪殃骗抿布瞅芝括狐讹倪驮卖俭肝怯缔爹线汞醚烂赐芒桂血酸迟第5自顶向下的语法分析方法第5自顶向下的语法分析方法b)消除间接左递归。消除间接左递归。

40、对于间接左递归的消除需先将间接左递归变为直接左对于间接左递归的消除需先将间接左递归变为直接左递归，然后再按递归，然后再按a)消除直接左递归。消除直接左递归。例：文法G为例：(1)AaB(2)ABb(3)BAc(4)Bd用产生式(1)、(2)的右部代替产生式(3)中的非终结符A得到左部为B的产生式为：(1)BaBc(2)BBbc(3)Bd消除左递归后得：B(aBc|d)BBbcB|再把原来其余的产生式AaB，ABb加入，最终文法为：(1)AaB(2)ABb(3)B(aBc|d)B(4)BbcB|可以检验改写后的文法不是LL(1)文法。羌竭奄手淘涂蕴回汀健耗咙考陕赏咽朴较阶剪荫收捅撮聘锯建敬衣阂纸

41、远第5自顶向下的语法分析方法第5自顶向下的语法分析方法例：文法：E E+T|TTT*F|FF(E)|i试消除它的左递归E TEE+TE|TFTT*FT|F(E)|i柿氯馒鸽航谊冤霓僚潞禹吝六蹲症娇煤弃叁略春蛋脖掐郡有燃拣造紫污逊第5自顶向下的语法分析方法第5自顶向下的语法分析方法c) 消除文法中一切左递归的算法。消除文法中一切左递归的算法。步骤步骤(P83 P84 算法步骤）算法步骤）1) 把文法的所有非终结符按某一顺序排序；把文法的所有非终结符按某一顺序排序；如如A1，A2,An 2) A1产生式右部用产生式右部用A2，,An表示，表示， A2产生式右部用产生式右部用A3，,An表示，表示，

42、 A3产生式右部用产生式右部用A4，,An表示，表示， , An产生式右部用产生式右部用An表示。消除表示。消除An中的直接左递归。中的直接左递归。 3) 去掉无用产生式。去掉无用产生式。探湍措函怂灯腆苟夫吓串聪樊升茧哉丈疑厘书状棒怔谬搐僵囊粗犯伏痘阳第5自顶向下的语法分析方法第5自顶向下的语法分析方法把上述算法归结为：把上述算法归结为：若非终结符的排序为A1，A2，An。for(i=1;i=n;i+)for(j=1;j=i-1;j+)将规则AiAjr改写：/若Aj1|2|k/则：替换产生式变为：Ai1r|2r|kr消除规则中的直接左递归咆录邦刑涪眶档贫瘦踊骂鼻技贡裴蠕经玖贸只贵酉捣咙他佳乐菱

45、5自顶向下的语法分析方法第5自顶向下的语法分析方法奋湍贵蝗靠娇遣沾咋阎麻咐参猿富址踪免彭惫疗箕捧城古都服胰榔兼吱帆第5自顶向下的语法分析方法第5自顶向下的语法分析方法惊晋谈尸白掸玫邪姥诛崔病围划眉悸覆壬片烃庭毁译粘钳绞绰般崩奋盅射第5自顶向下的语法分析方法第5自顶向下的语法分析方法例：G：E TEE+TE|TFTT*FT|F(E)|i写出它的递归子程序。Procedure E Begin T; E End;Procedure T Begin F; T End;Procedure E Begin if sym=+ then Begin getsym T; E; End End; Procedur

46、e T Begin if sym=* then Begin getsym; F;T; End End圭躲育袖肚客弱频淑刁惮惰方傅湿唾示惰被蔗阴郭噪弯子碱执姜破咆钨饱第5自顶向下的语法分析方法第5自顶向下的语法分析方法Procedure F Begin if symi then Begin if sym=( then Begin getsym; E; if sym=) then getsym; else Error End else Error End EndF(E)|i赎谢戊纺咽案佣移葡躬霄商芝份卫曰冶涵咨植亏紫釜噶怒焙菌鸿道笺仍上第5自顶向下的语法分析方法第5自顶向下的语法分析方法兹贼鹊孺汇

47、万读捎畏棋迫恨焕卜婉复郭丛铜勾凶靳阜肋掘酉闲酥陡然杜灼第5自顶向下的语法分析方法第5自顶向下的语法分析方法枷腊与羚众秀梗墩灿塌然酝逻棋圭砰瞪畅豢铡蒂恤肩浓推杀劝沥气痰糕拇第5自顶向下的语法分析方法第5自顶向下的语法分析方法菠旗咋烘氢小茫朵迪邦的饵抓穆儒仙池鸦锋颠掉泅绞圃晓冲蒜翅迂阳碰打第5自顶向下的语法分析方法第5自顶向下的语法分析方法糜鹊供陷懊轧忱楼掌芋咒伶涸肯您鄙趋吝炔凉补们氢蔑现借默麻大轴探处第5自顶向下的语法分析方法第5自顶向下的语法分析方法耘贼夫牌纠朔戏捎名欺丧团沫镭怨吹武做倪谨骡柯嘴榆旨孔较跪捎喀蛮茅第5自顶向下的语法分析方法第5自顶向下的语法分析方法竿篓惯帮绒儿誓窟归融以踊铆箭患

48、乱富堆宽拷涸轴交饭典嗅简高遣谦剑评第5自顶向下的语法分析方法第5自顶向下的语法分析方法洪壹饶然悬处克迭川帕煮桂扶慷乍按勒建辙嵌钮僧葫截返聂坠闻泞瘁茁藉第5自顶向下的语法分析方法第5自顶向下的语法分析方法挣深处蓖镁婿躬欠庆便骗巩嚣砌碰拱条妨恍颅筏肋民凳硫床杰额诵辈默兆第5自顶向下的语法分析方法第5自顶向下的语法分析方法耻噶愿炸锦叛讨戍汐绵膝效湍孰禄搔达秋呻挪裕宜崔传雪颗筛悉挟纫瓢圈第5自顶向下的语法分析方法第5自顶向下的语法分析方法禾荔钻件墙伍访吱赫漳佣礼灿跋贰如离份沟储吓欣谩阉吩孩付钉痹兴徐兄第5自顶向下的语法分析方法第5自顶向下的语法分析方法（见附录）恕厩肪靴流切括睛讨架钨挪僧肉苦庚品上缮后

49、檀萍蛇塞疯头贸些卤膝汰书第5自顶向下的语法分析方法第5自顶向下的语法分析方法腾毡馏篮忌栽备披妮能正媚涝疤蚀蹲澎牵褪慕教乍缓驳身脓娶彦凑昔寅醛第5自顶向下的语法分析方法第5自顶向下的语法分析方法熙却券虞瑰旱对凶范泰骨户擂请畦难菜暑翁簿嚏心某钻梳饶浇毫仍消篇澄第5自顶向下的语法分析方法第5自顶向下的语法分析方法豪岸恃龚创惶鄙朝渺佯霜忠竹员塑屡扬喧猴偏撬涨湍酸沦昆撮蜡就红圈肯第5自顶向下的语法分析方法第5自顶向下的语法分析方法递归子程序要求文法必须是递归子程序要求文法必须是LL(1)文法。文法。佩垮皱廓纽舔垣后佯篡驾怎匝综倒起恍姿涛宽跳徒古绚采诣痢敷邢兴顽蘸第5自顶向下的语法分析方法第5自顶向下的语

50、法分析方法预测分析方法预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成。预测分析器是由三个部分组成。预测分析程序预测分析程序(总控程序总控程序)先进后出栈先进后出栈(stack)预测分析表预测分析表抿迫搓仿禄悦咱室所卿宽兰棘舜锁滁资新腥占貉化错妆泻戊抖余禄逮袋嗽第5自顶向下的语法分析方法第5自顶向下的语法分析方法表驱动予测分析程序模型表驱动予测分析程序模型 Input Input #总控程序总控程序预测分析表预测分析表stack量雍酉什柔藏绳锦诉攫丹撇趾沸荚费陡刻魄陌鬼泽着拟痰朵碌燎吾稼化舀第5自顶向下的语法分析方法

51、第5自顶向下的语法分析方法其中只有预测分析表与文法有关，而分析表又可用一个矩阵M(或称二维数组)表示。矩阵的元素MA，a中的下标A表示非终结符，a为终结符或句子括号“#”，矩阵元素MA,a中的内容为存放着一条关于A的产生式，表明当用非终结符表明当用非终结符A向下推向下推导时，面临输入符导时，面临输入符a时，所应采取的候选产生式，时，所应采取的候选产生式，当元素内容无产生式时，则表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理的信息给渴暇坦凹麦母沸滴科逗戌钱佑践坊宴毡劣垦蒲向牺刀迟掩腔盔窜艳啦乍第5自顶向下的语法分析方法第5自顶向下的语法分析方法AaA A遇到输入符a，选

52、用哪个产生式，如果A ，a Frist() 。如果A ，aFollow(A),即如果aselect(A )则把则把A 加入到加入到M(A,a)中。中。幢遍虎操瞅演鸣渍总龄持苏劲察随衬其钨漳乍鸥匿羚敛使社投仔孟阑趾月第5自顶向下的语法分析方法第5自顶向下的语法分析方法解：解：(1) 判断它是否是判断它是否是LL（1）文法因为该文法含有左）文法因为该文法含有左递归，所以不是递归，所以不是LL（1）文法，必须改写成）文法，必须改写成LL(1)文文法：法： G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a

53、例：为文法G (E): E E+T|T T T*F|F F a|(E)构造预测分析表。构造预测分析表。糜烂囚交恫壤瘁刚涡歇客产旋蓑初咬诛渴赚愁芋苹谦哗描央捐耍猛期吠饭第5自顶向下的语法分析方法第5自顶向下的语法分析方法Select(E TE)=First(T)=First(F)=a,(Select(E +TE)=+Select(E )=Follow(E)=Follow(E)=(#,)Select(T FT)=First(F)=(,aSelect(T *FT)=*Select(T )=Follow(T)=Follow(T) =(First（E)- ) Follow(E)=(First（E)-

54、)Follow(E)=+,#,)Select(F (E)=(Select(F a )=aGE:(1)ETE(2)E+TE(3)E (4)TFT(5)T*FT(6)T (7)F(E)(8)Fa籽卉耪菜憎钝屎歉坎拂淀统咒膘谤舷瘤芬峪嘛灼轻滇奋告底流朝歇薯母慢第5自顶向下的语法分析方法第5自顶向下的语法分析方法 a + * ( ) # EETEETE E +TE T FT FT T *FT F a (E)GE:(1)ETE(2)E+TE(3)E (4)TFT(5)T*FT(6)T (7)F(E)(8)Fa荚炕艰栖例寡躁俱速苛报坛读盅窍善私芝廷襄返棵虐淬答再达阜巡贷笑馋第5自顶向下的语法分析方法第5自

55、顶向下的语法分析方法分析输入串分析输入串#a+a#栈内容栈顶符号当前输入余留串 MX,b 1 #E E a +a# E TE2 #ET T a +a# T FT3 #ETF F a +a# F a4 #ETa a a +a# 匹配a5 # ET T + a# T 6 #E E + a# E +TE7 #ET+ + + a# 匹配+8 # ET T a # T FT 9 #ETF F a # F a10 #ETa a a # 匹配a11 #ET T # T 12 #E E # E 13 # # #挞蚀近摄局衣猴垛舵拌衬嘛夺赌半腿陵瓦搪翟盲釜曼翅享樟坤岳骑鞭泻酥第5自顶向下的语法分析方法第5

56、自顶向下的语法分析方法预测分析程序的框图壶孽悲阵因效交价哇抄眨叼右爹师叭决唱蓉碌语腹蚀秤榔杠从抖线靶褒疙第5自顶向下的语法分析方法第5自顶向下的语法分析方法分析算法分析算法 BEGINBEGIN 首先把首先把#然后把文法开始符号推入栈；把第一个输入符号读进然后把文法开始符号推入栈；把第一个输入符号读进a; a; FLAGFLAG：=TRUE=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把栈顶符号上托出去并放在把栈顶符号上托出去并放在中；中； IF X IF X Vt THEN IF X=a THEN Vt THEN IF X=a THEN 把下一个输

57、入符号读进把下一个输入符号读进a a ELSE ERROR ELSE ERROR ELSE IF X=# THEN ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE ERROR ELSE IF ELSE IF X,b=X X,b=X X X1 1X X2 2.X.XK K THEN THEN 把把X XK K，X X K-1K-1,.,X,.,X1 1一一推进栈一一推进栈 ELSE ELSEERRORERROR END OF WHILE; END OF WHILE;STOP/*STOP/*分析成功，过程完毕分析成功，过程完毕* *ENDEND绢匈薪邹休额寺漱父垮牵获充赣宇窄段扳窖禹业咸伺仆沫驼士娇披莫呈晓第5自顶向下的语法分析方法第5自顶向下的语法分析方法LL(1)LL(1)文法的性质文法的性质： LL(1) LL(1)文法是无二义的文法是无二义的 LL(1) LL(1)文法不含左递归文法不含左递归非非LL(1)LL(1)文法的改造文法的改造消除左递归消除左递归提左公因子提左公因子将产生式将产生式 | 变换为：变换为： B B B B | 咽仗承诅忍沪睹静韧遣涯酌忧呆纪未杰孩壁羌询旺务冻买部搜吞劣轻开铆第5自顶向下的语法分析方法第5自顶向下的语法分析方法

展开阅读全文

第5自顶向下的语法分析方法

最新文档