高级语言及其语法描述 (2)精选PPT.ppt

《高级语言及其语法描述 (2)精选PPT.ppt》由会员分享，可在线阅读，更多相关《高级语言及其语法描述 (2)精选PPT.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于高级语言及其语法描述(2)现在学习的是第1页，共49页常用的高级语言常用的高级语言 FORTRANFORTRAN数值计算数值计算 COBOLCOBOL事务处理事务处理 PASCALPASCAL结构程序设计结构程序设计 ADAADA大型程序、嵌入式实时系统大型程序、嵌入式实时系统 PROLOGPROLOG 逻辑程序设计逻辑程序设计 ALGOLALGOL算法语言算法语言 C/C+C/C+系统程序设计系统程序设计 JavaJavaInternetInternet程序设计程序设计现在学习的是第2页，共49页与机器语言或汇编语言比较与机器语言或汇编语言比较，高级语言高级语言的优点：的优点：较接近于数

2、学语言和工程语言较接近于数学语言和工程语言，比较直观、比较直观、自然和易于理解自然和易于理解;便于验证其正确性便于验证其正确性，易于改错易于改错;编写效率高编写效率高;易于移植易于移植.现在学习的是第3页，共49页2.1 2.1 程序语言的定义程序语言的定义自然语言与计算机语言的区别与联系：自然语言与计算机语言的区别与联系：计算机程序语言计算机程序语言一个记号系统，一个记号系统，类似于自然语言，由语法类似于自然语言，由语法+语义定义语义定义 自然语言自然语言（1 1）人与人的通讯工具）人与人的通讯工具 （2 2）语义：由环境、背景知识、语气等决定）语义：由环境、背景知识、语气等决定 二义性（常

3、有）二义性（常有）难以形式化难以形式化计算机语言计算机语言 （1 1）计算机系统间、人机间通讯工具）计算机系统间、人机间通讯工具 （2 2）具有严格的语法、语义）具有严格的语法、语义 易于形式化（严格）易于形式化（严格）现在学习的是第4页，共49页2.1 2.1 程序语言的定义程序语言的定义一、语法一、语法 一组规则，使用它可以形成和产生一个合式的程序，则这组一组规则，使用它可以形成和产生一个合式的程序，则这组规则称为语法规则称为语法。定义了程序的形式结构，是判断输入字符串是否构成一定义了程序的形式结构，是判断输入字符串是否构成一个形式上（即合式）正确程序的依据。个形式上（即合式）正确程序的依

4、据。词法规则词法规则单词符号的形成规则，即规定了字母表中单词符号的形成规则，即规定了字母表中 哪样的字符串是一个单词符号。哪样的字符串是一个单词符号。单词符号单词符号语言中具有独立意义的最基本结构。语言中具有独立意义的最基本结构。语法规则语法规则语法单位的形成规则，即规定了如何从单语法单位的形成规则，即规定了如何从单词符号形成更大的结构（即语法单位）。词符号形成更大的结构（即语法单位）。现在学习的是第5页，共49页2.1 2.1 程序语言的定义程序语言的定义二、语义二、语义 1、语义规则：一组规则，使用它可以定义一个程序的意义、语义规则：一组规则，使用它可以定义一个程序的意义。离开语义，语言只

5、不过是一堆符号的集合；在许多语言中有离开语义，语言只不过是一堆符号的集合；在许多语言中有着形式上完全相同的语法单位，但含义却不尽相同。着形式上完全相同的语法单位，但含义却不尽相同。、注意：、注意：阐明语义要比阐明语法难得多，现在还没有一阐明语义要比阐明语法难得多，现在还没有一种公认的形式系统，借助于它可以种公认的形式系统，借助于它可以自动地自动地构造构造出实用的编译程序。出实用的编译程序。本书本书基于属性文法的语法制导翻译方法基于属性文法的语法制导翻译方法较接近形式化较接近形式化现在学习的是第6页，共49页程序语言的基本功能和层次结构程序语言的基本功能和层次结构程序语言的基本功能：描述数据和对

