编译原理2.1文法和语言

1、12.1 2.1 文法和语言文法和语言v 0 概述概述v 1 形式语言基础形式语言基础v 2 文法的直观理解文法的直观理解v 3 文法和语言的定义文法和语言的定义v 4 文法的类型文法的类型v 5 语法树与二义性语法树与二义性v 6 句型的分析句型的分析20 0 概述概述显然，用高级语言编程比用低级语言来得方便，显然，用高级语言编程比用低级语言来得方便，但要解决两个问题：但要解决两个问题：1.1.计算机怎样懂得高级语言程序，这就需要一计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。个翻译程序实现从源程序到目标程序的转换。2.2.用什么方法来精确定义高级语言，即怎样

2、精用什么方法来精确定义高级语言，即怎样精确描述高级语言。确描述高级语言。要构造一个编译程序，应深刻理解被编译的源要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）及其含义（即语义），语言的结构（即词法和语法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。么理论或什么方法来描述的。3当我们表述一种语言时，无非是要说明这种语言的当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句

3、子的语言来讲，就存有穷集就行了，但对于含有无穷句子的语言来讲，就存在着如何给出它的有穷表示的问题。在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明们可以给出一些规则，用这些规则来说明(或者定义或者定义)句句子的组成结构，比如汉语句子可以是由主语后随谓语而子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。成，构成谓语的是动词和直接宾语。4任何语言均可看作一个集合。这个集合中的每任何语言均可看作一个集合。这个集合中的每个元素都是在个元素都是在一定符号集（字母表）

4、上的一个符号一定符号集（字母表）上的一个符号串串。对于自然语言来说，它们是定义在某个字母表对于自然语言来说，它们是定义在某个字母表上的上的句子的集合句子的集合。对于程序语言来说，它们也是定义在某个字母对于程序语言来说，它们也是定义在某个字母表上的表上的句子句子的集合。的集合。这里的句子，就是一个源程序这里的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。算符以及一些界限符组成。这些语法成分统称为单词或单词符号。这些语法成分统称为单词或单词符号。单词符号是语言中具有独立意义的最基本单位。单词符号是语言中具有独立意义的

5、最基本单位。语言的单词符号是由词法规则所确定的，即词法规语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。则规定了单词符号的形成规则。5语言概述语言概述语言是由句子组成的集合，或说是由一组符号串语言是由句子组成的集合，或说是由一组符号串所构成的集合。所构成的集合。汉语汉语所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言所有该语言的源程序的全体所有该语言的源程序的全体 每个句子构成的规律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句

6、子和使用者的关系6研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics7语法语法 表示构成语言句子的各个记号之间的表示构成语言句子的各个记号之间的组合规律。组合规律。语义语义 表示各个记号的特定含义。（各个记表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）号和记号所表示的对象之间的关系）语用语用 表示在各个记号所出现的行为中，它们表示在各个记号所出现的行为中，它们的

7、来源、使用和影响。的来源、使用和影响。8如果不考虑语义和语用，即只从语法这一侧面来看语如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。形式语言抽象地定义为一个数学系统。“形式形式”是指这样的事实：语言的所有规则只以什麽是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。性的研究。是程序设计语言语法分析研究的基础。9一、一、

8、形式语言基础形式语言基础基本概念基本概念: :一、字母表和符号串一、字母表和符号串1.1.字母表：字母表：符号的非空有限集合符号的非空有限集合 例：例： = =aa，b b，cc2.2.符号：符号：字母表中的元素字母表中的元素 例：例： a a，b b，c c3.3.符号串：符号串：符号的有穷序列符号的有穷序列 例：例：a, aa, ac, abca, aa, ac, abc，. 特别地特别地, ,空符号串：空符号串：无任何符号的符号串无任何符号的符号串( () ) 10符号串的形式定义符号串的形式定义 有字母表有字母表 ，定义：，定义：（1 1）是是 上的符号串；上的符号串；（2 2）若）若

