




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 社交电商运营模式创新案例研究
- 2025至2030年中国电脑回单柜数据监测研究报告
- 电影产业发展趋势与未来展望
- 2025至2030年中国环烷基油墨油数据监测研究报告
- 合同解约申请书
- 知识产权交易平台在商业领域的实践与探索
- 门窗店合作合同范本
- 科技与空间现代茶室设计中的智能应用
- 2025年辽宁医药职业学院单招职业倾向性测试题库标准卷
- 2025至2030年中国液位控制计数据监测研究报告
- 《飞科电器公司盈利能力存在的问题及完善对策(7800字论文)》
- 零星维修工程项目施工方案1
- 楚辞离骚的原文全文完整注音版、拼音版标准翻译译文及注释
- 湖北省荆州市2024年七年级上学期期中数学试题【附答案】
- 刑事诉讼法课件
- 肩袖损伤病例讨论
- 《ISO 41001-2018 设施管理- 管理体系 要求及使用指南》专业读与应用指导材料之2:“4 组织环境-4.2 理解相关方的需要和期望”
- 2024年中国冻虾仁市场调查研究报告
- DB13(J)-T 8543-2023 公共建筑节能设计标准(节能72%)
- 2024年国家公务员考试行政职业能力测验真题及答案
- 某港口码头工程施工组织设计
评论
0/150
提交评论