自下而上的语法分析课件.ppt

《自下而上的语法分析课件.ppt》由会员分享，可在线阅读，更多相关《自下而上的语法分析课件.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、自下而上的语法分析第1页，此课件共58页哦5.1自下而上的语法分析概述n从叶结点出发，步步向上归约。若能归约到根结点，说明输入串是文法的一个句子，否则输入串存在语法错误。n比较：从文法的开始符号出发进行推导，最终推出确定的输入串（由单词种别构成的源程序）。第2页，此课件共58页哦5.1自下而上的语法分析概述n概述n实质上是一种移进归约法，设置一个栈，将输入串符号逐个移进栈内，一旦发现栈顶形成某个产生式的候选式时，立即将栈顶这一部分符号替换（归约）成该产生式的左部符号。第3页，此课件共58页哦5.1自下而上的语法分析概述n例给定文法：nSaAcBenAb|AbnBd n输入串abbcde 第4页

2、，此课件共58页哦5.1自下而上的语法分析概述n移进归约过程如下所示 第5页，此课件共58页哦5.1自下而上的语法分析概述n因最终归约到根结点，输入串abbcde是文法的一个句子。第6页，此课件共58页哦5.1自下而上的语法分析概述n问题n从第步到第步有二种选择，可将b归约成A，栈顶成aAA；也可将Ab归成A，栈顶成aA，显然后者是正确的，故需精确定义可归约串。第7页，此课件共58页哦5.1自下而上的语法分析概述n句柄和规范归约n短语n直接短语（简单短语）第8页，此课件共58页哦5.1自下而上的语法分析概述n句柄n句型aAbcde中存在三个短语，它们是Ab、d和aAbcde，其中Ab和d是直接

3、短语，句柄是Ab。不能因为存在规则Ab，就断定b是这个句型的一个短语，b不是句柄，甚至连短语都不是。第9页，此课件共58页哦5.1自下而上的语法分析概述n规范归约（最左归约）n规范句型n规范推导n图解法第10页，此课件共58页哦5.2算符优先文法算符优先文法n1.算符文法n比较简单，适合手工构造，特别适合算术表达式的语法分析n2.算符优先分析法的优先关系nP106第11页，此课件共58页哦5.2算符优先文法算符优先文法n3.算符优先文法的定义P107第12页，此课件共58页哦5.2算符优先文法算符优先文法n4.FIRSTVT集合定义P109nLASTVT集合定义P109第13页，此课件共58页

4、哦5.2算符优先文法算符优先文法n构造集合的规则第14页，此课件共58页哦5.2算符优先文法算符优先文法n5.构造算符优先文法分析表第15页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理nLR分析法适用范围广泛，适合自动生成，目前大多数编译程序的语法分析器都采用这种分析法第16页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n前缀前缀字的任意首部字的任意首部n活活前前缀缀规规范范句句型型的的一一个个前前缀缀，不不包包含含句句柄柄后后的的任任何何符符号号。活活就就是是其其右右部部添添加加一一些些终终结结符符后后，就就构构成成一一个规范句型个规范句型nLR分析法的基

5、本思想分析法的基本思想n把把每每个个句句柄柄的的识识别别（产产生生式式右右部部符符号号串串）过过程程划划分分为为若若干干状状态态，每每个个状状态态只只识识别别句句柄柄的的一一个个符符号号，若干个符号就可识别句柄左端的一部分符号。若干个符号就可识别句柄左端的一部分符号。n识识别别了了句句柄柄这这一一部部分分就就相相当当于于识识别别了了当当前前规规范范句句型型的左起部分，既规范句型的活前缀。的左起部分，既规范句型的活前缀。第17页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n对对于于文文法法G，可可以以构构造造一一个个有有限限自自动动机机DFA，用用它它去去识识别别给给定定文文法

6、法的的所所有有规规范范句句型型的的活活前前缀缀，然然后后把把这这个个DFA转转换换成成LR分析表。分析表。n因因此此，首首先先构构造造一一个个识识别别文文法法G所所有有活活前前缀缀的的NFA，这这个个NFA的的每每个个状状态态是是下下面面定义的一个定义的一个“项目项目”第18页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理nLR(0)项目（简称项目）项目（简称项目）n文法文法G的的LR（0）项目定义为：）项目定义为：n在在文文法法G每每个个产产生生式式右右部部的的某某个个位位置置添添加加一一个个园园点点“.”。如如A XYZ包包含含四四个个项项目目nA.XYZA X.YZnA

