第16讲算符优先分析表的构造-讲义-编译原理及实践教程(第3版)-黄贤英-清华大学出版社_第1页
第16讲算符优先分析表的构造-讲义-编译原理及实践教程(第3版)-黄贤英-清华大学出版社_第2页
第16讲算符优先分析表的构造-讲义-编译原理及实践教程(第3版)-黄贤英-清华大学出版社_第3页
第16讲算符优先分析表的构造-讲义-编译原理及实践教程(第3版)-黄贤英-清华大学出版社_第4页
第16讲算符优先分析表的构造-讲义-编译原理及实践教程(第3版)-黄贤英-清华大学出版社_第5页
已阅读5页,还剩1页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第16讲自下而上语法分析方法0.本节教学内容:1)回顾上一节的内容,为本节打下基础2)算符优先关系表的生成算法3)算符优先分析方法一.本节教学要求:1.掌握算符优先分析方法2.掌握算符优先关系表的构造算法二.教学方式及学时分配:采用教师讲授+提问+学生练习的方式总共2学时,提问及总结以前的内容大约20分钟三.教学重点:1.算符优先分析方法及其基本概念四.教学难点:1.算符优先分析中最左素短语的概念五.教学过程中的注意事项:1.算符优先关系表的构造要使用FirstVT,LastVT集合,因此必须在课前重新复习FirstVT,LastVT集的定义和计算方法,目的是为了讲解算符优先分析表的构造算法。2.本节内容中总控程序的工作过程的理解是关键,一定要讲清楚总控程序的工作过程,以及何时进行归约,如何进行归约。3.在讲解算符优先分析时要和规范归约过程进行比较,最左素短语与句柄之间的差别,也就是何时进行归约构成了算法之间的主要差别。六.学习方法:1.从整体上把握算符优先分析总控程序的工作过程以及何时进行归约,为理解和计算作准备。七.教学内容FirstVT,LastVT集的概念和计算方法2.构造优先关系表如果每个非终结符的先关系表。FIRSTVT和LASTVT集均已知,则可根据定义构造优