6、数据程序语言的基本功能：描述数据和对数据的运算。的运算。所谓程序，本质上说是描述一定数据的处所谓程序，本质上说是描述一定数据的处理过程。理过程。现在学习的是第7页，共49页程序的层次结构程序的层次结构程序程序|子程序或分程序、过程、函数子程序或分程序、过程、函数|语句语句|表达式表达式|数据引用数据引用 算符算符 函数调用函数调用现在学习的是第8页，共49页2.2.程序语言的语法描述程序语言的语法描述基本概念基本概念1、有穷字母表。有穷字母表。中的每个元素。中的每个元素。由由中的符号所构成的一个有穷序列。中的符号所构成的一个有穷序列。空字，不包含任何符号的序列。空字，不包含任何符号的序列。上的

7、所有符号串的全体，包括上的所有符号串的全体，包括。注：注：区分：、空集：不含任何元素的集合：符号：符号：上的符号串：上的符号串：*：现在学习的是第9页，共49页2.2.程序语言的语法描述程序语言的语法描述、（连接）积、（连接）积：UV=|U V U、V *UV不一定等于不一定等于 VU,但但(UV)W=U(VW)Vn=VVVV0=V*=V0 V1 V2 V3 V+=VV*n个个V的闭包V的正则闭包注：注：V V*中的每个符号串都是由中的每个符号串都是由V V中的符号串经中的符号串经有限次有限次连接而成的。连接而成的。现在学习的是第10页，共49页例：例：=a,b,U=ab,b V=aa,bb

8、a,b*=a,b0 a,b1 a,b2 .=,a,b,ab,aa,bb,ba.a,b+=a,ba,b*=a,b,a,b,ab,aa,bb,ba.=a,b,ab,aa,bb,ba.ab,b aa,bb=abaa,abbb,baa,bbbU V=*=+=现在学习的是第11页，共49页设：设：V a,aa 那么：那么：V*=,a,aa,aaa,aaaa,V=a,aa,aaa,aaaa,现在学习的是第12页，共49页2.2.程序语言的语法描述程序语言的语法描述一、上下文无关文法一、上下文无关文法1 1、定义：、定义：文法：文法：描述语言的语法结构的形式规则（即语法规则）。描述语言的语法结构的形式规则（

9、即语法规则）。上下文无关文法：上下文无关文法：所定义的语法范畴（或语法单位）是所定义的语法范畴（或语法单位）是完全独立完全独立于这种范畴可能出现的环境于这种范畴可能出现的环境的一种文法。的一种文法。描述语法规则的且描述语法规则的且独立于环境独立于环境描述语法规则描述语法规则例：例：英语中，一般句子是由英语中，一般句子是由主主谓谓二部分构成。二部分构成。现在学习的是第13页，共49页2.2.程序语言的语法描述程序语言的语法描述2 2、文法、文法语法的类比：语法的类比：分析：分析：The grey wolf will eat the goat.T h e grey wolf will e a t

10、t h e g o a t直接宾语直接宾语名词名词动词动词谓语谓语名词名词形容词形容词冠词冠词主语主语句子句子助动词助动词动词原形动词原形冠词冠词现在学习的是第14页，共49页2.2.程序语言的语法描述程序语言的语法描述、产生句子的规则、产生句子的规则从产生语言的角度从产生语言的角度(1)(2)the grey (5)(6)(9)will eat wolf goat 现在学习的是第15页，共49页2.2.程序语言的语法描述程序语言的语法描述B B、句子的语法组成、句子的语法组成终结符号集，非终结符号集，终结符号集，非终结符号集，语法规则，开始符号语法规则，开始符号终结符号集终结符号集 VT=t

11、he,grey,wolf,will,eat,goat非终结符号集非终结符号集 VN=,语法规则集语法规则集 P=,开始符号开始符号 S=现在学习的是第16页，共49页2.2.程序语言的语法描述程序语言的语法描述C C、句子的派生（推导）、句子的派生（推导）根据规则根据规则 the the grey the grey wolf the grey wolf the grey wolf will eat the goat现在学习的是第17页，共49页2.2.程序语言的语法描述程序语言的语法描述D D、句子的语义要求、句子的语义要求the grey wolf will eat the goatthe