9、x x是是 上的符号串，且上的符号串，且a a ，则，则axax或或xaxa是是 上的符号串；上的符号串；（3 3）y y是是 上的符号串，当且仅当上的符号串，当且仅当y y可由（可由（1 1）和（）和（2 2）产生。产生。 4.4.符号串集合：符号串集合：由符号串构成的集合。由符号串构成的集合。11v 重要约定：重要约定： 小写字母小写字母 s, t, u, , z 表示符号串表示符号串 大写字母大写字母 A, B, C, , Z 表示符号串集合表示符号串集合12二.符号串的运算1.符号串相等：符号串相等：设设 x 、y 是字母表是字母表 上的两个符号串，若上的两个符号串，若 x 与与 y

10、的诸符号的诸符号依次依次相等，则该两符号串相等，记为相等，则该两符号串相等，记为 x = y例：例：x=ab, y=ba, x=y?132.符号串长度：符号串长度：设设 x 是字母表是字母表 上的符号串，符号串中包含上的符号串，符号串中包含符号的符号的个数个数称为符号串称为符号串 x 的长度，用的长度，用 x 表示表示 例例: (1). | abc | = ? (2). | | = ? (3). | a x | = | x a | = | x | + 1 ( a )143. 符号串的连结：符号串的连结：设设 x 与与 y 是字母表是字母表 上的两个符号串，上的两个符号串，把把 y 的所有符号相

11、继写在的所有符号相继写在 x 的符号之后所得到的符号串的符号之后所得到的符号串称为称为x 与与 y 的连结，用的连结，用 x y 表示表示注意注意: | x y | = | x | + | y | x = x = x x y y x ( 一般说来一般说来 )15. 若若 x = abcd , 则则 = ? X4 .符号串的逆：符号串的逆：设设 x 是字母表是字母表 上的符号串，其逆为符号串上的符号串，其逆为符号串 x 的倒置，的倒置，记为记为 。X(2). = 165.符号串的前缀、后缀和子串：符号串的前缀、后缀和子串：设设 x、y、z 是字母表是字母表 上的上的符号串，则称符号串，则称 x

12、为符号串为符号串 x y 的的前缀前缀，y 是符号是符号 串串 x y 的的后缀后缀， x、y 、 z 、xy 、yz 是符号串是符号串 x y z 的的子串子串例例: abcd前缀、后缀、子串是什么？前缀、后缀、子串是什么？176.符号串集合的乘积：符号串集合的乘积：设设A、B为两个符号串集合，其乘积为为两个符号串集合，其乘积为 AB=xy|x A,y B例例: (1). 若若 A = ab, cd , B = ef, gh ，AB？ (2). x = x = x A = A = A187.空集：空集：不含任何元素的集合，记为不含任何元素的集合，记为 注意注意: (1). A = A = (

13、2). 198.符号串的幂：符号串的幂：设设 x 是字母表是字母表 上的符号串，则上的符号串，则 x 的幂运算的幂运算为为x 0 = x 1=x x 2=xx x n=x n-1x (xx n-1)例例: 若若 x = ab 则则: x 0 = ?, x 1 = ?, x 2 = ?, , x n = ?209.符号串集合的幂：符号串集合的幂：设设 A 是符号串集合，则符号串是符号串集合，则符号串 A 的幂运的幂运算为：算为： A0= A1=A A2=AA An=A n-1A (AA n-1)例例: 若若 A = ab, cd ,则则: A 0 = ?, A 1 = ?, A 2 = ?, 2

14、1注意注意:A*=A0A+ A+=AA*=A*A 若若 A = a, b 则则: A*= , a, b, aa, ab, ba, bb, aaa, A+= a, b, aa, ab, ba, bb, aaa, 10.符号串集合的闭包运算：符号串集合的闭包运算：设设A是符号串集合，定义是符号串集合，定义 A = A1 A2 A3 An 称为集合称为集合A的的正闭包正闭包。 A* = A0 A1 A2 A3 An = A0 A 称为集合称为集合A的的闭包闭包。22 为什么对符号、符号串、符号串集合以及它们的运算感兴趣？为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若若A为某语言的基本字符集

