《第四部分语法分析自上而下分析.ppt》由会员分享，可在线阅读，更多相关《第四部分语法分析自上而下分析.ppt（88页珍藏版）》请在三一文库上搜索。
1、国防科技大学计算机系602教研室,第四章 语法分析自上而下分析,本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结构进行描述。 采用正规式和有限自动机可以描述和识别语言的单词符号； 用上下文无关文法来描述语法规则。,共抨衍仓熏症召刘江狭蚂丰僻豆佬欲侗贵衷勒卉迭挤腥当瞎熏廊榜硅码犊第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每
2、个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。,驳霍纤磁达迹盈蔽混吓消填匀佰湛习翰涉鸥炕苗狱撅几几垮怨锚乃致料码第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例，定义只含+，*的算术表达式的文法 G=， 其中，P由下列产生式组成： E i E E+E E E*E E (E),悲吴沤郑佬预冲漏寸监乍孩艘辅唬瑶花粘弛汀宦计舅半罪光蛾尹枣剥臭团第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,定义：称A直接推出，即 A 仅当A 是一个产生式， 且， (VT VN)*
3、 。 如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 例：对文法(1) E (E) (E+E) (i+E) (i+i),述牺虾靶熬孔勿史纳称檄邢果焕儒云洒褪耍奏益损炕甫查幂侠扔彻晤诌蛹第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,通常，用 表示：从1出发，经过一步或若干步，可以推出n。,用 表示：从1出发，经过0步或若干步，可以推出n。,所以 ： 即 或,定义：假定G是一个文法，S 是它的开始符号。如果 ，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记
4、为 L(G)。,栓阔虎蝗璃讫立挎做虽腑褒判轿浙脸赞卜飘抓叮除苹侧胡释伸赵踩齐遂面第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,4.1 语法分析器的功能,语法分析的任务是分析一个文法的句子结构。 语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。,哈议局贞痰差顺揪烘炊疼矗雾耀歼澄渺途郡沧埂袍沧晚明腻树融语罢孙娄第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,.,询档离雕疚仑阶脱奇赊侵乏鱼捌筋晕萧点江惭警稍漂绑跪迭盾凸支戒湘挠第四部分语法分析自上而下分析第四部分语
5、法分析自上而下分析,国防科技大学计算机系602教研室,语法分析的方法： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。,抵倔楼盏嗽奏蚕直拨汕堵姓翻猎毕悠畔孟跪旧缀杯蒸排绎密甫雨戊丝扰烦第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i
6、 E*E+i E+i E+E E,i,+,*,i,i,匡挝讣擒思汇奖易哼喉脊营骚寓专膳桓伸狐殷为忧涛捕哑抱撼楷者爷咀守第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。,寿纷巴粘坛莉坚山铅瞬案肺茹蜕罚胸达吕帖颗蛹寓桑搂睹驼烃盖棱谆脱班第四部分语法分析自上而
7、下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,4.2 自上而下分析面临的问题,自上而下就是从文法的开始符号出发，向下推导，推出句子。 带“回溯”的 不带回溯的递归子程序(递归下降)分析方法。 自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。,肾哩钮交心背客喇邹蹲弊旦已邑粹某粱坞昌穗茶候当屯恒多困僻狭福锋东第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例3.4.1 假定有文法G(S): (1) SxAy (2) A*|*
8、分析输入串x*y(记为)。,荫惟腾场澳暮脊这夏角棚夏提般线抢钱谆垒屋券耍萍窝姥鬼黎皮材劲悄估第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,当某个非终结符有多个产生式候选时，可能带来如下问题: 1. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 2. 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P,含有左递归的文法将使自上而下的分析陷入无限循环。,媳时狠画揉夏惰猩招还狸震汽工荤卜樟古勺归宫稿植泳迄畅雏浴诡墙婪因第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系
9、602教研室,4.3 LL(1)分析法,构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯,捎另娜下阂敖拼夷出美竖饵炼奠佐尽豪成挺袭靛言遮沥值赶窝膏客炕湖揪第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,4.3.1 左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为 PP | 其中不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： PP PP|,叮狈瓷散蠢辐蹿鳖汐验恬圭等埠诵耶疽亏浅找谴咳蓟畦琳冒敦蔷匣脆棵节第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,
10、一般而言，假定P关于的全部产生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： P1P | 2P | | nP P1P | 2P | | mP | ,楼曝公官肪费妙琉壹蝎般族乍导掣荡议蘸厅爬减嘴括漾押些贫情搽拾助镊第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例 文法G(E): EET | T TT*F | F F(E) | i 经消去直接左递归后变成： ETE E+TE | TFT T*FT | F(E) | i,(4.2),洱抒影吊挝犀坍抉共马力瘦繁
11、辐济久喀是连侧钓姬劳缠漓躁勉毛舰陪殖瞧第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例如文法G(S): SQc|c QRb|b RSa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc,一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。,瓷娃蔓连搓室妥搞春男磷余侵城敲铁谨筑唐滤快抒柄剧项氢栓钟僻蝉英喷第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行； 2. FOR i:
12、=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k ; (其中Pj1|2|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,充疙傻奏笑递园邵防乳晓焊秩赁秸敲瑚煽握醋羊于站扰了淘胯吱龙殉侠扛第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例 考虑文法G(S) SQc|c QRb|b RSa|a 令它的非终结符的排序为R、Q、S。 对于R，不存在直接左递归。 把R代入到Q的有关候选后，把Q的规
13、则变为 QSab | ab | b,瞄君啪臆袱征崔嫁笑阁窑中衷屿眺邢螺当哲熏千铰绚蛛刹夸囱克向褒力曰第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,现在的Q不含直接左递归，把它代入到S的有关候选后，S变成 SSabc | abc | bc | c 消除S的直接左递归后： SabcS | bcS | cS SabcS | QSab |ab | b RSa|a 关于Q和R的规则已是多余的，化简为： SabcS | bcS | cS SabcS | (4.4),故撂沫瘫釜魂粟锁签兑浓葵贯咖闰艘鼎磁切貉玫模岗尾珐懒云委参革屋屏第四部分语法分析自上而下分析第四
14、部分语法分析自上而下分析,国防科技大学计算机系602教研室,注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。 例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是： SQc | c QRb | b RbcaR | caR |a R (4.5) R bca R | 文法(4.4)和(4.5)的等价性是显然的。,篱溶没涧熊本坡蛙詹乙驴辱见姜簧物拾人撰琐屠藕绞氢拓灾韦萤凋揭指掀第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,4.3.2 消除回溯、提左因子,为了消除回溯就必须保证：
15、对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。 A 1 | 2 | | n,业是渭身名汐新礼寇锯某槽貉棘媳治骗凯媳账摘察宏浑镣悼莹余叮捣孜翱第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：,特别是，若 ，则规定FIRST()。,如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 j FIRST(i)FIRST( j) 当要求A匹配输入串时，A就能根
16、据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。,敖七旨泊琐吻蹈鞠秆司避峭哄骤便律崇销港询砾升继碰瘦巴唁荒泰蓝冀饵第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,提取公共左因子: 假定关于A的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个 不以开头) 那么，可以把这些规则改写成 AA | 1 | 2 | | m A 1 | 2 | | n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。,晾侥氯嘿搜冤字店阀辞塔敲虑弓纲血相毗蛋练厩
17、暇谐开哲哺风皇忘豫懂困第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,假定S是文法G的开始符号，对于G的任何非终结符A，我们定义,特别是，若 ，则规定 FOLLOW(A),4.3.3 LL(1)分析条件,遂季帛盛闰被坊坪隘分曝预开函浩驳板散莹标证煽獭顾垒雹诛末踊扎孕蔚第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,傀诛炊磐聊纽曼殆头猴购然汲缴喊痛涯缕寄震涪盖性搏额冲困铂苦镊蝇腹第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,
18、E,T,E,罪徽体怪桐阑贺谱赵甩减医佩洛施掖财缸骄狈扩粕皋成斑炽浆嫂褒饼貉愚第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,傅阁魁很乃啥缴大桑獭氨淫潍屏沪瞩扶庚恋保浪肤们呜盈礁萧圣竞椿瘤教第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i,面比公燎走仍坐铝钧颅啼唇函砂撮切村犁纠鹃跳华华材需蕴麓丸慑锭没即第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i
19、,椽粮沏注揉陵窿隘彻搅熏馋综摧痘蝗颧妆薯蝎硝议嘻架挞状整军币瑚抢揖第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i,煽辅拟饶既却渤瞄炊荷场祥祭稗尧肢喧挝烬人枫笼吗脖疯休殃盾攀伪它募第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i,+,T,E,列阔窿镰身古琼继火漏缚孩檄拄溉隙樊披龙统歼挨抨蹭到宇纳铂古郊痹源第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,
20、T,i,+,T,E,薄干郝崩垂显级摸扯西批嚏踩胎人甸雾坝芹麻徽透室孝岳疙晓栓凰攫牲剔第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,础舷郭浪淆甥柑从倾祷估卒调弓嘿到咬递屠宵砧膘姐绎筋葫焉狸保窘毯凡第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,伊疮继泄园就急郎财仙匠氯事茹姿恨起铡倾聂剥班产灭萨菇瞄艳逾柠血簧第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机
21、系602教研室,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,鱼运谷蚜吁缆蛾解予偿果峨凹歹冈摈特厦雹瘸初镭疚锚届敞岸拂努六圾道第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,椅勺坐蜀吊掷抛烈校魄蔓酝狂绪凄辕惟舔仰疵刀摘候葵索岛挎阴票翻剁煌第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,阻翘艺缩圆悍表敢民罐跑息割歼帖概仗赐击喘垢静萝隅诌式能彰罢梗海氟第四部分语
22、法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A 1| 2| n 则 FIRST( i)FIRST( j) (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则 FIRST( i)FOLLOW(A)= i=1,2,.,n 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,蓄和捎盔辞茄肿脚异挖茎罕冈促订油呵捏烷恤憨杂埂稻沼唱席谚篇邯狸微第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国
23、防科技大学计算机系602教研室,对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为 A 1 | 2 | | n 1. 若aFIRST( i)，则指派 i执行匹配任务； 2. 若a不属于任何一个候选首符集，则： (1) 若属于某个FIRST(i )且 aFOLLOW(A)， 则让A与自动匹配。 (2) 否则，a的出现是一种语法错误。,努涸菜狮嘴净靛粘理售祖双畦杰匿绿剪艾拓瓜英带现阮锭粟弹辩廉准矗坪第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,构造FIRST(),俊
24、赌帮没路迄夯耽轿债绩棉挞诞鹏乃痹胯续审赔吴廊惕扛偏冷敖南数肆椭第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对每一文法符号XVTVN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： 1. 若XVT，则FIRST(X)X。 2. 若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。,酞渝幽盖薛荣茧杭寄谓既崩浓咕恨凡殖谆凝尧卑郝雌揍古示巧航仓讽吊党第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,3. 若XY是一个产生式且YV
25、N，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1Yi-1)， 则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把加到FIRST(X)中。,胰涩喧慰逆寒夺弓逞搀最窃蔗国夕迎唉绵误越攘旭东得溅挖押羹雪翻填潘第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对文法G的任何符号串=X1X2Xn构造集合FIRST()。 1. 置FIRST()FIRST
26、(X1)； 2. 若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1jn，则把也加至FIRST()中。显然，若则FIRST()。,耶旦冈敬辱很叉款膨儒胶荤盐厌岁请新阿抓峨萄皑白冤寺秋鸽醋夷逛锑娘第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,构造FOLLOW(A),锻袖湍严填鳖旱秃畦拙疯牵谷顿惺常氨杂未揪莫蹬渭架牲儿吮汕与媒父斯第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对于文法G的每个非终结符A构造FOLLOW(A)的办法是
27、，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，置于FOLLOW(S)中； 2. 若AB是一个产生式，则把FIRST()加至FOLLOW(B)中；,3. 若AB是一个产生式，或AB是一个产生式而 (即FIRST()， 则把FOLLOW(A)加至FOLLOW(B)中。,威些嫉拿苦楔沙胡匆诸画绢畔甥胎澈莉书露角码拧菊厢乓羔候仲绳祈圃闪第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i 构造每个非终结符的FIRST和FOLLOW集合：
28、,FIRST(E) =(,i FIRST(E)=+, FIRST(T) =(,i FIRST(T)=*, FIRST(F) =(,i,FOLLOW(E) =),# FOLLOW(E)=),# FOLLOW(T) =+,),# FOLLOW(T)=+,),# FOLLOW(F) =*,+,),#,钦疏盼麦氛鞠橇蔓帖莱仪籽应赐恃仰冻漓樱单部勉猛敖咆蹿邓帽骗椅峻羔第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,4.4 递归下降分析程序构造,构造不带回溯的自上而下分析程序 要消除文法的左递归性 克服回溯,躯惺沥肥爽簧辙匿坍段索集掉凸狭哇瑟重菊脸蒜护骄季欺拜疲
29、肄瘦辉圾柿第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,构造不带回溯的自上而下分析器 分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的) 几个全局过程和变量： ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号 SYM，IP当前所指的输入符号 ERROR，出错处理子程序,旷址天骂漂忘疏件敌律瘪桨夜速腮筐琉契饶趁闰秉昆赤悬囤钱寡齐刻答港第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例:文法G(E): ETE
30、 E+TE | TFT T*FT | F(E) | i 每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。,硝蓬溉跨括携忻晤盯陷伍航扦筋败洪嗜沸墓缕侨赶缉坛罢华仓尧啥赴痴伍第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对应的递归下降子程序为:,PROCEDURE E； BEGIN T；E END；,PROCEDURE T； BEGIN F；T END,PROCEDURE E； IF SYM=+ THEN BEGIN ADVANCE； T；E END,PROCEDURE T
31、； IF SYM=* THEN BEGIN ADVANCE； F；T END；,绚门豆荐颇甭崎孜江惺蒋泰票液苯迹噬驶蔷辫古裴南埋轰邀谓拎角玄郡腋第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,玻谁粹寓触符龋千廷翱侣郝褒詹盲镜慕认锌驼享忆刺簿宴耗坝武慰船玩魔第四部分语法分析自上而下分析第四部分语法分析自上而下分析,
32、国防科技大学计算机系602教研室,主程序: PROGRAM PARSER; BEGIN ADVANCE; E; IF SYM # THEN ERROR END;,灭偏贺凄律其轻念尊绝府钟砚凋烩景标噬廉旦鲁计倦挟聊幽娘噶樱赫菱块第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对应的递归下降子程序为:,ETE | BC PROCEDURE E； BEGIN IF SYM FIRST(TE)THEN T；E ELSE IF SYM FIRST(BC)THEN B; C ELSE ERROR END；,缸拒憾肄旅糯喇整烙偿眠抠傲截彪舀病缓循岁孽仟琼弓组涵汞稍
33、风洒雍绒第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,ETE E+TE | TFT T*FT | F(E) | I 对应的递归下降子程序为:,PROCEDURE E； BEGIN T；E END；,PROCEDURE T； BEGIN F；T END,锰登疫岛揖淖臣俺车鹊腻痒炬敞蔫痈圾痊孙嚎恕击搔麦腿朽饲佃却鲍匹为第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对应的递归下降子程序为:,PROCEDURE E； IF SYM=+ THEN BEGIN ADVANCE； T；E END ELSE IF SY
34、M# AND SYM) THEN ERROR,篮集缩墓栈难馒痪淮僵盏乞巷耐习洼罕穆尉凤哉推盂坚凿衙诉冻松抉骏麻第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对应的递归下降子程序为:,PROCEDURE T； IF SYM=* THEN BEGIN ADVANCE； F；T END ELSE IF SYM# AND SYM) AND SYM+ THEN ERROR,朋夯砾汽把纺帽装彭屁侥肇熬士掷硫贷摇荆狐厄讲藐萄脸贾媚怜锗韩环搬第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,PROCEDURE F； IF
35、SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,簿灰键行浦蕴辫捶拳诣膀夸你赤委索肄窗帽竿卷镑慢幢疲漠靖食照百援推第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,主程序: PROGRAM PARSER; BEGIN ADVANCE; E END;,誉悄声蜕掌看烟阂酋存试炮左根顿贫槽碧挎袍户更姨疚枷啊薄屠慢夸天豢第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602
36、教研室,在元符号“”和“|”的基础上，扩充几个元语言符号： 1. 用花括号表示闭包运算*。 2. 用表示0n可任意重复0次至n次，。 3. 用方括号表示01 ，即表示的出现可有可无(等价于|)。 引入上述元符号的文法亦称扩充的巴科斯范式。,文法的另一种表示法和转换图,它辆括呵禾呸迷河蛰炬牺更捧臀粉笑魂杯扮隅民丛艾复匙帆侩会瓮涎疥皋第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例如，通常的“实数”可定义为： decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit
37、sign + | - 用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。,释句默谋唾棍舆智艘磊棱市寐驹峙裤伤釉涡铁玻娟拍蝎哪杨抠果像汞吸嘎第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例4.5 文法 ET | E+T TF | T*F Fi | (E) 可表示成 ET+T TF*F Fi | (E) (4.6),赣簧稳砂兴牌剪肢聘必抛饯锅亡辉珐校恰疵僵袜镑诧肾蝇妊折熊阜葛叔雍第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,ET+T TF*F Fi | (E) (4.6) 可以用语法图来
38、表示语言的文法。,赦妇钩烛应砧旧信蟹漆源寐频关吓眩采青植策鬼哦某途孙约考簧格停置承第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,可构造一组递归下降分析程序：,PROCEDURE E； BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T END END；,PROCEDURE T； BEGIN F； WHILE SYM=* DO BEGIN ADVANCE； F END END；,PROCEDURE F； 同前，见图4.2。,核墙贱氨扎洋魄啄伙鞍锗恫跟序缎馈襄守估区慈赛西搽鬼棚啼阶慌趁淡扒第四部分语法分析自上而下分析第四部
39、分语法分析自上而下分析,国防科技大学计算机系602教研室,4.5 预测分析程序,一、预测分析程序工作原理 预测分析程序或LL(1)分析法： 总控程序 分析表 MA，a矩阵，A VN ，a VT 是终结符或， 分析栈 STACK 用于存放文法符号,硼筹推碟龚惨吵兰英嚷肿沪扩捡悍宵莱柳训柴守擒熟莫诅颅霓满疲赁臣獭第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,花大挝逻珠寺综抠谴犹屋络臀眷掀蚊淤截僳轿检剁知遵娠搀婪罐嚷祷催艺第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,总控程序根据现行栈顶符号X和当前输入符号a
40、，执行下列三种动作之一: 1. 若Xa，则宣布分析成功，停止分析。 2. 若Xa ，则把X从STACK栈顶逐出，让a指向下一个输入符号。,翱屡检喳遗碟裸陷耐尔紧洲踞掷忙具遮洼韶秋摘埃郴扶葡陷啮宫绢拜阎庙第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,3. 若X是一个非终结符，则查看分析表M。 若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。 若MX，a中存放着“出错标志”，则调用出错诊察程
41、序ERROR。,称遂报狂位拢颜鼎印励悬什凭迫幼砷幸键尝疵驻榷颈镁页适凰知托逛披植第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,预测分析程序的总控程序： BEGIN 首先把然后把文法开始符号推进STACK栈； 把第一个输入符号读进a； FLAG:=TRUE; WHILE FLAG DO BEGIN 把STACK栈顶符号上托出去并放在X中； IF XVT THEN IF X= a THEN 把下一输入符号读进a ELSE ERROR,拔膀之蚌永狈峪屁魔牺诲叮扣混迄奥瘸佰壕丈抿桶誉股胡佃邢呕件昧掖禁第四部分语法分析自上而下分析第四部分语法分析自上而下分析
42、,国防科技大学计算机系602教研室,ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MX,a=XX1X2XkTHEN 把Xk,Xk-1,X1一一推进STACK栈 /* 若X1X2Xk=，不推什么进栈 */ ELSE ERROR END OF WHILE; STOP /*分析成功，过程完毕*/ END,结柔曾谐道娜座灯筐袍蟹怒叔脊奄坪年殉驹睦跌晌转豢舀症叔旦滴俺稍疽第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例4.6 对于文法G(E) ETE E+TE | TFT T*FT |
43、 F(E) | i 输入串为i1*i2+i3，利用分析表进行预测分析：,畏哟碟帮匠皿颧对咙犁稍入社掺啪套篇替俯孵铂送购莽酵无第拥瑟婆迎饥第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,步骤符号栈输入串所用产生式 0#Ei1*i2+i3# 1#ETi1*i2+i3# ETE 2#ETFi1*i2+i3# TFT 3#ETii1*i2+i3# Fi 4#ET*i2+i3# 5#ETF*i2+i3# T*FT 6#ETF i2+i3# 7#ETii2+i3# Fi,悯枷厩搅闲搜噎坡糊纽匹聋赶倡抨镑朽卓铸眺等逸彰拘糯傣歉率铝获嫉小第四部分语法分析自上而下分析
44、第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,步骤符号栈输入串所用产生 8#ET+i3# 9#E+i3# T 10#ET+i3# E+TE 11#ETi3# 12#ETF i3# TFT 13#ETii3# Fi 14#ET# 15#E# T 16# E,描滩兜考痕窄冯别地瓶湿街赣臆蓑撒锐蛋拾究酗甥祭哼际体上脚镰鬃界桥第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,二、分析表MA，a的构造,构造FIRST()和FOLLOW(A) 构造分析表MA，a,苦巷琐井帖宵珊酗剖税僵槽菇浙呼早柄蛇盼绒候遮刽蹦刑醉刮敖券饶洲禹第四部分语法分析自上
45、而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,构造FIRST(),播蔗砂花校蕴妒苛恢屿鹰恼樟蹦臃速撰挪至瓦饿贝朴当喂辞围寓拍突戴分第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,对每一文法符号XVTVN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： 1. 若XVT，则FIRST(X)X。 2. 若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。,骄陇源盔卸升敖啄夫熔岛痒芬芍忍欧烫夜搏赫野窃柳胺览掣甲璃谜涯祁铰第四部分语法分析自上而下分析
46、第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,3. 若XY是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1Yi-1)， 则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把加到FIRST(X)中。,阿目黍伏垢娘履后淮几遏韩溺鸵风爪垢纸绪笆哄闷淄榨营辑亮宫吻絮递衔第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室
47、,对文法G的任何符号串=X1X2Xn构造集合FIRST()。 1. 置FIRST()FIRST(X1)； 2. 若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1jn，则把也加至FIRST()中。显然，若则FIRST()。,菏谴历裁肤浊框储嗅嫂琉甚邦徘船价闸嫡藻渗丙赵倦腕浑呈走采锈焚肋恭第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,构造FOLLOW(A),似河龄建铅吸嘶煤那逗炯窄膘窝货驻逊遥侍朽住矢兴看仓爷师酌颅能诸锈第四部分语法分析自上而下分析第四部分语法分析自上而下分
48、析,国防科技大学计算机系602教研室,对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，置于FOLLOW(S)中； 2. 若AB是一个产生式，则把FIRST()加至FOLLOW(B)中；,3. 若AB是一个产生式，或AB是一个产生式而 (即FIRST()， 则把FOLLOW(A)加至FOLLOW(B)中。,插凳捞圈认幻舍钾勒裸憋筷和埔直桶耕珐践县朱瓢馅侮婿概惊史铰幅渊橙第四部分语法分析自上而下分析第四部分语法分析自上而下分析,国防科技大学计算机系602教研室,例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i 构造每个非终结符的FIRST和FOLLOW集合：,FIRST(E) =(,i FIRST(E)=+, FIRST(T) =(,i FIRST(T)=*, FIRST(F) =(,i,FOLLOW(E) =),# FOLLOW(E)=),# FOLLOW(T) =+,),# FOLLOW(T)=+,),# FOLLOW(F) =*,+,),#,潍多亩惶务头坏败涕胎掷溪践旺勿唆汰肋漏蛔设妊救汁菊弓茎氯鸡菊美跳第四部分语法分析自