第2章(1)文法和语言的基本知识

1、第第2章章 文法和语言的基本知识文法和语言的基本知识 形式语言理论是编译的重要理论形式语言理论是编译的重要理论基础基础。本章主要介绍编译理论中用到。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念的有关形式语言理论的最基本概念，重点介绍如何采用形式化的方法描述重点介绍如何采用形式化的方法描述程序设计语言。程序设计语言。第第2章章 文法和语言的基本知识文法和语言的基本知识q字母表和符号串字母表和符号串q文法和语言的形式定义文法和语言的形式定义q短语、直接短语和句柄短语、直接短语和句柄q语法树和文法的二义性语法树和文法的二义性q文法和语言的分类文法和语言的分类2.1 概概 述述 对程序设计

2、语言的描述是从语对程序设计语言的描述是从语法、语义和语用三个因素来考虑。法、语义和语用三个因素来考虑。语法语法是对语言结构的定义。是对语言结构的定义。 语用语用则是从使用的角度去描述则是从使用的角度去描述语言。语言。语义语义是描述了语言的含义。是描述了语言的含义。2.1 概概 述述例如例如 赋值语句赋值语句s s2 2* *3.14163.1416* *r r* *(r+h)(r+h)的的 非形式化的描述为：非形式化的描述为：语法：语法：赋值语句由一个变量，后随一个赋赋值语句由一个变量，后随一个赋 值号值号“”，其后面再跟一个表达式构成。，其后面再跟一个表达式构成。语义：语义：首先计算语句右部

3、表达式的值，然首先计算语句右部表达式的值，然后把所得结果送给左部变量中。后把所得结果送给左部变量中。语用：语用：赋值语句可用来计算和保存表达式赋值语句可用来计算和保存表达式的值。的值。2.1 概 述 这种非形式化的描述这种非形式化的描述, ,不够清晰不够清晰和准确和准确, ,为了精确定义和描述程序设为了精确定义和描述程序设计语言计语言, ,需采用形式化的方法。所谓需采用形式化的方法。所谓形式化的方法形式化的方法, ,是用一整套带有严格是用一整套带有严格规定的符号体系来描述问题的方法。规定的符号体系来描述问题的方法。 形式语言理论是编译的重要理论形式语言理论是编译的重要理论基础基础。重点介绍如何

4、采用形式化的方重点介绍如何采用形式化的方法描述程序设计语言。法描述程序设计语言。 2.2 字母表和符号串的基本概念字母表和符号串的基本概念内容主要包括：内容主要包括：1.字母表和符号串的定义字母表和符号串的定义2.符号串的运算符号串的运算2.2.1 字母表和符号串字母表和符号串元素的非空有穷集合。元素的非空有穷集合。例如，例如，= a, b, c 1. 字母表字母表 根据字母表的定义，根据字母表的定义，是是字母表，字母表，它由它由a a、b b、c c三个三个元素元素组成。组成。2.2.1 字母表和符号串字母表和符号串 是一个字母表，由是一个字母表，由0 0、1 1两个元素两个元素组成。组成。

5、注意注意:例如，例如， =0, 1 (2) 字母表中的元素字母表中的元素, 可以是字母、可以是字母、数字或其他符号数字或其他符号。(1) 字母表中至少包含一个元素字母表中至少包含一个元素。2.2.1 字母表和符号串字母表和符号串 字母表中的元素称为符号或称为字母表中的元素称为符号或称为字符。字符。例如，前述例子中例如，前述例子中2. 符号（字符）符号（字符）a、b、c 是字母表是字母表中的符号；中的符号；0、1 是字母表是字母表中的符号。中的符号。2.2.1字母表和符号串字母表和符号串 例如，设有字母表例如，设有字母表= a, b, c 符号的有穷序列称为符号串。符号的有穷序列称为符号串。 符

