chapter2文法和语言.ppt

文法和语言,教学目的: 使学生了解文法基本概念、文法类型，掌握文法和语言的形式定义，学会用语法树进行句型分析。 教学重点：文法和语言的形式定义，句型分析。,本章知识点(内容),文法的直观概念,符号和符号串,文法和语言的形式定义,文法的类型,上下文无关文法及其语法树,句型的分析,有关文法实用中的一些说明,1、语言：是由句子组成的集合，是由一组符号所构成的集合。 2、汉语：所有符合汉语语法的句子的全体。 3、英语：所有符合英语语法的句子的全体。 4、程序设计语言：所有该语言的程序的全体。 每个句子构成的规律 研究语言 每个句子的含义 每个句子和使用者的关系,文法的直观概念,当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则。,巴科斯范式：巴科斯范式(BNF: Backus-Naur Form 的缩写)是由 John Backus 和 Peter Naur 首先引入的用来描述计算机语言语法的符号集。现在，几乎每一位新编程语言书籍的作者都使用巴科斯范式来定义编程语言的语法规则。,EBNF(扩充BNF)描述符,“我是大学生”是汉语的一个句子,句子=主语谓语 主语=代词名词 代词=我你他 名词=王明大学生工人英语 谓语=动词直接宾语 动词=是学习 直接宾语=代词名词,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成： 句子 主语谓语， 然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词， 那么得到：主语谓语 代词谓语， 重复做下去， 句子：“我是大学生”的全部动作过程是： 句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子，这些规则就是我们判别句子结构合法与否的依据，可以将这些规则看成是一种元语言，用它描述汉语。,文法：就是这样一些规则的有穷集合，它是以有穷规则集来刻划无穷句子集合的工具。,字母表：元素的非空有穷集，记为 ，语言的字母表是由字母、数字、若干专用符号及保留字组成，是符号（元素）的非空有穷集合。 符号：字母表中的元素。 符号串：由字母表中的符号组成的任何有穷序列 空符号串：什么符号也不含的符号串，记为 。 例： =a,b,c,d,z。a、b、c都称为符号。hello、stri、aezfg、main、fjfka都是上的符号串。 符号串的长度：符号所包含符号的个数，设x是一符号串，其长度记为|x|。 例：|hello|=5,|main|=4,| |=0。,符号和符号串,符号串的运算 1、符号串的长度：符号串中符号的个数。符号串s的长度记为|s|。 的长度为0 2、连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a = a 3、方幂：符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a, a2=aa则a0=,4、符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 5、两个符号串集合A和B的乘积定义为 AB =xy|xA且yB,【例】若 集合A=ab,cde B = 0,1 则 AB =ab1,ab0,cde0,cde1,规定 0 = . 令： * = 0 1 2 称 *是的闭包。 记 + = * -= 1 2 n , 称 +是的正则包。,使用 * 表示上的一切符号串（包括）组成的集合。*称为的闭包。,【说明】 上的除外的所有符号串组成的集合记为+ 。 +称为的正闭包。 闭包 *中的每个符号都是由中的符号串经有限次连接而成的。,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,由句子组成的集合，是由一组符号所构成的集合。换言 之,字母表上的一个语言是上的一些符号串的集合 (字母 表上的每个语言是*的一个子集)。,语 言,【例如】字母表 =a,b, *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或表示为w|w*且w=anbn,n1为字母表上的一个语言。 集合a,aa,aaa, 表示为w|w*且w=an,n1 为字母表上的一个语言。 是一个语言。 即 是一个语言,文法和语言的形式定义,如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示;如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个 途径： 一、生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。 二、识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,文法是用生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造。,文法G定义为四元组(VN，VT，P，S )其中 VN为非终结符号(或语法实体，或变量)集； VT为终结符号集； P为产生式(也称规则)的集合； VN，VT和P是非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。,Define a grammar,A grammar G is defined as a 4-tuple (VN，VT，P，S ) VN is a set of nonterminals VT is a set of terminals P is a set of productions，each production consists of a left side,an arrow(or :=),and a right side S is a designation of one of the nonterminals as the start symbol V =VN VT is the alphabet of G,文法的定义,【例】 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,【例】 文法G=（VN，VT，P，S） VN =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,文法的写法 【例1】G：SaAb Aab AaAb A 【例2】GS：Aab AaAb A SaSb 【例3】 GS： Aab |aAb | SaSb,1、推导、归纳、句型、句子和语言 假定G是一个文法，S是它的开始符号。如果S*(表示从S出发，经0步或若干步可推出，则称是一个句型。 仅含终结符号的句型是一个句子。这个过程称为推导推导的逆过程称为归纳。 文法G所产生的句子的全体是一个语言，将它记为L(G)。 L(G)=|S + & VT ,文法产生的语言 文法产生的语言是由文法开始符号推导出的终结符号串的集合,【例】G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型有 ： S,0S1 ,00S11 ,000S111,00001111等。 G的句子 ：00001111, 01等。,例如：终结符号串（i*i+i)是文法 EE+E|E*E|(E)| 的一个句子。 因为： E(E)(E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) 根据定义可知（i*i+i)是该文法的一个句子，而E,(E),(E*E+E)等是文法的句型。,例1：考虑一个文法G1: SbA AaA|a 它定义了一个什么语言呢？,从开始符S出发，我们可以推出如下句子： SbA ba SbA baA baa SbA baA baaa 可以写为：L(G1)=ban|n1,【例】,【例】 设有文法G SP|aPPb P ba|bQa Q ab 求语言L(G).,解： L(G)=ba,baba,abab,ababab ,【例】 构造一个文法G3使 L(G3)=anbn|n1,解; SaSb|ab,【例】G： S0S1， S01 L(G)=0n1n|n1,【例】 试构造生成语言L=anbnci|n1, i 0的文法,解：G(Z): ZAB A aAb|ab B cB|,【例】 已知语言L=anbbn| n 1, 写出产生L的文法。,解： GS: S aAb A aAb|b,【例】 已知文法G=(A,B,C,a,b,c,A,P) 其中产生式P由以下组成： A abc A aBbc Bb bB Bc Cbcc bC Cb aC aaB aC aa 问：此文法表示的语言是什么？,解：由于A为开始符。 由于AaBbc abBc abCbcc aCbbcc aabbcc 语言为： anbncn, n0 ,【例】试写一文法，使其描述的语言L(G) 是能被5整除的整数集合。,解： G(Z): Z (+|- )A(0|5) A 0|1|2|3|4|5|6|7|8|9|AA,解： G(Z)： Z aZa|bZb|cZc|a|b|c|,【例】 已知语言L=x | xa,b,c*,且x重复排列是 对称的（aabcbaa,aabbaa,等) 写出该语言的文法。,首先要了解如何确切地描述或定义一种程序设计语言，其次才能识别和分析这种语言。20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。,文法的类型,语言学家乔姆斯基把文法分为四种类型： 0型、1型、2型、3型。0行强于1型，1行强于2型，2型强于3型。这几种文法的差别在于对产生式施加不同的限制。,0型文法 对文法的生成规则没有任何限制。在计算机语言应用中很少见。 1型文法（上下文有关文法） 在推导过程中，要依据上下文才能作相应替换。实际程序设计语言可能包含这种上下文有关的成分，但不是主要的。 2型文法（上下文无关文法） 是描述程序设计语言语法部分的主要文法。 3型文法（正则文法） 高级程序设计语言的单词符号，如标识符、无符号整数等都是采用3型文法来描述的。,G=(VT ,VN ,S ,P) 是一个0型文法，如果它的每个产生式 是这样的结构 (VNVT)* 且至少有一个非终结符，而(VNVT)* 。 0型文法也称短语文法。,如果对0型文法分别施加以下的第i条限制，则就得到第i型文法: (1)G的任何产生式 均满足 | |（其中|和|分别为和的长度；仅S例外 (2）G的任何产生式为A, AVN , (VN VT)* 。 (3) G的任何产生式为AB或 A，其中VT*，A、B VN 。 【说明】其中1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文并且一般不允许替换成空串。,2型文法也称上下文无关文法。 G的任何产生式为A，AVN， （VNVT)* 表明凡出现在产生式左边的符号都是非终结符。 3型文法也称右线性文法。3型文法还有另一种形式，称左线性文法：一个文法G为左线性文法，如果G的任何产生式为 AB 或A ，其中VT , A、B VN 由于3型文法等价于正规式所以也称正规文法。,2型文法,1型文法,0型文法,3型文法,四类文法之间的逐级“包含”关系,若“ ”左侧有终结符，则该文法一定属于0型或1型文法。若产生式“ ”的左部的符号串长度均小于或等于产生式“ ”的右部的符号串长度，则为1型文法，否则为0型文法。 2、3型文法的产生式“ ”的左部仅为单个非终结符。若“ ”的左部形式上为AB或 A， VT，A、B VN （称为右线性，也可定义一个等价的左线性文法）,BNF表示的整数生成规则 :=| -|+ :=| 例：EBNF表示的整数生成规则 integer=“+”|”-”digitdigit. EBNF表示式比BNF要清晰、简单得多,例：文法GS： SCD AbbA CaCA BaaB CbCB BbbB ADaD C BDbD D AabD,判断文法的类型,例： 文法GS： SAB ABS|0 BSA|1,判断文法的类型,GS： S0A|1B|0 A0A|1B|0S B1B|1|0,GI： I lT I l T aT T dT T l T d,判断文法的类型,思考:以上文法的类型？,【例】文法GS：S aSYZ SaYZ aYay yYyy yZyz ZYYZ zZzz 【例】文法GS：S xSYZ SxYZ xYx yYyy yZyz ZYYZ zZzz 【例】文法GS：SaT TbT|cT|b|c 【例】文法GS：SxB|c BAz AcS,判断下列文法类型,上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构 语法树-句型推导的直观表示,前面我们提到过可以用一张图表示一个句型的推导，这种表示称为语法分析树，或简称语法树。 语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。每个新结和其父亲结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。,【例】 GS: SaAS ASbA ASS Sa Aba,从左到右读出推导树的叶子标记，所得的句型为推导树的结果。,句型的语法树构造方法：以文法开始符S作为根结点，随着推导的展开，对句型中某个非终结符A用产生式A的右部替换时，对标记A的结点生成其子结点从左至右依次为的子树，直至推导结束。,SaASaAaaSbAaaSbbaaaabbaa,规范推导 规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换； 最右推导被称为规范推导； 由规范推导所得的句型称为规范句型。,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,例: GS: SaAS ASbA ASS Sa Aba,语法树,给定文法G=( VN,VT,P,S)，若一棵树满足下列4个条件，则此树称作G的语法树(或推导树）： 1. 每个结点都有一个标记，此标记是V的一个符号 2. 根的标记是S 3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN 4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式。,上下文无关文法的语法树,句型aabbaa的可能推导序列和语法树,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,问题：一个句型是否对应唯一的一棵语法树？,例：GE: E i E E+E E E*E E (E) 考虑句型i*i+i的语法树？,句型 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,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同的最左（或右）推导，则称这个文法是二义的。 产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。,二义文法的解决方案,1、修改编译算法 如文法GE EE+E|E*E|(E)| 是二义性的文法，在编译方法中可以规定运算符的 优先级来避免文法的二义性。 比如规定: a）”*、/”优先与“+、-” b）同级的按先左后右,2、修改文法 【如】 将文法： EE+E|E*E|(E)| 修改为： E-E+T|T T-T*F|F F-(E)|i,句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,两种方法反映了两种语法树的构造过程,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串。 自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树。,自上而下的语法分析,例：文法G：S cAd A ab A a 识别输入串w=cabd是否为该文法的句子,S S S c A d c A d a b 推导过程：S cAd cAd cabd,自下而上的语法分析,例：文法G： S cAd A ab A a 识别输入串w=cabd是否该文法的句子,句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？ 2）在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,短语和句柄,定义令（1）是文法G的一个句型 （2）且S=* A且A=+ 则称是句型相对于非终结符A的短语。 若A= ，则称 是句型的直接短语。 一个句型的最左直接短语称为句柄。,语法树子树的末端结点符号串即是语法树所描述句型的短语； 简单子树（只有父子两代）的末端节点符号串即是简单短语； 最左简单子树的末端节点符号串即为句柄。,语法树与短语的关系,【例】给定文法GS S-aAcBe A-b A-Ab B-d （1）若有句型aAbcde，试问b是它的直接短语吗？ （2）它的短语是什么？句柄是什么？ （3）写出句子abbcbe的最左推导过程,句型aAbcde对应的语法分析树如下：,句型aAbcde的短语为aAbcde、Ab、d，简单短语为Ab、d，句柄为Ab,【例】