第03章文法和语言.

1第三章文法和语言本章目的——为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具——形式语言，抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。2本章知识点(内容)引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明33.1文法的直观概念和语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构。4“我是大学生”。是汉语的一个句子〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉有了一组规则以后，不断地用∷=的右边代替左边，就可以导出句子。5“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。6语言概述语言是由句子组成的集合，是由一组符号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体语法Syntax语言研究的三个方面语义Semantics语用Pragmatics7如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。83.2有关定义和记号的回顾符号和符号串符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合（符号集）。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是上的符号串2.若x是上的符号串，a是的元素，则xa是上的符号串3.y是上的符号串，当且仅当它可以由1和2导出。例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是上的符号串9符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀。符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀。符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串。10对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x,相应地，是s的前缀，后缀或子串，并且sx符号串的运算•符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。ε的长度为0•连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd有εa=aε•方幂：符号串自身连接n次得到的符号串an定义为aa…aan个a的连接a1=a,a2=aa则a0=ε11符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy|xA且yB若集合A=ab,cde，B=0,1则AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。12例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}......}{2*......}{32**13有关定义和记号语言是由句子组成的集合，是由一组符号所构成的集合。换言之，字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}•集合{ab,aabb,aaabbb,…,anbn,…}或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。•集合{a,aa,aaa,…}或表示为{w|w∈Σ*且w=an,n≥1}为字母表上的一个语言。ε是一个语言。即是一个语言。14语言上的有关运算设L是（上的）一个语言，M是（上的）一个语言，语言L和M的并，交，差，补是一个语言。语言L和M的并为LM，是一个语言:{w|wisinLorisinM}如：L1={a,b,…y,z}M1={0,1,2…8,9}L1M1={a,b,…y,z，0,1,2…8,9}语言L和M的连接是一个语言，记为LMLM={st|s∈L且t∈M}如：L1M1={a1,b1,…y1,z0,z1,a2,b2…a9…z9}有Lε=εL=L。L的n次连接Ln=LL...L15语言L的闭包记为L*，L*=L0L1L2…L0=εLn=LLn-1=Ln-1L，n1语言L的正闭包记为L+L+=L1L2L3...L*=L+ε如：L1={a,b,…y,z}，M1={0,1,2…8,9}（L1M1）={a,b,…y,z，0,1,2…8,9}（L1M1）*={a,b,…y,z,0,1,2…8,9,aa,0a,…xyz,6789st..}L1（L1M1）*={所有字母打头的字母和数字符号串}163.3文法和语言的形式定义一、如何来描述一种语言如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：1.生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。2.识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）什么17文法即是用生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义，进而在文法的定义的基础上，给出推导的概念，句型、句子和语言的定义。18二、文法的定义文法G定义为四元组(VN，VT，P，S)其中：VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪VT，称为文法G的字母表或字汇表。规则，也称重写规则、产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，其中α是字母表V的正闭包V+中的一个符号，且至少包含一个非终结符;β是V*中的一个符号。α称为规则的左部，β称作规则的右部。19例：文法G=（VN，VT，P，S）VN={S}VT={0,1}P={S→0S1，S→01}S为开始符号20例：文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={标识符→字母标识符→标识符字母标识符→标识符数字字母→a,…,字母→z数字→0,…,数字→9}S=标识符21三、文法的写法1.G：S→aAbA→abA→aAbA→ε2.G[S]：S→aAbA→abA→aAbA→ε3.G[S]：S→aAbA→ab|aAb|ε一般用写法322元符号:→∷=|习惯表示大写字母：非终结符小写字母：终结符如：S–ABA–Ax|yB–z23四、直接推导、推导的定义1.直接推导α→β是文法G的产生式，若有v,w满足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*则称v直接推导到w,也称w是v的直接推导，记作vw也称w直接归约到v例：G[S]：S→0S1，S→010S100S1100S11000S111000S11100001111S0S124+*2.推导:若存在vw0w1...wn=w,(n0)则记为v=w，称v推导出w，或w归约到v若有v=w，或v=w，则记为v=w++*25例：G[S]：S→0S1，S→01S0S10S100S1100S11000S111000S11100001111S0S100S11000S11100001111S=00001111S=S00S11=00S11+**26五、句型、句子的定义1.句型有文法G，若S=x，则称x是文法G的句型。即：从开始符号推导出的任意符号串。2.句子有文法G，若S=x，且x∈VT*，则称x是文法G的句子。即：从开始符号推导出的终结符号串。例：G：S→0S1，S→01S0S100S11000S11100001111S01G的句型有：S，0S1，00S11，000S111，00001111，01G的句子有：00001111,01**27例：G[E]：E→E+T|TT→T*F|FF→(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号a，+，*，(和)构成的算术表达式28六、语言的定义由文法G生成的语言记为L(G)，它是文法G的一切句子的集合:L(G)={x|S=x，其中S为文法的开始符号，且x∈VT*}例：G[S]：S→0S1，S→01L(G)={0n1n|n≥1}*29七、文法的等价若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1[A]：A→0R与G2[S]：S→0S1等价A→01S→01R→A1303.4文法的类型通过对产生式施加不同的限制，Chomsky(乔姆斯基）将文法分为四种类型：0型文法（短语文法）：对任一产生式α→β，都有α∈(VN∪VT)+，且至少含有一个非终结符，β∈(VN∪VT)*1型文法（上下文有关文法）：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外31文法的类型(续)2型文法（上下文无关文法）：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法（正规文法）：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT32文法的类型举例例：1型（上下文有关）文法文法G[S]：S→CDAb→AaC→aCABa→BAC→bCBBb→AbAD→aDC→aBD→bDD→aAa→Da33文法的类型举例例：2型（上下文无关）文法文法G[S]：S→ABA→BS|0B→SA|134文法的类型举例G[S]：S→0A|1B|0A→0A|1B|0SB→1B|1|0G[I]：I→lTI→lT→lTT→dTT→lT→d例：3型文法（正规文法）35四种文法之间的逐级“包含”关系2型文法1型文法0型文法3型文法36文法和语言0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）四种文法之间的关系是将产生式做进一步限制而定义的。37根据形式语言理论,文法和自动机（识别系统）间有这样的关系0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下