6、号串总是建立在某个特定字符号串总是建立在某个特定字母表上的且只母表上的且只由字母表上的有穷多由字母表上的有穷多个符号组成。个符号组成。 则有则有: 符号串符号串 a a，b b，abab，baba， cbacba， abcabc 3. 符号串（字）符号串（字）2.2 字母表和符号串字母表和符号串说明说明: :不包含任何符号的符号串不包含任何符号的符号串, , 称为称为空空符号串符号串，用，用表示。表示。符号串中符号的符号串中符号的顺序顺序是很重要的。是很重要的。abab和和baba是字母表是字母表上的上的两个两个不同的不同的符号串。符号串。空符号串由空符号串由0 0个符号组成，个符号组成，其长

7、度其长度| |=0|=0我们有我们有 x x x。2.2 .2 符号串的运算符号串的运算 设设x和和y是符号串，则串是符号串，则串xy称为它称为它们的们的连结连结。则则XY_，YX _ 。注意注意：对任意一个符号串：对任意一个符号串x，1. 符号串的连结符号串的连结例如例如，设，设XABC，Y10A2.2.2 符号串的运算符号串的运算2. 集合的乘积集合的乘积 设设A和和B是符号串的集合是符号串的集合, 则则A和和B的乘积定义为：的乘积定义为： 集合的乘积是满足于集合的乘积是满足于 xA, yB的的所有符号串所有符号串 xy 所构成的集合。所构成的集合。AB=xy | xA, yB A A A

8、2.2.2 符号串的运算符号串的运算例如：例如：设设A= a, b , B= c, d 则则AB= ac, ad, bc, bd 由于对任意的符号串由于对任意的符号串x，总有总有 x=x =x所以所以, 对任意集合对任意集合A, 我们有我们有:2.2.2 符号串的运算符号串的运算 特别指出的是特别指出的是， 是符号串是符号串, 不是不是集合，而集合，而 表示由空符号串表示由空符号串 所组所组成的集合成的集合, 但这样的集合不是空集合但这样的集合不是空集合= 。2.2.2 符号串的运算符号串的运算 3. 符号串的幂运算符号串的幂运算 设设x是符号串是符号串, 则则x的幂运算定义为：的幂运算定义为

9、： x0= x1= x x2= xx x3= xxx xn= xx x=x xn-1(n0)n注意：注意：x0 12.2.2 符号串的运算符号串的运算例如例如, 设设 xabc 则则x0= _x1= _x2=xx= _ 2.2.2 符号串的运算符号串的运算 4. 集合的幂运算集合的幂运算 设设A是符号串的集合，则集合是符号串的集合，则集合A的的幂运算定义为：幂运算定义为：A0= A1=AA2=AA An= AA A=AAn-1(n0)n2.2.2 符号串的运算符号串的运算例如，设例如，设A= a, b ，则则A0= _A1=A= a, b A2=AA= _ A3=AAA=A2A= aaa, a

10、ab, aba, abb, baa, bab, bba, bbb 2.2.2 符号串的运算符号串的运算5. 集合集合A的正闭包的正闭包A与闭包与闭包A* 设设A是符号串的集合，则是符号串的集合，则A的正闭的正闭包包A和和A的闭包的闭包A*的定义为的定义为:A+=A1A2 An A*= A0 A1A2 An =A+2.2.2 符号串的运算符号串的运算 可见可见, ,集合集合A的正闭包表示的正闭包表示A上元素上元素a, ,b构成的构成的所有符号串所有符号串的集合的集合, ,集合集合A的闭包比集合的闭包比集合A的正闭包的正闭包多含一个空多含一个空符号串符号串 。例如，设例如，设A= a, b , 则

11、：则：A+= a, b, aa, ab, ba, bb, aaa, aab, A*= , a, b, aa, ab, ba, bb, aaa, aab, 2.3 2.3 文法和语言的形式定义文法和语言的形式定义 每个形式语言都是某个字母表上按每个形式语言都是某个字母表上按某种规则构成的某种规则构成的所有符号串的集合所有符号串的集合。反之，任何一个字母表上符号串的集反之，任何一个字母表上符号串的集合均可定义为一个形式语言合均可定义为一个形式语言。2.3.1形式语言形式语言序列的集合称为形式语言序列的集合称为形式语言。2.32.3.1.1 形式语言形式语言 对每个具体语言对每个具体语言, ,都有语

