第03章文法和语言ppt课件.ppt

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

1、第三章文法和语言本章目的——为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具——形式语言，抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。1本章知识点(内容)引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明23.1文法的直观概念和语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示

2、的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构。3“我是大学生”。是汉语的一个句子〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉有了一组规则以后，不断地用∷=的右边代替左边，就可以导出句子。4“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是

3、一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。5语言概述语言是由句子组成的集合，是由一组符号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体语法Syntax语言研究的三个方面语义Semantics语用Pragmatics6如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其

4、特性的研究。是程序设计语言语法分析研究的基础。73.2有关定义和记号的回顾符号和符号串符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合（符号集）。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是上的符号串2.若x是上的符号串，a是的元素，则xa是上的符号串3.y是上的符号串，当且仅当它可以由1和2导出。例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是上的符号串8符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一

5、个前缀。符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀。符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串。9对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x,相应地，是s的前缀，后缀或子串，并且sx符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为

6、s

7、。ε的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abc

8、d有εa=aε方幂：符号串自身连接n次得到的符号串an定义为aa…aan个a的连接a1=a,a2=aa则a0=ε10符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy

9、xA且yB若集合A=ab,cde，B=0,1则AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。11例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,

10、…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}12有关定义和记号语言是由句子组成的集合，是由一组符号所构成的集合。换言之，字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}集合{ab,aabb,aaabbb,…,anbn,…}或表示为{w

11、w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。集合{a,aa,aaa,…}或表示为{w

12、w∈Σ*且w=an,n≥1}为字母表上的一个语言。ε是一个语言。即是一个

13、语言。13语言上的有关运