第二章 高级语言及其语法描述ppt课件.ppt

《第二章 高级语言及其语法描述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章文法和语言主要学习内容：高级语言的语法描述，上下文无关文法，语法分析树和二义性，乔姆斯基文法体系。学习目标：理解程序语言的词法、语法和语义等概念，进一步掌握高级程序设计语言的一般结构和主要共同特征，使学生具有必要的基础知识；理解文法和语言的一些基本概念，如文法的定义和构造、句型、句子、语言、推导、语法树等。学习重点和难点：语法，语义，文法的构造。3.1程序语言的定义一、语法程序本质上是一定字符集（称为字母表）上的一字符串（有限序列）。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。（1）词法规则（2）语法规则3.1

2、程序语言的定义一、语法（1）词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机（2）语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法语法规则和词法规定义了程序的的形式结构。3.1程序语言的定义二、语义语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：本书所使用的方法：基于属性文法的语法制导翻译方法3.2程序语言的语法描述一、基本概念（一）字母表

3、和符号串1、字母表定义字母表是一个非空有穷集合。常用V、表示例如：1＝{0,1}1是二进制数的字母表2＝{a,b…….z}2是英文小写字母2、符号定义字母表中的元素称为符号或称为字符。例如：设有字母表＝{+，-，*，/}则+、-、*、/为符号3.2程序语言的语法描述一、基本概念（一）字母表和符号串3、符号串定义符号的有穷序列称为符号串。例如：设有字母表＝{a，b，c}则有符号串：a，b，c，aa，ab，ac，aaa…4、空字（空符号串）定义不含任何符号的符号串，记为ε。3.2程序语言的语法描述一、基本概念（一）字母表和符号串5、符号串

4、集合定义字母表上若干符号串组成的集合称为符号串集合。例如：设有字母表＝{a，b，c}，则有符号串集合：A={ab，bc}A={a，ab，abc}3.2程序语言的语法描述一、基本概念（二）符号串的运算1、符号串相等定义设x，y是字母表上两个符号串，若x与y的诸符号一次相等，则称量符号串相等。记为x=y例如：设＝{a，b，c}若x=abbc，y=abbc，则x=y；若x=ab，y=ba，则x≠y；3.2程序语言的语法描述一、基本概念（二）符号串的运算2、符号串的长度定义设x是字母表上的符号串，符号串中包含符号的个数称为符号串x的长度，用

5、x

6、

7、表示。例如：

8、abc

9、=3

10、ε

11、=0

12、ax

13、=

14、xa

15、=

16、x

17、+13.2程序语言的语法描述一、基本概念（二）符号串的运算3、符号串的连结定义设x，y是字母表上两个符号串，把y的所有符号相继写在x的符号之后所得到的串称为x与y的连结，用xy表示。例如：若x=ab，y=abc，则xy=ababc而且

18、xy

19、=

20、x

21、+

22、y

23、3.2程序语言的语法描述一、基本概念（二）符号串的运算4、符号串的逆定义设x是字母表上的符号串，其逆为符号串x的倒置，记为。例如：若x=abc，则x=cba3.2程序语言的语法描述一、基本概念（二）符号串的运算5、符号串的前缀、后

24、缀和子串定义设x，y，z是字母表上的符号串，则称x为符号串xy的前缀，y为符号串xy的后缀，y是符号串xyz的子串。3.2程序语言的语法描述一、基本概念（二）符号串的运算6、符号串集合的乘积定义设A、B为两个符号串集合，其乘积为AB={xy

25、x∈A，y∈B}例如:若A＝{ab，bc}，B={ac，cb}则AB={abac，abcb，bcac，bccb}3.2程序语言的语法描述一、基本概念（二）符号串的运算7、空集定义不含任何元素的集合称为空集，记为Ø注意：ε、Ø、{ε}的区别3.2程序语言的语法描述一、基本概念（二）符号串的运算8、符号串的幂定义

26、设x是字母表上的符号串，则x的幂运算为：x0=εX1=xX2=xx…Xn=xn-1x(xxn-1)(n>0)3.2程序语言的语法描述一、基本概念（二）符号串的运算9、符号串集合的幂定义设A为符号串集合，则符号串集合A的幂运算为：A0={ε}A1=AA2=AA…An=An-1A(AAn-1)(n>0)3.2程序语言的语法描述一、基本概念（二）符号串的运算10、集合A的闭包与正闭包定义集合A的闭包表示为A*（又称为自反闭包或星闭包），具体定义为A*=A0∪A1∪A2∪A3∪…正闭包表示为A+=A1∪A2∪A3∪…还可以证明：A＋＝AA*=A*A3.2

27、程序语言的语法描述二、文法描述语言的语法结构的形式规则。例如：Hegavemeabook我们热爱祖国文法是在形式上用以描述