12、法和语都有语法和语义两个方面，形式语言是指不考虑义两个方面，形式语言是指不考虑语言的具体意义，即不考虑语义。语言的具体意义，即不考虑语义。 2.3.1 2.3.1 形式语言形式语言形式语言的描述形式语言的描述 对形式语言的描述有两种方法，对形式语言的描述有两种方法，一种方法是当语言为一种方法是当语言为有穷集合有穷集合时，用时，用枚举法枚举法来表示语言。来表示语言。 2.3.1 2.3.1 形式语言形式语言 均表示字母表均表示字母表A上的一个形式语言。上的一个形式语言。由于由于这三个语言均是有限符号串的集合，因此，这三个语言均是有限符号串的集合，因此，可枚举出其全部句子来表示该语言。可枚举出其全

13、部句子来表示该语言。 例如，设有字母表例如，设有字母表A= a, b, c ，则则L L1 1= a, b, c L L2 2= a, aa, ab, ac L L3 3= c, cc 2.3.1 2.3.1 形式语言形式语言例如，设字母表例如，设字母表= 0, 1 , 则则+ +=1 12 23 3= = 0, 1, 00, 10, 11, 01, 000, 100, 当语言为当语言为无穷集合无穷集合时，用时，用文法文法来描述来描述语言。语言。 2.3.1 2.3.1 形式语言形式语言 下面用下面用A表示表示+，用式子用式子A0表示符表示符号串号串0A或或A生成生成符 号 串符 号 串 0

14、， 符 号， 符 号“”读作读作“生成生成”或或“由由组成组成”。则集合则集合A可表示成：可表示成： A0A1AA0AA1+ +=1 12 23 3= = 0, 1, 00, 10, 11, 01, 000, 100, 2.3.1 2.3.1 文法的形式定义文法的形式定义 规则是一个符号与一个符号串的规则是一个符号与一个符号串的有序对有序对（A,），通常写作：通常写作： A（或（或A ) 1.1. 规则规则 也称产生式也称产生式 规则的作用是告诉我们如何用规则的作用是告诉我们如何用规规则中的符号串生成语言中的序列则中的符号串生成语言中的序列。2.3.2.3.2 2 文法的形式定义文法的形式定义

15、 例如，前述例中一组规则例如，前述例中一组规则 描述的语言序列只可能是由描述的语言序列只可能是由0和和1组成的符号串。组成的符号串。A0A1AA0AA12.3.2.3.2 2 文法的形式定义文法的形式定义 规则中出现的符号分为两类规则中出现的符号分为两类，一类，一类是是终结符号终结符号，另一类是，另一类是非终结符号非终结符号。 非终结符号非终结符号是出现在规则是出现在规则左部左部能能派生出符号或符号串的那些符号，即派生出符号或符号串的那些符号，即每个非终结符号表示一定符号串的集每个非终结符号表示一定符号串的集合，合，用大写字母表示或用尖括号把非用大写字母表示或用尖括号把非终结符号括起来。例如，

16、上例中的终结符号括起来。例如，上例中的A。2.3.2.3.2 2 文法的形式定义文法的形式定义 终结符号终结符号是不属于非终结符号是不属于非终结符号的那些符号的那些符号, 它是它是组成语言的基本符组成语言的基本符号号，是一个语言的不可再分的基本是一个语言的不可再分的基本符号符号，通常用小写字母表示。，通常用小写字母表示。 例如，上例中的例如，上例中的0和和1。 2.3.2.3.2 2 文法的形式定义文法的形式定义 规则的非空有穷集合，规则的非空有穷集合，通常表示通常表示成四元组成四元组VN是规则中非终结符号的集合。是规则中非终结符号的集合。VT是规则中终结符号的集合。是规则中终结符号的集合。P

