编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt

编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt

ID:51619211

大小:971.50 KB

页数:66页

时间:2020-03-26

编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt_第1页
编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt_第2页
编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt_第3页
编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt_第4页
编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt_第5页
资源描述:

《编译技术 张莉第一部分-基础篇 电子教案-第2章-文法和语言的概念和表示.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第二章文法和语言的概念和表示预备知识-形式语言基础文法和语言的定义若干术语和重要概念文法的表示:扩充的BNF范式和语法图文法和语言的分类2.1预备知识一、字母表和符号串字母表:符号的非空有限集例:={a,b,c}符号:字母表中的元素例:a,b,c符号串:符号的有穷序列例:a,aa,ac,abc,..空符号串:无任何符号的符号串(ε)符号串的形式定义有字母表,定义:(1)ε是上的符号串;(2)若x是上的符号串,且a,则ax或xa是上的符号串;(3)y是上的符号串,iff(当且仅当)y可由(1)和(2)产生。符号串集合:由符号串

2、构成的集合。通常约定:用英文字母表开头的小写字母和字母表靠近末尾的大写字母来表示符号如:a,b,c,d,…,r和S,T,U,V,W,X,Y,Z用英文字母表靠近末尾的小写字母来表示符号串如:s,t,u,v,w,x,y,z用英文字母表开头的大写字母来表示符号串集合如:A,B,C,D,…,R二、符号串和符号串集合的运算1.符号串相等:若x、y是集合上的两个符号串,则x=yiff(当且仅当)组成x的每一个符号和组成y的每一个符号依次相等。2.符号串的长度:x为符号串,其长度

3、x

4、等于组成该符号串的符号个数。例:x=STV,

5、x

6、=3例:A={s,t

7、},B={u,v},AB=?4.符号串集合的乘积运算:令A、B为符号串集合,定义AB={xy

8、x∈A,y∈B}{su,sv,tu,tv}因为εx=xε=x,所以{ε}A=A{ε}=A3.符号串的联接:若x、y是定义在Σ上的符号串,且x=XY,y=YX,则x和y的联接xy=XYYX也是Σ上的符号串。注意:一般xy≠yx,而εx=xε问题{ε}A=A{ε}=A{}A=A{}=?фA=Aф=ф6.符号串集合的闭包运算:设A是符号串集合,定义A+=A1∪A2∪A3∪……∪An∪……称为集合A的正闭包。A*=A0∪A+称为集合A的闭包。例:A={x,

9、y}A+=?A*=?5.符号串集合的幂运算:有符号串集合A,定义A0={ε},A1=A,A2=AA,A3=AAA,…………An=An-1A=AAn-1,n>0{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy,……}A1A2A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy,……}A0A1A2A3为什么对符号、符号串、符号串集合以及它们的运算感兴趣?若A为某语言的基本字符集(把字符看作符号)A={a,b,……z,0,1,……,9,+,-,×,

10、_,/,(,),=,……}B为单词集(单词是符号串)B={begin,end,if,then,else,for,……,<标识符>,<常量>,……}则BA*。(把单词看作符号,句子便是符号串)语言的句子是定义在B上的符号串。若令C为句子集合,则CB*,程序C若把字符看作符号,则单词就是符号串,单词集合就是符号串的集合。若把单词看作符号,则句子就是符号串,而所有句子的集合(即语言)就是符号串的集合。习题:p223,4p281-82.2文法的非形式讨论1.什么是文法:文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法

11、”(或称为“语法”)。例:有一句子:“我是大学生”。这是一个在语法、语义上都正确的句子,该句子的结构(称为语法结构)是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性?有穷语言无穷语言2.语法规则:我们通过建立一组规则,来描述句子的语法结构。规定用“::=”表示“由...组成”(或“定义为...”)。<句子>::=<主语><谓语><主语>::=<代词>

12、<名词><代词>::=你

13、我

14、他<名词>::=王民

15、大学生

16、工人

17、英语<谓语>::=<动词><直接宾语><动词>::=是

18、学习<直接宾语>::=<代词>

19、<名词>3.由规则推

20、导句子:有了一组规则之后,可以按照一定的方式用它们去推导或产生句子。推导方法:从一个要识别的符号开始推导,即用相应规则的右部来替代规则的左部,每次仅用一条规则去进行推导。<句子>=><主语><谓语><主语><谓语>=><代词><谓语>…………这种推导一直进行下去,直到所有带<>的符号都由终结符号替代为止。<句子>=><主语><谓语>=><代词><谓语>=>我<谓语>=>我<动词><直接宾语>=>我是<直接宾语>=>我是<名词>=>我是大学生<句子>::=<主语><谓语><主语>::=<代词>

21、<名词><代词>::=你

22、我

23、他<名词>::=王

24、民

25、大学生

26、工人

27、英语<谓语>::=<动词><直接宾语><动词>::=是

28、学习<直接宾语>::=<代词>

29、<名词>推导方法:从一个要识别的符号开始推导,即用相应规则的右部来替代规

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

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

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