–构造思路:•(1)若产生式是形如:则有a==bP→„ab„或P→„aQb„的形式,...aR...的形式,则对于每个b∈a∈•(2)若产生式右部是FirstVT(R)都有a《b•(3)若产生式右部有...Rb的形式,则对于每个LastVT(R)集,都有a》b优先关系表构造算法for每个形如PX1X2„Xn的产生式dofori=1ton-1dobeginifXi和Xi+1都是终结符Xi=Xi+1ifi<=n-2,Xi和Xi+2是终结符Xi=Xi+2ifXi为终结符,Xi+1为非终结符thenthen,但Xi+1为非终结符thenforFirstVT中的每个元素adoXi<a;ifXi为非终结符,Xi+1为终结符thenforLastVT中的每个元素adoa>Xi+1;end;练习给定文法G[S]:S->a|(T)T->T,S|S的FirstVT和LastVT集,构造优先关系表。{a,(}FirstVT(S)=FirstVT(T)={a,(,,}LastVT(S)={a,)}LastVT(T)={a,),,}a,()#a,>><>>>=>><<<<()>=#<<3.算符优先分析方法原理:–通过比较相邻终结符间的优先关系来实现•实现机制:–仍然采用“移进-归约”方式,不断移进输入符号,识别可归约串,并进行归约。•分析方法:–根据优先性“高于”来识别句柄的头,句柄的尾。各种优先关系已经存于优先关系表中。根据优先性“低于”来识别几个定义1.算符优先分析过程,不是严格的规范归约,每次归约的符号串,不一定是规范归约中的“句柄”,当前句型的最左素短语不能识别只由一个非终结符组成的句柄,是.•2.素短语:是一个短语,至少含有一个终结符其它更小的素短语。,且除自身外,不再包含任何•3.最左素短语(leftmostprimephrase):是指位于句型最左边的那个素短语。例:给定右边的文法的一个句型:T*F+i求其短语、素短语、最左素短语?T->F|T*FE->T|E+TEE+TTFiT*FF->i|(E)短语有:i,T*F,T*F+i素短语有:i,T*F最左素短语是:T*F练习:给定文法G[E]:E->T|E+TT->F|T*FE+E+TETFPTT*FiF->i|(E)求句型T+T*F+i的短语、素短语、最左素短语。根据语法树可知:句型#T+T*F+i#的短语有:T—相对非终结符E的短语T的短语T*F—相对非终结符T+T*F—相对非终结符i—相对非终结符E的短语P、F、T的短语E的短语T+T*F+i—相对非终结符根据素短语的定义可知:i和T*F为素短语。其中:T+T*F(含T*F素短语)、T+T*F+i(含T*F素短语)和T(不含终结符)也不是素短语T*F为最左素短语。定理:设算符文法G的句型的一般形式为#N1a1N2a2„Nnan#(Ni∈VN∪{ε},ai∈VT)它的最左素短语是满足下列条件的最左子串:NiaiNi+1ai+1„NjajNj+1其中:ai-1≮ai,ai≡ai+1≡„..≡aj-1≡aj,aj≯aj+1该定理说明了最左素短语与周围符号之间的关系算符优先分析分析时使用一个栈和输入缓冲区,句型表示:一般形式:初态:符号栈的内容剩余输入串#输入串#终态:#S#符号栈内容+输入缓冲区内容=#当前句型#句型的一般形式:#N1a1N2a2„NnanNn+1#(ai为终结符,Ni为可有可无的分析栈中为:#,输入缓冲区为:输入串非终结符)算符优先分析过程#:开始:•过程:–(1)从左向右扫描输入符号并移入堆栈足aj>aj+1时为止.–(2)再从ai开始往左扫描堆栈止,并查优先矩阵,直至找到满,直至找到某个i,满足ai-1ai为–(3)NiaiNi+1ai+1„NjajNj+1形式的子串即为最左素短语,应被归约。•结束:输入缓冲区为#,分析栈中为练习:给定文法#S,分析成功;否则失败G[E]:E->T|E+TT->F|T*FF->i|(E)对表达式i+i*i的算符优先过程栈输入缓冲说明#i+i*i#初始状态#i#F+i*i##<i,i入栈+i*i##<i>+,用Fi归约#F+i*i##F+i*i##F+F*i##F+F*i##F+F*i##F+F*F##F+T##<+,+入栈+<i,i入栈+<i>*,用Fi归约+<*,*入栈*<i,i入栈*<i>#,用Fi归约+<*>#,用TF*F归约#E##<+>#,用ET+F归约算法描述:P93k:=1;s[k]=‘#’;Repeata:=下一个输入符号;Ifs[k]∈VtTHENj:=kELSEj:=k-1;WHILEs[j]>aDOBEGINREPEATq:=s[j];IFs[j-1]∈VtTHENj:=j-1elsej:=j-2;UNTILs[j]<q;把s[j+1]„.s[k]归约为某个N,将N入栈;k:=j+1;ENDIFs[j]<aORs[j]=aTHENBEGINk:=k+1;s[k]:=a;END;ELSEerror;UNTILa=‘#’;•算符优先分析一般并不等价于规范归约•并不对文法的非终结符定义优先关系,无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如:TF)进行归约。•算符优先分析比规范归约过程要快,跳过了所有的单非终结产生式。•可能将本来不是句子的输入串误认为是句子。总结归约的策略:在文法中寻找这样的产生式:它的右部形如应位置上的终结符号完全相同:NiaiNi+1ai+1„NjajNj+1,其中每个终结符号与最左素短语对,而每一个非终结符号uk应与相应位置上的非终结符号Nk相对应,不必完全相同。–简单、效率高算符优先分析法小结优点–能够处理部分二义性文法•缺点–文法书写限制大–占用内存空间大–不规范、存在查不到的语法错误4.本次教学内容小节:1.算符优先分析方法总控程序的工作过程2.算符优先关系表的自动生成算法3.算符优先分析中

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论