17、 是文法规则的集合。是文法规则的集合。 2. 文法文法G=(VN,VT, P, S )2.3.2.3.2 2 文法的形式定义文法的形式定义 S 是一个非终结符号是一个非终结符号，称为文法称为文法的开始符号或文法的识别符号的开始符号或文法的识别符号，它，它至少要在一条规则中作为左部出现。至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语由它开始，识别出我们所定义的语言言。 由文法定义可知，文法是对语言由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中结构的定义和描述，文法四大要素中关键是规则的集合关键是规则的集合。 2.3.2.3.2 2 文法的形式定义文法的形式定义 将它

18、们缩写为：将它们缩写为：A 1 | 2 | | nA 1A 2A n 其中每个其中每个 i有时也称为有时也称为A的一个的一个候选式候选式。 为了书写方便，对于若干个左为了书写方便，对于若干个左部相同的规则部相同的规则，如，如2.3.2.3.2 2 文法的形式定义文法的形式定义 我们我们约定约定： 第一条规则的左部是第一条规则的左部是识别符号识别符号。 对文法对文法G不用四元式显示表示不用四元式显示表示，仅只将仅只将规则写出规则写出。 2.3.1 2.3.1 文法的形式定义文法的形式定义 G=(VN，VT，P，S )VN=AVT=0，1P: A 0 | 1 | A0 | A1S=A前例中描述前例

19、中描述+ +的文法是的文法是: :2.3.2.3.2 2 文法的形式定义文法的形式定义 例例1 设字母表设字母表=a, b，试设计一个试设计一个文法，描述语言文法，描述语言 L= a2n, b2n | n1 分析分析 设计一个文法来描述一个语言设计一个文法来描述一个语言, , 关键是设计一组规则生成语言中的关键是设计一组规则生成语言中的符号串。符号串。因此，为设计该语言文法，因此，为设计该语言文法，必须分析这个语言是由怎样一些符必须分析这个语言是由怎样一些符号串组成的，即首先号串组成的，即首先分析语言中串分析语言中串的结构特征的结构特征： 2.3.2.3.2 2 文法的形式定义文法的形式定义

20、当当n1 L=_ L=aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, 即即语言语言L是由是由偶数个偶数个a，偶数个偶数个b这样这样的符号串组成的集合的符号串组成的集合。 L=a2n, b2n | n1当当n2 L=_当当n3 L=aaaaaa, bbbbbb2.3.2.3.2 2 文法的形式定义文法的形式定义 因此，定义语言因此，定义语言L的文法的文法 G=( VN，VT，P，S )其中：其中： VN=A, B, DVT=a, bP= Aaa S=ABaa Dbb | bbD | bb | bbD注意注意:VTaa,bb | aaB| aaB2.3.2.3.2 2 文法

21、的形式定义文法的形式定义 提出问题提出问题: 描述该语言的文法描述该语言的文法是否唯一呢？是否唯一呢？ 显然，显然，G不同于不同于G。由此可见，由此可见，对于一个给定的语言，对于一个给定的语言，描述该语言描述该语言的文法是不唯一的的文法是不唯一的。 P : AB | DBaa | aBaDbb | bDb 若若G和和G是两个不同的文法，如是两个不同的文法，如果它们描述的语言相同，那么，称果它们描述的语言相同，那么，称G和和G 为为等价文法等价文法。2.3.2.3.2 2 文法的形式定义文法的形式定义 描述该语言的文法是否描述该语言的文法是否G？2.3.2.3.2 2 文法的形式定义文法的形式定