15、为某语言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), =B为单词集为单词集 B =begin, end, if, then,else,for, +,_/, ( , ), 则则B A* 。语言的句子是定义在语言的句子是定义在B上的符号串上的符号串。若令若令C为句子集合，则为句子集合，则C B * , 程序程序 C23二、文法的直观理解二、文法的直观理解1.1.什么是文法：什么是文法： 文法是对语言结构的定义与描述。即从形式上用于描述文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为和规定语言结构的称为“文法文法”（或称为（或称为“语法语法”）。）。 例：有

16、一句子：例：有一句子：“我是大学生我是大学生” 。这是一个在语法、语这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的的语法决定的 。在本例中它为。在本例中它为“主谓结构主谓结构”。如何定义句子的合法性如何定义句子的合法性？有穷语言有穷语言无穷语言无穷语言24 2.2.语法规则：语法规则： 我们通过建立一组规则（产生式），来描述句子我们通过建立一组规则（产生式），来描述句子的的语法结构语法结构。规定用。规定用“”或或“:=:=”表示表示“由由组成组成”。 | 你你| |我我| |他他 王民王民| |大学生大学生

17、| |工人工人| |英语英语 是是| |学习学习 | 25由产生式推导句子：由产生式推导句子： 这种推导一直进行下去，直到所有带这种推导一直进行下去，直到所有带的符号都由终结符号的符号都由终结符号替代为止。替代为止。 有了一组产生式之后，可以按照一定的方式用它们去推导或有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。产生句子。 推导方法：推导方法：从一个初始的符号开始推导，即用相应产生式的从一个初始的符号开始推导，即用相应产生式的右部右部来替代产生式的来替代产生式的左部左部，每次仅用一条产生式去进行推导。，每次仅用一条产生式去进行推导。26 我我 我我 我我是是 我是我是 我是大

18、学生我是大学生 | 你你| |我我| |他他 王民王民| |大学生大学生| |工人工人| |英语英语 是是| |学习学习 | 推导方法：推导方法：从一个初始的符号从一个初始的符号开始推导，即用相应产生式的开始推导，即用相应产生式的右部右部来替代产生式的来替代产生式的左部左部，每，每次仅用一条产生式去进行推导。次仅用一条产生式去进行推导。例：例：给定给定一组语法规则，考一组语法规则，考察一个句子：察一个句子：“我是大学生我是大学生”的推导过程。的推导过程。271文法的定义文法的定义三三 文法和语言的形式定义文法和语言的形式定义 定义定义1: 文法是产生式的有穷集合文法是产生式的有穷集合,通常定义

19、为四元组通常定义为四元组: G=（VN，VT，P，S） VN ：非终结符号集：非终结符号集 VT ：终结符号集：终结符号集 P：产生式或规则的集合：产生式或规则的集合 S：开始符号（识别符号）：开始符号（识别符号） SVNVVNVT称为文法的符号集称为文法的符号集产生式：产生式：U : xU VN, xV*其中其中: 产生式：产生式：产生式是一个有序对产生式是一个有序对(U, x), 通常写为通常写为: U : x 或或U x； | U| = 1 |x| 0非终结符号：非终结符号：出现在产生式的左部出现在产生式的左部,且能推出符号或符号串的且能推出符号或符号串的那些符号。其全体构成非终结符号集

20、，记为那些符号。其全体构成非终结符号集，记为VN 。终结符号：终结符号：不出现在产生式的左部不出现在产生式的左部,且不能推出符号或符号串且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为的那些符号。其全体构成终结符号集，记为VT 。28P = ； ； ； 00； 11； 99； S = ；例：无符号整数的文法：例：无符号整数的文法：G=（VN，VT，P，Z）VN, VT = 0,1,2,3,929几点说明几点说明：产生式左边符号构成集合产生式左边符号构成集合VN，且，且 S VN有些产生式具有相同的左部，可以合在一起有些产生式具有相同的左部，可以合在一起例、例、 ； | ； 00 |

