编译原理-第3章文法和语言.ppt

《编译原理-第3章文法和语言.ppt》由会员分享，可在线阅读，更多相关《编译原理-第3章文法和语言.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3 3章章:文法和语言的概念和表示文法和语言的概念和表示v 概述概述v 形式语言基础形式语言基础v3.2 文法的直观理解文法的直观理解v3.3 文法和语言的定义文法和语言的定义v 文法的类型文法的类型v 语法树与二义性语法树与二义性v 句型的分析句型的分析3.0 3.0 概述概述 用高级语言编程比用低级语言方便，但要解决两个问题：用高级语言编程比用低级语言方便，但要解决两个问题：(1)(1)计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目 标程序的转换。标程序的转换。(2)(2)用什么方法来精确定义高级语言，即

2、怎样精确描述高级语言。用什么方法来精确定义高级语言，即怎样精确描述高级语言。要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。论或什么方法来描述的。本章目的本章目的 为语言的语法描述寻求工具，该工具要对程序设计语言给出精为语言的语法描述寻求工具，该工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）确无二义的语法描述。（严谨、简洁、易读）形式工

3、具形式工具-形式语言抽象地定义为一个数学系统。形式语言抽象地定义为一个数学系统。“形式形式”是指是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。语言概述语言概述语言是由句子组成的集合，或说是由一组符号串所构成的集合。语言是由句子组成的集合，或说是由一组符号串所构成的集合。汉语汉语所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律每个句子构成的规律研究语言研究语言

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

5、出现的行为中，它们的来源、使用和影响。表示在各个记号所出现的行为中，它们的来源、使用和影响。每每种种语语言言具具有有两两个个可可开开始始的的特特性性，即即语语言言的的形形式式和和该该形形式式相相关关联联的的意意义。义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意义。幽默、双关语

6、和谜语就是利用这两方面意义间的差异。意义。幽默、双关语和谜语就是利用这两方面意义间的差异。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式形式”是指这是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语

7、言语法分析研究的基础。分析研究的基础。任何语言均可看作一个集合。这个集合中的每个元素都是在任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集一定符号集（字母表）上的一个符号串（字母表）上的一个符号串。对于自然语言来说，它们是定义在某个字母表上的对于自然语言来说，它们是定义在某个字母表上的句子的集合句子的集合。对于程序语言来说，它们也是定义在某个字母表上的对于程序语言来说，它们也是定义在某个字母表上的句子句子的集合。的集合。这里这里的句子，就是一个源程序的句子，就是一个源程序。通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。通常，源程序是由关键字、标识符、常数、运算符

8、以及一些界限符组成。这些语法成分统称为单词或单词符号。这些语法成分统称为单词或单词符号。单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。规则所确定的，即词法规则规定了单词符号的形成规则。当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，就存在着如何给出它的

9、有穷表示的问题。言来讲，就存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明用这些规则来说明(或者定义或者定义)句子的组成结构，比如汉语句子可以是由主语句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。后随谓语而成，构成谓语的是动词和直接宾语。“我是大学生我是大学生”。是汉语的一个句子。是汉语的一个句子 用语法来描述：用语法来描述：句子句子=主语主语谓语谓语主语主语=代词代词名词名词代词代词=我我你你他他名词名词=王明王明大学生大学生工

10、人工人英语英语谓语谓语=动词动词直接宾语直接宾语动词动词=是是学习学习直接宾语直接宾语=代词代词名词名词 有了一组规则以后，按照如下方式用它们导出句子：开始去找有了一组规则以后，按照如下方式用它们导出句子：开始去找=左左端的带有端的带有句子句子的规则并把它由的规则并把它由=右端的符号串代替，这个动作表示右端的符号串代替，这个动作表示成：成：句子句子 主语主语谓语谓语，然后在得到的串，然后在得到的串主语主语谓语谓语中，选取中，选取主语主语或或谓语谓语，再用相应规则的，再用相应规则的=右端代替之。比如，右端代替之。比如，选取了选取了主语主语，并采用规则，并采用规则主语主语=代词代词，那么得到：那么

11、得到：主语主语谓语谓语 代词代词谓语谓语，重复做下去，重复做下去，句子：句子：“我是大学生我是大学生”的全部动作过程是：的全部动作过程是：句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 “我是大学生我是大学生”的构成符合上述规则，而的构成符合上述规则，而“我大学生是我大学生是”不符合上不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里的依据，换句