22、义 对此例，对此例，我们提出下面这样一个问题：我们提出下面这样一个问题： G=( A, a, b, P, A ) 其中其中P= Aaa | bb | Aaa | Abb 对于文法对于文法G来说，它所产生的来说，它所产生的有些符号串，如有些符号串，如aabb，bbaa， 不属于语言不属于语言L，即即设计的文法超出了设计的文法超出了所定义语言的范围所定义语言的范围。 2.3.2.3.2 2 文法的形式定义文法的形式定义 P= Aaa | bb | Aaa | Abb 2.3.2.3.2 2 文法的形式定义文法的形式定义 例例2 试设计一个表示所有试设计一个表示所有标识符标识符的文法的文法 分析分析

23、 题意是用题意是用文法定义标识符文法定义标识符，必须确定必须确定P中规则。为了设计出一组中规则。为了设计出一组规则，首先应搞清楚规则，首先应搞清楚集合中串的结集合中串的结构特征。构特征。 2.3.2.3.2 2 文法的形式定义文法的形式定义 用用I代表标识符；代表标识符；L代表字母；代表字母；D代表数字代表数字; 则定义标识符的文法则定义标识符的文法为：为： 字母字母 字母或数字串字母或数字串标识符的结构可用下图表示标识符的结构可用下图表示:2.3.2.3.2 2 文法的形式定义文法的形式定义 G=(VN，VT，P，S)其中：其中： VN=I, L, DVT=a,b,c, x,y,z,0,1,

24、2,x,y,z,0,1,2, ,9,9P= IL S=ILa | b | c | | x | y | zD0 | 1 | 2 | 3 | | 9 | I L| I D2.3.2.3.2 2 文法的形式定义文法的形式定义 若将定义标识符的文法设计成：若将定义标识符的文法设计成： 其中其中 VN，VT ，S 同上同上 G=(VN，VT，P，S )P= IL | I DLa | b | c | |x|y|z|x|y|zD0 | 1 | 2 | 3 | |9 |9 2.3.2.3.2 2 文法的形式定义文法的形式定义 该文法不能定义该文法不能定义ab，abc 仅由字母串组成的标识符，仅由字母串组成的标

25、识符，缩小缩小了所定义语言的范围了所定义语言的范围。 P= IL | I DLa | b | c | |x|y|z|x|y|zD0 | 1 | 2 | 3 | |9 |9 2.3.2.3.2 2 文法的形式定义文法的形式定义 用用I代表标识符；代表标识符；L代表字母；代表字母；D代表数字；代表数字；T代表字母数字串；代表字母数字串；则则定义标识符的文法还可写为：定义标识符的文法还可写为： 字母字母 字母或数字串字母或数字串2.3.2.3.2 2 文法的形式定义文法的形式定义 P: IL | LT TL | D | LT | DT La | b | c | |x|y|z|x|y|z D0 | 1

26、 | 2 | 3 | | 9 字母字母 字母或数字串字母或数字串2.3.2.3.2 2 文法的形式定义文法的形式定义 例例3 用文法定义一个含、用文法定义一个含、* *的算术表达式，定义用下述自然语的算术表达式，定义用下述自然语言描述：言描述： 变量是一个表达式；变量是一个表达式； 若若 E1和和 E2是算术表达式是算术表达式, 则则 E1E2、E1* *E2、(E1) 也是算术表也是算术表达式。达式。 2.3.2.3.2 2 文法的形式定义文法的形式定义 分析分析 算术表达式的定义用自然算术表达式的定义用自然语言描述，这是对算术表达式的非语言描述，这是对算术表达式的非形式定义，形式定义，题意

27、用题意用文法来定义算术文法来定义算术表达式表达式，即是，即是用形式化用形式化的的方法定义方法定义表达式。定义算术表达式的文法为：表达式。定义算术表达式的文法为： G=(E, i, +, * *, (, ) , P, E )其中其中P为：为：Ei | E+E | E* *E | (E)2.3.2.3.2 2 文法的形式定义文法的形式定义 P为：为：Ei | E+E | E* *E | (E) i, i+i, i* *i, i+i* *i, (i+i), 注意：是符号注意：是符号串的集合串的集合2.3.2.3.2 2 文法的形式定义文法的形式定义 例例4 设字母表设字母表 = a, b , 试设计