12、grey wolf will eat the wolfthe grey goat will eat the wolfthe grey goat will eat the goat符合语法且符合语义的句子仅是：符合语法且符合语义的句子仅是：the grey wolf will eat the goat现在学习的是第18页，共49页2.2.程序语言的语法描述程序语言的语法描述3 3、上下文无关文法的形式定义、上下文无关文法的形式定义是一个四元组（是一个四元组（，），）终结符号集，非空有限集终结符号集，非空有限集非终结符号集，非空有限集非终结符号集，非空有限集 终结符号：终结符号：描述单词符号描述单

13、词符号,组成语言的基本符号，是一个组成语言的基本符号，是一个 语言的不可再分的基本符号。语言的不可再分的基本符号。例如：基本字，标识符，常数，算符，界符等例如：基本字，标识符，常数，算符，界符等非终结符：非终结符：代表语法范畴，一个非终结符代表一个一定的语代表语法范畴，一个非终结符代表一个一定的语 法概念，每个非终结符表示一定符号串的集合。法概念，每个非终结符表示一定符号串的集合。例如：算术表达式，布尔表达式，赋值句，分程序，过程等例如：算术表达式，布尔表达式，赋值句，分程序，过程等现在学习的是第19页，共49页2.2.程序语言的语法描述程序语言的语法描述开始符号，一个特殊的非终结符号开始符号

14、，一个特殊的非终结符号产生式集合，有限集产生式集合，有限集产生式：定义语法范畴的一种书写规则产生式：定义语法范畴的一种书写规则形式：形式：A AVN,(VTVN)*注：注：“”:“定义为定义为”“”：“或或”非终结符号非终结符号:用大写字母、用大写字母、或汉语组代表或汉语组代表 终结符终结符:用小写字母用小写字母代表代表至少必须在某个产生式的至少必须在某个产生式的左部出现一次左部出现一次现在学习的是第20页，共49页巴科斯范式（BNF：Backus-Naur Form 的缩写）描述计算机语言语法的符号集。由 John Backus 和 Peter Naur 首次引入一种形式化符号来描述给定语言

15、的语法（最早用于描述ALGOL 60 编程语言）。John BackusPeter NaurBNF现在是定义一种计算机语言的标准方式。现在学习的是第21页，共49页2.2.程序语言的语法描述程序语言的语法描述例例1：上下文无关文法：上下文无关文法：Ei|EAE A+|*非终结符号：非终结符号：开始符号：开始符号：终结符号：终结符号：E，AE+，*，iGE现在学习的是第22页，共49页2.2.程序语言的语法描述程序语言的语法描述例例2：算算术术表表达达式式的的文文法法标识符标识符(id)(常量、变量常量、变量)是表达式是表达式(E)；表达式加一个表达式是表达式；表达式加一个表达式是表达式；表达式

16、减一个表达式是表达式；表达式减一个表达式是表达式；表达式乘一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号是表达式；表达式加上括号是表达式；Eid EE+E EE-E EE*E EE/E E(E)P:Eid|E+E|E-E|E*E|E/E|(E)现在学习的是第23页，共49页2.2.程序语言的语法描述程序语言的语法描述、文法与语言的关系、文法与语言的关系中心思想：中心思想：从文法的开始符号出发，反复连续使用产从文法的开始符号出发，反复连续使用产 生式，对非终结符施行生式，对非终结符施行替换替换和和展开展开。一个上下文无关文法

17、如何定义一个语言呢？一个上下文无关文法如何定义一个语言呢？现在学习的是第24页，共49页2.2.程序语言的语法描述程序语言的语法描述()(+)(+)(+)例：例：Eid|E+E|E-E|E*E|E/E|(E)(i+i)注：注：我们可以从出发，进行一系列的推导，推出种种不我们可以从出发，进行一系列的推导，推出种种不 同的算术表达式出来同的算术表达式出来该推导过程证明了（该推导过程证明了（+）是文法所定义的一个算术表达式。）是文法所定义的一个算术表达式。现在学习的是第25页，共49页2.2.程序语言的语法描述程序语言的语法描述“”：若若 ，则称该序列是从，则称该序列是从至至的的一个推导（一个推导（

