东北大学秦皇岛分校编译原理课件第二章第三章.ppt

第三章第三章 文法和语言文法和语言本章目的本章目的 为语言的语法描述寻求工具为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描工具要对程序设计语言给出精确无二义的语法描工具要对程序设计语言给出精确无二义的语法描工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）述。（严谨、简洁、易读）述。（严谨、简洁、易读）述。（严谨、简洁、易读）形式形式工具工具-形式语言抽象地定义为一个数学形式语言抽象地定义为一个数学系统。系统。“形式形式”是指这样的事实：语言的是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来所有规则只以什麽符号串能出现的方式来陈述陈述1本章知识点本章知识点(内容内容)引言和预备知识引言和预备知识引言和预备知识引言和预备知识文法和语言的形式定义文法和语言的形式定义文法的类型文法的类型上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法的句型分析上下文无关文法的句型分析有关文法实用中的一些说明有关文法实用中的一些说明23.1文法的直观概念和语言概述语言概述当我们表述一种语言时，无非是说明这当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，句子，则只需列出句子的有穷集就行了，但对于但对于含有无穷句子含有无穷句子的语言来讲，存在的语言来讲，存在着如何给出它的着如何给出它的有穷表示有穷表示的问题：给出的问题：给出一些规则，用这些规则来说明一些规则，用这些规则来说明(或者定义或者定义)句子的句子的组成结构组成结构。3“我是大学生”。是汉语的一个句子句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 4有了一组有了一组规则规则规则规则以后，按照如下方式用它们以后，按照如下方式用它们导出导出导出导出句子：开始去句子：开始去找找=左端的带有句子的规则并把它由左端的带有句子的规则并把它由=右端的符号串代右端的符号串代替，这个动作表示成：替，这个动作表示成：句子句子主语谓语，主语谓语，然后在得到的串主语谓语中，选取主语或谓然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的语，再用相应规则的=右端代替之。比如，选取了主语右端代替之。比如，选取了主语，并采用规则主语，并采用规则主语=代词，代词，那么得到：主语谓语那么得到：主语谓语代词谓语，代词谓语，重复做下去，重复做下去，句子：句子：“我是大学生我是大学生”的全部动作过程是：的全部动作过程是：句子句子主语谓语主语谓语代词谓语代词谓语我谓语我谓语我动词直接宾语我动词直接宾语我是直接宾语我是直接宾语我是名词我是名词 我是大学生我是大学生 5“我是大学生我是大学生”的构成符合上述规则，而的构成符合上述规则，而“我大我大学生是学生是”不符合上述规则，我们说它不是句不符合上述规则，我们说它不是句子。这些规则成为我们子。这些规则成为我们判别句子结构合判别句子结构合法与否的依据法与否的依据，换句话说，这些规则看成，换句话说，这些规则看成是一种是一种元语言元语言，用它描述汉语。这里仅仅，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述涉及汉语句子的结构描述。其中一种描述元语言称为文法。元语言称为文法。注注:用于用于产生产生其他语言的语言称为元语言。其他语言的语言称为元语言。63.2 编译原理所涉及到的一些数学概念和运算编译原理所涉及到的一些数学概念和运算v 集合集合v 笛卡儿乘积笛卡儿乘积v 关系关系v 符号串符号串73.2.1 集合集合v 概念概念v 表示法：（表示法：（1）枚举法：枚举法：1,2,3 （2）谓词法：）谓词法：x|x-32v 特性：特性：（1）唯一性）唯一性 （2）确定性）确定性v 集合间的关系：相等、不相等、子集集合间的关系：相等、不相等、子集v 集合的运算：并集、交集、差集、幂集集合的运算：并集、交集、差集、幂集83.2.2 笛卡儿乘积笛卡儿乘积v 序偶：由两个按一定次序排列的客体组序偶：由两个按一定次序排列的客体组成的序列，记为（成的序列，记为（x，y）v n重序组：由重序组：由n个按一定次序排列的客个按一定次序排列的客体组成的序列，记为（体组成的序列，记为（x1 1，x2 2，xn n）v 笛卡儿乘积：笛卡儿乘积：A、B为任意两个集合，为任意两个集合，若序偶的第一个成员是集合若序偶的第一个成员是集合A的一个元素，的一个元素，第二个成员是集合第二个成员是集合B的一个元素，则所有的一个元素，则所有这样的序偶组成的集合称为集合这样的序偶组成的集合称为集合A和和B的的笛卡儿乘积。笛卡儿乘积。93.2.3 关系关系v 定义定义定义定义v 关系矩阵和关系图关系矩阵和关系图关系矩阵和关系图关系矩阵和关系图v 关系的基本性质关系的基本性质关系的基本性质关系的基本性质1 1、自反、自反、自反、自反2 2、非自反、非自反、非自反、非自反3 3、对称、对称、对称、对称4 4、非对称、非对称、非对称、非对称5 5、传递、传递、传递、传递v 关系的乘积关系的乘积关系的乘积关系的乘积v 关系的传递闭包关系的传递闭包关系的传递闭包关系的传递闭包v 自反传递闭包自反传递闭包自反传递闭包自反传递闭包103.3 有关定义和记号有关定义和记号符号：可以相互区别的记号（元素）。符号：可以相互区别的记号（元素）。字母表字母表：符号（元素）的非空有穷集合。：符号（元素）的非空有穷集合。符号串：由字母表符号串：由字母表 中的符号组成的任何有穷序中的符号组成的任何有穷序列称为该字母表上的符号串。列称为该字母表上的符号串。1.空符号串空符号串(没没有有符号的符号串符号的符号串)是是 上的符号串上的符号串 2.若若x是是 上上的符号串的符号串,a是是 的元素的元素,则则xa是是 上的符号串上的符号串 3.y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由1和和2导出。导出。例如：例如：=a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba都都是是 上的符号串上的符号串11介绍有关符号串的一些运算介绍有关符号串的一些运算 符号串的头符号串的头,尾，固有头和固有尾尾，固有头和固有尾：如果：如果z=xy是是一符号串，那么一符号串，那么x是是z的头，的头，y是是z的尾，如果的尾，如果x是非空的，那么是非空的，那么y是固有尾；同样如果是固有尾；同样如果y非空，非空，那么那么x是固有头。举个例子是固有头。举个例子:设设z=abc,那么那么z的的头是头是,a,ab,abc,除除abc外，其它都是固有头；外，其它都是固有头；z的尾是的尾是,c,bc,abc,z的固有尾是的固有尾是,c,bc。当对符号串当对符号串z=xy的头感兴趣而对其余部分不感的头感兴趣而对其余部分不感兴趣时，采用省略写法：兴趣时，采用省略写法：z=x；如果只是为了强调如果只是为了强调x在符号串在符号串z中的某处出现，中的某处出现，则可表示为：则可表示为：z=x；符号；符号t是符号串是符号串z的第的第一个符号，则表示为一个符号，则表示为z=t。12符号串的连接符号串的连接：设：设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符号写在的符号写在x的符号之后得到的符号串的符号之后得到的符号串.由由于于 的含义，显然有的含义，显然有 x=x =x。例如例如 x=ST，y=abu，则它们的连接，则它们的连接xy=STabu，看出，看出x=2，y=3，xy=5符号串的符号串的方幂方幂：符号串自身连接：符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaa n aaaa n个个a aa a1 1=a,a=a,a2 2=aa=aa且且a a0 0=例；若例；若x=AB 则则:x0=x1=AB x2=ABAB x3=ABABAB xn=xxn-1=xn-1 x (n0)13符号串集合：若集合符号串集合：若集合A中所有元素都是某字母表中所有元素都是某字母表 上上的符号串，则称的符号串，则称A为字母表为字母表 上的符号串集合。上的符号串集合。两个符号串集合两个符号串集合A和和B的乘积定义为的乘积定义为 AB=xy|xxy|x A A且且y y B B 若若 集合集合A=ab,cdeab,cde B=0,10,1 则则 AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 使用使用 *表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集）组成的集合。合。*称为称为的闭包的闭包。上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为+。+称为称为的正闭包的正闭包。14例：例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,15有关定义和记号有关定义和记号语言语言语言语言是由句子组成的集合，是由一组符号所构成的集合。换言是由句子组成的集合，是由一组符号所构成的集合。换言是由句子组成的集合，是由一组符号所构成的集合。换言是由句子组成的集合，是由一组符号所构成的集合。换言之之之之,字母表字母表字母表字母表 上上上上的一个语言是的一个语言是的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合上的一些符号串的集合上的一些符号串的集合 (字母表字母表字母表字母表 上上上上的每个语言是的每个语言是的每个语言是的每个语言是 *的一个子集的一个子集的一个子集的一个子集)。例如：例如：例如：例如：字母表字母表字母表字母表=a,b=a,b=a,b=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,集合集合集合集合ab,aabb,aaabbb,aab,aabb,aaabbb,aab,aabb,aaabbb,aab,aabb,aaabbb,an n n nb b b bn n n n,或表示为或表示为或表示为或表示为w|ww|ww|ww|w*且且且且w=aw=aw=aw=an n n nb b b bn n n n,n1,n1,n1,n1为为为为字母表字母表字母表字母表 上上上上的一个语言。的一个语言。的一个语言。的一个语言。集合集合集合集合a,aa,aaa,a,aa,aaa,a,aa,aaa,a,aa,aaa,或或或或表示为表示为表示为表示为w|ww|ww|ww|w*且且且且w=aw=aw=aw=an n n n,n1,n1,n1,n1 为为为为字母表字母表字母表字母表 上上上上的一个语的一个语的一个语的一个语言。言。言。言。是一个语言。是一个语言。是一个语言。是一个语言。即即即即 是一个语言。是一个语言。是一个语言。是一个语言。163.4文法和语言的形式定义文法和语言的形式定义语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系语言概述语言概述17程序设计语言的概念和描述方法程序设计语言的概念和描述方法v 程序设计语言是形式语言，其定义和描述程序设计语言是形式语言，其定义和描述包括语法、语义和语用三个方面。包括语法、语义和语用三个方面。v程序设计语言的语法实际上是一组规则。程序设计语言的语法实际上是一组规则。v 程序设计语言的语句可分为两大类：程序设计语言的语句可分为两大类：1、非执行语句、非执行语句2、可执行语句、可执行语句v 描述程序程序设计语言的语法规则的有效描述程序程序设计语言的语法规则的有效工具是文法中的上下文无关文法。工具是文法中的上下文无关文法。18语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics语法语法-表示构成语言句子的各个记号之间的表示构成语言句子的各个记号之间的组合规律，即句子的组成结构。组合规律，即句子的组成结构。语义语义-表示各个记号的特定含义。（各个记表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）号和记号所表示的对象之间的关系）语用语用-表示在各个记号所出现的行为中，它表示在各个记号所出现的行为中，它们的来源、使用和影响。们的来源、使用和影响。编译原理只讨编译原理只讨论语言的语法论语言的语法和语义和语义19每每种种语语言言具具有有两两个个可可识识别别的的特特性性，即即语语言言的的形式形式和该形式相关联的和该形式相关联的意义意义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽幽默默、双双关关语语和和谜谜语语就就是是利利用这两方面意义间的差异。用这两方面意义间的差异。20如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来来看看语语言言，这这种种意意义义下下的的语语言言称称作作形形式式语语言言。形形式式语语言言抽抽象象地地定定义义为为一一个个数数学学系系统统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只只以以什什麽麽符符号号串串能能出出现现的的方方式式来来陈陈述述。形形式式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究究。是是程程序序设设计计语语言言语语法法分分析析研研究的基础。究的基础。21文法和语言的形式定义文法和语言的形式定义如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：有穷表示有两个途经：生成方式生成方式（文法）：语言中的每个句子可以用严格（文法）：语言中的每个句子可以用严格定义的规则来构造。定义的规则来构造。识别方式识别方式（自动机）：用一个过程，当输入的一任（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止意串属于语言时，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要麽能停止并回答，若不属于，要麽能停止并回答“不不是是”，（要麽永远继续下去。），（要麽永远继续下去。）22文法即是生成方式描述语言的：语言文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构中的每个句子可以用严格定义的规则来构造造.下面给出文法的定义下面给出文法的定义.进而在进而在文法的定文法的定义的基础上，义的基础上，给出给出推导的概念，句型、句推导的概念，句型、句子和语言的定义。子和语言的定义。23定义定义文法文法文法文法GG定义为四元组定义为四元组定义为四元组定义为四元组(V VNN，V VT T，P P，S S)其中其中其中其中V VNN为非终结符号为非终结符号为非终结符号为非终结符号(或语法实体，或变量或语法实体，或变量或语法实体，或变量或语法实体，或变量)集；集；集；集；V VT T为终结符号集；为终结符号集；为终结符号集；为终结符号集；P P为产生式为产生式为产生式为产生式(也称规则也称规则也称规则也称规则)的集合；的集合；的集合；的集合；V VNN，V VT T和和和和P P是非空有是非空有是非空有是非空有穷集。穷集。穷集。穷集。S S称作识别符号或开始符号，它是一个非终结符，至称作识别符号或开始符号，它是一个非终结符，至称作识别符号或开始符号，它是一个非终结符，至称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。少要在一条产生式中作为左部出现。少要在一条产生式中作为左部出现。少要在一条产生式中作为左部出现。V VNN和和和和V VT T不含公共的元素，即不含公共的元素，即不含公共的元素，即不含公共的元素，即V VN N V VT T=用用用用V V表示表示表示表示V VN N V VT T，称为文法，称为文法，称为文法，称为文法GG的字母表或字汇表的字母表或字汇表的字母表或字汇表的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如规则，也称重写规则、产生式或生成式，是形如规则，也称重写规则、产生式或生成式，是形如规则，也称重写规则、产生式或生成式，是形如 或或或或 =的的的的(，)有序对，其中有序对，其中有序对，其中有序对，其中 是字母表是字母表是字母表是字母表V V的正闭的正闭的正闭的正闭包包包包V V+中的一个符号，中的一个符号，中的一个符号，中的一个符号，是是是是V V*中的一个符号。中的一个符号。中的一个符号。中的一个符号。称为规称为规称为规称为规则的左部，则的左部，则的左部，则的左部，称作规则的右部。称作规则的右部。称作规则的右部。称作规则的右部。24文法的定义文法的定义例例 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号25例例 文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,0,99 S=26文法的写法文法的写法 1 G 1 G：SaASaAb Aab Aab AaA AaAb A A 2 GS 2 GS：Aab AaA Aab AaAb A A SaSSaSb 3 GSGS：Aab|aAAab|aAb|SaS|SaSb27元元符号:=|习惯表示习惯表示 大写字母：终结符大写字母：终结符 小写字母：非终结符小写字母：非终结符S ABA Ax|yB z28推导的定义推导的定义直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=,v=,w=,其中其中VV*,V,V*则称则称v v直接直接推导推导到到w,w,记作记作 v v w w 也称也称w w直接直接归约归约到到v v例：例：G G：S0S1，S01 0S100S1100S11000S111000S11100001111 S 0S129.VAR;BEGINREAD()END.VARA;BEGINREAD()END.30推导的定义推导的定义若存在若存在vw0w1.wn=w,(n0)则记为则记为v=+w，v推导出推导出w，或，或w归约到归约到v若有若有v=+w，或，或v=w，则记为则记为v=*w31例：例：G G：S0S1，S010S100S1100S11000S111000S11100001111 S 0S100S11000S11100001111 S=+00001111 S=*S 00S11=*00S1132句型、句子的定义句型、句子的定义句型句型有文法有文法G，若，若S=*x，则称，则称x是文法是文法G的句型。的句型。句子句子有文法有文法G，若，若S=*x，且，且xVVT T*，则称，则称x是文法是文法G的句子。的句子。例：例：G G：S0S1，S01S 0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,0133例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式34文法，语言的定义文法，语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的的一切句子的集合一切句子的集合:L(G)=x|S=*x，其中，其中S为文法的开始为文法的开始符号，且符号，且x VVT T*例：例：G G：S0S1，S01L(G)=0n1n|n135例例 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL（G）=anbnen|n1 36S aSBE(SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成37使用产生式使用产生式(1)n-1次，得到推导序列：次，得到推导序列：S=*an-1S(BE)n-1，然后使用产生式，然后使用产生式(2)一次，得到：一次，得到：S=*an-1S(BE)n-1an(BE)n。然后从。然后从an(BE)n继续继续推导，总是对推导，总是对EB使用产生式使用产生式(3)的右部进行替换，的右部进行替换，而最终在得到的串中，所有的而最终在得到的串中，所有的B都先于所有的都先于所有的E。例如，若例如，若n=3,aaaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：。即有：S=*anBnEn接着，使用产生式接着，使用产生式(4)一次，得到一次，得到S=*anbBn-1En，然后使用产生式然后使用产生式(5)n-1次得到：次得到：S=*anbnEn，最后使用产生式，最后使用产生式(6)一次，使用产生式一次，使用产生式(7)n-1次，得到：次，得到：S=*anbnen也能证明，对于也能证明，对于n1，串，串anbnen是唯一形式的终结符是唯一形式的终结符号串号串38文法的等价文法的等价z若若L（G1）=L（G2），则称文法），则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等价等价 A01 S01 A01 S01 RA1 RA139文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将文法分将文法分为四种类型：为四种类型：0型文法型文法：对任一产生式：对任一产生式，都有，都有(V(VN NVVT T)+，(V(VN NVVT T)*1 1型文法型文法：对任一产生式对任一产生式，都有，都有|，仅仅仅仅 S S除外除外2 2型文法型文法：对任一产生式对任一产生式，都有，都有VVN N ，(V(VN NVVT T)*3 3型文法型文法：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T40文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCD SCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD C CBDbDBDbD D DAabDAabD41文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1423 3型文法型文法GS：S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d43文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法44文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（CFG ）产生的语言产生的语言称为称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）45根据形式语言理论根据形式语言理论,文法和识别系文法和识别系统间有这样的关系统间有这样的关系 0型文法（短语结构文法）的能力相当于型文法（短语结构文法）的能力相当于图图灵机灵机，可以表征任何递归可枚举集，而且，可以表征任何递归可枚举集，而且任何任何0型语言都是递归可枚举的型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形式为式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其识。其识别系统是别系统是线性界限自动机线性界限自动机。46带带a0a1a2a3a4a5a6a7a8an-1an有限控制器有限控制器磁头磁头任何能用图灵机描述的计算都能机械实现，任何能在现任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述代计算机上实现的计算都能用图灵机描述47 2型文法（上下文无关文法型文法（上下文无关文法CFG）：产生式）：产生式的形式为的形式为AA，取代取代A A时与时与A A的上下文无的上下文无关。其识别系统是关。其识别系统是不确定的下推自动不确定的下推自动机机。3型文法（正规文法型文法（正规文法RG）：产生的语言是）：产生的语言是有穷自动机有穷自动机（FA）所接受的集合）所接受的集合48上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的上下文无关文法有足够的能力描述程序设计语言的语法结构语法结构语法树语法树-句型推导句型推导的的直观表示直观表示49例文法例文法G=(E,+,*,i,(,),P,E)其中其中P为：为：Ei,EE+E,EE*E,E(E)E表示算术表达式表示算术表达式,i表示程序的表示程序的“变量变量”，该文法定义，该文法定义了由变量，了由变量，+，*,(和和)组成的算术表达式的语法结组成的算术表达式的语法结构，即：构，即：变量是算术表达式；若变量是算术表达式；若E1和和E2是算术表达式，则是算术表达式，则E1+E2，E1*E2和和(E1)也是算术表达式也是算术表达式描述一种简单赋值语句的产生式：描述一种简单赋值语句的产生式：赋值语句赋值语句i=E描述条件语句的产生式：描述条件语句的产生式：条件语句条件语句if条件条件then语句语句if条件条件then语句语句else语句语句50句型、推导GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aE EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aE EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a51规范推导规范推导规范句型规范句型最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中中的最左（右）非终结符进行替换的最左（右）非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型52语法树语法树设设G=(VN,VT,P,S)为一上下文无关文法，若一棵树满足为一上下文无关文法，若一棵树满足下列下列4个条件，则此树称作个条件，则此树称作G的语法树的语法树(推导树推导树)(派派生树）：生树）：1.每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号的一个符号2.根的标记是根的标记是S3.若一结点若一结点n至少有一个它自己除外的子孙，并且有至少有一个它自己除外的子孙，并且有标记标记A，则肯定，则肯定AVVN N4.如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次其直接子孙结点从左到右的次序是序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中的一个产生中的一个产生式式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成的行谓之句型。从左到右读出叶子的标记而构成的行谓之句型。53构造语法树构造语法树GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a E EE+T E +T T E E +T T F54E EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aE EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aE EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a E E E+T E+T T T*F T T*F F F a F F a a a a a 看不出句型中的符号被替代看不出句型中的符号被替代的顺序的顺序55上下文无关文法的语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法例例:GS:SaASASbAASSSaAbaSaASSbAaaba句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符号法符号串串，为，为GS的的句型句型。也把该推导树称。也把该推导树称为该为该句型句型的的语法树语法树。56上下文无关文法的语法树上下文无关文法的语法树z推导过程中推导过程中施用施用产生式产生式的的顺序顺序例例:GS:SaASASbAASSSaAbaSaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa57一棵一棵语语法法树树表示了一个句型的种种可能的表示了一个句型的种种可能的(但但未必是所有的未必是所有的)不同推不同推导过导过程，包括最左程，包括最左(最最右右)推推导导。但是，一个句型是否只。但是，一个句型是否只对应对应唯一唯一的一棵的一棵语语法法树树呢呢?一个句型是否只有唯一的一个句型是否只有唯一的一个最左一个最左(最右最右)推推导导呢呢?58例：例：GE:GE:E iE iE E+EE E+EE E*EE E*EE (E)E (E)E E E+E E+E E*E i E*E i i i i i E E E*E E*E i E+E i E+E i i i i句型句型i*i+i的两个不同的最左推导：的两个不同的最左推导：推导推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i59二义文法二义文法 若一个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是则称这个文法是二义二义的的或者，若一个文法存在某个句子有两个不同的最或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是左（右）推导，则称这个文法是二义二义的的 判定任给的一个上下文无关文法是否二义，判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件以为无二义性寻找一组充分条件 60文法的二义性和语言的二义性是两个不同的概念。因为可能文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法有两个不同的文法G G和和GG，其中，其中G G是二义的，但是却有是二义的，但是却有L(G)=L(G)L(G)=L(G)，也就是说，这两个文法所产生的语言是相同，也就是说，这两个文法所产生的语言是相同的。的。二义文法改造为无二义文法二义文法改造为无二义文法GE:E i GEGE:E i GE：E T|E+TE T|E+T E E+E T F|T*F E E+E T F|T*F E E*E F E E*E F （E E）|i|i E (E)E (E)规定优先顺序和结合律规定优先顺序和结合律 如果产生上下文无关语言的每一个文法都是二义的，则说如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。析是唯一的。61句型的分析句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法一个符号串是否为某文法的的句型句型，是某个，是某个推导推导的构造过程。的构造过程。在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程程序序称为称为分析程序分析程序或或识别程序识别程序。分析算法又。分析算法又称称识别算法识别算法。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识识别输入符号串别输入符号串，首先识别符号串中的，首先识别符号串中的最左最左符号，进而符号，进而依次识别右边依次识别右边的一个符号，的一个符号，直直到分析结束到分析结束。62句型的句型的分析算法分类分析算法分类分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文法的，反复使用文法的产生式，产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。63两种方法反映了两种语法树的构两种方法反映了两种语法树的构造过程。造过程。自上而下方法自上而下方法是从文法符号开始，将它做为语法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串果正好是输入符号串自下而上方法自下而上方法则是从输入符号串开始，以它做为则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树语法树的结果，自底向上地构造语法树64自上而下的语法分析自上而下的语法分析例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAdab推导过程：推导过程：ScAdcAdcabd65自下而上的语法分析自下而上的语法分析例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAAcabdcabdcabd规约规约过程构造的推导：过程构造的推导：cAdcabdScAd66(1)S cAd(2)A ab(3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子自上而下的语法分析自上而下的语法分析若S cAd 后选择(3)扩展A，S cAd cad那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即c