28、一试设计一个文法，描述语言个文法，描述语言 L= abna | n0 分析分析 该该语言中串的结构特征语言中串的结构特征是是 当当n1 L= aba L= aa, aba, abba, 当当n2 L= abba 当当n0 L= aa (b0=)2.3.2.3.2 2 文法的形式定义文法的形式定义 所以所以定义语言的文法为：定义语言的文法为： G=( A, B, a, b, P, A )P= AaBa BBb | L= aa, aba, abba, 2.3.2.3.2 2 文法的形式定义文法的形式定义 例例5 设字母表设字母表= (, ) ,试设计试设计一个文法描述语言一个文法描述语言 L= (

29、n )n | n0分析分析 该该语言中串的结构特征语言中串的结构特征是是 当当n=0 L= 注注: (0 )0= 当当n=1 L= ( ) 当当n=2 L= ( ) L= , ( ), ( ), ( ), 2.3.2.3.2 2 文法的形式定义文法的形式定义 P: S | ( S )所以定义语言的文法为： L= (n )n | n02.3.2.3.3 3 语言的形式定义语言的形式定义 1. 直接推导 令令G是一文法，我们称是一文法，我们称 xAy直接直接推导出推导出 xy ，即即 xAyxy 仅仅 A 是是 G 的一条规则的一条规则, 且且 x, y (VNVT)*。也就是说从符号也就是说从符

30、号串串 xAy 直接推导出直接推导出 xy 仅使用一次仅使用一次规则规则。 2.3.2.3.3 3 语言的形式定义语言的形式定义例如，设有文法例如，设有文法GS: S01 使用规则使用规则 S01 此时此时 x ， y P为：为：S 0 1 | 0 S 1 有如下直接推导：有如下直接推导：S0S1 使用规则使用规则 S0S1 此时此时 x ， y 2.3.2.3.3 3 语言的形式定义语言的形式定义 0S10011 使用规则使用规则 S01 此时此时 x0， y1 00S11000S111 使用规则使用规则 S0S1 此时此时 x00 , y11 000S11100001111 使用规则使用规

31、则 S01 此时此时 x000 y111S 0 1 | 0 S 12.3.32.3.3 语言的形式定义语言的形式定义 (1) 形式上形式上的区别，推导用的区别，推导用“”表示，规则用表示，规则用“”表示表示 。 (2) 对文法对文法G中任何规则中任何规则A，我我们们有有A，即即推导的依据是规则推导的依据是规则。 注意推导和规则的区别：注意推导和规则的区别：即表示从即表示从 0 出发，经出发，经 一步或若干步一步或若干步 或或者说者说 使用若干次规则使用若干次规则可推导出可推导出 n。 2.3.32.3.3 语言的形式定义语言的形式定义 如果存在一个直接推导序列：如果存在一个直接推导序列： 则我

32、们称这个序列是一个从则我们称这个序列是一个从 0至至 n的的长度为长度为n的推导，记为的推导，记为 2推导推导0 1 2 n+0 n2.3.32.3.3 语言的形式定义语言的形式定义 例如例如 设有文法设有文法GE=(E,T,F,i,+,* *,(,),P,E)对对 i+ +i* *i 有如下直接推导序列有如下直接推导序列: : 我们可记为我们可记为 其中其中P为：为：EE+T | TTT* *F | FF(E) | iEE+TT+TF+Ti+Ti+T* *Fi+F* *Fi+i* *Fi+i* *iEi+i* *i+2.3.32.3.3 语言的形式定义语言的形式定义 3广义推导广义推导 我们