18、可推导出可推导出）：+*表示表示“直接推出直接推出”，即仅推出一步。，即仅推出一步。AA ,仅当仅当 是一个产生式，且是一个产生式，且,(,()*“推导推导”：从从出发，经过出发，经过步步或或若干步若干步，可推导出，可推导出从从出发，经出发，经一步一步或或若干步若干步，可推导出，可推导出注：符号的含义注：符号的含义现在学习的是第26页，共49页已知文法G：T T*F|FF FP|PP(T)|aT*P(T*F)现在学习的是第27页，共49页2.2.程序语言的语法描述程序语言的语法描述“句型句型”：设是一个文法，是其开始符号，设是一个文法，是其开始符号，,(V VN N)*)*5 5、语言、语言“

19、句子句子”：仅含终结符号的句型是一个句子。仅含终结符号的句型是一个句子。+“语言语言”：文法所产生的句子的全体是一个语言，记为文法所产生的句子的全体是一个语言，记为（）（）*现在学习的是第28页，共49页已知文法G：S aAbA BcA|BBidt|(1)aidtcBcAb(2)aidtccb(3)ab(4)abidt句型句子？现在学习的是第29页，共49页2.2.程序语言的语法描述程序语言的语法描述6 6、最左右推导、最左右推导定义：定义：任何一步任何一步 都是对都是对 中的中的最左最右最左最右非终结符非终结符进行替换的。进行替换的。+（）（）（*+）（*+）（+）（）（）+（）（）（+）（

