法和语言的形式定义。 规则，也称重写规则、产生式或生成式，是形如a→B或a:=B的(a,B)有序对，其中。 是某字母表V的正闭包V+中的一个符号，B是V·中的一个符号。a称为规则的左部，3 称作规则的右部。 定义3.1 文法G定义为四元组(V、V,P,S) 其中V为非终结符号（或语法实体，或变量）集，V,为终结符号集P为产生式（也你 规则)的集合；V,V,和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结 符，至少要在一条规则中作为左部出现。 V和V,不含公共的元素，即 VwnVT-9 通常用V表示VwUV,V称为文法G的字母表或字汇表。 例3.1文法G=(V,V,P,S),其中Vw={S,V=0,1,P=S+0S1,S→01 这里，非终结符集中只含一个元素S:终结符集由两个元素0和1组成：有两条产生式：开 始符号是S。 例3.2文法G=(Vw,V,P,S) 其中V=《标识符，字母，数字V=《a,b,c,.xy,z,0,l,.9} P=《标识符)→（字母》 (标识符)·（标识符）（字母） (标识符)→（标识符）（数字） 〈字母》+a (字母》→b 〈字母)→z (数字)→0 (数字)+1 〈数字)→9} S=〈标识符， 这里，使用尖括号“(”和“》”括起非终结符】 很多时候，不用将文法G的四元组显式地表示出来，而只将产生式写出。一般约定 第一条产生式的左部是识别符号：用尖括号括起来的是非终结符号，不用尖括号括起来的 是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。另外也有一种习 惯写法，将G写成G[S],其中S是识别符号，例3.1还可以写成： G:S-→0S1 S-01 或G[S]:S→0S1 S-*01 ·32
为定义文法所产生的语言，我们还需要引入推导的概念，即定义V中的符号之间的 关系：直接推导→、长度为n(n≥I)的推导去和长度为n(n≥0)的推导兰 定义3.2 如a→B是文法G=(VxV,P,S)的规则（或说是P中的一产生式），Y和8是V*中 的任意符号，若有符号串v,w满足： v=rao,w=r8o 则说v(应用规则a→)直接产生w,或说，w是v的直接推导，或说，w直接归约到v,记 作 V→W 例如，对于例3.1的文法G,可以给出直接推导的一些例子如下： v=0S1,w=0011,直接推导：0S1→0011，使用的规则：S→01，这里Y=0,8=1。 v=S,w=0S1,直接推导：S→0S1使用的规则：S→0S1,这里Y=e,6=e v=0S1,w=00S11,直接推导：0S1→00S11,使用的规则：S→0S1,这里Y=0,8=1。 对于例3.2的文法G,直接推导的例子有： =〈标识符)，w=〈标识数)（字母），直接推导：（标识符）→（标识符）（字母），使用的 规则：〈标识符)→（标识符》（字母），这里Y==e v=(标识符)（字母）（数字） w=〈字母)（字母）（数字） 直接推导：〈标识符)字母)（数字）→〈字母)（字母）（数字）.使用规则：（标识符）→（字母） 这里1=c,6→（字母）（数字）。 v=abc(数字)，w=bc5,直接推导：abc(数字)→abc5,使用规则：数字)-+5，这里y =abc,6=e。 定义3.3 如果存在直接推导的序列： v=w→w1→w2.→w,=w,(n>0) 则称v推导出（产生）w(推导长度为n),或称w归约到v。记作v去w。 定义34 若有v土w,或v=w,则记作V整w 例如，对例3.1的文法，存在直接推导序列v=0S1→00S11→000S111→00001111 w,即0S1去00001111，也可记作0S1兰00001111 对例3.2的文法，存在直接推导序列v一〈标识符)→（标识符）〈数字)→（字母）（数 字)→x《数字)→x1=w,即<标识符)去x1,也可记作（标识符）兰x1. 定义3.5 设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S三x×,则称x是文 法G[S]的句型。若x仅由终结符号组成，即S善x,x∈V:,则称x为G[S]的句子。 例如，S,0S1,000111都是例3.1的文法G的句型，其中000111是G的句子。（标识 符)（字母），（字母）（数字），a1等都是例3.2文法G的句型，其中a1是G的句子， 定义3.6 ·33·
文法G所产生的语言定义为集合{xS与x,其中S为文法识别符号，且x∈V竿)。可 用L(G)表示该集合。 从定义3.6看出两点：第一一，符号串x可从识别符号推出，也即x是句形。第一，x仅 由终结符号组成，即x是文法G的句子。也就是说，文法描述的语言是该文法一切句子的 集合。 考虑例3.1的文法G,有两条产生式（规则）：(1)S→0S1和(2)S→01，通过对第一个 产生式使用n一1次，然后使用第2个产生式一次，得到： S→0S1→00S11→ →0-1S9-1→1-1→0°1 是不是L(G)中的元素仅是这样的串(01)？是的，这可以由下面的讨论证得。在使用 了第二个产生式后，发现句型S的个数减少了一个。每次使用第一个产生式之后，S的左 端多一个0，右岩多一个1，S的个数不变，因此，使用了S01之后，就再也没有S留在结 果串中了。由于两个产生式都是以S为左端，所以为生成句子，仅能按下列次序使用产生 式：即使用第一个产生式若干次，然后使用第二个产生式。因此L(G)={01°n≥1}. 例3.2的文法G的句子是字母字符打头的、字母字符和数字字符构成的串。这就是 程序设计语言中用于表示名字的标识符。 例3.3设G=(VVrP,S),V={S,B,E,V={a,b,e,P由下列产生式组成： (1)S-aSBE (2)S-aBE (3)EB-BE (4)aB-→ab (5)bB→bb (6)bE-be (7)eE-cee 例3.1和例3.2都是较简单的文法的例子，比较容易确定哪些符号串可以推导出来 哪些不能。一般说来，确定文法将产生什么可能是很困难的。如现在的例子（例33）就较 为困难 对每一个n≥1，L(G)含有句子abc,因为我们能使用产生式(1)n一1次，得到推导 序列：S与a-1S(BE)-1,然后使用产生式(2)一次，得到：S三a(BE)”然后从a(BE)”继 续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先 于所有的E.例如，若n=3,RaaBEBEBE→aaaBBEEBE→aaaBBEBEE→aaaBBBEEE。即 有： Sa"B"E。 接着，使用产生式(4)一次，得到S兰abB-E”,然后使用产生式(5)n一1次得到： S兰abE,最后使用产生式(6)一次，使用产生式(7)n一1次，得到：S兰ab"e 我们也能证明，对于n>1,串abe'是唯一形式的终结符号串。在从S开始的任何推 导中，在未使用产生式(2)之前，是不能使用产生式(4)、(5)，(6)或(7)的，因为从(4)到(7) 的每一个产生式的左端都婴求B或者E的左边直接有个终结符。使用产生式(2)之前，所 ·34·
有的句型都是由多个a跟以一个S,然后跟以多个B和E组成，使用产生式(2)之后，对于 n≥l,句型就由n个a,后面跟某种次序的n个B和n个E组成，因为没有S出现在句型 中了，所以以后的推导中不可再使用产生式(1)和(2)了，从S推导出的串的特点都是全部 终结符后面是全部非终结符，在使用产生式(3)到(7)中任何一个之后，推导出的串仍具有 这种特点。而产生式(4)到(7)只能在终结符和非终结符的边界上使用，它们的作用是把 个B变为b或把一个E变为e。产生式(3)的使用可把B移到左边，把E移到右边。为得 到终结符号串，在任何E被转换成©之前，所有的B都必须在终结符和非终结符接口处 被转换为b。否则假设在所有的B转换到b之前，把一个E转换到©。这时推导出的串可 表示为ab'ea,其中i<n,a是由B和E组成的串，接着进行推导时，只有产生式(3)和(？) 可以使用：(3)用在非终结符中，(3)只能重新安排α中的B和E,但却不能删除任何B,产 生式(7)用于终结符和非终结符间的交换处，能把E转换为©，但最后一个B是最左非终 结符。没有产生式能改变这个B。即永远无法推导出终结符号串，因此所做的假设是不成 立的，结论只能是在任何E被转换为©之前，所有的B都必须在终结符和非终结符之间 的接口处转换成b,后面的推导都是在形为BBEE的串上继续，即ab心是仅可能 推导出的串 因此L(G)={ab"en≥1}。 定义3.7 若L(G)■L(G2),则称文法G,和G2是等价的。 例如文法G[A]: A-+0R A+01 R-A1 和例3.1的文法等价 3.4文法的类型 自从乔姆斯基(Chomsky)于1956年建立形式语言的描述以来，形式语言的理论发展 很快。这种理论对计算机科学有着深刻的影响，特别是对程序设计语言的设计、编译方法 和计算复杂性等方面更有重大的作用。 乔姆斯基把文法分成四种类型，即0型1型、2型和3型。这几类文法的差别在于对 产生式施加不同的限制。 设G=(Vw,V,P,S),如果它的每个产生式a→B是这样一种结构：a∈(VUV)“ 且至少含有-一个非终结符，而∈(VUV)·,则G是一个0型文法. 0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵机 (Turing).或者说，任何0型语言都是递归可枚举的：反之，递归可枚举集必定是一个0型 语言。 对0型文法产生式的形式作某些限制，以给出1,2和3型文法的定义， ·35·
设G=(V,V,P,S)为一文法，若P中的每一个产生式a→B均满足Bl≥a,仅仅 S+除外，则文法G是1型或上下文有关的。 例3.3的文法是上下文有关的。同样例3.1的文法也是上下文有关的。 在有些定义中，将上下文有关文法的产生式的形式描述为aAa,→aa,其中a,a 和3都在(VvUV,)·中（即在V“中），3e,A在Vv中。这种定义与前边的定义等价，但 它更能体现“上下文有关"这一术语，因为只有A出现在a,和a,的上下文中，才允许用P 取代A。 设G=(V,V,P,S),若P中的每一个产生式a→9满足：a是一非终结符，BE(VU V,)·则此文法称为2型的或上下文无关的。有时将2型文法的产生式表示为形如：A→9 其中A∈VN,也就是说用B取代非终结符A时，与A所在的上下文无关，因此取名为上下 文无关 例3.1和例3.2中的文法都是上下文无关的，下面我们再给出一个例子（例3.4），例 中的文法G是上下文无关文法，G的语言是由相同个数的a和b所组成的{a,b}·上的 例3.4G=({S,A,B},{a,b,P,S),其中P由下列产生式组成 S-B A-bAA S→bA B-+b A-a B→bs A-aS B→aBB 有时，为书写简洁，常把相同左部的产生式，形如 A-a A-+az A-a 缩写为： A-*a,lal.an 这里的元符号“1”读做“或” 例3.4的P可写为 S-aBIbA A→alaSIbAA B-bIbSlaBB 设G=(Vw,Vr,P,S),若P中的每一个产生式的形式都是A→aB或A→a,其中A和 B都是非终结符，a是终结符，则G是3型文法或正规文法。 例3.5文法G=(S,A,B},{0,1,P.S),其中P由下列产生式组成 S-=0A A-1B S→1B B-1B S-*0 B→1 A→0A B*0 36·