33、有：我们有： 0 n表示从表示从 0出发，经出发，经0步或若干步，步或若干步， 可推导出可推导出 n。* *也就是说也就是说 0 n意味着意味着 0 n或者或者 0= n。* *+ +EE* *Ei+i* *i* *对上例对上例 EE+T | T TT* *F | F F(E) | i2.3.32.3.3 语言的形式定义语言的形式定义 区别：区别：直接推导的直接推导的长度为长度为1，推，推导的导的长度大于等于长度大于等于1，而广义推导的，而广义推导的长度大于等于长度大于等于0。 句型和句子句型和句子 4. 句型和句子句型和句子 设有文法设有文法GS（S是文法是文法G的开始符号）的开始符号） 如

34、果如果S x, x, x x (VNVT)* 则称符号串则称符号串x x 为文法为文法GS的的句型句型。* * 如果如果S x, x, x x VT* 则称符号串则称符号串x x为文法为文法 GS的的句子句子。* *2.3.32.3.3 语言的形式定义语言的形式定义 例例1 设有文法设有文法GS： 我们有我们有: 显然，符号串显然，符号串01、0S1、00S11和和000111 都是文法都是文法GS的句型，而的句型，而01和和000111又是文法又是文法GS的句子。的句子。 S01 | 0S1S 0101*S 0S10S1*S 00S1100S11*S 000111000111*2.3.32.

35、3.3 语言的形式定义语言的形式定义 例例2 设有文法设有文法GE： 试证明符号串试证明符号串 (i* *i+i) 是文法是文法GE的一的一个句子。个句子。 分析分析 只要证明符号串只要证明符号串 (i* *i+i) 对文法对文法 G存在一个推导，就可证明符号串存在一个推导，就可证明符号串 (i* *i+i) 是文法是文法GE的一个句子的一个句子。 EE+E | E* *E | (E) | i2.3.32.3.3 语言的形式定义语言的形式定义 EE+E | E* *E | (E) | iE(E)(E+E)(E* *E+ +E)(i* *E+ +E)(i* *i+E)(i* *i+i) 即有即有

36、 E(i* *i+i), 所以符号串所以符号串(i+i* *i)是文法是文法 GE的一个句子。的一个句子。 * *（2）L(G)是是VT* 的子集。即属于的子集。即属于VT* 的符的符 号串号串 x 不一定属于不一定属于L(G)。2.3.32.3.3 语言的形式定义语言的形式定义 5语言语言 文法文法GS产生的所有句子的集合称为文产生的所有句子的集合称为文 法法G所定义的语言所定义的语言,记为记为L(GS)： 由语言定义可知：由语言定义可知：（1）一当文法给定，语言也就确定。）一当文法给定，语言也就确定。L(GS)=x|Sx且且xVT*+2.3.32.3.3 语言的形式定义语言的形式定义 例例

37、3 设有文法设有文法GS ：S01 | 0S1求该文法所描述的语言是什么？求该文法所描述的语言是什么？ 分析分析 由识别符号由识别符号S出发，将推出出发，将推出一些什么样的句子，也就是说，一些什么样的句子，也就是说，L(GS)将由什么样的一些符号串所将由什么样的一些符号串所组成的集合组成的集合，找出其中的规律，用式，找出其中的规律，用式子或自然语言描述出来。子或自然语言描述出来。 2.3.32.3.3 语言的形式定义语言的形式定义 我们应用第二个规则我们应用第二个规则n1次，然后再次，然后再应用第一个规则应用第一个规则1次，有：次，有： S0S100S110n-1S1n-10n1n即即S0n1

38、n* *可见，此文法定义的语言为可见，此文法定义的语言为L(GS)= 0n1n | n1S01 | 0S12.3.32.3.3 语言的形式定义语言的形式定义 例例4 设有文法设有文法GS：S0S | 1S |该文法所定义的语言是什么？该文法所定义的语言是什么？ 由该文法所确定的语言为由该文法所确定的语言为 L(GS)=, 0, 1, 00, 01, 10, 11, = x | x0,1* 2.3.32.3.3 语言的形式定义语言的形式定义 例例5 设有文法设有文法GA： 该文法所定义的语言是什么？该文法所定义的语言是什么？ 分析分析 从文法开始符号从文法开始符号A出发可推导出出发可推导出以以y