21、 1 | 2 | 3 | | 9 文法的文法的BNF表示表示给定一个给定一个 文法，实际只需给出产生式集合，并指定开始符号文法，实际只需给出产生式集合，并指定开始符号例例: G ； | ； 00 | 1 | 2 | 3 | | 930v例例 文法文法G=（VN，VT，P，S），其中），其中VN = S ，VT = 0, 1 ，P= S0S1, S01 思考：思考：S？ 31v例例文法文法G=（VN，VT，P，S），其中），其中VN =标识符，字母，数字标识符，字母，数字 ，S=VT =a,b,c,x,y,z,0,1,9P a z 0 9 思考：思考：S？322 推导与归约推导与归约 定义定义2

22、： 直接推导：文法直接推导：文法G：vx Uy，wxuy, 其中其中x、y V* ，UVN, u V*, 若若U uP，则，则v w，即，即x Uy xuy 。 若若xy，有，有U u，则，则U u 换句话说，换句话说，x和和y是符号串，若使用一次产生式是符号串，若使用一次产生式可以从可以从x变换出变换出y，则称，则称x直接推导出直接推导出y(或者说或者说y是是x的直接推导），记为的直接推导），记为x y。33 当符号串已没有非终结符号时，推导就必须终止。当符号串已没有非终结符号时，推导就必须终止。例如：例如：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6| 7| 8|

23、9N ND NDD ND9 N09 D09 109 (6) (1) (3)(4) (2)(5) 34 N 109定义定义3：+ +推导：推导：x和和y是符号串，若使用若干次产生式可以从是符号串，若使用若干次产生式可以从x变换出变换出y，则称则称x推导出推导出y(或者说或者说y是是x的推导），记为的推导），记为 x y。例：例：则有：则有： 定义定义4： * *推导：推导：x和和y是符号串，若使用是符号串，若使用0次或若干次产生式可以从次或若干次产生式可以从x变变换出换出y，则称，则称x*推导出推导出y(或者说或者说y是是x的的*推导），记为推导），记为x y。* *N 109则有：则有： *N

24、 N或者说：或者说：若有直接推导序列：若有直接推导序列： x=U0 U1 U2 Un=y,则则 x y 。+N ND NDD ND9 N09 D09 109 (6) (1) (3)(4) (2)(5) 35直观意义：规范推导最右推导直观意义：规范推导最右推导 定义定义5： 最右推导：最右推导：若符号串若符号串中有两个以上的非终结符时，对推中有两个以上的非终结符时，对推导的每一步坚持把导的每一步坚持把中的最右中的最右非终结符进行替换，称为最非终结符进行替换，称为最右右推推导。导。 最左推导：最左推导：若符号串若符号串中有两个以上的非终结符时，对推中有两个以上的非终结符时，对推导的每一步坚持把导的

25、每一步坚持把中的最左中的最左非终结符进行替换，称为最非终结符进行替换，称为最左左推推导。导。 定义定义6： 推导的逆过程称之为推导的逆过程称之为归约归约。例：例：x y,可称为可称为x直接推导出直接推导出y，也可称为，也可称为y直接归约出直接归约出x。 x y ,可称为可称为x推导出推导出y，也可称为，也可称为y归约出归约出x。363 语言的形式定义语言的形式定义文法文法GSGS所产生的所产生的所有句子的集合所有句子的集合 定义定义7：文法文法GS （1）句型句型：x是句型是句型 S x,且且xV*；*（2）句子句子：x是句子是句子 S x, 且且xVT*；*（3）语言语言：L（GS）=x|

26、S x， xVT* ；即：即：句型是由文法开始符号推导出来的句型是由文法开始符号推导出来的由终结符和非终结符组成的符号串。由终结符和非终结符组成的符号串。即：即：句子是由文法开始符号推导出来的句子是由文法开始符号推导出来的由终结符组成的符号串。由终结符组成的符号串。37例：例：abna|n1,构造其文法构造其文法 G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb 定义定义8: G和和G是两个不同的文法，若是两个不同的文法，若 L(G) = L(G) , 则则G和和G为为等价文法等价文法。38编译感兴趣的问题是编译感兴趣的问题是: :p给定给定x, G, 求求x L(G) ?x

27、算法算法1算法算法2x L(G) ?Gyn出错处理出错处理停机停机394 递归文法递归文法1.递归产生式递归产生式：产生式右部有与左部相同的符号：产生式右部有与左部相同的符号 对于对于 U xUy 若若x=,即即U Uy，左递归；，左递归； 若若y=,即即U xU，右右递归；递归； 2.递归文法递归文法：文法文法G，存在，存在U VN if U U, 则则G为递归文法；为递归文法； if U U, 则则G为左递归文法；为左递归文法； if U U, 则则G为右递归文法；为右递归文法；+404. 递归文法的优点：可用有穷条产生式，定义无穷语言递归文法的优点：可用有穷条产生式，定义无穷语言!3.

28、左左递归文法的缺点：不能用自顶向下的方法来进行语法分析递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）会造成死循环（后面将详细论述）41四四 文法分类文法分类 形式语言：用文法和自动机所描述的没有语义的语言。形式语言：用文法和自动机所描述的没有语义的语言。 文法定义：乔姆斯基将所有文法都定义为一个文法定义：乔姆斯基将所有文法都定义为一个四元组四元组：G=（VN，VT，P，S） VN：非终结符号集：非终结符号集 VT：终结符号集：终结符号集 P：产生式或规则的集合：产生式或规则的集合 S：开始符号（开始符号）：开始符号（开始符号） ZVN 语言定义：语言定义： L

29、（GS）=x| S x , xVT*, *42 文法和语言分类：文法和语言分类：0型、型、1型、型、2型、型、3型型 这几类文法的差别在于对产生式施加不同的限制。这几类文法的差别在于对产生式施加不同的限制。定义定义9：设设G（VN，VT，P，S），如果它的），如果它的每个每个产生式产生式、是这样一种结构：是这样一种结构：(VNVT)*且且至少包至少包含一个含一个非终结符，非终结符， (VNVT)*，则，则G是一个是一个0型文法型文法（短语文法、无限制文法短语文法、无限制文法）43定义定义10：设设G（VN，VT，P，S）如果在 P 中所有的规则都有如下形式A 这里的 A VN，, (VN U

30、VT)* (VN U VT)+仅S 除外，此时 S 不出现在任何规则的右手端。则称文法G为1型文法或上下文有关文法。S aRcR aRT | bbTc bbccbTT bbUTUT UUUUc VUc VccUV VVbVc bbccbVV bbWVWV WWWWc TWc TccWT TT44定义定义11：设设G（VN，VT，P，S），如果它的），如果它的每个每个产生式产生式A均满足：均满足：A是是一个一个非终结符，非终结符， V*，则文法，则文法G是是2型文法型文法（上下文无关文法上下文无关文法）这个例子可以产生变量 x,y,z 的算术表达式：S - T + S | T - S | TT

31、- T * T | T / T | ( S ) | x | y | z例如字串 ( x + y ) * x - z * y / ( x + x ) 就可以用这个文法来产生。 45（右线性）（右线性） AB或或A其中其中 A是是一个一个非终结符，非终结符， VT，则文法，则文法G是是3型文法型文法（正则文法正则文法）（左线性）（左线性） AB或或A定义定义12：设设G（VN，VT，P，S），如果它的），如果它的每个每个产生式产生式限制为形如：限制为形如：例：文法例：文法GS：S 0A|1B|0A 0A|1B|0SB 1B|1|046根据上述讨论，根据上述讨论，L0 L1 L2 L30型文法可以产

32、生型文法可以产生L0、L1、L2、L3，但，但2型文法只能产型文法只能产生生L2、L3，不能产生，不能产生L1。47五五 语法树与二义性文法语法树与二义性文法上下文无关文法有足够的能力描述现今程序设计语言的上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式、描述各种语句等语法结构，比如描述算术表达式、描述各种语句等例例3.6：文法：文法G=(E,+,*,i,(,),P,E)其中其中P为：为：EiEE+EEE*E E (E)ifthen| ifthenelse 48给定文法给定文法G=（VN，VT，P，S），对于），对于G的任何句型都的任何句型都能构造与之关联的语法树（

33、推导树、语法分析树、分能构造与之关联的语法树（推导树、语法分析树、分析树）。析树）。这棵树满足下列这棵树满足下列4个条件：个条件：（1）每个结点都有一个）每个结点都有一个V中的符号作标记中的符号作标记（2）根的标记是开始符号）根的标记是开始符号S（3）若一结点）若一结点n至少有一个它自己除外的子孙，并且有标记至少有一个它自己除外的子孙，并且有标记A，则，则AVN（4）如果结点）如果结点n的直接子孙，从左到右的次序是结点的直接子孙，从左到右的次序是结点n1,n2,nk，其标记分别为，其标记分别为A1,A2,Ak，那么，那么AA1A2Ak一定是一定是P中的一个产生式中的一个产生式49例：文法例：文

34、法G=(S，A,a,b,P,E)其中其中P为：为：(1)SaAS(2)ASbA(3)ASS (4)S a (5)A ba图图3.1的推导树是文法的推导树是文法G的的句型句型aabbaa的推导过程的推导过程把把aabbaa叫做推导树的结果，叫做推导树的结果，把推导树叫做句型把推导树叫做句型aabbaa的语法树的语法树图图3.1 推导树推导树 50文法文法G的句型的句型aabbaa的推导过程：的推导过程：（1）SaASaAaaSbAaaSbbaaaabbaa（2）SaASaSbASaabASaabbaSaabbaa（3）SaASaSbASaSbAaaabAaaabbaa如果在推导的任何一步如果在推

35、导的任何一步 ，其中，其中、是句型，都是句型，都是对是对中的最左（最右）非终结符进行替换，则称这种推中的最左（最右）非终结符进行替换，则称这种推导为导为最左（最右）推导最左（最右）推导。在形式语言中，最右推导被称为。在形式语言中，最右推导被称为规范推导规范推导，由规范推导所得的句型称为，由规范推导所得的句型称为规范句型规范句型你会忘记我吗？你会忘记我吗？51例：例：GE:E iE E+EE E*EE (E)句型句型 i*i+i 的两个：的两个：推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+i一个句型是否只对

36、应唯一的一棵语法树？一个句型是否只一个句型是否只对应唯一的一棵语法树？一个句型是否只有唯一的一个最左（最右）推导？有唯一的一个最左（最右）推导？ 不是不是52图图3.2推导推导1的语法树的语法树图图3.3推导推导2的语法树的语法树53若一个文法存在某个句子对应若一个文法存在某个句子对应两棵不同的语法树两棵不同的语法树，则称这，则称这个文法是个文法是二义的二义的。或者，若一个文法存在某个句子有或者，若一个文法存在某个句子有两个两个不同的最左（右）推导不同的最左（右）推导，则称这个文法是，则称这个文法是二义的二义的54注意，注意，文法的二义性文法的二义性和和语言的二义性语言的二义性是两个不同的概念

37、。是两个不同的概念。因为可能有两个不同的文法因为可能有两个不同的文法G和和G，其中，其中G是二义的，但是二义的，但是却有是却有L(G)=L(G)产生某上下文无关语言的每一个文法都是二义的，则称此产生某上下文无关语言的每一个文法都是二义的，则称此语言是语言是先天二义的先天二义的你是怎么理你是怎么理解我的？解我的？55课堂习题与练习：课堂习题与练习：1、假设G是一个文法，S是文法的开始符号，如果Sx，则称x是_。 *句型2、文法G产生的_的全体是该文法描述的语言。句子3、乔姆斯基定义的四种形式语言文法分别为: (1) 文法(又称 (2) 文法)、 (3) 文法(又称 (4) 文法)、 (5) 文法(又称 (6) 文法)、 (7) 文法 (又称 (8) 文法)。答案：答案： (1) 0型型 (2) 短语结构短语结构 (3) 1型型 (4) 上下文有关上下文有关 (5) 2型型 (6) 上下文无关上下文无关 (7) 3型型 (8) 正规正规 564、如果一个文法满足 ，则称该文法是二义文法。 文法的某一个句子存在两棵（包括两棵）以上的语法树