![第2章+文法和语言_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-1/6/57c6c4dc-1bc8-4668-929d-c09eb8ead199/57c6c4dc-1bc8-4668-929d-c09eb8ead1991.gif)
![第2章+文法和语言_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-1/6/57c6c4dc-1bc8-4668-929d-c09eb8ead199/57c6c4dc-1bc8-4668-929d-c09eb8ead1992.gif)
![第2章+文法和语言_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-1/6/57c6c4dc-1bc8-4668-929d-c09eb8ead199/57c6c4dc-1bc8-4668-929d-c09eb8ead1993.gif)
![第2章+文法和语言_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-1/6/57c6c4dc-1bc8-4668-929d-c09eb8ead199/57c6c4dc-1bc8-4668-929d-c09eb8ead1994.gif)
![第2章+文法和语言_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-1/6/57c6c4dc-1bc8-4668-929d-c09eb8ead199/57c6c4dc-1bc8-4668-929d-c09eb8ead1995.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、文法和语言文法和语言n一个程序设计语言是一个记号系统,它的完整一个程序设计语言是一个记号系统,它的完整定义应包括两个方面定义应包括两个方面:q语法语法指一组规则,用它可以形成和产生一个合适的程序。q语义语义n静态语义是一系列限定规则,并确定哪些合乎语法的程序是合适的;n动态语义也称作运行语义或执行语义,表明程序要做些什么,要计算什么。n文法是阐明语法的一个工具文法是阐明语法的一个工具2. 2 符号和符号串符号和符号串n字母表字母表 q字母表是元素的非空有穷集合字母表是元素的非空有穷集合n符号符号q字母表中的元素称为符号字母表中的元素称为符号n符号串符号串q由符号组成的任何有穷序列由符号组成的任
2、何有穷序列q符号串符号串x的长度:的长度:x所包含的符号个数,记作所包含的符号个数,记作|x|q空符号串空符号串 n符号串的头、尾、固有头、固有尾符号串的头、尾、固有头、固有尾n符号串的连接符号串的连接q设设x和和y是符号串,它们的连接是符号串,它们的连接xy是把是把y的符号写在的符号写在x的符号之后得到的符号串。的符号之后得到的符号串。n符号串的方幂符号串的方幂q设设x是符号串,把是符号串,把x自身连接自身连接n次得到符号串次得到符号串z,即即z=xx.xx,称为符号串称为符号串x的方幂。的方幂。0=, n =n-1 =n-1(n0)n符号串集合及其运算符号串集合及其运算q若集合若集合A中的
3、一切元素都是字母表上的符号串,则中的一切元素都是字母表上的符号串,则称称A为该字母表上的符号串集合。为该字母表上的符号串集合。q合并:字符串集合合并:字符串集合A和和B的合并的合并AB=|A或或B。q乘积:字符串集合乘积:字符串集合A和和B的乘积的乘积AB=|A且且B。显然显然A=A=A。q幂:幂:An=An-1A=AAn-1(n0),),并规定并规定A0=。q正闭包:正闭包:A+ =A1A2An。q闭包:闭包:A*=A0A+。显然显然*=012n 。*表示表示上的所有有穷长的串的集合上的所有有穷长的串的集合2.3 文法和语言的形式定义文法和语言的形式定义n引例引例1 =a, A=an|n1n
4、引例引例2 =a,b, A=anbm|n,m1n引例引例3 =a,b, A=anbn|n1n定义定义2.1-文法文法文法文法G定义为四元组定义为四元组(VN,VT,P,S)。其中其中VN: 非终结符的非空有穷集;非终结符的非空有穷集;VT: 终结符的非空有穷集;终结符的非空有穷集;P: 产生式(也称规则)的非空有穷集;产生式(也称规则)的非空有穷集; S: 开始符号,它是一个非终结符,至少要开始符号,它是一个非终结符,至少要在一条规则中作为左部出现。在一条规则中作为左部出现。通常用通常用V表示表示VN VT,V称为文法称为文法G的的文法文法符号集符号集。n例例1=a,b, A=ambn|mn0
5、n例例2=a,b, A=wwR|wR是是w的反向串的反向串n例例3GS:SaSBE|aBEEB BEaB abbB bbbE beeE een定义定义2.2-直接推导、直接归约直接推导、直接归约设设 是文法是文法G=(VN ,VT,P,S)的规则,的规则, 和和 是是V*中的任意符号串。若有符号串中的任意符号串。若有符号串v,w满满足:足:v=, w=,则说则说 v(应用规则应用规则 )直接产生)直接产生w,或说或说w是是v的直接推导,或说的直接推导,或说w直接归约到直接归约到v,记作记作 vw。n定义定义2.3 -推导推导若存在若存在v w0 w1 . wn=w (n0),则则说说v推导出推
6、导出w,或说或说w归约到归约到v,记为记为 v w。n定义定义2.4-星推导星推导若有若有v w,或或v=w,则记为则记为v w。*n最左(最右)推导最左(最右)推导q如果在推导的任何一步如果在推导的任何一步 ,其中,其中 V* ,都是,都是对对 中的最左(最右)非终结符进行替换,则称这中的最左(最右)非终结符进行替换,则称这种推导为最左(最右)推导种推导为最左(最右)推导n规范推导规范推导q在形式语言中,最右推导常被称为规范推导。在形式语言中,最右推导常被称为规范推导。n定义定义2.5-句型、句子句型、句子设设有文法有文法G。若若S x,则称则称x是文法是文法G的句型;的句型;若若S x,且
7、且xVT*,则称则称x是文法是文法G的句子。的句子。n规范句型规范句型q由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。*n定义定义2.6- 语言语言由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的一切的一切句子的集合。句子的集合。n定义定义2.7-文法等价文法等价若若L(G1) = L(G2),则称文法则称文法G1和和G2是等价的。是等价的。2.4 文法的类型文法的类型nChomsky分类分类q0型文法型文法 短语文法短语文法对任一产生式对任一产生式,都有都有(VNVT)+且至少含有一个且至少含有一个非终结符,非终结符, (VNVT)*q1型文法型
8、文法-上下文有关文法(上下文有关文法(CSG) 对任一产生式对任一产生式,都有都有|, 仅仅仅仅 S除外除外q2型文法型文法-上下文无关文法(上下文无关文法(CFG) 对任一产生式对任一产生式,都有都有VN , (VNVT)*q3型文法型文法-正规文法(正规文法(RG) 任一产生式任一产生式的形式都为的形式都为AaB或或Aa,其中其中AVN ,BVN ,aVT2型文法型文法1型文法型文法0型文法3型文法2型文法型文法1型文法型文法2型文法型文法1型文法型文法2型文法型文法1型文法型文法0型文法3型文法n0型文法产生的语言称为型文法产生的语言称为0型语言型语言1型文法或上下文有关文法产生的语言称
9、为型文法或上下文有关文法产生的语言称为1型语言或上下文有关语言型语言或上下文有关语言2型文法或上下文无关文法产生的语言称为型文法或上下文无关文法产生的语言称为2型语言或上下文无关语言型语言或上下文无关语言3型文法或正规文法产生的语言称为型文法或正规文法产生的语言称为3型语言型语言正则规语言正则规语言n例例给出一个正规文法给出一个正规文法G,使使L(G)=anbm|n,m12.5 上下文无关文法及其语法树上下文无关文法及其语法树n引例引例GS:SaAS | aASbA | SS | ba写出写出aabbaa的最左推导和最右推的最左推导和最右推导。导。n给定文法给定文法G=( VN,VT,P,S)
10、,对于对于G的任何句型的任何句型都能够造与之关联的语法树。这棵树满足下列都能够造与之关联的语法树。这棵树满足下列4个条件:个条件:q每个结点都有一个标记,此标记是每个结点都有一个标记,此标记是V的一个符号。的一个符号。q根的标记是根的标记是S。q若一结点若一结点n至少有一个它自己除外的子孙,并且有至少有一个它自己除外的子孙,并且有标记标记A,则肯定则肯定AVN。q如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次其直接子孙结点从左到右的次序是序是n1,n2,nk,其标记分别为其标记分别为A1,A2,Ak,那么那么AA1A2Ak一定是一定是P中的一个产生式。中的一个产生式。n一棵语法树
11、表示了一个句型的种种可能的一棵语法树表示了一个句型的种种可能的(但未但未必是所有的必是所有的)不同推导过程,包括最左不同推导过程,包括最左(最右最右)推推导。从左到右读出推导树的叶子标记连接成的导。从左到右读出推导树的叶子标记连接成的文法符号串为文法符号串为G的的句型。句型。n若一个文法存在某个句子对应两棵不同的语法若一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。或者说,若一个树,则称这个文法是二义的。或者说,若一个文法存在某个句子有两个不同的最左(右)推文法存在某个句子有两个不同的最左(右)推导,则称这个文法是二义的。导,则称这个文法是二义的。n例例1GE:EE+E|E*E
12、|(E)|In例例2GE:E-EE|-E|a|b|cn文法的二义性和语言的二义性是两个不同的概文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法念。因为可能有两个不同的文法G和和G,其中其中G是二义的,但是却有是二义的,但是却有L(G)=L(G),也就是说也就是说,这两个文法所产生的语言是相同的。,这两个文法所产生的语言是相同的。2.6 句型的分析句型的分析n句型分析句型分析q句型分析就是识别一个符号串是否为某文法的句型,句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。是某个推导的构造过程。n分析程序(识别程序)分析程序(识别程序)q在语言的编译实现中,把
13、完成句型分析的程序称为分在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序。析程序或识别程序。n分析算法分析算法q自上而下分析法自上而下分析法q自下而上分析法自下而上分析法考虑文法考虑文法GS:S cAdA abA a识别输入串识别输入串w=cabd是否该文法的句子。是否该文法的句子。q自上而下分析法的主要问题:自上而下分析法的主要问题:假定要被替换的最左非终结符是假定要被替换的最左非终结符是V且有且有n条产生式:条产生式:V 1 | 2 | n,那么如何确定用哪个右部去替那么如何确定用哪个右部去替换换V?q自下而上分析法的关键问题:自下而上分析法的关键问题:从当前串中选择一个可以
14、归约到某个非终结符的子从当前串中选择一个可以归约到某个非终结符的子串(称为串(称为“可归约串可归约串”)。)。n定义定义3.8-短语,直接短语,句柄短语,直接短语,句柄设文法设文法GS如果有如果有S A且且A ,则称则称是句型是句型相相对于非终结符对于非终结符A的短语。的短语。如果有如果有A ,则称则称是句型是句型相对于非终相对于非终结符结符A的直接短语(简单短语)。的直接短语(简单短语)。一个句型的最左直接短语称为该句型的句柄一个句型的最左直接短语称为该句型的句柄。*n例例设文法设文法GE:EE+T|TEE+T|TTTTT* *F|FF|FF(E)|iF(E)|i求句型求句型i i* *i+ii+i的短语、直接短语和句柄的短语、直接短语和句柄2.7 有关文法实用中的一些说明有关文法实用中的一些说明n在实用中,我们将限制文法中不得含有有害规则在实用中,我们将限制文法中不得含有有害规则和多余规则。和多余规则。q有害规则有害规则是形如是形如 U U的产生式。的产生式。q多余规则多余规则是文法中连一个句子
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 第3章《硫、氮及其循环》单元检测题 高一上学期沪科版(2020)必修第一册
- 初中作文指导:《小标题式结构作文》教学设计
- 治本攻坚三年行动工作节点落实情况汇报
- 外科感染病人的护理
- 黄金卷05(考试版)-【赢在高考·黄金8卷】备战2024年高考地理模拟卷(山东专用)
- 适用于新高考新教材备战2025届高考历史一轮总复习第5单元晚清时期的内忧外患与救亡图存课时练第16讲挽救民族危亡的斗争课件
- 射频消融并发症
- 老房装饰拆除合同
- 2024年饲用生物活性制剂项目发展计划
- 读彩虹鸽有感1000字
- 施工组织设计评审表
- 六年级下册研究性学习全册教案
- 小浪底土石坝的砂石料加工系统
- 液压与气动技术ppt课件
- 新教师如何备课和上课PPT
- 《2021给水排水规范资料》TCECS463-2017 污水提升装置应用技术规程
- 小学生幼儿园写拼音练习表(24个韵母)
- 多源信息融合理论及技术发展
- 0.报告正本目录及业务项目管理控制流转表
- 第5讲MATLAB多项式及插值
- 机组启动试验设备操作运行规程
评论
0/150
提交评论