文法和语言的基本知识(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 概 述 这种非形式化描述这种非形式化描述, ,不够清晰和不够清晰和准确。准确。 为了精确定义和描述程序设计语为了精确定义和描述程序设计语言言, ,需采用形式化的方法。需采用形式化的方法。 形式化方法形式化方法, ,是用一整套带有严是用一整套带有严格规定的符号体系来描述问题的方法。格规定的符号体系来描述问题的方法。 2.2 字母表和符号串的基本概念字母表和符号串的基本概念内容主要包括：内容主要包括：1.字母表和符号

4、串的定义字母表和符号串的定义2.符号串的运算符号串的运算2.2.1 字母表和符号串字母表和符号串元素的非空有穷集合。元素的非空有穷集合。例如，例如，= a, b, c 1. 字母表字母表 根据字母表的定义，根据字母表的定义，是是字母表，字母表，它由它由a a、b b、c c三个三个元素元素组成。组成。不同的语言有不同的字母表不同的语言有不同的字母表任何语言的字母表指出该语言中允任何语言的字母表指出该语言中允许出现的一切符号许出现的一切符号2.2.1 字母表和符号串字母表和符号串 是一个字母表，由是一个字母表，由0 0、1 1两个元素两个元素组成。组成。注意注意:例如，例如， =0, 1 (2)

5、 字母表中的元素字母表中的元素, 可以是字母、可以是字母、数字或其他符号数字或其他符号。(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.1 字母表和符号串字母表和符号串说明说明: :不包含任何符号的符号串不包含任何符号的符号串, , 称为称为空空符号串符号串，用，用表示。表示。符号串中符号的符号串中符号的顺序顺序是很重要的。是很重要的。abab和和baba是字母表是字母表上的上的两个两个不同的不同的符号串。符号串。空符号串由空符号串由0 0个符号组成，个符号组成，其长度其长度| |=0|=0 x x x2

7、.2 .2 符号串的运算符号串的运算 设设x和和y是符号串，则串是符号串，则串xy称为它称为它们的们的连接连接。则则xy_ yx _ 注意注意：对任意一个符号串：对任意一个符号串x，1. 符号串的连接符号串的连接(结结)例如例如，设，设xabc，y102.2.2 符号串的运算符号串的运算2.(符号串的符号串的)集合的乘积集合的乘积 设设A和和B是符号串的集合是符号串的集合, 则则A和和B的乘积定义为：的乘积定义为： 集合的乘积是满足于集合的乘积是满足于 xA, yB的的所有符号串所有符号串 xy 所构成的集合。所构成的集合。AB=xy | xA, yB A A A2.2.2 符号串的运算符号串

8、的运算例如：例如：设设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的幂运算定义为：的幂运算定义为： x0= x1= x x2= xx x3= xxx xn= xx x

9、=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, aab, aba, abb, baa, bab, bb

10、a, bbb 2.2.2 符号串的运算符号串的运算5. 集合集合A的正闭包的正闭包A与闭包与闭包A* 设设A是符号串的集合，则是符号串的集合，则A的正闭的正闭包包A和和A的闭包的闭包A*的定义为的定义为:A+=A1A2 An A*= A0 A1A2 An =A+n 例如例如: 假设假设A a，n A 0 n A 1 an A 2 aan则则A + a，aa，aaa，aaaa， nA*= A0A+ = ， a，aa，aaa，2.2.2 符号串的运算符号串的运算A+表示表示A中中元素元素a, ,b构成的构成的所有符号所有符号串串的集合的集合A*比比A+多含一个空符号串多含一个空符号串 。例如，设例

11、如，设A= a, b , 则：则：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、，义两个方面，形式语言形式语言不考虑语言不考虑语言的具体意义，即的具体意义，即不考虑语义不考虑语义。C C语言是其字母表上的符合要求的语言是其字母表上的符合要求的符号串的集合，每个符号串的集合，每个C C语言程序是语言程序是一个符号串。一个符号串。 2.3.1 2.3.1 形式语言形式语言形式语言的描述形式语言的描述 对形式语言的描述有两种方法：对形式语言的描述有两种方法： 当语言为当语言为有穷集合有穷集合时，用时，用枚举法枚举法来表来表示语言。示语言。 当语言为当语言为无穷集合无穷集合时，用时，用文法文法来描述来描述语言。语言。 2.3.1 2.3.1 形式语言形式语言 均表示字母表均表示字

13、母表A上的一个形式语言。上的一个形式语言。由于由于这三个语言均是有限符号串的集合，因此，这三个语言均是有限符号串的集合，因此，可枚举出其全部句子来表示该语言。可枚举出其全部句子来表示该语言。 例如，设有字母表例如，设有字母表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, 当语言为当语言为无穷集合无穷集合时，用时，用文法文法来描

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

15、何用规规则中的符号串生成语言中的序列则中的符号串生成语言中的序列。2.3.2.3.2 2 文法的形式定义文法的形式定义 例如，前述例中一组规则例如，前述例中一组规则 描述的语言序列只可能是由描述的语言序列只可能是由0和和1组成的符号串。组成的符号串。A0A1AA0AA12.3.2.3.2 2 文法的形式定义文法的形式定义 规则中出现的符号分为两类规则中出现的符号分为两类 终结符号终结符号 非终结符号非终结符号 终结符号终结符号是是组成语言的基本符号组成语言的基本符号，是一个语是一个语言的不可再分的基本符号言的不可再分的基本符号，通常用小写字母，通常用小写字母表示。表示。 例如，上例中的例如，上

16、例中的0和和1。 2.3.2.3.2 2 文法的形式定义文法的形式定义 非终结符号非终结符号是出现在规则是出现在规则左部左部能派能派生出符号或符号串的那些符号。生出符号或符号串的那些符号。每个非终结符号表示一定符号串的每个非终结符号表示一定符号串的集合。集合。用大写字母表示或用尖括号把非终用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的结符号括起来。例如，上例中的A。2.3.2.3.2 2 文法的形式定义文法的形式定义 规则的非空有穷集合，规则的非空有穷集合，通常表示通常表示成四元组成四元组VN是规则中非终结符号的集合。是规则中非终结符号的集合。VT是规则中终结符号的集合。是规则中终

17、结符号的集合。P 是文法规则的集合。是文法规则的集合。 2. 文法文法G=(VN,VT, P, S )S 是文法的开始符号是文法的开始符号 SVN 2.3.2.3.2 2 文法的形式定义文法的形式定义 文法的开始符号也称文法的识文法的开始符号也称文法的识别符号别符号，它至少要在一条规则中作，它至少要在一条规则中作为左部出现。代表我们为左部出现。代表我们所定义的语所定义的语言言。 由文法定义可知，文法是对语言由文法定义可知，文法是对语言结构的定义和描述，四大要素结构的定义和描述，四大要素关键是关键是规则的集合规则的集合。 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 文法的形式定义文法的形式定义 当当n1 L=_ L=aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, 即即语言语言L是由是由偶数个偶数个a，偶数个偶数个b这样这样的符号串组成的集合的符号串组成的集合。

20、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、。 P : AB | DBaa | aBaDbb | bDb 若若G和和G是两个不同的文法，如是两个不同的文法，如果它们描述的语言相同，那么，称果它们描述的语言相同，那么，称G和和G 为为等价文法等价文法。2.3.2.3.2 2 文法的形式定义文法的形式定义 描述该语言的文法是否描述该语言的文法是否G也可以也可以？2.3.2.3.2 2 文法的形式定义文法的形式定义 对此例，对此例，我们提出下面这样一个问题：我们提出下面这样一个问题： G=( A, a, b, P, A ) 其中其中P= Aaa | bb | Aaa | Abb 对于文法对于文法G来说，它所产生的来说，它所产生的有些符号串，如

22、有些符号串，如aabb，bbaa， 不属于语言不属于语言L，即即设计的文法超出了设计的文法超出了所定义语言的范围所定义语言的范围。 2.3.2.3.2 2 文法的形式定义文法的形式定义 P= Aaa | bb | Aaa | Abb 2.3.2.3.2 2 文法的形式定义文法的形式定义 例例2 试设计一个表示所有试设计一个表示所有标识符标识符的文法的文法 分析分析 为为确定确定P中规则。应搞清楚中规则。应搞清楚集合中串的结构特征。集合中串的结构特征。 2.3.2.3.2 2 文法的形式定义文法的形式定义 用用I代表标识符；代表标识符；L代表字母；代表字母；D代表数字代表数字; 则定义标识符的文

23、法则定义标识符的文法为：为： 字母字母 字母或数字串字母或数字串标识符的结构可用下图表示标识符的结构可用下图表示:2.3.2.3.2 2 文法的形式定义文法的形式定义 G=(VN，VT，P，S)其中：其中： VN=I, L, DVT=a,b,c, x,y,z,0,1,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

24、，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 仅由字母串组成的标识符，仅由字母串组成的标识符，缩小缩小了所定义语言的范围了所定义语言的范围。 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代表字母数字串；代表字母数字串

25、；则则定义标识符的文法还可写为：定义标识符的文法还可写为： 字母字母 字母或数字串字母或数字串2.3.2.3.2 2 文法的形式定义文法的形式定义 P: IL | LT TL | D | LT | DT La | b | c | |x|y|z|x|y|z D0 | 1 | 2 | 3 | | 9 字母字母 字母或数字串字母或数字串2.3.2.3.2 2 文法的形式定义文法的形式定义 例例3 用文法定义一个含、用文法定义一个含、* *的算术表达式，定义用下述自然语的算术表达式，定义用下述自然语言描述：言描述： 变量是一个表达式；变量是一个表达式； 若若 E1和和 E2是算术表达式是算术表达式,

26、则则 E1E2、E1* *E2、(E1) 也是算术表也是算术表达式。达式。 2.3.2.3.2 2 文法的形式定义文法的形式定义 分析分析 定义用自然语言描述是非定义用自然语言描述是非形式定义，形式定义，用用文法来定义文法来定义即是即是用形用形式化式化的的方法定义表达式。定义算术方法定义表达式。定义算术表达式的文法为：表达式的文法为： 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,

27、i+i* *i, (i+i), 注意：是符号注意：是符号串的集合串的集合2.3.2.3.2 2 文法的形式定义文法的形式定义 例例4 设字母表设字母表 = a, b , 试设计一试设计一个文法，描述语言个文法，描述语言 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= a

28、a, aba, abba, 2.3.2.3.2 2 文法的形式定义文法的形式定义 例例5 设字母表设字母表= (, ) ,试设计试设计一个文法描述语言一个文法描述语言 L= (n )n | n0分析分析 该该语言中串的结构特征语言中串的结构特征是是 当当n=0 L= 注注: (0 )0= 当当n=1 L= ( ) 当当n=2 L= ( ) L= , ( ), ( ), ( ), 2.3.2.3.2 2 文法的形式定义文法的形式定义 S | ( S )所以定义语言的文法为： L= (n )n | n02.3.2.3.3 3 语言的形式定义语言的形式定义 1. 直接推导 令令G是一文法，我们称是一

29、文法，我们称 xAy直接直接推导出推导出 xy ，即即 xAyxy 仅仅 A 是是 G 的一条规则的一条规则, 且且 x, y (VNVT)*。也就是说从符号也就是说从符号串串 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 使用规则使

30、用规则 S01 此时此时 x0， y1 00S11000S111 使用规则使用规则 S0S1 此时此时 x00 , y11 000S11100001111 使用规则使用规则 S01 此时此时 x000 y111S 0 1 | 0 S 12.3.32.3.3 语言的形式定义语言的形式定义 (1) 形式上形式上的区别，推导用的区别，推导用“”表示，规则用表示，规则用“”表示表示 。 (2) 对文法对文法G中任何规则中任何规则A，我我们们有有A，即即推导的依据是规则推导的依据是规则。 注意推导和规则的区别：注意推导和规则的区别：即表示从即表示从 0 出发，经出发，经 一步或若干步一步或若干步 或或者

31、说者说 使用若干次规则使用若干次规则可推导出可推导出 n。 2.3.32.3.3 语言的形式定义语言的形式定义 如果存在一个直接推导序列：如果存在一个直接推导序列： 则我们称这个序列是一个从则我们称这个序列是一个从 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+

32、TT+TF+Ti+Ti+T* *Fi+F* *Fi+i* *Fi+i* *iEi+i* *i+2.3.32.3.3 语言的形式定义语言的形式定义 3广义推导广义推导 有：有： 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 广义推导的广义推导的长度大

33、于等于长度大于等于0句型和句子句型和句子 4. 句型和句子句型和句子 设有文法设有文法GS（S是文法是文法G的开始符号）的开始符号） 如果如果S x, xx, x (VNVT)* 则称符号串则称符号串x x 为文法为文法GS的的句型句型。* * 如果如果S x, xx, x VT* 则称符号串则称符号串x x为文法为文法 GS的的句子句子。* *2.3.32.3.3 语言的形式定义语言的形式定义 例例1 设有文法设有文法GS： 我们有我们有: 01、0S1、00S11和和000111 都是都是G的句型，的句型，01和和000111还是文法还是文法GS的句子的句子 S01 | 0S1S 0101

34、*S 0S10S1*S 00S1100S11*S 000111000111*2.3.32.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)

35、(E* *E+ +E)(i* *E+ +E)(i* *i+E)(i* *i+i) 即有即有 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）一旦文法给定，语言也就确定。）一旦文法给定，语言也就确定。

36、L(GS)=x|Sx且且xVT*2.3.32.3.3 语言的形式定义语言的形式定义 例例3 设有文法设有文法GS ：S01 | 0S1求该文法所描述的语言是什么？求该文法所描述的语言是什么？ 分析分析 由开始符号由开始符号S出发，将推出出发，将推出一些什么句子，找出其中的规律，用一些什么句子，找出其中的规律，用式子或自然语言描述出来。式子或自然语言描述出来。 2.3.32.3.3 语言的形式定义语言的形式定义 我们应用第二个规则我们应用第二个规则n1次，然后再次，然后再应用第一个规则应用第一个规则1次，有：次，有： S0S100S110n-1S1n-10n1n即即S0n1n* *可见，此文法定

37、义的语言为可见，此文法定义的语言为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开头后面跟一个或多个开

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

39、，但这给定一种语言，能确定其文法，但这种文法种文法不是唯一的不是唯一的(2) 给定一个文法，就能从结构上给定一个文法，就能从结构上唯一唯一确确定其语言定其语言2.3.42.3.4 规范推导和规范归约规范推导和规范归约 文法和语言是密切相关的，文法文法和语言是密切相关的，文法所定义的任一句型和句子所定义的任一句型和句子, 都可以根都可以根据文法推导出来。据文法推导出来。我们提出一个问题：我们提出一个问题：这种推导过程是否唯一？这种推导过程是否唯一？2.3.42.3.4 规范推导和规范归约规范推导和规范归约 同一个句型同一个句型(句子句子)可以通过可以通过不同不同的推导序列推导出来，这是因为的推导

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

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

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