编译原理第二章文法和语言讲义.doc

第二章 文法和语言 本章讲述目前广泛使用的上下文无关文法。即用上下文无关文法作为程序设计语言语法的描述工具。阐明语法的一个工具是文法。本章将介绍文法和语言的概念。 本章重点：上下文无关文法及其句型分析中的有关问题。 第一节 文法的直观概念 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。是汉语的一个句子。汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则： 〈句子〉∷＝〈主语〉〈谓语〉 〈主语〉∷＝〈代词〉|〈名词〉 〈代词〉∷＝我|你|他 〈名词〉∷＝王明|大学生|工人|英语 〈谓语〉∷＝〈动词〉〈直接宾语〉 〈动词〉∷＝是|学习 〈直接宾语〉∷＝〈代词〉|〈名词〉 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。 一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是： 〈句子〉〈主语〉〈谓语〉 〈代词〉〈谓语〉 我〈谓语〉 我〈动词〉〈直接宾语〉 我是〈直接宾语〉 我是〈名词〉 我是大学生 符号的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。 显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。 第二节 符号和符号串 符号和符号串，在形成语言中和编译技术中是很重要的概念。任何一种语言，都是由许多语言的基本符号组成的符号串的集合。如：英语的基本符号有26个字母和一些标点符号，英语，就是由这些符号所组成的符号串的集合。 （一）字母表和符号串 字母表是元素的非空有穷集合，字母表中的元素称为符号。由字母表中的符号所组成的任何有穷序列称之为“符号串”。 例如： 00，01，10 是字母表Σ＝{0，1}上的符号串，又如ab，abc，bc 是字母表Σ＝{a，b，c}上的符号串。还允许有空符号串。空符号串是不包含任何符号的符号串。用ε表示，其长度为0，即|ε|=0。 （二）符号串的运算 相等 X＝Y当且仅当组成X的诸符号与组成Y的诸符号依次相等，Σ＝{a，b ，c} X＝abbc Y＝abbc X＝Y X＝ab Y＝ba X≠Y 符号串的长度，X是符号串，则其长度用|X|表示。其数值等于组成该符号串的符号个数。 如：X＝STV |X|＝3 而 |ε|＝0 ②符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串. 如： b是符号串banana的一个前缀. 符号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串. 如:nana是符号串banana的一个后缀. Z＝abc，那么Z的前缀.是ε，a，ab，abc Z的后缀.ε，c，bc，abc ③符号串的联接，X和Y是符号串，它们的联接XY是把Y的符号写在X的符号之后，得到的符号串。 X＝ST Y＝abu XY＝STabu |X|＝2 |Y|＝3 |XY|＝5 由于ε的含义 显然有εX＝Xε＝X ④符号串的方幂，X是符号串，把X自身连接几次得到的符号串Z，Z＝XX……XX ， Z＝Xn X0＝ε X1＝X X2＝XX X＝abc X0＝ε X1＝abc X2＝abcabc…… n＞0有Xn＝XXn-1＝Xn-1x ⑤集合的乘积运算 符号串的集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。 AB＝{XY|X∈A，Y∈B} 如：A＝{a，b} B＝{c，d} AB＝{ac，ad，bc，bd} ∵对于任意符号串X总有εX＝Xε＝X ∴{ε}A＝A{ε}＝A ⑥集合A的闭包A*和集合A的正闭包A+ A