39、开头后面跟一个或多个开头后面跟一个或多个x结尾的符号结尾的符号串，所以该文法定义的语言为串，所以该文法定义的语言为AyBB xB | xL(GA)= yxn | n12.3.32.3.3 语言的形式定义语言的形式定义 由此可见，从已知文法确定语言由此可见，从已知文法确定语言的的中心思想是：中心思想是：从文法的从文法的开始符号开始符号出出发，发，反复反复连续地连续地使用规则使用规则替换、展开替换、展开非终结符，找出句子的规律，用式子非终结符，找出句子的规律，用式子或自然语言描述出来。或自然语言描述出来。 2.3.32.3.3 语言的形式定义语言的形式定义 形式语言理论可以证明如下两点：形式语言理

40、论可以证明如下两点：(1) 给定一种语言，能确定其文法，但这给定一种语言，能确定其文法，但这种文法种文法不是唯一的不是唯一的，即：，即：LG1或或G2或或(2) 给定一个文法，就能从结构上给定一个文法，就能从结构上唯一唯一确确定其语言，即：定其语言，即：GL(G)；2.3.42.3.4 规范推导和规范归约规范推导和规范归约 文法和语言是密切相关的，文法文法和语言是密切相关的，文法所定义的任一句型和句子所定义的任一句型和句子, 都可以根都可以根据文法推导出来。据文法推导出来。我们提出一个问题：我们提出一个问题：这种推导过程是否唯一？这种推导过程是否唯一？2.3.42.3.4 规范推导和规范归约规

41、范推导和规范归约 同一个句型同一个句型(句子句子)可以通过可以通过不同不同的推导序列推导出来，这是因为的推导序列推导出来，这是因为在在推导过程中与所选择非终结符的次推导过程中与所选择非终结符的次序无关。序无关。2.3.42.3.4 规范推导和规范归约规范推导和规范归约例如，设有文法例如，设有文法GN1 N1NNND | DD0 | 1 | 2 N1NNDN2D212 N1NNDDD1D12 N1NNDDDD212句子句子12有下列三种不同的推导序列有下列三种不同的推导序列:2.3.42.3.4 规范推导和规范归约规范推导和规范归约 最左最左(最右最右)推导，是指对于一个推导，是指对于一个推导序

42、列中的推导序列中的每一步直接推导每一步直接推导 , 都是对都是对 中的最左中的最左(最右最右)非终结符进非终结符进行替换。行替换。 最右推导也称为最右推导也称为规范推导规范推导，用规，用规范推导推导出的句型称为范推导推导出的句型称为规范句型规范句型。 2.3.42.3.4 规范推导和规范归约规范推导和规范归约 例例 设有文法设有文法GS: 请给出句子请给出句子101001的最右、最左推导。的最右、最左推导。 分析分析 最右推导是指在推导过程中最右推导是指在推导过程中任何一步任何一步 (和和是句型是句型)，都是对，都是对中的中的最右最右非终结符进行替换。非终结符进行替换。SABAA0 | 1BB

43、0 | S12.3.42.3.4 规范推导和规范归约规范推导和规范归约SABAS1AAB1AA01A1B01A10011B1001101001句子句子101001的最右推导为的最右推导为: SABAA0 | 1BB0 | S12.3.42.3.4 规范推导和规范归约规范推导和规范归约 最左推导是指在推导过程中任何最左推导是指在推导过程中任何一步一步 (和和是句型是句型), 都是对都是对的的最最左左非终结符进行替换。非终结符进行替换。句子句子101001的最左推导为：的最左推导为： SABAA0 | 1BB0 | S1SAB1BB10B10S110AB1101BB11010B11010012.3.42.3.4 规范推导和规范归约规范推导和规范归约归约归约是与推导相对的概念，推导是把是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替句型中的非终结符用规则的一个右部来替换的过程，而换的过程，而归约则是把句型中的某个子归约则是把句型中的某个子串用一个非终结符来