欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    程序语言的基本知识.ppt

    • 资源ID:6596250       资源大小:397KB        全文页数:70页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    程序语言的基本知识.ppt

    编 译 原 理,杭州电子科技大学,2023/11/16,2,第 2 章 程序语言的基本知识,符号串的集合文法和语言分析树和二义性形式语言概观,2023/11/16,3,2.1 符号串的集合,字母表,字母表是符号的非空有穷集合,用 表示,符号:可以相互区别的记号(元素),不同的语言有不同的字母表英语26个英文字母Pascal语言 AZ,az,09,+,-,*,/,:,;,.,(,),2023/11/16,4,2.1 符号串的集合,符号串,符号串是由字母表中的符号所组成的有穷序列,例如:=a,b 则 a,b,aa,ab,aabba都是上的符号串是任何上的符号串,在语言理论中,符号串又称为:句子、字,2023/11/16,5,2.1 符号串的集合,符号串的长度符号串中包含符号的个数符号串 s 的长度记为|s|,例,对于字母表a,b,c,aab 是其上的一个符号串,|aab|=3 注意:空符号串,|=0,2023/11/16,6,2.1 符号串的集合,符号串的前缀、后缀、子串,后缀:删去符号串 s 头部的零个或多于零个符号得到的符号串,前缀:移走符号串 s 尾部的零个或多于零个符号得到的符号串,2023/11/16,7,2.1 符号串的集合,符号串的真前缀、真后缀和真子串非空,子串:从 s 中删去一个前缀和一个后缀得到的符号串,*对于每个符号串s,s 和两者都是符号串 s 的前缀、后缀和子串,2023/11/16,8,2.1 符号串的集合,符号串的运算:连接:符号串、的连接,是把 的符号写在 的符号之后得到的符号串,如=ab,=cd 则=abcd 注:=,方幂:符号串自身连接 n 次得到的符号串,n 定义为 n 个1=,2=,注:0=,2023/11/16,9,2.1 符号串的集合,例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的 PASCAL 程序构成的集合,注意:空集、和 的不同,语言,某个字母表上的符号串的集合,2023/11/16,10,2.1 符号串的集合,语言的运算:,语言是符号串的集合,集合的运算有并、交、差等,并运算 等同于集合的并运算,2023/11/16,11,2.1 符号串的集合,连接两个符号串集合 L 和 M 的乘积定义为:LM=st|s L 且 t M,例如:集合 A=ab,cde B=0,1 则 AB=ab1,ab0,cde0,cde1,L=L=L L L L=Ln L0=,2023/11/16,12,2.1 符号串的集合,*闭包(Kleene 闭包)L*=L0L1L2L3,+闭包(正闭包)L+=L1L2L3L*=L+,2023/11/16,13,2.1 符号串的集合,注意:后面通常是考虑字母表的*闭包和+闭包,例:=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2023/11/16,14,2.1 符号串的集合,综合性的例子:P10 例2.1 L=A,B,C,Z,a,b,c,z D=0,1,9,把 L 和 D 两个字母表看作长度为 1 的符号串集合,即语言,1.L D 2.LD 3.L4 4.L*5.L(L D)*6.D+,2023/11/16,15,2.2 文法和语言,如何来描述一种语言?,如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示,如果语言是无穷的,找出语言的有穷表示。,2023/11/16,16,2.2 文法和语言,语言有穷表示的两个途经,*文法即是以生成方式描述语言的,生成方式,语言中的每个句子可以用严格定义的规则来构造,2023/11/16,17,2.2 文法和语言,*自动机即是以识别方式描述语言的,识别方式,用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,(要么永远运行下去),2023/11/16,18,2.2 文法和语言,一个自然语言的例子,规则(文法),句子 主语 谓语(1)主语 冠词 形容词 名词(2)冠词the 形容词 grey 谓语 动词 直接宾语(5)动词 助动词 动词原形(6)助动词will 动词原形 eat 直接宾语 冠词 名词(9)名词wolf 名词 goat,2023/11/16,19,句子 主语 谓语 冠词 形容词 名词 谓语 the 形容词 名词 谓语 the grey名词 谓语 the grey wolf 谓语 the grey wolf 动词 直接宾语.the grey wolf will eat the goat,句子可根据规则推导(生成)出来:,The grey wolf will eat the goat,分析句子,2023/11/16,20,谓语,主语,冠词,形容词,名词,动词,直接宾语,句子,The grey wolf will eat the goat,2023/11/16,21,2.2 文法和语言,文法 G,VT,VN,S,P,终结符号集,非终结符号集,开始符号,产生式集合,文法的形式定义,2023/11/16,22,终结符号集 VT,代表语言中不可再分的基本符号,如汉语中的汉字、PASCAL语言中的基本字,其中的元素一般用小写字母或数字表示(a,b,c,0,1),2.2 文法和语言,2023/11/16,23,非终结符号集 VN,代表语法单位,如汉语中的语句、段落,PASCAL语言中的语句、表达式、子程序等,其中的元素一般用大写字母表示(A,B,C),或者用尖括号括起一个串来表示,2.2 文法和语言,2023/11/16,24,开始符号 S,是一个特殊的非终结符号,代表最高级的语法单位,S 至少要在一条产生式中作为左部出现,2.2 文法和语言,2023/11/16,25,产生式集合 P,2.2 文法和语言,产生式(重写规则、生成式),是形如或=的(,)有序对,且V+,V*,其中 V=(VTVN)称为产生式的左部,不能为空称为产生式的右部,可以为空(如:A),2023/11/16,26,2.2 文法和语言,例1:文法 G=(VT,VN,S,P)VN=S VT=0,1 P=S0S1,S01,可以只写出产生式,通过产生式可以得到文法的其它部分,左部相同的产生式可以写在一起,如:S 0S1|01,2023/11/16,27,2.2 文法和语言,例2:文法 G=(VT,VN,S,P)VN=,VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,2023/11/16,28,2.2 文法和语言,推 导,直接推导,直接归约,归 约,如果 A 是 G 的一条产生式,则称用代替A为一步直接推导,记为A,2023/11/16,29,2.2 文法和语言,推导是用产生式的右部代替左部,归约是用产生式的左部代替右部,归约是推导的逆过程,直接推导,直接归约,用A代替为一步直接归约,记为=A,2023/11/16,30,2.2 文法和语言,推导的长度直接推导的次数,长度大于等于 1 的推导,长度大于等于 0 的推导,推导的例子:S 0S1 00S11 000111,长度为 3 记为:S 000111 S S,2023/11/16,31,2.2 文法和语言,最左推导,最右推导,对中的最左非终结符进行展开,对中的最右非终结符进行展开,2023/11/16,32,2.2 文法和语言,例子:表达式文法 E E+T E T T T*F T F F(E)F a,最左推导:E T T*F F*F a*F a*a,*最右推导又称为规范推导,最右推导:E T T*F T*a F*a a*a,2023/11/16,33,2.2 文法和语言,最右归约,最左归约,最左推导的逆过程是最右归约,即对最右边的可归约串进行归约,最右推导的逆过程是最左归约,即对最左边的可归约串进行归约,a*a=a*F=F*F=T*F=T=E,a*a=F*a=T*a=T*F=T=E,*最左归约称为规范归约,2023/11/16,34,2.2 文法和语言,句型,句子,只包含终结符号的句型称为句子。句子是一种特殊的句型。,从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串(S)。句型可以既包含终结符号又包含非终结符号。,2023/11/16,35,2.2 文法和语言,例:在推导E T T*F F*F a*F a*a 中,,句型有:E、T、T*F、F*F、a*F、a*a,句子是:a*a,E E+T E T T T*F T F F(E)F a,2023/11/16,36,2.2 文法和语言,语言的形式定义,文法 G 推导出的所有句子组成的集合,称为语言,记为 L(G),L(G)=|S,VT*,2023/11/16,37,2.2 文法和语言,例子:G1:S A A 0A1 A 01,是由一个或多个 0 开头,后跟同样数目的 1 的符号串构成的集合(语言),,可记为:L(G)=0 n 1 n|n 1,2023/11/16,38,2.2 文法和语言,G2:E idE E+EE E*EE(E),产生的是表达式的集合,2023/11/16,39,2.2 文法和语言,G3:E E+T E T T T*F T F F(E)F id,产生的也是表达式的集合,2023/11/16,40,2.2 文法和语言,一个文法对应一个语言,但一个语言可能有若干个文法产生它,这若干个文法是等价的,称为 等价文法,例 G2 与 G3,2023/11/16,41,2.2 文法和语言,上下文无关文法能够描述现今程序设计语言的大部分语法结构,算术表达式赋值语句条件语句等,2023/11/16,42,2.2 文法和语言,表达式文法:G=(+,*,id,(,),E,E,P)P:E idE E+EE E*EE(E),E 表示算术表达式,id 表示程序的“变量”,该文法定义了由变量,+,*,(和)组成的算术表达式的语法结构,即:变量是算术表达式;若 E1 和 E2 是算术表达式,则 E1+E2,E1*E2 和(E1)也是算术表达式。,2023/11/16,43,2.2 文法和语言,描述一种简单赋值语句的产生式:赋值语句 id=E,描述条件语句的产生式:条件语句 if条件then语句 if条件then语句else语句,2023/11/16,44,2.3 分析树和二义性,分析树是描述上下文无关文法句型推导的一种直观方法,也称为推导树,分析树,句型推导,对应关系,2023/11/16,45,2.3 分析树和二义性,为句型推导构造分析树例子:,E T,E E+T E T T T*F T F F(E)F a,T*F,F*F,a*F,T,T,*,F,F,a,a,E,a*a,2023/11/16,46,2.3 分析树和二义性,分析树的特性:,根标识为开始符号,内部结点标识为非终结符号,每一内部结点及其子结点对应一条产生式,该结点是产生式的左部,子结点从左至右排列构成产生式的右部,叶结点从左至右排列构成句型,T,T,*,F,F,a,a,E,2023/11/16,47,2.3 分析树和二义性,分析树与句型推导的关系,一次推导(不是一个句型)对应一棵分析树,一棵分析树可能对应若干个推导,例如下面的推导对应的也是上面那棵分析树 E T T*F T*a F*a a*a,T,T,*,F,F,a,a,E,2023/11/16,48,2.3 分析树和二义性,说明分析树没有严格反映推导的顺序,但是一棵分析树对应一个最左推导,也只能对应一个最右推导,T,T,*,F,F,a,a,E,2023/11/16,49,2.3 分析树和二义性,对应最左推导,分析树,对应最右推导,分析树,2023/11/16,50,2.3 分析树和二义性,分析句型:短语、直接短语、句柄,如果 S A和 A,则称是关于 A的,句型的一个短语(子树的叶子),S,A,2023/11/16,51,2.3 分析树和二义性,例:句型 F*a 的短语,T,T,*,F,F,a,E,F*a,E E+T E T T T*F T F F(E)F a,F,a,2023/11/16,52,2.3 分析树和二义性,如果S A和 A,则称是关于 A的,句型的一个直接短语(只有父子两代的子树的叶子),S,A,2023/11/16,53,2.3 分析树和二义性,例:句型 F*a 的直接短语,T,T,*,F,F,a,E,F,a,2023/11/16,54,2.3 分析树和二义性,最左直接短语称为句柄最左性体现在分析树和句型中,S,A,2023/11/16,55,2.3 分析树和二义性,例:句型 F*a 的句柄,T,T,*,F,F,a,E,F,2023/11/16,56,2.3 分析树和二义性,句型的素短语、最左素短语,1、是关于 A 的,句型的一个短语,2、至少含有一个终结符,3、除自身外不含更小的带终结符的短语,称是关于 A 的,句型的一个素短语,句型最左边的素短语称为最左素短语,2023/11/16,57,例:,E,E,+,T,E,+,T,F,T,T,*,F,a,句型:T+T*F+a,短语:T+T*F+a、T+T*F、T*F、T(左边)、a,直接短语:T、T*F、a,句柄:T,素短语:T*F、a,最左素短语:T*F,E E+T E T T T*F T F F(E)F a,2023/11/16,58,2.3 分析树和二义性,句子、文法和语言的二义性,如果一个文法的句子有两棵或两棵以上的分析树,称此句子是二义的,最左(右)推导与分析树一一对应,句子二义说明它有两个或以上最左(右)推导,2023/11/16,59,2.3 分析树和二义性,E E+E id+E id+E*E id+id*E id+id*id,E E*E E+E*E id+E*E id+id*E id+id*id,E,E,+,E,id,*,E,E,id,id,E,E,*,E,id,+,E,E,id,id,例:,E id E E+E E E*E E(E),2023/11/16,60,2.3 分析树和二义性,如果一个文法有一个句子是二义的,此文法称为二义文法,E id E E+E E E*E E(E),2023/11/16,61,2.3 分析树和二义性,如果一个语言的所有文法都是二义的,称此语言是二义的,希望文法是无二义的,因为希望对于每一个句子进行唯一确定的分析,2023/11/16,62,2.4 形式语言概观,乔姆斯基(Chomsky)在 1956 年提出形式语言理论,他将形式文法分为四类(0,1,2,3),对应四类形式语言(0,1,2,3),分类的方法是对文法的产生式进行不同的限制,2023/11/16,63,2.4 形式语言概观,0 型文法|0,即(),1 型(上下文有关)文法|(),2 型(上下文无关)文法 A VN,(VTVN)*(A),3 型(正规)文法Aa 或 AaB(右线性)Aa 或 ABa(左线性),2023/11/16,64,2.4 形式语言概观,例:1 型(上下文有关)文法 文法 G:SCD AbbACaCABaaBCbCBBbbBADaDCBDbDDAabDL(G)=ww|wa,b*,2023/11/16,65,2.4 形式语言概观,例:2 型(上下文无关)文法 文法 G1:SaB|bAAa|aS|bAABb|bS|aBB 文法 G2:S0A|1B|0A0A|1B|0SB1B|1|0,2023/11/16,66,2.4 形式语言概观,例:3 型(正规)文法 文法 G:S0A|1B|0A0A|1B|0SB1B|1|0,2023/11/16,67,2.4 形式语言概观,0 型文法产生的语言称为 0 型语言,1 型文法或上下文有关文法产生的语言称为 1 型语言或上下文有关语言,2 型文法或上下文无关文法产生的语言称为 2 型语言或上下文无关语言,3 型文法或正则(正规)文法产生的语言称为 3 型语言正则(正规)语言,2023/11/16,68,2.4 形式语言概观,四种文法(语言)之间的逐级“包含”关系,2 型文法(语言),1 型文法(语言),0 型文法(语言),3 型文法(语言),2023/11/16,69,2.4 形式语言概观,识别各类语言的数学模型(自动机),图灵机(0 型语言),有界图灵机、线性有界自动机(1 型语言),下推自动机(2 型语言),有限自动机(3 型语言),2023/11/16,70,The End!,

    注意事项

    本文(程序语言的基本知识.ppt)为本站会员(牧羊曲112)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开