12、话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。3.1 3.1 形式语言基础形式语言基础基本概念基本概念:一、字母表和符号串一、字母表和符号串1.1.字母表：字母表：符号的非空有限集合符号的非空有限集合 例：例：=aa，b b，cc2.2.符号：符号：字母表中的元素字母表中的元素 例：例：a a，b b，c c3.3.符号串：符号串：符号的有穷序列符号的有穷序列 例：例：a,aa,ac,abca,aa,ac,abc，.特别地特别地,空符号串：空符号串：无任何符号的符号串无任何符号的

13、符号串()符号串的形式定义符号串的形式定义 有字母表有字母表，定义：，定义：（1 1）是是 上的符号串；上的符号串；（2 2）若）若x x是是 上的符号串，且上的符号串，且a a ，则，则axax或或xaxa是是 上的符号串；上的符号串；（3 3）y y是是 上的符号串，上的符号串，iffiff（当且仅当）（当且仅当）y y可由（可由（1 1）和（）和（2 2）产生。）产生。4.4.符号串集合：符号串集合：由符号串构成的集合。由符号串构成的集合。二、符号串和符号串集合的运算二、符号串和符号串集合的运算 5.5.符号串相等：符号串相等：若若x x、y y是集合上的两个符号串，则是集合上的两个符号

14、串，则x xy yiffiff（当且仅当）组成（当且仅当）组成x x的每一个符号和组成的每一个符号和组成y y的的每一个每一个符号符号依次相等。依次相等。6.6.符号串的长度：符号串的长度：x x为符号串，其长度为符号串，其长度|x|x|等于组成该符等于组成该符 号串的符号个数。号串的符号个数。例：例：x xSTV STV，|x|=3|x|=3 特别地特别地,|=0,|=0例：例：Aa,b,B=c,d,AB=？8.符号串集合的乘积运算符号串集合的乘积运算：令：令A、B为符号串集合，定义为符号串集合，定义 AB xy|xA，yB ac，ad，bc，bd 因为因为xxx，所以，所以A=A=A 7.

15、7.符号串的联接：符号串的联接：若若x x、y y是定义在是定义在是上的符号串，且是上的符号串，且x xXYXY，y yYXYX，则，则x x和和y y的联接的联接 xyxyXYYXXYYX也是也是上的符号串。上的符号串。注意：一般注意：一般xyyxxyyx，而，而xxxxx x 9.方幂运算方幂运算：符号串集合的方幂符号串集合的方幂 符号串的方幂符号串的方幂 有任一符号串集合有任一符号串集合A，定义，定义:有任一符号串有任一符号串X，定义，定义:A0=,X0=A1=A,X1=XA2=AA,X2=XXA3=AAA,X3=XXX AnAn-1A=AAn-1 Xn=XX X A A A n个个 n

16、个个其中其中:n010.10.符号串集合的闭包运算：符号串集合的闭包运算：设设A A是符号串集合，定义是符号串集合，定义 A=A1 A2 A3 An 称为集合称为集合A A的的正则闭包正则闭包。A*=A0 A1 A2 A3 An =A0 A 称为集合称为集合A A的的星闭包星闭包。例：例：A=x,y A？A*？x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3 为什么对符号、符号串、符号串集合以及它们的运算感兴趣为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若若A为某语

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

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

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

20、=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|推导方法：推导方法：从一个要开始的符号从一个要开始的符号开始推导，即用相应产生式的开始推导，即用相应产生式的右部右部来替代产生式的来替代产生式的左部左部，每，每次仅用一条产生式去进行推导。次仅用一条产生式去进行推导。例：例：给定给定一组语法规则，考一组语法规则，考察一个句子：察一个句子：“我是大学生我是大学生”的推导过程。的推导过程。例：有一英语句子：例：有一英语句子：The big elephant ate the peanut.:=:=:=:=:=:=the:=:=big:=:=elephant:=:=

21、:=:=ate:=:=:=:=peanut =the =the big =the big elephant =the big elephant =the big elephant ate =the big elephant ate =the big elephant ate the =the big elephant ate the peanut:=:=:=:=:=:=the:=:=big:=:=elephant|peanut:=:=:=:=ate:=:=The big elephant ate the peanut.上述推导可写成上述推导可写成=the big elephant ate th

