第03章文法和语言.ppt

第03章文法和语言现在学习的是第1页，共69页本章知识点本章知识点(内容内容)引言和预备知识引言和预备知识文法和语言的形式定义文法和语言的形式定义文法的类型文法的类型上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法的句型分析上下文无关文法的句型分析有关文法实用中的一些说明有关文法实用中的一些说明现在学习的是第2页，共69页3.1文法的直观概念和文法的直观概念和语言概述语言概述当我们表述一种语言时，无非是说明这种语言的句当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明以给出一些规则，用这些规则来说明(或者定义或者定义)句子的句子的组成结构。组成结构。现在学习的是第3页，共69页“我是大学生我是大学生”。是汉语的一个句子是汉语的一个句子句子句子=主语主语谓语谓语主语主语=代词代词名词名词代词代词=我我你你他他名词名词=王明王明大学生大学生工人工人英语英语谓语谓语=动词动词直接宾语直接宾语动词动词=是是学习学习直接宾语直接宾语=代词代词名词名词有了一组规则以后，有了一组规则以后，不断地用不断地用=的的右边代替左边右边代替左边，就可以导出句子。就可以导出句子。现在学习的是第4页，共69页“我是大学生我是大学生”的构成符合上述规则，而的构成符合上述规则，而“我大学生是我大学生是”不符合上述规则，我们说它不符合上述规则，我们说它不是句子。不是句子。这些规则成为我们判别句子结构合法与否这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。一种描述元语言称为文法。现在学习的是第5页，共69页语语 言言 概概 述述语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 语法语法 Syntax语言研究的三个方面语言研究的三个方面 语义语义 Semantics 语用语用 Pragmatics现在学习的是第6页，共69页如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来来看看语语言言，这这种意义下的语言称作形式语言。种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。形式语言抽象地定义为一个数学系统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只只以以什什么么符号串能出现的方式来陈述。符号串能出现的方式来陈述。形形式式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究。究。是程序设计语言语法分析研究的基础。是程序设计语言语法分析研究的基础。现在学习的是第7页，共69页3.2 有关定义和记号的回顾有关定义和记号的回顾符号和符号串符号和符号串符号：符号：可以相互区别的记号（元素）。可以相互区别的记号（元素）。字母表字母表：符号（元素）的非空有穷集合（符号集）。符号（元素）的非空有穷集合（符号集）。符号串：符号串：由字母表由字母表 中的符号组成的任何有穷序列称为该字母表上的符号中的符号组成的任何有穷序列称为该字母表上的符号串。串。1.空符号串空符号串(没有没有符号的符号串符号的符号串)是是 上的符号串上的符号串 2.若若x是是 上的符号串，上的符号串，a是是 的元素，则的元素，则xa是是 上的符号串上的符号串 3.y是是 上的符号串，当且仅当它可以由上的符号串，当且仅当它可以由1和和2导出。导出。例如：例如：=a,b=a,b ,a,b,aa,ab,aabba ,a,b,aa,ab,aabba都都是是 上的符号串上的符号串现在学习的是第8页，共69页 符号串符号串s的头（前缀）：的头（前缀）：移走符号串移走符号串s尾部的零个或多于零个符号尾部的零个或多于零个符号得到的符号串。得到的符号串。如：如：b是符号串是符号串banana的一个前缀。的一个前缀。符号串符号串s的尾（后缀）：的尾（后缀）：删去符号串删去符号串s头部的零个或多于零个符号得头部的零个或多于零个符号得到的符号串。到的符号串。如如:nana是符号串是符号串banana的一个后缀。的一个后缀。符号串符号串s的子串：的子串：从从s中删去一个前缀和一个后缀得到的符号串。中删去一个前缀和一个后缀得到的符号串。如如:ana是符号串是符号串banana的一个子串。的一个子串。现在学习的是第9页，共69页对于每个符号串对于每个符号串s，s和和两者两者都都是符号串是符号串s的前缀，后缀和子串。的前缀，后缀和子串。符号串符号串s的真前缀，真后缀，真子串：的真前缀，真后缀，真子串：任何非空符号串任何非空符号串 x,相应地，相应地，是是s的前缀，后缀或子串，并且的前缀，后缀或子串，并且 s x 符号串的运算符号串的运算符号串的长度：符号串的长度：符号串中符号的个数符号串中符号的个数.符号串符号串s的长度记为的长度记为|s|。的长度为的长度为0连接：连接：符号串符号串x x、y y的连接的连接,是把是把y y的符号写在的符号写在x x的符号之后得到的符号之后得到的符号串的符号串xy xy 如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcd xy=abcd 有有a=a a=a 方幂：方幂：符号串自身连接符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaaaa naa n个个a a的连接的连接 a a1 1=a,a=a,a2 2=aa=aa则则a a0 0=现在学习的是第10页，共69页符号串集合符号串集合：若集合若集合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 使用使用 *表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合。）组成的集合。*称为称为的闭包的闭包。上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为+。+称为称为的正闭包的正闭包。现在学习的是第11页，共69页例：例：=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,现在学习的是第12页，共69页有关定义和记号有关定义和记号语言语言是由句子组成的集合，是由一组符号所构成的集合。换言是由句子组成的集合，是由一组符号所构成的集合。换言之，字母表之，字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合 (字母表字母表 上上的每个语言是的每个语言是*的一个子集的一个子集)。例如：例如：字母表字母表=a,b,=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,集合集合ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n,或表示为或表示为w|ww|w*且且w=aw=an nb bn n,n1,n1为为字母表字母表 上上的一个语言。的一个语言。集合集合a,aa,aaa,a,aa,aaa,或或表示为表示为w|ww|w*且且w=aw=an n,n1,n1 为为字母表字母表 上上的一个语言。的一个语言。是一个语言。是一个语言。即即 是一个语言。是一个语言。现在学习的是第13页，共69页语言语言上上的有关运算的有关运算 设设L是（是（上的）一个语言，上的）一个语言，M是（是（上的）一个语言，上的）一个语言，语言语言L和和M的并，交，差，补的并，交，差，补是一个语言。是一个语言。语言语言L和和M的并为的并为 L M，是一个语言是一个语言:w|w is in L or is in w|w is in L or is in M M 如：如：L1=a,b,=a,b,y,z My,z M1 1=0,1,2=0,1,28,9 8,9 L1 M1 1=a,b,=a,b,y,z y,z，0,1,20,1,28,9 8,9 语言语言L和和M的连接的连接是一个语言，记是一个语言，记为为 LM LM=st|sst|sL且且 t tM 如：如：L1M1=a1,b1,=a1,b1,y1,z0,z1,a2,b2y1,z0,z1,a2,b2a9a9z9 z9 有有L =L=L。L的的n次连接次连接Ln=LL.L 现在学习的是第14页，共69页 语言语言L的的 闭包闭包记记为为 L*，L*=L0 L1 L2 L0=Ln=L Ln-1=Ln-1 L，n 1 语言语言L的正的正 闭包闭包记记为为 L+L+=L1 L2 L3.L*=L+如：如：L1 =a,b,=a,b,y,zy,z，M M1 1=0,1,2=0,1,28,9 8,9 （L1 M1 1）=a,b,=a,b,y,z y,z，0,1,20,1,28,98,9 （L1 M1 1）*=a,b,=a,b,y,z,0,1,2 y,z,0,1,28,9,8,9,aa,0a,xyz,6789st.L1（L1 M1 1）*=所有字母打头的字母和数字符号串所有字母打头的字母和数字符号串 现在学习的是第15页，共69页3.3 文法和语言的形式定义文法和语言的形式定义一、如何来描述一种语言一、如何来描述一种语言如果语言是如果语言是有穷有穷的（只含有有穷多个句子），可以将句子逐一列出的（只含有有穷多个句子），可以将句子逐一列出来表示来表示如果语言是如果语言是无穷无穷的，找出语言的有穷表示。语言的有穷表示有两个途的，找出语言的有穷表示。语言的有穷表示有两个途经：经：1.1.生成方式生成方式 （文（文法）法）：语言中的每个句子可以用严格定义的规则来构造。语言中的每个句子可以用严格定义的规则来构造。2.2.识别方式识别方式（自动机）（自动机）：用一个过程，当输入的一任意串属于用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答语言时，该过程经有限次计算后就会停止并回答“是是”，若不，若不属于，要么能停止并回答属于，要么能停止并回答“不是不是”，（要么永远继续下去。），（要么永远继续下去。）什么现在学习的是第16页，共69页文法即是用生成方式描述语言的：文法即是用生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义，进而在下面给出文法的定义，进而在文法的定义的基础上，文法的定义的基础上，给给出出推导的概念，句型、句子和语言的定义。推导的概念，句型、句子和语言的定义。现在学习的是第17页，共69页二、文法的定义二、文法的定义文法文法G定义为四元组定义为四元组(VN，VT，P，S)其中：其中：VN为非终结符号为非终结符号(或语法实体，或变量或语法实体，或变量)集；集；VT为终结符号集；为终结符号集；P为产生式为产生式(也称规则也称规则)的集合；的集合；VN，VT和和P是是非空有穷集。非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。中作为左部出现。VN和和VT不含公共的元素，即不含公共的元素，即VN VT=用用V表示表示VN VT，称为文法，称为文法G的字母表或字汇表。的字母表或字汇表。规则规则，也称重写规则、产生式或生成式，是形如，也称重写规则、产生式或生成式，是形如或或=的的(，)有序对，其中有序对，其中是字母表是字母表V的正闭包的正闭包V+中的一个符号，且中的一个符号，且至少至少包含一个非终结符包含一个非终结符;是是V*中的一个符号。中的一个符号。称为规则的左部，称为规则的左部，称称作规则的右部。作规则的右部。现在学习的是第18页，共69页例：例：文法文法G=（VN，VT，P，S）VN=S VT=0,1 P=S0S1，S01 S为开始符号为开始符号现在学习的是第19页，共69页例：例：文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,0,99 S=现在学习的是第20页，共69页三、文法的写法三、文法的写法 1.G1.G：SaASaAb Aab Aab AaA AaAb A A 2.GS 2.GS：SaASaAb Aab AaA Aab AaAb A A 3.3.GSGS：SaASaAb Aab|aA Aab|aAb|一般用写法一般用写法 3 3现在学习的是第21页，共69页元符号元符号:=|习惯表示习惯表示 大写字母：大写字母：非终结符非终结符 小写字母：小写字母：终结符终结符如：如：S AB A Ax|y B z现在学习的是第22页，共69页四、四、直接推导、推导的定义直接推导、推导的定义1.直接推导直接推导 是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=,v=,w=,其中其中VV*,V,V*则称则称v v直接推导直接推导到到w,w,也称也称w w是是v v的直接推导，的直接推导，记作记作 v v w w 也称也称w w直接归约直接归约到到v v例：例：GSGS：S0S1，S01 0S100S1100S11000S111000S11100001111 S 0S1现在学习的是第23页，共69页 +*2.推导推导:若存在若存在vw0w1.wn=w,(n0)则记为则记为v=w，称，称v推导出推导出w，或，或w归约到归约到v若有若有v=w，或，或v=w，则记为则记为v=w+*现在学习的是第24页，共69页例：例：GSGS：S0S1，S01S0S10S100S1100S11000S111000S11100001111 S 0S100S11000S11100001111 S=00001111 S=S 00S11=00S11+*现在学习的是第25页，共69页五、句型、句子的定义五、句型、句子的定义1.句型句型 有文法有文法G，若，若S=x，则称，则称x是文法是文法G的句型。的句型。即：即：从开始符号推导出的任意符号串。从开始符号推导出的任意符号串。2.句子句子 有文法有文法G，若，若S=x，且，且xVVT T*，则称，则称x是文法是文法G的句子。的句子。即：即：从开始符号推导出的终结符号串。从开始符号推导出的终结符号串。例：例：G G：S0S1，S01 S 0S100S11000S11100001111S 01 G的的句型句型有：有：S，0S1，00S11，000S111，00001111，01 G的的句子句子有：有：00001111,01*现在学习的是第26页，共69页例：例：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，+，*，(和和)构成的算术表达式构成的算术表达式现在学习的是第27页，共69页六、语言的定义六、语言的定义由文法由文法G生成的生成的语言语言记为记为L(G)，它是文法，它是文法G的的一切句子的集合一切句子的集合:L(G)=x|S=x，其中，其中S为文法的开始符为文法的开始符号，且号，且x VVT T*例：例：GS：S0S1，S01 L(G)=0n1n|n1*现在学习的是第28页，共69页七、七、文法的等价文法的等价若若L（G1）=L（G2），则称文法），则称文法G1和和G2是等价的。是等价的。如文法如文法G G1AA：A0R A0R 与与 G G2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1现在学习的是第29页，共69页3.4 文法的类型文法的类型 通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky(乔姆斯基）乔姆斯基）将文法分为四种类型：将文法分为四种类型：0型文法（短语文法）型文法（短语文法）：对任一产生式：对任一产生式，都，都有有(V(VN NVVT T)+，且至少含有一个非终结符，且至少含有一个非终结符，(V(VN NVVT T)*1 1型文法（上下文有关文法）型文法（上下文有关文法）：对任一产生式对任一产生式，都有，都有|，仅仅仅仅 SS除外除外 现在学习的是第30页，共69页文法的类型文法的类型(续续)2 2型文法（上下文无关文法）型文法（上下文无关文法）：对任一产对任一产生式生式，都有，都有VVN N ，(V(VN NVVT T)*3 3型文法（正规文法）型文法（正规文法）：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T现在学习的是第31页，共69页文法的类型举例文法的类型举例例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCDSCDAbAaAbAa CaCA CaCABaBABaBA CbCB CbCBBbAbBbAbADaDADaD Ca CaBDbDBDbD Da DaAaDaAaDa现在学习的是第32页，共69页文法的类型举例文法的类型举例例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1现在学习的是第33页，共69页文法的类型举例文法的类型举例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 d例：例：3 3型文法（正规文法）型文法（正规文法）现在学习的是第34页，共69页四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系2型文法型文法1型文法型文法0型文法型文法3型文法型文法现在学习的是第35页，共69页文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语言称为产生的语言称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法型文法或上下文无关文法（CFG ）产生的语言称为产生的语言称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）3 3型文法或正则（正规）文法型文法或正则（正规）文法（RG）产生的语言称为产生的语言称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）四种文法之间的关系四种文法之间的关系 是将产生式做进一步限制而定义的。是将产生式做进一步限制而定义的。现在学习的是第36页，共69页根据形式语言理论根据形式语言理论,文法和自动机（识别文法和自动机（识别系统）间有这样的关系系统）间有这样的关系 0型文法型文法（短语结构文法）的能力相当于（短语结构文法）的能力相当于图灵机图灵机，可以，可以表征任何递归可枚举集，而且任何表征任何递归可枚举集，而且任何0型语言都是递归型语言都是递归可枚举的可枚举的 1型文法型文法（上下文有关文法）：产生式的形式为（上下文有关文法）：产生式的形式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上下文中的上下文中时，才允许时，才允许取代取代A A。其识别系统是。其识别系统是线性界限自动机线性界限自动机。现在学习的是第37页，共69页带带a0a1a2a3a4a5a6a7a8an-1an有限控制器有限控制器磁头磁头任何能用任何能用图灵机图灵机描述的计算都能机械实现，任何描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述能在现代计算机上实现的计算都能用图灵机描述现在学习的是第38页，共69页 2型文法型文法（上下文无关文法（上下文无关文法CFG）：产生式的形式为）：产生式的形式为AA，取代取代A A时与时与A A的上下文无关。其识别系统是的上下文无关。其识别系统是不确定的不确定的下推自动机下推自动机。3型文法型文法（正规文法（正规文法RG）：产生的语言是有）：产生的语言是有穷自动机穷自动机（FA）所接受的集合）所接受的集合现在学习的是第39页，共69页3.5 上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构上下文无关文法有足够的能力描述程序设计语言的语法结构语法树语法树-句型推导句型推导的的直观表示直观表示现在学习的是第40页，共69页一、句型、推导一、句型、推导GE：EE+T|TTT*F|FF(E)|iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iEE+TT+TT+T*FF+T*FF+F*Fi+F*Fi+F*ii+i*i现在学习的是第41页，共69页规范推导规范推导规范句型规范句型最左（最右）推导：最左（最右）推导：在推导的任何一步在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中的最左（右）非终结符进行中的最左（右）非终结符进行替换替换最右推导被称为最右推导被称为规范推导规范推导。由规范推导所得的句型称为由规范推导所得的句型称为规范句型规范句型现在学习的是第42页，共69页二、语二、语法法树树设设G=(VN,VT,P,S)为一为一CFG，若一棵树满足下列，若一棵树满足下列4个条件，则此个条件，则此树称作树称作G的语法树的语法树(推导树推导树)(派生树）：派生树）：1.每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号的一个符号2.根的标记是根的标记是S3.若一结点若一结点n至少有一个它自己除外的子孙，并且有标记至少有一个它自己除外的子孙，并且有标记A，则肯定，则肯定AVVN N4.如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次序是其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一一定是定是P中的一个产生式中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行谓之语法树的结果：从左到右读出叶子的标记而构成的行谓之现在学习的是第43页，共69页语法树语法树-句型推导句型推导的的直观表示直观表示给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何句型都能构造与之的任何句型都能构造与之关联的语法树关联的语法树(推导树推导树)定理：定理：G为上下文无关文法，为上下文无关文法，对于对于，有，有S=，当且仅当，当且仅当文法文法G有以有以为结果的一棵语法树为结果的一棵语法树(推导树推导树)*现在学习的是第44页，共69页构造语法树构造语法树GE：EE+T|TTT*F|FF(E)|iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i E EE+T E +T T E E +T T F现在学习的是第45页，共69页E EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i(最最左推导左推导)E EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i(最右最右推导推导)E EE+TT+TT+T*FF+T*FF+F*Fi+F*Fi+F*ii+i*i E E E+T E+T T T*F T T*F F F i F F i i i i i 看不出句型中的符号被替代的顺序看不出句型中的符号被替代的顺序现在学习的是第46页，共69页上下文无关文法的语法树的用处上下文无关文法的语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法例例:GS:SaASASbAASSSaAbaSaASSbAaaba句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符号法符号串串，为，为GS的的句型句型。也把该推导树称为该。也把该推导树称为该句型句型的的语语法树法树。现在学习的是第47页，共69页上下文无关文法的语法树上下文无关文法的语法树z推导过程中推导过程中施用施用产生式产生式的的顺序顺序例例:GS:SaASASbAASSSaAbaSaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa现在学习的是第48页，共69页一棵一棵语语法法树树表示了一个句型的种种可能的表示了一个句型的种种可能的(但但未必是所有的未必是所有的)不同推不同推导过导过程，包括最左程，包括最左(最右最右)推推导导。但是，一个句型是否只但是，一个句型是否只对应对应唯一的一棵唯一的一棵语语法法树树呢呢?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左(最右最右)推推导导呢呢?现在学习的是第49页，共69页例：例：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+i现在学习的是第50页，共69页三、二义文法三、二义文法 若一个文法存在某个句子对应两棵不同的语法树，则称这个若一个文法存在某个句子对应两棵不同的语法树，则称这个文法文法是二义是二义的的或者，若一个文法存在某个句子有两个不同的最左（右）推导，或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个则称这个文法是二义文法是二义的的 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件，如：规定运算符的优先顺序和结合规则。义性寻找一组充分条件，如：规定运算符的优先顺序和结合规则。现在学习的是第51页，共69页文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法同的文法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)规定优先顺序和结合律规定优先顺序和结合律z如果产生上下文无关语言的每一个文法都是二义的，则说此语言是如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。二义的，因为希望对它的每个语句的分析是唯一的。现在学习的是第52页，共69页3.6 句型的分析句型的分析一、有关概念一、有关概念1.句型分析句型分析句型分析就是识别一个符号串是否为某文法的句句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。型，是某个推导的构造过程。2.分析程序分析程序在语言的编译实现中，把完成句型分析的程序称为在语言的编译实现中，把完成句型分析的程序称为分分析程序析程序或或识别程序识别程序。分析算法又称。分析算法又称识别算法识别算法。3.从左到右的分析算法从左到右的分析算法从左到右的分析算法从左到右的分析算法，即总是从左到右地识，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。个符号，直到分析结束。现在学习的是第53页，共69页二、句型的分析算法分类二、句型的分析算法分类分析算法可分为分析算法可分为2类：类：1.自顶向下自顶向下(自上而下自上而下)分析法：分析法：从文法的开始符号出发，反复使用文法的产生式，从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的寻找与输入符号串匹配的推导推导。2.自底向上自底向上(自下而上自下而上)分析法：分析法：从输入符号串开始，逐步进行从输入符号串开始，逐步进行归约归约，直至归约到文，直至归约到文法的开始符号。法的开始符号。现在学习的是第54页，共69页两种方法反映了两种语法树的构造过程两种方法反映了两种语法树的构造过程自顶向下方法自顶向下方法是从文法符号开始，将它做为语是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串；结果正好是输入符号串；自底向上方法自底向上方法则是从输入符号串开始，以它做则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树。为语法树的结果，自底向上地构造语法树。现在学习的是第55页，共69页自顶向下的语法分析自顶向下的语法分析-例例例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAdab推导过程：推导过程：ScAdcAdcabd现在学习的是第56页，共69页自底向上的语法分析自底向上的语法分析-例例例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAAcabdcabdcabd规约规约过程构造的推导：过程构造的推导：cAdcabdScAd现在学习的是第57页，共69页(1)S cAd(2)A ab(3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子1.1.自顶向下的语法分析自顶向下的语法分析若若S cAd 后选择后选择(3)扩展扩展A，S cAd cad ，那将会？那将会？w的第二个符号可以与叶子结点的第二个符号可以与叶子结点a得以匹配，但第三个符得以匹配，但第三个符号却不能与下一叶子结点号却不能与下一叶子结点d匹配匹配？宣告分析失败（其意味着，识别程序不能为串？宣告分析失败（其意味着，识别程序不能为串cad构造语构造语法树，即法树，即cad不是句子）不是句子）-显然是错误的结论。显然是错误的结论。导致失败的原因是在分析中对导致失败的原因是在分析中对A的选择不是正确的。的选择不是正确的。S c A d a现在学习的是第58页，共69页对串对串cabd的分析中，如果不是选择的分析中，如果不是选择ab用产生式用产生式(2),而是选择而是选择a用产用产生式生式(3)将将a归约到了归约到了A，那么最，那么最终就达不到归约到终就达不到归约到S的结果，的结果，因而也无从知道因而也无从知道cabd是一个句是一个句子。子。c a b d c A b d a(1)S cAd(2)A ab(3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子2.2.自底向上的语法分析自底向上的语法分析现在学习的是第59页，共69页三、句型分析的有关问题三、句型分析的有关问题1.在自顶向下的分析方法中在自顶向下的分析方法中如何如何选择选择使用使用哪个哪个产生式进行产生式进行推导推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条规则：条规则：BA1|A2|An，那么如何确定用哪个右部去替代，那么如何确定用哪个右部去替代B？2.在自底向上的分析方法中在自底向上的分析方法中如何如何识别可归约的串识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择选择一个一个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可可归约串归约串”现在学习的是第60页，共69页四、四、刻画刻画“可归约串可归约串”文法文法GS1.句型的短语句型的短语S=A且且A=，则称则称是是句型句型相对于相对于非终结符非终结符A的的短语。短语。2.句型的直接短语句型的直接短语(或简单短语或简单短语)若有若有A，则称则称是句型是句型相对于非终结符相对于非终结符A的的直接短语。直接短语。3.句型的句柄句型的句柄一个句型的一个句型的最左直接短语最左直接短语称为称为该句型该句型的的句柄。句柄。*+现在学习的是第61页，共69页例例i*i+ii*i+i例例 ：i*i+i i*i+i 的短语、直接短语和句柄的短语、直接短语和句柄 E E +T T FT *F i3 短语短语：i1*i2+i3，i1*i2，F i2i1，i2，i3。i1直接短语直接短语：i1，i2，i3。句柄句柄：i1GEGE：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|i F(E)|i句型：句型：i*i+ii*i+i现在学习的是第62页，共69页3.7 文法实用中的一些说明文法实用中的一些说明-化简文法化简文法一、文法中不含有害规则和多余规则一、文法中不含有害规则和多余规则1.有害规则：有害规则：形如形如PP的产生式。会引起文法的二义性。的产生式。会引起文法的二义性。2.多余规则：多余规则：指文法中任何句子的推导都不会用到的规则。指文法中任何句子的推导都不会用到的规则。文法中不含有文法中不含有不可到达不可到达和和不可终止不可终止的非终结符。的非终结符。3.不可到达：不可到达：文法中某些非终结符不在任何规则的右部出现，该非终文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。结符称为不可到达。4.不可终止不可终止:文法中某些非终结符，由它不能推出终结符号串，该非文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。终结符称为不可终止。现在学习的是第63页，共69页二、不含多余非终结符的条件二、不含多余非终结符的条件对于文法对于文法GS，为了保证任一非终结符，为了保证任一非终结符A在句子推导中在句子推导中出现，必须满足如下两个条件：出现，必须满足如下两个条件：1.A必须在某句型中出现必须在某句型中出现即有即有S=A，其中，其中，属于属于V V*2.必须能够从必须能够从A推出终结符号串推出终结符号串t来来即即A=t，其中，其中tVT*现在学习的是第64页，共69页三、三、化简文法化简文法例例例：例：GS：1)SBe2)BCeD为不可到达为不可到达3)BAfC为不可终止为不可终止4)AAe5)Ae6)CCf7)Df产生式产生式2），），6），），7）为）为多余规则，多余规则，应去应去掉。掉。现在学习的是第65页，共69页四、四、上下文无关文法中