编译原理 之 自顶向下语法分析方法
63页1、第五章 自顶向下语法分析方法,本章要点 LL(1)分析 First 集合和Follow集合 使用递归下降分析算法进行自顶向下的分析 预测分析程序 非LL(1)文法的改造,自上而下分析算法,自顶向下分析法也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子,若输入串是给定的句子,则必能推出,反之必然出错。 自顶向下分析法又分为确定的和不确定的两种。,5.1 确定的自顶向下分析思想,确定的自顶向下分析方法,首先要解决从 文法的开始符号出发,如何根据当前的输 入符号(单词符号)唯一地确定选用哪个 产生式替换相应非终结符往下推导,或构 造一棵相应的语法树。,例5.1,若有文法G1S: S pA | qB A cAd | a B dB | b 若输入串W=pccadd。自顶向下推导过程为 S=pA=pcAd=pccAdd=pccadd,这个文法有以下两个特点:,每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始。,例5.2,若有文法G2S为: S Ap S Bq A a A cA B b B db,当输入串W=cc
2、ap,那么试图推出输入串的推导过程为: S=Ap=cAp=ccAp=ccap,例5.2文法的特点是:,产生式的右部不全是由终结符开始 如果两个产生式有相同的左部,它们的右部是由不同的终结符或非终结符开始。 文法中无空产生式,定义5.1,设G=(VT,VN,P,S)是上下文无关文法 FIRST()=a| a,aVT, ,V*若 则规定FRIST()不难求出在文法G2中 FIRST(Ap) = a, c FIRST(Bq) = b, d,例5.3,若有文法GS: SaA Sd AbAS A 若输入串W=abd,则试图推导出abd串的推 导过程为:S=aA=abAS=abS=abd,从例5.3可以得出下列结论,当某一非终结符的产生式中含有空产生式 时,它的非空产生式右部的首符号集两两 不相交,并与在推导过程中紧跟该非终结 符右边可能出现的终结符集也不相交,则 仍可构造确定的自顶向下分析。,定义5.2,设G=(VT,VN,P,S)是上下文无关文法, AVN, S是文法开始符号 FOLLOW(A)=aS A 且aVT aFRIST(),V*,V+ 若S A ,且 ,则 #FOLLOW(A),定义
3、5.3,给定上下文无关文法的产生式A, AVN, V*, 若*,则 SELECT(A ) = FIRST() 如果 ,则 SELECT(A ) = (FIRST() - )FOLLOW(A),定义5.4,一个上下文无关文法是LL(1)文法的充 分必要条件是,对每个非终结符A的两个 不同产生式,A, A,满足 SELECT(A) SELECT(A ) = 其中、不能同时 。,LL(1)文法的含义:,第1个“L”指的是由左向右地处理输入。第2 个“L”指的是它为输入串描绘出一个最左推 导。括号中的数字1意味着它只需向右看一 个符号便可决定如何推导即选择哪个产生 式(规则)进行推导。,例5.3的文法,SaA Sd AbAS A,不难看出: SELECT(SaA) = a SELECT(Sd) = d SELECT(AbAS) = b SELECT(A) = a, d, # 所以 SELECT(SaA) SELECT(Sd) = SELECT(AbAS) SELECT(A)=,例5.4,设文法GS为: SaAS Sb AbA A,则 SELECT(SaAS) = aSELECT(Sb) = b
4、SELECT(AbA) = bSELECT(A) = a, b SELECT(SaAS) SELECT(Sb)= SELECT(AbA)SELECT(A),5.2 LL(1)文法的判别,1求出推出的非终结符 2计算FIRST集 3计算FOLLOW集 4计算SELECT集,1求出推出的非终结符,扫描文法中的产生式 删除所有右部含有终结符的产生式, 若这使得以某个非终结符为左部的所有产生式都被删除,说明该非终结符不能推出. 若某个非终结符的某个产生式的右部为,说明该非终结符能推出. 删除以该非终结符为左部的所有产生式. 扫描产生式右部的每一个符号 若扫描到的非终结符能推出, 则删除该非终结符,如这样使产生式右部为空,说明该非终结符能推出. 删除以该非终结符为左部的所有产生式. 若扫描到的非终结符不能推出, 则删除该产生式,如这样使以该非终结符为左部的所有产生式都被删除,说明该非终结符不能推出. 重复,直到扫描完文法的产生式,数组中非终结符的特征在没有改变为止.,例5.5 若文法GS为:,SAB SbC A Ab B BaD CAD Cb DaS Dc,SAB A B CAD,SAB CAD
《编译原理 之 自顶向下语法分析方法》由会员xzh****18分享,可在线阅读,更多相关《编译原理 之 自顶向下语法分析方法》请在金锄头文库上搜索。
爱心树活动教案
世界文化之旅0
七年级学年知识归纳
七年级历史下册第二单元第12课《蒙古的兴起和元朝的建立》课件人教新课标版
一片美丽的叶子
非谓语动词 (6)
[中学联盟]江苏省太仓市第二中学七年级英语上册教学课件:Unit3READING1 (2)
“数与代数”教材修订说明
2014年7月师院培训
字理教学快捷入门之一20140521s
议论文写作指导之新材料作文审题立意 (2)
压缩语段 (2)
琵琶行课件 (2)
2014年各年级的教学计划和建议
(苏教版)五年级数学下册找规律第二课时
秋姑娘的信 (5)
苏教版数学五年级上册《复式条形统计图》课件 (2)
【名校课时通】2014届九年级化学全册第二单元探秘水世界第三节原子的构成名师教学课件鲁教版
《逻辑与语文》课件2
《检阅》[1]
2022-05-20 22页
2022-05-20 29页
2022-04-21 115页
2022-04-21 68页
2022-04-17 34页
2022-04-17 38页
2022-04-15 89页
2022-04-15 181页
2022-04-15 148页
2022-04-15 81页