编译原理ppt31_第1页
编译原理ppt31_第2页
编译原理ppt31_第3页
编译原理ppt31_第4页
编译原理ppt31_第5页
已阅读5页,还剩22页未读 继续免费阅读

下载本文档

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

文档简介

1、第三章 语法分析任务:识别由词法分析得出的记号序列是否是给定文法的句子主要内容上下文无关文法自上而下语法分析自下而上语法分析13.1 上下文无关文法接收词法分析器提供的记号串检查记号串是否能由源程序语言的文法产生用易于理解的方式提示语法错误信息,并能从常见的错误中恢复过来词 法分析器记号取下一个记号源程序语法树前端的其余部分语法分析器中间表示符号表2自上而下语法分析自下而上语法分析33.1.1 上下文无关文法的定义文法是描述语言的语法结构的形式规则以自然语言为例 He gave me a book.4 He me a gave book 5从出发,反复把规则中“”左边的成分替换成右边的成分He

2、 He He gave He gave He gave me He gave me He gave me a He gave me a book6句子主语谓语间接宾语直接宾语代词动词冠词名词Hegavemeabook代词7一个上下文无关文法(Context-Free Grammar) G是一个四元组(VT,VN,S,P),其中VT是一个非空有限集,它的每个元素称为终结符号;VN是一个非空有限集,它的每个元素称为非终结符号,VTVN;S是一个非终结符号,称为开始符号;是一个产生式集合(有限),每个产生式的形式是P,其中,PVN, (VTVN)* 。开始符号S至少必须在某个产生式的左部出现一次。8

3、说明非终结符号(Nonterminal Symbol):是所要定义语言中的一个语法实体(或语法单位,语法范畴、语法成分),每个非终结符号表示一定符号串的集合终结符号(Terminal Symbol):是组成语言的基本符号,例如He,gave,book等等,在程序语言中就是单词记号,如基本字、标识符、常量、算符和界符等开始符号(Start Symbol):是一个特殊的非终结符,也称识别符号,它所代表的符号串的集合就是该文法所定义的语言9产生式(Production):用来说明由终结符和非终结符怎样组合成符号串,也称产生规则 形式为: A 其中A是一个非终结符, 是由终结符和/或非终结符组成的符号

4、串 “”有的地方也用“:=”表示,含义是“定义为.”10例如,算术表达式的上下文无关文法expr expr op exprexpr (expr)expr exprexpr idop +op *终结符:id,+,*, (,)非终结符:expr, op开始符号:expr11符号使用约定下列符号是终结符字母表中比较靠前的小写字母,如a,b,c等操作符,如+,-等标点符号,如逗号,句号等数字0,1,.,9黑体串,如id, if等12下列符号是非终结符字母表中比较靠前的大写字母,如A,B,C等字母S,常代表开始符号小写斜体名字,如expr, stmt等13字母表中比较靠后的大写字母,如X,Y,Z等,表示

5、文法符号,也就是说,可以是终结符也可以是非终结符字母表中比较靠后的小写字母,如u,v,.,z等,表示终结符号串小写希腊字母,如, , 等,表示文法符号串对于多个左部相同的产生式:A1,A2 ,An ,可写为: A1| 2|n ,其中每个i称为是A的一个候选式。除非另有说明,否则第一个产生式左部的符号是开始符号14例,算术表达式的文法可以简写为EEAE | (E) | -E | idA + | * 153.1.2 推导有了文法规则以后,怎样定义该文法所表示的语言?推导:是从开始符号开始,通过使用产生式的右部取代左部,直到所得的符号串中不再包含非终结符为止每使用产生规则替换一次,就说进行了一次推导

6、,并用“”表示这种替换操作16文法G(E) E E+E | E*E | (E) | -E | id证明字符串id+id是一个表达式E E+E id+E id+id17称A直接推出,即A 仅当A 是一个产生式, 且, (VT VN)* 。如果1 2 n,则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导,则称1可以推导出n 。18通常,用 表示:从1出发,经过一步或若干步,可以推出n。 用 表示:从1出发,经过0步或若干步,可以推出n。19定义:假定G是一个文法,S 是它的开始符号。如果 ,则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言,将它记为 L

7、(G)。20例,字符串-(id+id)是文法GE的句子E -E -(E) -(E+E) -(id+E) -(id+id)21推导过程中的选择选择被替换的非终结符选择用于替换该非终结符的候选式最左推导:任何一步都是对中的最左非终结符进行替换最右推导(规范推导):任何一步都是对中的最右非终结符进行替换22例:文法GS: SAB AaA | a BbB | b该文法定义的语言L(G)=ambn|m,n1给出aabb的最左推导和最右推导。最左:SABaABaaBaabBaabb最右:SABAbBAbbaAbbaabb233.1.3 分析树和推导分析树是推导的图形表示。分析树的每个内部结点由非终结符标记,它的子结点由该非终结符本次推导所用产生式的右部各符号从左到右依次标记。分析树的叶结点由非终结符或终结符标记,所有这些标记从左到右构成一个句型。注意:分析树不能显示出替代顺序的选择24EEEEE()EEE()EEE+EE()EEE+idEE()EEE+idid253.1.4 二义性如果一个文法存在某个句子对应两棵不同的分析树,则称这个文法是二义的。若一个文法中存在某个句子,它有两个不同的最左(最右)推导,则这个文法是二义的。26G E : E E + E | E * E

温馨提示

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

评论

0/150

提交评论