7、XY.ZA XYZ.n特例，特例，A的项目为的项目为A.。第19页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n例文法n0.SEn1.EaAn2.AcAn3.Adn4.Ed第20页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n这个文法的项目有这个文法的项目有n1S.E2SE.n3E.aA4Ea.A 5EaA.n6A.cA7Ac.A 8AcA.n9A.d 10Ad.n11E.d12Ed.第21页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n构造识别活前缀的构造识别活前缀的NFAn将将每每个个项项目目视视为为识识别别活活前前缀缀NFA的的一一个

8、状态。个状态。n规规定定状状态态S.S为为NFA的的唯唯一一初初态态，状状态态SS.为为NFA的的唯唯一一接接受受态态（S为为原原文文法开始符号，法开始符号，S为拓广文法开始符号）。为拓广文法开始符号）。第22页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n因因在在每每个个状状态态都都可可识识别别出出一一个个活活前前缀缀（初初态态可可识识别别出出活活前前缀缀），故故NFA的的每每个个状状态态都都是是终终态态，终终态又称为活前缀识别态。态又称为活前缀识别态。n如如果果状状态态i和和状状态态j源源自自于于同同一一产产生生式式，而而且且状状态态i和状态和状态j的园点位置相差一个文法

9、符号，例的园点位置相差一个文法符号，例状态状态i为为ni:XX1Xi-1.XiXi+1Xn状态状态j为为nj:XX1Xi-1Xi.Xi+1Xnn那那么么状状态态i和和j之之间间存存在在一一条条弧弧，标标记记为为Xi，表表示示在在状态状态i读入读入Xi进入状态进入状态j。第23页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n若若状状态态i园园点点之之后后的的符符号号为为非非终终结结符符（例例i:X.A），那那么么从从状状态态i画画一一条条弧弧到到所所有有k:A.状状态态,表表示示只只有有看看到到了了从从A推出的全部符号推出的全部符号:状态状态i:X.A才可经才可经A弧进入弧进入

10、状态状态j:XA.。第24页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n接接上上例例，构构造造识识别别文文法法活活前前缀缀的的NFA，如下所示：如下所示：n其中其中1称为初态（含有称为初态（含有S.E的项目），的项目），状态状态2、8、10、5和和12称为句柄识别态称为句柄识别态（含有形如（含有形如A.的项目的项目），其中），其中2又称又称为接受态（含有为接受态（含有SE.的项目）。的项目）。第25页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理第26页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n构造识别活前缀的构造识别活前缀的DFA n

11、其其中中0是是初初态态，1为为接接受受态态，3、4、6和和7是句柄识别态。是句柄识别态。第27页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理第28页，此课件共58页哦5.3 LR分析法的基本原理分析法的基本原理n项目分类项目分类n凡是圆点在最右端的项目称为凡是圆点在最右端的项目称为归约项目归约项目，A.n对文法开始符号对文法开始符号S的归约项目称为的归约项目称为接受项目接受项目n形如形如A.a的项目称为的项目称为移进项目移进项目，a为终结符为终结符n形如形如A.B的项目称为的项目称为待约项目待约项目，B为非终结符为非终结符第29页，此课件共58页哦5.3 LR分析法的基本原理

12、分析法的基本原理nLR(0)项项目目集集规规范范族族（简简称称项项目目集集规规范范族）族）n识识别别一一个个文文法法活活前前缀缀的的DFA的的项项目目集集（状态）的全体（状态）的全体n活前缀识别工作原理活前缀识别工作原理 输入串输入串acd第30页，此课件共58页哦5.4项目集规范族的构造项目集规范族的构造n文法拓广文法拓广引进产生式引进产生式SSn项目集项目集I 的闭包（的闭包（CLOSURE(I)）P132n状态转换函数（状态转换函数（GO(I,X)）P132n项目集规范族构造算法项目集规范族构造算法nC=I0;/项目集的集合项目集的集合nIf(GO(Ii,XK)&GO(Ii,XK)!C)

13、n j+;Ij=GO(Ii,XK);C=C Ij;第31页，此课件共58页哦5.4项目集规范族的构造项目集规范族的构造第32页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n预备工作预备工作n引入产生式引入产生式SS，将文法拓广成，将文法拓广成G。n对对G的产生式进行编号。的产生式进行编号。n构构造造文文法法G的的状状态态转转换换函函数数GO(I,X)和和项目集规范族项目集规范族C。第33页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n构造法构造法n设设项项目目集集规规范范族族C=I0、I1、In，将将I0、I1、In视视为为分分析析表表状状态态0、1、n。LR(

14、0)分分析析表表存存放放在在二二维维数数组组M中中，第第一一维维为为状状态态，第第二二维维为为文文法法符号。符号。n若若 移移 进进 项项 目目A.aIi且且GO(Ii,a)=Ij，其其 中中aVT，则置，则置Mia=sj（s表示移进）。表示移进）。第34页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n若若 归归 约约 项项 目目 A.Ii，对对 于于 任任 何何aVT#，置置Mia=rk（k是是产产生生式式A的编号，的编号，r表示归约）。表示归约）。n若若 接接 受受 项项 目目 SS.Ii，则则 置置Mi#=Acc（Acc表示接受）。表示接受）。n若若待待约约项项目目A.B

