-自顶向下语法分析方法.pptx
《-自顶向下语法分析方法.pptx》由会员分享,可在线阅读,更多相关《-自顶向下语法分析方法.pptx(69页珍藏版)》请在咨信网上搜索。
1、第五章第五章第五章第五章 自顶向下语法分析方法自顶向下语法分析方法自顶向下语法分析方法自顶向下语法分析方法学习目标学习目标:掌掌握握:LL(1)LL(1)文文法法的的判判别别,预预测测分分析析法,递归子程序的构造方法法,递归子程序的构造方法理解:理解:LLLL(1 1)文法文法了解:不确定的自顶向下分析了解:不确定的自顶向下分析语语法法分分析析的的作作用用是是识识别别由由词词法法分分析析给给出出的的单单词词序序列是否是给定文法的正确句子列是否是给定文法的正确句子分类分类:语法分析语法分析自顶向下分析自顶向下分析自底向上分析自底向上分析确定的确定的不确定的不确定的算法优先分析(第六章)算法优先分
2、析(第六章)LR分析(第七章)分析(第七章)自顶向下的基本思想自顶向下的基本思想:从从文文法法的的开开始始符符出出发发企企图图推推导导出出与与输输入入的的单单词词串串完全相匹配的句子完全相匹配的句子.5.1确定的自顶向下分析思想确定的自顶向下分析思想5.2LL(1)文法的判别文法的判别5.3某些非某些非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换5.4不确定的自顶向下分析思想不确定的自顶向下分析思想5.5确定的自顶向下分析方法确定的自顶向下分析方法5.1 5.1 确定的自顶向下分析思想确定的自顶向下分析思想确定的自顶向下分析思想确定的自顶向下分析思想1 确定分析的条件确定分析的
3、条件2 开始符号集开始符号集FIRST()的定义的定义3 后跟符号集后跟符号集FOLLOW(A)的定义的定义4 选择集合选择集合SELECT(A)的定义的定义5 LL(1)文法的定义文法的定义1 1 确定分析的条件确定分析的条件确定分析的条件确定分析的条件从从文文法法的的开开始始符符出出发发,如如能能根根据据当当前前的的输输入入符符号号(单单词词符符号号)唯唯一一地地确确定定选选用用哪个产生式进行推导,则分析是确定的。哪个产生式进行推导,则分析是确定的。例例1设有文法设有文法G1S:SpA|qBAcAd|aBdB|b若输入串若输入串W=pccadd。自顶向下的推导过程为自顶向下的推导过程为:S
4、SApcAdcAda=pA=pcAd=pccAdd=pccaddG1S有如下特点:有如下特点:(1)每个产生式的右部由终结符开头每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同一非终结符的不同产生式的右部由不同的终结符开头。同的终结符开头。对于这种文法,在推导过程可以根据当前的对于这种文法,在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导,输入符号唯一确定选哪个产生式往下推导,即分析过程是确定的。即分析过程是确定的。例例2:设有文法设有文法G2S为为:SAp|BqAa|cABb|dBpAScAcAa=ccapS=cAp=ccAp=Ap该例说明,当该例说明,当
5、(1)产产生生式式右右部部以以终终结结符符或或非非终终结结符符开开头头(无无空空产生式);产生式);(2)同一非终结符的不同产生式的右部由不同的同一非终结符的不同产生式的右部由不同的符号开头。符号开头。对于这种文法,在推导过程选用哪个产生式不直对于这种文法,在推导过程选用哪个产生式不直观,关键是判断观,关键是判断产生式右部推出的开始符号(集)产生式右部推出的开始符号(集),分析过程可能是确定,分析过程可能是确定若输入串若输入串W=ccap,自顶向下的自顶向下的推导过程为:推导过程为:例例3:设有文法设有文法G3SSaA|dAbAS|若输入串若输入串W=abd,自顶向下的推导过程为:自顶向下的推
6、导过程为:AaSbSA d=abd S=abAS=abS文法的特点是文法的特点是:包含空产生式包含空产生式对于空产生式左部的非终结符对于空产生式左部的非终结符,关键是判断关键是判断该该非终结符的后跟符号(集非终结符的后跟符号(集),分析过程可),分析过程可能是确定的。能是确定的。=aA要进行确定的自顶向下的分析,文法要满足一要进行确定的自顶向下的分析,文法要满足一定的限制定的限制即文法是即文法是LL(1)文法。文法。先研究三个定义先研究三个定义开始符号集开始符号集FIRSTFIRST后跟符号集后跟符号集FOLLOWFOLLOW选择集合选择集合SELECTSELECT2 2 开始符号集开始符号集
7、开始符号集开始符号集FIRST()FIRST()的定义的定义的定义的定义定义定义:设设G=(VN,VT,P,S)是上下文无关文法,是上下文无关文法,(VN VT)*FIRST()=a VT|*a.若若*则规定则规定 FIRST()直观上说文法符号串直观上说文法符号串 的开始符号集是由的开始符号集是由 推导出的开头的终结符(包括推导出的开头的终结符(包括)组成。组成。例文法例文法G2S:SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRST(b)=bFIRST(dB)=d由于由于同一非终结符同一非终结符的两个的两
8、个产生式的右部产生式的右部推导出来的推导出来的开始符号集开始符号集不相交,因此可根据当前输入符属于哪不相交,因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进个产生式右部的开始符号集而决定选哪个产生式进行推导,可以进行确定的自顶向下分析行推导,可以进行确定的自顶向下分析3 3 后跟符号集后跟符号集后跟符号集后跟符号集FOLLOW(A)FOLLOW(A)的定义的定义的定义的定义定义定义 设设G=(VT,VN,P,S)是上下文无关文法,是上下文无关文法,A VN,FOLLOW(A)=a|S=*Aa,a VT,若有若有S=*A,则规定则规定#FOLLOW(A)(注:(注:#输入串
9、输入串#,#做为输入串的结束符)做为输入串的结束符)直观上说直观上说,非终结符非终结符A的后跟符号集是由句型中紧跟的后跟符号集是由句型中紧跟A后的那些终结符(包括后的那些终结符(包括#)组成。)组成。例例 文文 法法G3S:SaA|d AbAS|由由 S=*S 得得#FOLLOW(S)由由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOW(S)=#,a,d由由S=*aA 得得#FOLLOW(A)由由S=*abAS=*abAaA 得得 a FOLLOW(A)=*abAd 得得 d FOLLOW(A)FOLLOW(A)=#,a,d说明:说明:对于非终结符对于非终结符A的
10、两个产生式的两个产生式AbAS 和和 A,当输入符号当输入符号FIRST(bAS)=b时,选时,选AbAS推导,推导,当输入符号当输入符号FOLLOW(A)=#,a,d 时,选时,选A推导。推导。由于由于FIRST(bAS)FOLLOW(A)=,所以可进行确定所以可进行确定的自顶向下分析。的自顶向下分析。4 4 选择集合选择集合选择集合选择集合SELECT(A)SELECT(A)的定义的定义的定义的定义定义定义对给定的上下文无关文法的产生式对给定的上下文无关文法的产生式A,A VN,V*,若若*,则则SELECT(A)=FIRST()若若=*,则则SELECT(A)=(FIRST()-)FOL
11、LOW(A)解释解释当当A面面对应输入符对应输入符a,在自顶向下的分析中应选择这在自顶向下的分析中应选择这样的产生式样的产生式A 进行推导:进行推导:First()中包含中包含a;此外若此外若 可能导出空串,可能导出空串,A自动获得匹配,输入符自动获得匹配,输入符a有可能与有可能与A后后的一个符号匹配,所以当的一个符号匹配,所以当a应属于应属于Follow(A)时,选择产生式时,选择产生式A 也是可以的也是可以的。直观上说某产生式直观上说某产生式A的选择集合是指遇到哪些输的选择集合是指遇到哪些输入符号(包括入符号(包括#)时选用该产生式向下推导。)时选用该产生式向下推导。例例 G3S:SaA
12、Sd AbAS ASELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(AbAS)=FIRST(bAS)=bSELECT(A)=FOLLOW(A)=#,a,d若若*,则则SELECT(A)=FIRST()若若=*,则则SELECT(A)=(FIRST()-)FOLLOW(A)说明:说明:同一非终结符的不同产生式同一非终结符的不同产生式A与与A,若若SELECT(A)SELECT(A)=,则一定则一定可以进行确定的自顶向下分析可以进行确定的自顶向下分析5 5 LL(1)LL(1)文法的定义文法的定义文法的定义文法的定义定义定义:一一个个上上下下文文
13、无无关关文文法法是是LL(1)文文法法的的充充分分必必要要条条件件是是,对对每每个个非非终终结结符符A的的两两个个不不同同产产生生式式A与与A,满足满足SELECT(A)SELECT(A)=。LL(1)文法的含义是:文法的含义是:第一个第一个L表示从左到右扫描输入串表示从左到右扫描输入串第二个第二个L表示分析过程用最左推导表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式表明只需向前看一个符号便可以决定选哪个产生式进行推导,类似地进行推导,类似地LL(k)文法需要向前看文法需要向前看K个符号才个符号才可以确定选用哪个产生式。可以确定选用哪个产生式。例例 有文法有文法GS为:为
14、:SaAS SbAbAASELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=Follow(A)=a,b由于由于SELECT(AbA)SELECT(A)=b,所以文法所以文法GS不是不是LL(1)文法,当文法,当A遇输入符遇输入符b时,不时,不能确定选能确定选AbA还是还是A去推导。去推导。5.2 5.2 LLLL(1 1)文法的判别文法的判别文法的判别文法的判别要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步:分为五步:1.求能推出求能推出的非终结符集的非终结符集 2.计算每个产生式右部计算每个产生式右部的的F
15、IRST()集集 3.计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集 4.计算每个产生式计算每个产生式A的的SELECT(A)集集 5.按按LL(1)文法的定义判别文法的定义判别1.1.求出能推出求出能推出求出能推出求出能推出 的非终结符集的非终结符集的非终结符集的非终结符集算法算法:用用S表示能推出表示能推出的非终结符集的非终结符集第一步令第一步令S=Aj|Aj 产生式集产生式集对对 每每 个个 产产 生生 式式 p:ApX1.Xn,若若X1.Xn S,则则S:=S Ap重重复复第第二二步步的的循循环环,直直至至S收收敛敛(不不再再变化)为止。变化)为止。例例GS:SAB|bC
16、Ab|BaD|CAD|b DaS|cA,B,A,B,S S 第一次第一次 A,BA,B初值初值A,B,SA,B,S收敛收敛第二次第二次非终结符集非终结符集S S能推出能推出的非终结符集为的非终结符集为A,B,S2.2.计算每个产生式右部计算每个产生式右部计算每个产生式右部计算每个产生式右部 的的的的FIRSTFIRST()集集集集首首先先对对每每一一文文法法符符号号X(X VT VN),求求FIRST(X)的算法的算法:1.对每个对每个a VT:First(a)=a2.对每个对每个A VN:若若A*则则First(A):=否则否则First(A):=3.对每个产生式对每个产生式AX1XjXn做
17、:做:First(A)=First(A)SectionFirst(X1XjXn)其中其中 SectionFirst(XSectionFirst(X1 1X Xj jX Xn n)=(First(X=(First(X1 1)-)-)(First(X(First(X2 2)-)-)(First(First(X(Xj j)-)-)First(XFirst(Xj+1j+1)X Xj+1j+1是产生式右部中第一个不能推出是产生式右部中第一个不能推出的符号的符号若若X X1 1 *则则SectionFirst(XSectionFirst(X1 1X Xj jX Xn n)=First(X)=First(X
18、1 1)若若X X1 1X Xn n全可推出全可推出则则SectionFirst(XSectionFirst(X1 1X Xn n)=FIRST(X)=FIRST(X1 1)FIRST(XFIRST(Xn n)4.4.重复重复3 3直到每个符号的直到每个符号的FIRSTFIRST集合都不再增大为止。集合都不再增大为止。例例GS:SAB|bC Ab|BaD|CAD|b DaS|cb ba aa ca cb a cb a c a b b aFirstFirst集集(3)(3)b ba aa ca cb b a b bFirstFirst集集(2)(2)b ba a FirstFirst集集(1)(
19、1)A AB BC CD Da ab bS Sa ab bFirstFirst集集(0)(0)已求出能推出已求出能推出的非终结符集的非终结符集为为A,B,Sbbab ba ca caa ca c利用求出利用求出每个文法符号每个文法符号的的FIRST集集求求符号串符号串的的FIRST集集设设=X1X2Xn1.当当X1不能不能=*,则,则FIRST()=FIRST(X1)2.若对任何若对任何j(1jn)都有都有 FIRST(Xj),则则FIRST()=(FIRST(X1)-)(FIRST(Xj)-)FIRST(Xj+1)3.若对所有若对所有i(1in),都有都有 FIRST(Xi),则则 FIRS
20、T()=FIRST(X1)FIRST(Xn)例例GS SAB|bC Ab|BaD|CAD|b DaS|c已求出非终结符的已求出非终结符的First集合如下集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,c 产生式右部产生式右部符号串符号串的开始符集合为的开始符集合为:SABFIRST(AB)=FIRST(A)FIRST(B)=a,b,SbCFIRST(bC)=bAFIRST()=AbFIRST(b)=bCADFIRST(AD)=(FIRST(A)-)FIRST(D)=b,a,cDaSFIRST(aS)=a3 3计
21、算每个非终结符计算每个非终结符计算每个非终结符计算每个非终结符AA的的的的FOLLOWFOLLOW(AA)集集集集1.对对所所有有A VN令令Follow(A)=;对对开开始始符符S,令令Follow(S)=#因为因为S=*S,显然,显然#FOLLOW(S)2.对每条产生式对每条产生式AxBy,考察产生式右部的每一非终考察产生式右部的每一非终结符结符B,x,y V*,如果如果y不能推出不能推出Follow(B)=Follow(B)First(y)否则否则Follow(B)=Follow(B)(First(y)-)Follow(A)3.重复重复2,直至对所有,直至对所有A VN,Follow(A
22、)收敛为止。收敛为止。若若a FOLLOW(A),则表明则表明S=*Aa,由于由于AxBy,且且y=*,则有则有 S=*Aa=xBya=xBa,即即S=*xBa,所以所以a FOLLOW(B)例例GS:1SAB2SbC3Ab4A5BaD6B7CAD8Cb9DaS10Dc已求出已求出 非终结符的非终结符的First集合如下集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,c#D#C#Ba#A#a#cSFollow集集(2)Follow集集(1)Follow集集(0)c4 4计算每个产生式计算每个产生式计算每个产生式计
23、算每个产生式AA的的的的SELECTSELECT(A)A)集集集集按定义计算按定义计算SELECT(A):若若*,则则SELECT(A)=FIRST()若若=*,则则SELECT(A)=(FIRST()-)FOLLOW(A)例例GS:SAB|bC Ab|BaD|CAD|b DaS|c是否是否=*FirstFirst集集 FollowFollow集集S S是是a,b,#A A是是 b,a,c,#B B是是 a,#C C否否a,b,ca,b,c#D D否否a,ca,c#部分产生式的部分产生式的select集合集合SELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=b,a,#SELE
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 向下 语法分析 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。