20、）（）（）（）（）（）（）（）最左推导：最左推导：最右推导最右推导：现在学习的是第30页，共49页练习：练习：GS:GS:S Sa|a|(T)|(T)T TT,S|ST,S|S分别给出下列句子的最左和最右推导过程：分别给出下列句子的最左和最右推导过程：（1 1）（）（a,(a,a)a,(a,a)（2 2）(a,(a,)(a,(a,)（1 1）最左推导：）最左推导：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)=(a,(S,S)=(a

21、,(a,S)=(a,(a,a)（2 2）最左推导：）最左推导：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,)=(a,(S,S)=(a,(a,S)=(a,(a,)现在学习的是第31页，共49页2.2.程序语言的语法描述程序语言的语法描述7 7、例题、例题例例.考虑一个文法考虑一个文法：定义了一个什么样的语言？定义了一个什么样的语言？.（）（）？现在学习的是第32页，共49页2.2.程序语言的语法描述程序语言的语法描述例例.考虑文法考虑文

22、法：定义了一个什么样的语言？定义了一个什么样的语言？分析：分析：？与类似与类似由由可知，其必产生可知，其必产生，且以此终结，且以此终结（）（），现在学习的是第33页，共49页2.2.程序语言的语法描述程序语言的语法描述例、例、构造一个文法构造一个文法，使（，使（）分析：分析：与与的区别在于，的区别在于，必须使、出现的必须使、出现的次数相次数相 等等，故而、必须，故而、必须同时出现。同时出现。GG：现在学习的是第34页，共49页2.2.程序语言的语法描述程序语言的语法描述思考思考:考虑文法考虑文法 D DD D；D|TLD|TL T Tint|charint|char L LL L，id|idi

23、d|id定义了一个什么样的语言？定义了一个什么样的语言？现在学习的是第35页，共49页2.2.程序语言的语法描述程序语言的语法描述二、语法分析树与二义性二、语法分析树与二义性、语法分析树、语法分析树用用树的形式表示一个句型的推导生成树的形式表示一个句型的推导生成，有助于理解，有助于理解一个句子语法结构的层次。一个句子语法结构的层次。树根：树根：开始符号开始符号中间结点：中间结点：非终结符非终结符叶结点：叶结点：终结符非终结符终结符非终结符现在学习的是第36页，共49页2.2.程序语言的语法描述程序语言的语法描述例例：（）的最左推导（）（）的最左推导（）（根）（根）（）+*次次 层层结论：结论：

24、一个句型不一定有唯一的一棵语法树。一个句型不一定有唯一的一棵语法树。即即一个句型的最左右推导可能不唯一。一个句型的最左右推导可能不唯一。现在学习的是第37页，共49页2.2.程序语言的语法描述程序语言的语法描述例：例：（）关于文法的另一个最左推导（）关于文法的另一个最左推导（）（）*+（）（）（*）（）（）（+）（）（）（）（）现在学习的是第38页，共49页2.2.程序语言的语法描述程序语言的语法描述2 2、二义文法、二义文法用若一个文法中存在某个句子，它有两个不同的用若一个文法中存在某个句子，它有两个不同的最左右推导，则该文法为二义文法最左右推导，则该文法为二义文法例：例：上述文法上述文法*

25、（）（）实质：实质：同一个句子存在两棵语法分析树。同一个句子存在两棵语法分析树。现在学习的是第39页，共49页2.2.程序语言的语法描述程序语言的语法描述例：例：句子句子+的最左推导过程的最左推导过程最最左左推导推导+*现在学习的是第40页，共49页2.2.程序语言的语法描述程序语言的语法描述最最右右推导推导+*+*+现在学习的是第41页，共49页已知文法GE：E EOE|(E)|v|dO+|*请证明该文法是二义的。提示：v*v+d的语法树不只一棵现在学习的是第42页，共49页2.2.程序语言的语法描述程序语言的语法描述注意：注意：、区分：文法的二义性、区分：文法的二义性语言的二义性语言的二义

26、性二义文法二义文法无二义文法无二义文法但（）（但（）（）例如：例如：+*（）（）：+*（）（）（）（）（）现在学习的是第43页，共49页B B、二义问题是不可判定的：、二义问题是不可判定的：即不存在一个算法，它能在有限步骤内，确切即不存在一个算法，它能在有限步骤内，确切的判定一个文法是否为二义的的判定一个文法是否为二义的所能做的只是为无所能做的只是为无二义性寻找一组充二义性寻找一组充分条件分条件2.2.程序语言的语法描述程序语言的语法描述现在学习的是第44页，共49页形式语言鸟瞰形式语言鸟瞰Chomsky于于1956年建立形式语言体系，年建立形式语言体系，他把文法分成四种类型：他把文法分成四种

27、类型：0，1，2，3型。型。与上下文无关文法一样，它们都由四部与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。分组成，但对产生式的限制有所不同。现在学习的是第45页，共49页乔姆斯基（Noam Chomsky,1928-），美国语言学家，转换-生成语法的创始人。从上世纪60年代起，他一直在骂美国外交政策，从越战骂到伊战，骂成著作等身的“老愤青”。他被美主流媒体封杀，邮箱曾一度需要特工检查后才能打开。他的海报贴在北京大学校园：“继上个世纪罗素与杜威之后，最有名的西方学者的东方之行”，他来华演讲的诱惑无人能抵挡。在他演讲前的几个小时，满广场的学生和老师在等侯着多余的门票。在北大

28、，这是某国总统演讲时才会出现的场面。82岁的他首次访华，“作为一名美国异见分子，不用指望受到当权者的欢迎”，他在演讲中说。现在学习的是第46页，共49页2.2.程序语言的语法描述程序语言的语法描述三、形式语言三、形式语言G=(VG=(VT T,V,VN N,S,S,)0 0型文法：型文法：(VN VT)*，至少有一个非终结符至少有一个非终结符 任何产生式任何产生式 均满足均满足|；仅仅S S例外，但例外，但S S不得出现在任何产生式的右不得出现在任何产生式的右部。部。1 1型文法：型文法：短语短语文法文法上下文上下文有关有关文法文法现在学习的是第47页，共49页2.2.程序语言的语法描述程序语言的语法描述2 2型文法：型文法：A A,A,A V VN N,(V(VN N V VT T)*)*G G的任何产生式为的任何产生式为A AB B或或 A A其中其中V VT T*，A A、B B V VN N 。3 3型文法：型文法：G G的任何产生式为的任何产生式为A A B B 或或 A A，其中其中V VT T*，A A、B B V VN N 。上下文上下文无关无关文法文法正规正规文法文法右线性右线性正规文法正规文法左线性左线性正规文法正规文法现在学习的是第48页，共49页感感谢谢大大家家观观看看现在学习的是第49页，共49页