《文法和语法》PPT课件

《文法和语法》PPT课件

ID:45443229

大小:279.00 KB

页数:53页

时间:2019-11-13

《文法和语法》PPT课件_第1页
《文法和语法》PPT课件_第2页
《文法和语法》PPT课件_第3页
《文法和语法》PPT课件_第4页
《文法和语法》PPT课件_第5页
资源描述:

《《文法和语法》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第3章文法和语言教学要求:本章是编译原理课程的理论基础,要求理解文法、语言、规范推导、规范归约和短语、简单短语、句炳的基本概念;掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。教学重点:上下文无关文法,语言定义一、语言语言是由句子组成的集合,是由一组记号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体“我是大学生”是否是该语言的句子?〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

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

3、我

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

5、大学生

6、工人

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

8、词〉::=是

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

10、〈名词〉二、文法一种语言描述工具,用来定义句子的结构,用有限的规则把语言的全部句子描述出来,是以有穷的集合刻划无穷的集合的工具。〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

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

12、我

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

14、大学生

15、工人

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

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

18、〈名词〉三、符号和符号串字母表:元素的非空有穷集合。(符号集)符号:字母表中的

19、元素。例如:汉语的字母表中包括汉字、数字及标点符号等。C语言的字母表是由字母、数字、若干专用符号及IF、FOR之类的保留字组成。任何一种语言可看成是某个符号集上定义的,按一定规则构成的一切基本符号串组成的集合。符号串:由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1、形式定义:1.空符号串ε(没有符号的符号串)是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号串,当且仅当它可以由1和2导出。例:Σ={a,b}ε,a,b,aa,ab,aabba,…,都是上的符号串例:Σ={0,1} ε,0,1,00,01,11,1001110

20、等都是上的符号串.例:Σ={a,b,c}上的符号串有:ε,a,b,c,ab,ba,aaca,acaa等.注意:符号串中的符号排列是有顺序的。2、符号串的运算符号串的长度:符号串中符号的个数.符号串s的长度记为

21、s

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

23、x

24、=2,

25、y

26、=3,

27、xy

28、=5εx=xε=x方幂:符号串x自身连接n次得到的符号串xx…xx(n个x)定义为xnx0=ε,x1=x,x2=xx,x3=xxxx=AB,则x0=ε,x1=AB,x2=ABAB,x3=ABABAB对于n>

29、0,xn=xxn-1=xn-1x如果z=xy是一符号串,那么:1x是z的头,y是z的尾;2如果x非空,那么y是固有尾;如果y非空,那么x是固有头。例:设z=abc,那么z的头是:ε,a,ab,abc(除abc外都是固有头)z的尾是:ε,c,bc,abc(除abc外都是固有尾)3、符号串的头、尾、固有头、固有尾4、符号串集合若集合A中一切元素都是某字母表上的符号串,则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy

30、xA且yB若集合A=a,bB=c,d则AB=ac,ad,bc,bd{ε}A=A{ε}=A(∵εx=xε=x)使用*表示

31、上的所有有穷长的串(包括ε)的集合。Σ*称为Σ的闭包。从*中除去ε得到的集合记为+。Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例:设Σ={0,1},则Σ*={ε,0,1,00,01,10,11,000,001,010,…}例:设Σ={a,b},则Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}四、文法和语言的形式定义1、文法的形式定义1)规则(重写规则、产生式或生成式):是一个有序对(α,β)。记为α→β或α∷=

32、β。α称为规则的左部(或产生式的左部)。β称为规则的右部(或产生式的右部)。2)文法G[S]:文法为四元组(VN,VT,P,S)VN:非终结符集VT:终结符集P:产生式(规则)集合S:开始符号(识别符号)VN、VT和P是非空有穷集。S至少在一条规则中作为左部出现。VN∩VT=φ,S∈VNV=VN∪VT,称为文法G的字母表(字汇表)例3.1文法G=(VN,VT,P,S)VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号例3.2文法G=(VN,VT,P,S)VN=

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。