第2章 文法和语言.ppt

1,第2章 文法和语言,2,构造编译程序，需针对特定的程序语言，故需对被编译的程序语言本身做精确地描述。为语言的语法（文法）描述寻求工具。工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）。,本章目的,对于程序设计者而言，文法给出了语言的精确的语法规范说明。,3,程序设计语言描述,语法Syntax：对语言结构的定义。语义Semantics：描述语言的含义。语用Pragmatics：从使用者角度描述语言。,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。,4,形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,5,2.1 字母表和符号串2.2 文法和语言的形式定义2.3 语法树和文法的二义性2.4 文法的类型,6,2.1 字母表和符号串,7,每个程序设计语言都是一个“基本符号”串，设有一基本符号集，那么程序设计语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。为了给出语言的形式定义，首先学习一些基本概念和术语。,8,（1）空符号串：没有符号的符号串。例如：=a,b,a,b,aa,ab,aabba都是上的符号串,1.字母表：符号（元素）的非空有穷集合。,字符（符号）：可以相互区别的记号（元素）。,2.符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。,9,（2）符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀。符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀。,（3）符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串。,10,对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。（4）符号串s的真前缀，真后缀，真子串 3.符号串的运算(1)符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。的长度为0。(2)连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy。如 x=ab,y=cd 则 xy=abcd 有a=a=a(3)方幂：符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a,a2=aa则a0=,11,(4)符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为：AB=xy|xA且yB 若 集合A=ab,cde B=0,1，则 AB=ab1,ab0,cde0,cde14.闭包：使用*表示上的一切符号串（包括）组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。,12,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,13,文法的直观概念,14,当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构。比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，以下是该句的构成规则：,15,“我是大学生。”是一个汉语句子,句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,16,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子 主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。重复做下去，句子：“我是大学生”的全部动作过程是：,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,符号 的含义：使用一条规则，代替左边的某个符号，产生右端的符号串。,17,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，那么它就不是句子。这些规则成为我们判别句子结构合法与否的依据。换句话说，这些规则看成是一种元语言，用它描述汉语结构。这种描述语言的语法结构的形式规则称为文法。,18,王明是大学生。他学习英语。你是工人。,使用文法作为工具，不仅能严格定义句子结构，也能用有限的规则把语言的全部句子描述出来。所以，文法是以有穷集合刻划无穷集合的工具。,19,上例中的局限性,对“我是大学生”作扩充“我是计算机专业的大学生。”该句子中多了定语，相应的对前面的7条规则做相应修改。,因此，用文法描述的一组规则只能描述一类句子，不同类的句子应使用不同的规则。,同理，程序设计语言也不能只用一组规则就把程序都描述完整。,20,2.2 文法和语言的形式定义,21,一、文法二、推导 1.直接推导（一步推导）2.推导序列（多步推导）三、句型，句子四、语言 1.语言等价 2.文法与语言的关系,22,如何来描述一种语言？,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示。如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：,生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。,识别方式（自动机）：是一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,23,文法是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造。下面给出文法的四个组成部分，初步对文法的形式定义有一个初步了解。,24,1.终结符：语言中不可再分的基本符号，通常是一个语言的字母表。如程序设计语言中的基本字、常数、运算符、分界符等。,2.非终结符：它不像终结符代表了语法的最小元素，是一种个体记号，它是一个类、一个集合。一个非终结符代表了一定的语法概念。程序设计语言中常见的语法单位有“过程”、“赋值语句”、“表达式”等。,3.开始符号：是一个特殊的非终结符。,4.产生式：构造某个语法时应满足的规则。,25,文法G定义为四元组(VN，VT，P，S)其中：VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；S为开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。P为产生式(也称规则)的集合；,VN，VT和P是非空有穷集。VN和VT不含公共的元素，即VN VT=用V表示VN VT，称为文法G的字母表。,26,文法的举例,例:文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号,27,定义中的注意事项,1.产生式形如，“”读作“是”或“定义为”。其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。,2.若 1，2 n，可简写为：1|2|n,习惯表示 小写字母：终结符 大写字母：非终结符,28,例：文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,29,文法的几种等价写法,GS：Aab|aAb|SaAb,G：SaAb Aab AaAb A,GS：Aab AaAb A SaAb,30,直接推导“”,是文法G的产生式，若有v,w满足：v=,w=,其中V*,V*则称v直接推导到w,记作 v w。也称w直接归约到v。,例：G：S0S1，S01 0S1 00S11 使用产生式 00S11 000S111 使用产生式 000S111 00001111 使用产生式 S 0S1 使用产生式,31,推导序列,1.若存在v w0 w1.wn=w,(n0)+则记为v=w，称v推导出w，或w归约到v。+*2.若有v=w，或v=w，则记为v=w,32,推导举例,例：文法G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S11100001111+S=00001111,33,句型、句子的定义,1.句型:有文法G，若S=*x，则称x是文法G的 句型。2.句子:有文法G，若S=*x，且xVT*，则称 x是文法G的句子。例：G：S0S1|01 S 0S1 00S11 000S111 00001111,G的句型:S，0S1，00S11，000S111，00001111G的句子：00001111,01,34,推导句子a+a*a,例：GE：EE+T|T TT*F|F F(E)|aE E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号a，+，*，(和)构成的算术表达式,35,语言的定义,由文法G生成的语言记为L(G)，它是文法G的一切句子的集合:例：G：S0S1，S01 L(G)=0n1n|n1,L(G)=x|S=*x，其中S为文法的开始符号，且x VT*,36,语言是由句子组成的集合，是由一组符号所构成的集合。换言之，字母表上的一个语言是上的一些符号串的集合。字母表上的每个语言是*的一个子集。,37,例如：字母表=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，为字母表上的一个语言。,是一个语言。,即 是一个语言。,38,语言的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。,G1A：A0R A01 RA1,G2S：S0S1 S01,等价,39,文法与语言的关系,给定一个文法，就能从结构上确定其语言，且是唯一的。GL(G)给定一种语言，能确定其文法，但这种文法不是唯一的。LG1或G2或,40,2.3 语法树和文法的二义性,41,上下文无关文法有足够的能力描述程序设计语言的语法结构。语法树-句型推导的直观表示。,42,句型、推导,GE：EE+T|T TT*F|F F(E)|a,最左推导 EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,最右推导 EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a,无规律 EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,43,规范推导 规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。,最右推导被称为规范推导。由规范推导所得的句型称为规范句型。,44,语法树的构造过程,以文法开始符号S为根结点，随着推导的逐步展开，对句型中某个非终结符A用相应产生式A的右部替换时，为A的结点生成其子结点依次为的子树，直至推导结束。,45,构造语法树,GE：EE+T|T TT*F|F F(E)|aE E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,E EE+T E+T T E E+T T F,46,EE+T T+T F+T a+T a+T*Fa+F*F a+a*F a+a*aEE+T E+T*F E+T*a E+F*a E+a*aT+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,E E+T T T*F F F a a a 看不出句型中的符号被替代的顺序,47,语法树中的几个概念,1.一棵语法树中没有后代的结点，称为端末结。,2.一棵语法树生长的任何时刻，所有没有后代的端末结自左至右排列起来就是一个句型。,3.在一棵语法树中，一个内部结点A连同它的所有后裔组成了一棵子树。只有单层分支的子树称为简单子树。（只有父子两代，没有第三代。）,48,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)。,定理：G为上下文无关文法，对于，有S=*，当且仅当文法G有以为结果的一棵语法树(推导树),49,语法树要满足的条件,1.每个结点都有一个标记，此标记是V的一个符号。2.根的标记是S（开始符号）。3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN。4.如果结点n有标记A,其直接子结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式。,50,语法树的用处,用于描述上下文无关文法句型推导的直观方法。,例:GS:SaAS|a ASbA ASS Aba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子结点连接成的文法符号串，为GS的句型。,51,推导过程中施用产生式的顺序,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,例:GS:SaAS|a ASbA ASS Aba,52,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢？一个句型是否只有唯一的一个最左(最右)推导呢?,53,例：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,54,文法的二义性,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。,55,文法的二义性与语言的二义性,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)。这两个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,56,2.4 文法的类型,57,通过对产生式施加不同的限制，将文法分为四种类型：,0型文法：对任一产生式，都有(VNVT)*且至少含有一个非终结符，(VNVT)*,1型文法：对任一产生式，都有|，仅仅 S除外。,2型文法：对任一产生式，都有VN，(VNVT)*,3型文法(右线性文法)：任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT,58,1型文法举例,例：1型（上下文有关）文法 文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabD,59,2型文法举例,例：2型（上下文无关）文法 文法GS：SABABS|0BSA|1,60,3型文法举例,GS：S0A|1B|0 A0A|1B|0S B1B|1|0,61,文法的类型,0型文法,四种文法之间的逐级“包含”关系,3型文法,62,本章小结,63,1.本章出现的概念较多，应该重点理解文法、推导、句型、句子及语言的定义等概念。语法分析有关内容在后面章节详细讨论。2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什么样的符号串出现。请记住文法和语言的形式定义中的“形式”的含义只涉及语言的语法不涉及语言的语义。,