22、e peanut+说明：说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为分进行推导，这称之为最左推导最左推导，类似的有，类似的有最右推导最右推导（一般推（一般推 导）。导）。(2)从一组产生式可推出不同的句子，如以上产生式还可推从一组产生式可推出不同的句子，如以上产生式还可推出出“大象吃象大象吃象”、“大花生吃象大花生吃象”、“大花生吃花生大花生吃花生”等句子，等句子，它们它们 在语法上都正确，但在语义上都不正确。在语法上都正确，但在语义上都不正确。所谓所谓文法文法是在是在形式上形式上对句子结构的定义与描述，而未

23、对句子结构的定义与描述，而未涉及涉及语义语义问题。问题。4.4.语法树语法树：我们用语法树来描述一个句子的语法结构。：我们用语法树来描述一个句子的语法结构。Thebigelephantatethepeanut语法成分（在形式语法成分（在形式语言中又称语言中又称“非终非终结符结符”）单词符号（在形单词符号（在形式语言中又称式语言中又称“终结符号终结符号”)文法的定义文法的定义3.3 3.3 文法和语言的形式定义文法和语言的形式定义 定义定义1:文法文法G=（VN，VT，P，Z）VN：非终结符号集：非终结符号集 VT：终结符号集：终结符号集 P：产生式或规则的集合：产生式或规则的集合 Z：开始符号

24、（识别符号）：开始符号（识别符号）ZVNVVNVT称为文法的字汇表称为文法的字汇表产生式：产生式：U:xU VN,xV*其中其中:产生式：产生式：产生式是一个有序对产生式是一个有序对(U,x),通常写为通常写为:U:x 或或U x；|U|=1|x|0非终结符号：非终结符号：出现在产生式的左部出现在产生式的左部,且能推出符号或符号串的且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为那些符号。其全体构成非终结符号集，记为VN。终结符号：终结符号：不出现在产生式的左部不出现在产生式的左部,且不能推出符号或符号串且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为的那些符号。其全体

25、构成终结符号集，记为VT。P=；00；11；99；Z=；例：无符号整数的文法：例：无符号整数的文法：G=（VN，VT，P，Z）VN,VT =0,1,2,3,9几点说明几点说明：产生式左边符号构成集合产生式左边符号构成集合VN，且，且 Z VN有些产生式具有相同的左部，可以合在一起有些产生式具有相同的左部，可以合在一起例、例、；|；00|1|2|3|9 文法的文法的BNF表示表示给定一个给定一个 文法，实际只需给出产生式集合，并指定开始符号文法，实际只需给出产生式集合，并指定开始符号例、例、G ；|；00|1|2|3|93.3.2 推导与归约推导与归约 定义定义2：直接推导：文法直接推导：文法G

26、：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。当符号串已没有非终结符号时，推导就必须终止。因为当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。符号称为非终

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