15、Ii且且GO(Ii,B)=Ij，其中，其中BVN，则置，则置MiB=j。n分析表中的空白表示出错。分析表中的空白表示出错。第35页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n规则规则若若归约项目归约项目A.Ii，对于任何，对于任何aVT#，置，置Mia=rk（k是产生式是产生式A的编号，的编号，r表示归表示归约）。约）。n某一个状态若含有归约项目，则在该状态下应执行某一个状态若含有归约项目，则在该状态下应执行归约操作，该规则简单处理为遇到任何符号都执行归约操作，该规则简单处理为遇到任何符号都执行归约，而不考虑有些终结符出错的问题，这就是归约，而不考虑有些终结符出错的问题，这就

16、是LR（0）分析法中）分析法中0的含义，的含义，0表示没有任何展望。表示没有任何展望。n1表示有展望，向前看一个输入符号表示有展望，向前看一个输入符号第36页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n例已知文法例已知文法GnEaA|dnAcA|d构造它的构造它的LR(0)分析表。分析表。第37页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n解：解：预备工作预备工作n1）引入产生式）引入产生式SE，将文法，将文法G拓广成拓广成G。n2）产生式编号如下：）产生式编号如下：n0.SEn1.EaAn2.Edn3.AcAn4.Adn3）构构造造上上述述文文法法的的状状

17、态态转转换换函函数数GO(I,X)和和项项目目集集规范族。规范族。第38页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n构造分析表（过程，手工完成）构造分析表（过程，手工完成）第39页，此课件共58页哦5.5 LR(0)分析表的构造分析表的构造n总结总结n若文法的项目集规范族中的每个项目集不存在以若文法的项目集规范族中的每个项目集不存在以下情况：下情况：n1.既含有移进项目又含有归约项目既含有移进项目又含有归约项目n2.含有多个归约项目含有多个归约项目则称该文法是一个则称该文法是一个LR（0）文法）文法即即LR（0）文法的项目集规范族的任何一个项目集）文法的项目集规范族的任何一

18、个项目集都不包含冲突项目，仅当一个文法是都不包含冲突项目，仅当一个文法是LR（0）文）文法时，才能构造出不含冲突的法时，才能构造出不含冲突的LR（0）分析表）分析表第40页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造nSLR(1)分析法的引出分析法的引出n例简单算术表达式文法例简单算术表达式文法G：n0.SEn1.EE+Tn2.ETn3.TT*Fn4.TFn5.F(E)n6.Fi第41页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造n它的项目集规范族如下图所示：第42页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造n项项目目集集规规范范族族共共

19、有有12个个状状态态（I0-I11），根根据据项项目目集集规规范范族族构构造造LR(0)分分析析表表，如如下：下：第43页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造n因因M2*=s7r2、M9*=s7r1，分分析析表表含含多多重重定定义义，故故上上述述分分析析表表不不是是LR(0)分析表。分析表。第44页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造nSLR(1)分析法的基本思想分析法的基本思想n假定假定I是项目集规范族的一个项目集是项目集规范族的一个项目集nI=X.b，A.，B.n若若follow(A)follow(B)=、follow(A)b=、foll

20、ow(B)b=，则则SLR(1)分分析析法法处理如下：处理如下：第45页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造 n若若当当前前输输入入符符号号t.code和和b相相等等，则则移移进输入符号。进输入符号。n若若当当前前输输入入符符号号t.codefollow(A)，则则用产生式用产生式A进行归约。进行归约。n若若当当前前输输入入符符号号t.codefollow(B)，则则用产生式用产生式B进行归约。进行归约。n此外报错。此外报错。第46页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造n构造法构造法nSLR(1)分分析析表表的的构构造造是是在在LR(0)分分

