资源描述：
《北京航空航天大学《编译原理》第2章 文法和语言的概念.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章文法和语言的概念和表示••预备知识-形式语言基础预备知识-形式语言基础••文法和语言的定义文法和语言的定义••若干术语和重要概念若干术语和重要概念••文法的表示：扩充的BNF范式和语法图文法的表示：扩充的BNF范式和语法图••文法和语言的分类文法和语言的分类北京航空航天大学计算机学院2.1预备知识一、字母表和符号串字母表：符号的非空有限集例：∑={a，b，c}符号：字母表中的元素例：a，b，c符号串：符号的有穷序列例：a,aa,ac,abc，..空符号串：无任何符号的符号串(ε)符号串的形式定义符号串的形式定义有字母表有字母表∑∑，定义：，定义：（1）（1）ε是ε是
2、∑∑上的符号串；上的符号串；（2）若x是（2）若x是∑∑上的符号串，且a上的符号串，且a∈∑∈∑，则ax或xa，则ax或xa是是∑∑上的符号串；上的符号串；（3）y（3）y是是∑∑上的符号串，iff（当且仅当）y可由（1）和（2）产生。上的符号串，iff（当且仅当）y可由（1）和（2）产生。符号串集合符号串集合：：由符号串构成的集合由符号串构成的集合。。北京航空航天大学计算机学院•通常约定：–用英文字母表开头的小写字母和字母表靠近末尾的大写字母来表示符号如：a,b,c,d,…,r和S,T,U,V,W，X,Y,Z–用英文字母表靠近末尾的小写字母来表示符号串如：s,t,u,v
3、,w,x,y,z–用英文字母表开头的大写字母来表示符号串集合如：A,B,C,D,…,R北京航空航天大学计算机学院二、符号串和符号串集合的运算1.符号串相等：若x、y是集合上的两个符号串，则x＝yiff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。2.符号串的长度：x为符号串，其长度
4、x
5、等于组成该符号串的符号个数。例：x＝STV，
6、x
7、=3北京航空航天大学计算机学院3.符号串的联接：若x、y是定义在Σ上的符号串，且x＝XY，y＝YX，则x和y的联接xy＝XYYX也是Σ上的符号串。注意：一般xy≠yx，而εx＝xε4.符号串集合的乘积运算：令A、B为符号串集合
8、，定义AB＝{xy
9、x∈A,y∈B}例：A＝{s,t},B={u,v},AB=？{su，sv，tu，tv}因为εx＝xε＝x，所以{ε}A=A{ε}=A北京航空航天大学计算机学院问题{ε}A=A{ε}=A{}A=A{}=？фA=Aф=ф北京航空航天大学计算机学院5.符号串集合的幂运算：有符号串集合A，定义A0={ε},A1=A,A2=AA,A3=AAA,…………An＝An-1A=AAn-1，n>06.符号串集合的闭包运算：设A是符号串集合，定义A＋＝A1∪A2∪A3∪……∪An∪……称为集合A的正闭包。A*＝A0∪A＋称为集合A的闭包。例：A={x,y}A＋＝？{x,y,
10、xx,xy,yx,yy,xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy,……}A1A2A3A*＝？{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy,……}A0A1A2A3北京航空航天大学计算机学院为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集(把字符看作符号）A＝{a,b,……z,0,1,……,9,+,－,×,_,/,(,),=,……}B为单词集（单词是符号串）B={begin,end,if,then,else,for,……,<标识符>,<常量>,……}则B⊂A*。（把单词
11、看作符号，句子便是符号串）语言的句子是定义在B上的符号串。若令C为句子集合，则C⊂B*,程序⊂C北京航空航天大学计算机学院•若把字符看作符号，则单词就是符号串，单词集合就是符号串的集合。•若把单词看作符号，则句子就是符号串，而所有句子的集合（即语言）就是符号串的集合。习题：习题：p19p193,43,4p261,p261,－－,8,8北京航空航天大学计算机学院2.2文法的非形式讨论1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：“我是大学生”。这是一个在语法、语义上都正确的句子，该句子的结构（称
12、为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性？•有穷语言•无穷语言北京航空航天大学计算机学院2.语法规则：我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由...组成”（或“定义为...”）。<句子>::=<主语><谓语><主语>::=<代词>
13、<名词><代词>::=你
14、我
15、他<名词>::=王民
16、大学生
17、工人
18、英语<谓语>::=<动词><直接宾语><动词>::=是
19、学习<直接宾语>::=<代词>
20、<名词>北京航空航天大学计算机学院3.由规则推导句子：有了一组规则之后，可以按照
