第 2 讲 文法和语法.ppt

《第 2 讲 文法和语法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二讲文法和语言文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明第一节语言语言:是由句子组成的集合。汉语---所有符合汉语语法的句子的全体英语---所有符合英语语法的句子的全体程序设计语言---所有该语言的程序的全体研究语言：每个句子构成的规律每个句子的含义每个句子和使用者的关系研究程序设计语言：每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面：语法Syntax语义Semantics语用Pragmatics语法：表示构成语言句子的各个记号之间的组合规律语义：表

2、示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用：表示在各个记号所出现的行为中，它们的来源、使用和影响。第二节文法“我是大学生”是否是该语言的句子？〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

3、〈名词〉〈代词〉::=你

4、我

5、他〈名词〉::=王明

6、大学生

7、工人

8、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是

9、学习〈直接宾语〉::=〈代词〉

10、〈名词〉以自然语言为例，用EBNF描述一种语言：〈句子〉〈主语〉〈谓语〉①〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

11、〈名词〉〈代词

12、〉::=你

13、我

14、他〈名词〉::=王明

15、大学生

16、工人

17、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是

18、学习〈直接宾语〉::=〈代词〉

19、〈名词〉〈代词〉〈谓语〉②我〈谓语〉③我〈动词〉〈直接宾语〉⑤我是〈直接宾语〉⑥我是〈名词〉⑦我是大学生④〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

20、〈名词〉〈代词〉::=你

21、我

22、他〈名词〉::=王明

23、大学生

24、工人

25、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是

26、学习〈直接宾语〉::=〈代词〉

27、〈名词〉下列是否是句子?我大学生是大学生是王明第三节符号和符号串字母表：元

28、素的非空有穷集合。（符号集）符号：字母表中的元素。例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是上的符号串。2.若x是上的符号串，a是的元素，则xa和ax是上的符号串。3.y是上的符号串,当且仅当它可以由1和2导出。例如：Σ={a,b}ε,a,b,aa,ab,aabba,…,都是上的符号串。例：Σ={0,1}ε,0,1,00,01,

29、11,1001110等都是上的符号串.例：Σ={a,b,c}上的符号串有：a,b,c,ab,ba,aaca,acaa等.注意：符号串中的符号排列是有顺序的.可以用字母表示符号串，如：x=aaca如果z=xy是一符号串，那么：x是z的头(前缀)，y是z的尾(后缀)；如果x非空，那么y是固有尾(真后缀)；如果y非空，那么x是固有头(真前缀)。例：设z=abc,那么z的头是：ε,a,ab,abc（除abc外都是固有头）z的尾是：ε,c,bc,abc（除abc外都是固有尾）几种表示法（x，z是符号串，t是符号）：z=x…x是符号串z的头z=…

30、xx是符号串z的尾z=…x…x在符号串z中某处出现z=t…符号t是符号串z的第一个符号z=…t符号t是符号串z的最后一个符号符号串的运算符号串的长度：符号串中符号的个数。符号串s的长度记为

31、s

32、。ε的长度为0。连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy例：x=ST，y=abu则xy=STabu

33、x

34、=2，

35、y

36、=3，

37、xy

38、=5εx=xε=x方幂符号串x自身连接n次得到的符号串xx…xx(n个x)表示为xnx0=ε,x1=x,x2=xx，…　，xn=xx…xx=AB,则x0=ε,x1=AB,x2=ABAB,x

39、3=ABABAB对于n>0,xn=xxn-1=xn-1x符号串集合：若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积：定义为AB=xy

40、xA且yB例：若，集合A=a,bB=c,d则，AB=ac,ad,bc,bd{ε}A=A{ε}=A(∵εx=xε=x)闭包：使用*表示上的所有有穷长的串（包括ε）的集合。Σ*称为Σ的闭包。正闭包：从*中除去ε得到的集合记为+。Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2…∪Σn∪…Σ+=Σ1∪Σ2…∪Σn∪…Σ*=Σ0∪Σ+Σ

41、+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例1：设Σ={0,1}，则：Σ*={ε，0，1，00，01，10，11，000，001，010，…}例2：设Σ={a,b}，则Σ*={ε，a，b，aa，ab，ba，bb，