21、析析表表基基础础上上进进行行的的，只只要要对对LR(0)分分析析表表的的构构造造方方法法稍稍加加修修改改，就就可可获获得得SLR(1)分分析析表表的构造方法，修改部分如下所述：的构造方法，修改部分如下所述：第47页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造n预备工作预备工作n引入产生式引入产生式n产生式编号产生式编号n构造状态转换函数和项目集规范族构造状态转换函数和项目集规范族n计算非终结符的计算非终结符的follow集。集。n构造法构造法nn若若归归约约项项目目A.Ii，对对于于任任何何afollow(A)，置置Mia=rk（k是是产产生生式式A的的编编号号，r表表示示归

22、归约约）。n第48页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造n接上例，构造接上例，构造G的的SLR(1)分析表。分析表。n解：解：预备工作预备工作n1）文法拓广（同上）文法拓广（同上）n2）产生式编号（同上）产生式编号（同上）n3）构造状态转换函数）构造状态转换函数GO(I,X)和项目集规范族（同上）和项目集规范族（同上）n4）计算非终结符的）计算非终结符的follow集集nfolow(S)=#、folow(E)=#,+,)、folow(T)=#,+,),*、folow(F)=#,+,),*第49页，此课件共58页哦5.6 SLR(1)分析表的构造分析表的构造n构造分析表

23、第50页，此课件共58页哦5.7LR语法分析器的控制程序语法分析器的控制程序n数据结构数据结构nLR分析表分析表n状态栈状态栈n符号栈符号栈n产生式右部符号串长度产生式右部符号串长度n手工模拟控制程序计算手工模拟控制程序计算第51页，此课件共58页哦5.7LR语法分析器的控制程序语法分析器的控制程序n算法描述算法描述n分分析析表表用用二二维维数数组组M存存储储，栈栈顶顶状状态态用用Stop表表示示，当当前前输输入入符符号号用用t.code表表示示，控制程序的算法归纳如下：控制程序的算法归纳如下：第52页，此课件共58页哦5.7LR语法分析器的控制程序语法分析器的控制程序n移进移进n若若MSto

24、pt.code=sj，说说明明句句柄柄尚尚未未形形成成，应应执执行行移移进进操操作作。s表表示示移移进进，j为为状状态态号号，将将j移移入入状状态态栈栈，将将t.code移移入入符符号号栈栈，j成成为为新新的的栈栈顶顶状状态态Stop。读读下下一一个单词。个单词。第53页，此课件共58页哦5.7LR语法分析器的控制程序语法分析器的控制程序n归约归约n若若MStopt.code=rk，说说明明句句柄柄已已出出现现在在栈栈顶顶，应应该该用用编编号号为为k的的产产生生式式A进进行行归归约约。假假设设，LEN()=r，MStop-rA=j。首首先先将将栈栈顶顶r个个元元素素出出栈栈，然然后后将将j和和

25、A分分别别移移入入状状态态栈栈和和符符号号栈栈，j成成为为新的栈顶状态新的栈顶状态Stop。当前处理单词不变。当前处理单词不变。第54页，此课件共58页哦5.7LR语法分析器的控制程序语法分析器的控制程序n接受接受nMStopt.code=Acc，表表示示输输入入串串是是一一个合法句子，程序终止运行。个合法句子，程序终止运行。n出错出错nMStopt.code=空空白白，表表示示出出错错，最最简简单处理为程序终止运行。单处理为程序终止运行。第55页，此课件共58页哦5.8二义文法在二义文法在LR分析法中的分析法中的应用应用n任任何何二二义义文文法法都都不不是是LR文文法法，可可通通过过现现两种

26、途径来解决文法的二义性问题。两种途径来解决文法的二义性问题。n例例 简简 单单 算算 术术 表表 达达 式式 文文 法法 G：EE+E|E*E|(E)|i，它它是是一一个个二二义义文文法法，二二义义性性源源自自于于文文法法本本身身没没有有规规定定运运算符的优先性和结合性。算符的优先性和结合性。第56页，此课件共58页哦5.8二义文法在二义文法在LR分析法中的分析法中的应用应用n根据条件将文法修改成无二义性文法根据条件将文法修改成无二义性文法n规规定定*优优先先+，同同级级运运算算服服从从左左结结合合，修修改文法为改文法为G1：nEE+T|TnTT*F|FnF(E)|inG1是与是与G等价的非二义文法。等价的非二义文法。第57页，此课件共58页哦5.8二义文法在二义文法在LR分析法中的分析法中的应用应用n根据条件消除分析表的多重定义根据条件消除分析表的多重定义n二二义义文文法法简简单单，分分析析表表规规模模小小，在在程程序序设设计计语语言言中中仍仍有有应应用用。可可根根据据二二义义文文法法构构造造分分析析表表，然然后后根根据据条条件件消消除除分分析析表表的多重定义。的多重定义。第58页，此课件共58页哦