28、干次产生式可以从x变变换出换出y，则称，则称x*推导出推导出y(或者说或者说y是是x的的*推导），记为推导），记为x y。*N=109则有：则有：*N=N或者说或者说：若有直接推导序列：若有直接推导序列：x=U0=U1=U2=Un=y,则则 x=y 。+直观意义：规范推导最右推导直观意义：规范推导最右推导 定义定义5：最右推导：最右推导：若符号串若符号串中有两个以上的非终结符时，对推中有两个以上的非终结符时，对推导的每一步坚持把导的每一步坚持把中的最右中的最右非终结符进行替换，称为最非终结符进行替换，称为最右右推推导。导。最左推导：最左推导：若符号串若符号串中有两个以上的非终结符时，对推中有两

29、个以上的非终结符时，对推导的每一步坚持把导的每一步坚持把中的最左中的最左非终结符进行替换，称为最非终结符进行替换，称为最左左推推导。导。定义定义6：推导的逆过程称之为推导的逆过程称之为归约归约。例：例：x=y,可称为可称为x直接推导出直接推导出y，也可称为，也可称为y直接归约出直接归约出x。x=y,可称为可称为x推导出推导出y，也可称为，也可称为y归约出归约出x。3.3.3 语言的形式定义语言的形式定义文法文法GZGZ所产生的所产生的所有句子的集合所有句子的集合 定义定义7：文法文法GZ （1）句型句型：x是句型是句型 Z x,且且xV*；*（2）句子句子：x是句子是句子 Z x,且且xVT*

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

31、法1算法算法2x L(G)?Gyn出错处理出错处理停机停机3.3.4 递归文法递归文法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为右递归文法；为右递归文法；+4.递归文法的递归文法的优点优点：可用有穷条产生式，定义无穷语言：可用有穷条产生式，定义无穷语言 例：对于前面给出的无符号

32、整数的文法是有递归文法，用例：对于前面给出的无符号整数的文法是有递归文法，用13条产生式就可以定义出所有的无符号整数。若不用递归文法，条产生式就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条产生式呢？那将要用多少条产生式呢？!3.左左递归文法的递归文法的缺点缺点：不能用自顶向下的方法来进行语法分析：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）会造成死循环（后面将详细论述）3.4 文法分类文法分类 形式语言：形式语言：用文法和自动机所描述的没有语义的语言。用文法和自动机所描述的没有语义的语言。文法定义：文法定义：乔姆斯基将所有文法都定义为一个乔姆斯基将所有文法都定

33、义为一个四元组四元组：G=（VN，VT，P，Z）VN：非终结符号集：非终结符号集 VT：终结符号集：终结符号集 P：产生式或规则的集合：产生式或规则的集合 Z：开始符号（开始符号）：开始符号（开始符号）ZVN 语言定义：语言定义：L（GZ）=x|Z=x,xVT*,*文法和语言分类：文法和语言分类：0型、型、1型、型、2型、型、3型型 这几类文法的差别在于对产生式施加不同的限制。这几类文法的差别在于对产生式施加不同的限制。定义定义9：0型文法：型文法：P：u:=v 其中其中uV*，vV*0型语言：型语言：L0 这种语言可以用图灵机这种语言可以用图灵机(Turing)接受接受.0型文法称为型文法称

34、为短语结构文法短语结构文法。产生式的左部和右部都可。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。以是符号串，一个短语可以产生另一个短语。定义定义10：1型文法：型文法：P：xUy:=xuy 其中其中 UVN，x、y、uV*1型语言：型语言：L1 这种语言可以由一种这种语言可以由一种线性界限自动机线性界限自动机接受接受.称为称为上下文敏感上下文敏感或或上下文有关上下文有关。也即只有在。也即只有在x、y这样的这样的上下文中才能把上下文中才能把U改写为改写为u定义定义10：1型文法：型文法：P：u:=v u v u,v V*定义定义11：2型文法：型文法：P：U:=u 其中其中 U

35、VN，uV*2型语言：型语言：L2 这种语言可以由这种语言可以由下推自动机下推自动机接受接受.称为称为上下文无关文法上下文无关文法。也即把。也即把U改写为改写为u时，不必考虑上下文。时，不必考虑上下文。注意：注意：2型文法与型文法与BNF表示相等价。表示相等价。（右线性）（右线性）P：U:=t 或或 U:=tW 其中其中 U、WVN tVT 3型语言：型语言：L3 又称正则语言、正则集合又称正则语言、正则集合 这种语言可以由这种语言可以由有穷自动机有穷自动机接受接受.3型文法又被称为型文法又被称为正则文法正则文法。它是对。它是对2型文法进行进一步限制。型文法进行进一步限制。（左线性）（左线性）

36、P：U:=t 或或 U:=Wt 其中其中 U、WVN tVT定义定义12：3型文法：型文法：根据上述讨论，根据上述讨论，L0 L1 L2 L30型文法可以产生型文法可以产生L0、L1、L2、L3，但，但2型文法只能产型文法只能产生生L2，不能产生，不能产生L1。3.5 语法树与二义性文法语法树与二义性文法3.5.1 推导与语法树推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。结点和有向边组成。结点结点：符号符号 根结点：根结点：开始符号开始符号 中间结点：中间结点：非终结符非终结符 叶结点：叶结点：终结符或非

37、终结符终结符或非终结符 有向边有向边：表示结点间的派生关系。：表示结点间的派生关系。Z ZU UV Va abcd 注意一个重要事实注意一个重要事实：文法所能产生的句子，可以：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法树的生成规律不同，但最终生成的语推导出来。语法树的生成规律不同，但最终生成的语 法树形状完全相同。某些文法有此性质，而某些文法法树形状完全相同。某些文法有此性质，而某些文法 不具此性质。不具此性质。(2)句型的推导及语法树的生成（自顶向下）句型的推导及语法树的生成（自顶向下）给定给定GZ，句型，句

38、型w：可建立可建立推导序列推导序列，Zw 可建立可建立语法树语法树，以，以Z为树根结点，每步推导生成语法树为树根结点，每步推导生成语法树的一层分支，最终可生成句型的语法树。的一层分支，最终可生成句型的语法树。*1(1)(2)(3)(5)(4)0一般推导：一般推导：(3)子树与简单子树子树与简单子树 子树：子树：语法树中的某个结点（子语法树中的某个结点（子树的根）连同它向下派生的部分树的根）连同它向下派生的部分所组成。所组成。简单子树：简单子树：只有单层分枝的子树只有单层分枝的子树称为简单子树。称为简单子树。1(1)(2)(3)(5)(4)0(4)树与推导树与推导句型推导过程句型推导过程 句型语

39、法树的生长过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从从开始符号开始符号开始，开始，自左向右自左向右建立建立推导推导序列。序列。由由根结点根结点开始，开始，自上而下自上而下建立建立语法树语法树。例：给定文法例：给定文法G和句型和句型10,考察考察语法语法树与推导树与推导过程。过程。规范推导规范推导R R 0R0 0R110R 由语法树构造归约由语法树构造归约2自下而上自下而上地修剪子树的末端结点，直至把整棵树剪掉地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。（留根），每剪一次对应一次归约。从句型开始，从句型开始，自右向左自右向左地逐步进行地逐步进行归约

40、归约，建立，建立归约归约序列。序列。规范归约与规范推导互为逆过程规范归约与规范推导互为逆过程01R R 0R 0R10R定义定义14：通过规范推导或规范归约所得到的句型称为通过规范推导或规范归约所得到的句型称为规范句型规范句型。不是规范推导不是规范推导 在上例中，在上例中，就不是规范句型，因为：就不是规范句型，因为：RR3.5.2 文法的二义性文法的二义性 定义：定义：若对于一个文法的某一句子存在两棵不同的若对于一个文法的某一句子存在两棵不同的语法树语法树，则该文法是则该文法是二义性文法二义性文法，否则是无二义性文法。，否则是无二义性文法。换而言之，无二义性文法的句子换而言之，无二义性文法的句

41、子只有一棵语法树只有一棵语法树，尽管推，尽管推导过程可以不同。导过程可以不同。下面举一个二义性文法的例子：下面举一个二义性文法的例子：GE:E:=E+E|E*E|(E)|i VN=E VT=+,*,(,),i 对于句子对于句子Sii *i L（GE），存在不同的规范推导：），存在不同的规范推导：EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树这两种不同的推导对应了两种不同的语法树(1)E E+E E+E*E E+E*i E+i*i ii *iRRRRR(2)E E*E E*i E+E*i E+i*i ii*iRRRRRGE:E:=E+E|E*E|(E)|i 定义：

42、定义：若一个文法的某句子存在两个不同的若一个文法的某句子存在两个不同的规范推导规范推导，则，则该文法是该文法是二义性二义性的，否则是无二义性的。的，否则是无二义性的。以上是以上是自顶向下自顶向下来看文法的二义性，我们还可以来看文法的二义性，我们还可以自底向上自底向上来看文法的二来看文法的二义性。义性。上例中，规范句型上例中，规范句型E+E*i 是由是由ii*i通过两步规范规约得到的，但对于通过两步规范规约得到的，但对于同一个句型同一个句型E+E*i，它有两个不同的，它有两个不同的句柄句柄（对应上述两棵不同的语法树）：（对应上述两棵不同的语法树）：i 和和 EE。因此语法的二义性意味着句型的句柄

43、不唯一。因此语法的二义性意味着句型的句柄不唯一。EEE+EE*iEEE*EE+i句柄：句柄：i句柄：句柄：EE 若文法是二义性的，则在编译时就会产生不确定性，遗若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：憾的是在理论上已经证明：文法的二义性是不可判定的文法的二义性是不可判定的，即，即不可能构造出一个算法，通过有限步骤来判定任一文法是否不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。有二义性。现在的解决办法是：提出一些现在的解决办法是：提出一些限制条件限制条件，称为无二义性，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无的充分条件，当文

44、法满足这些条件时，就可以判定文法是无二义性的。二义性的。由于无二义性文法比较简单，我们也可以采用另一种解由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种决办法：即不改变二义性文法，而是确定一种编译算法编译算法，使，使该算法满足无二义性充分条件。该算法满足无二义性充分条件。定义定义14.3 若一个文法的某规范句型的若一个文法的某规范句型的句柄句柄不唯一，则该文法不唯一，则该文法是是二义性二义性的，否则是无二义性的。的，否则是无二义性的。例例:算术表达式的文法：算术表达式的文法：E:=E+E|E*E|(E)|iE:=E+T|TT:=T*F|FF:=(E)|i

45、例例:Pascal 语言条件语句的文法语言条件语句的文法:=If then|If then else :=|.3.6 句型的分析句型的分析 任务：给定任务：给定GZ:S VT*,判定是否有判定是否有 S L(GE)?这是这是词法分析词法分析和和语法分析语法分析所要做的工作，将在第三、所要做的工作，将在第三、四章中详细介绍。四章中详细介绍。3.6.1 句型的短语、简单短语和句柄句型的短语、简单短语和句柄*定义定义15:给定文法给定文法GZ,w=xuyV+，为该文法的句型，为该文法的句型,若若 ZxUy,且且U u,则则u是句型是句型w相对于相对于U的短语；的短语；其中其中U VN，u V+，x,

46、y V*直观理解：短语是前面句型中的某个非终结符所能推出直观理解：短语是前面句型中的某个非终结符所能推出的符号串。的符号串。或短语定义或短语定义:设设GZ是给定文法是给定文法,w=xuyV+，为该文法的句型，为该文法的句型,如果如果满足下面两个条件满足下面两个条件:Z xUy；U u；则称句型则称句型xuy 中的子串中的子串u是句型是句型xuy的短语。的短语。*定义定义17.任一句型的最左简单短语称为该句型的任一句型的最左简单短语称为该句型的句柄句柄。给定句型找句柄的步骤：给定句型找句柄的步骤：短语短语 简单短语简单短语 句柄句柄注意注意：短语、简单短语是相对于句型而言，一个句型：短语、简单短

47、语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。可能有多个短语、简单短语，句柄只能有一个。定义定义16:给定文法给定文法GZ,w=xuyV+，为该文法的句型，为该文法的句型,若若 Z xUy,且且U u,则则u是句型是句型w相对于相对于U的简单短语。的简单短语。其中其中U VN，u V+，x,y V*例：例：给定文法给定文法G：ET|E+T|ET TF|T*F|TF Fi|(E)符号串（符号串（T+i）*iF F是文法是文法G G的一个句型，求其短语、简单短语和句柄。的一个句型，求其短语、简单短语和句柄。E ET T TT T T*FT T F*FT T (E)*FT T

48、 (T+T)*FT T (T+F)*FT T (T+i)*FT T (T+i)*iT T (T+i)*iT T解：短语有解：短语有8个：个：1.E E，E（T+i）*iF 则有：则有：（T+i）*iF2.E TF，T（T+i）*i 则有：则有：（T+i）*i3.E T*iF，T（T+i）则有：则有：（T+i）4.E(E)*iF，ET+i 则有：则有：T+i5.E(E+i)*iF，ET 则有：则有：T6.E(T+F)*iF，Fi 则有：则有：第一个第一个i7.E(T+i)*FF，Fi 则有：则有：第二个第二个i8.E(T+i)*FT，TF 则有：则有：F*+*+*+*+*+*+*+*+定义定义:

49、给定文法给定文法GZ,w=xuyV+，为该文法的句型，为该文法的句型,若若 ZxUy,且且U u,则则u是句型是句型w相对于相对于U的短语；的短语；若若 Z xUy,且且U u,则则u是句型是句型w相对于相对于U的简单短语。的简单短语。其中其中U VN，u V+，x,y V*U其简单短语有其简单短语有4个：个：1.E(E+i)*iF,EF,ET 则有：则有：T2.E(T+F)*iF,FF,Fi 则有：则有：第一个第一个i i3.E(T+i)*FF,FF,Fi 则有：则有：第二个第二个i i4.E(T+i)*FT T,T,TF 则有：则有：F F句柄有句柄有1 1个：个：T TEETT TT*F

50、F F(E E)F Fi iE+TT TF Fi i用语法树求用语法树求短语、简单短语和句柄短语、简单短语和句柄的方法：的方法：1）每个句型都有一棵语法树；）每个句型都有一棵语法树；2）每棵语法树的叶（从左到右）组成一句型；）每棵语法树的叶（从左到右）组成一句型；3）每个子树）每个子树 的叶（从左到右）组成一短语；的叶（从左到右）组成一短语；4）每个简单子树）每个简单子树 的叶（从左到右）组成一简单短语；的叶（从左到右）组成一简单短语；5）最左简单子树）最左简单子树 的叶（从左到右）组成一句柄。的叶（从左到右）组成一句柄。只需画出句型的语法树，然后根据子树找短语只需画出句型的语法树，然后根据子