第2章 文法和语言.ppt

《第2章 文法和语言.ppt》由会员分享，可在线阅读，更多相关《第2章 文法和语言.ppt（63页珍藏版）》请在三一文库上搜索。

1、1,第2章 文法和语言,2,构造编译程序，需针对特定的程序语言，故需对被编译的程序语言本身做精确地描述。 为语言的语法（文法）描述寻求工具。工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）。,本章目的,对于程序设计者而言，文法给出了语言的精确的语法规范说明。,3,程序设计语言描述,语法Syntax：对语言结构的定义。 语义Semantics：描述语言的含义。 语用Pragmatics：从使用者角度描述语言。,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。,4,形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以符号串能

2、出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,5,2.1 字母表和符号串 2.2 文法和语言的形式定义 2.3 语法树和文法的二义性 2.4 文法的类型,6,2.1 字母表和符号串,7,每个程序设计语言都是一个“基本符号”串，设有一基本符号集，那么程序设计语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。 为了给出语言的形式定义，首先学习一些基本概念和术语。,8,（1）空符号串：没有符号的符号串 。 例如： =a,b ,a,b,aa,ab,aabba都是上的符号串,1. 字母表：符号（元素）的非空有

3、穷集合。,字符（符号）：可以相互区别的记号（元素）。,2. 符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。,9,（2）符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。 如：b是符号串banana的一个前缀。 符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。 如:nana是符号串banana的一个后缀。,（3）符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。 如:ana是符号串banana的一个子串。,10,对于每个符号串s， s和两者都是符号串s的前缀，后缀和子串。 （4）符号串s的真前缀，真后缀，真子串 3.符号串

4、的运算 (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,cde1 4.闭包：

5、使用 *表示上的一切符号串（包括）组成的集合。*称为的闭包。 上的除外的所有符号串组成的集合记为+ 。 +称为的正闭包。,12,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,13,文法的直观概念,14,当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构。 比如汉语句子可以是由主语后随谓语而成，构

6、成谓语的是动词和直接宾语，以下是该句的构成规则：,15,“我是大学生。”是一个汉语句子,句子=主语谓语 主语=代词名词 代词= 我你他 名词= 王明大学生工人英语 谓语=动词直接宾语 动词= 是学习 直接宾语=代词名词,16,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成： 句子 主语谓语， 然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。 重复做下去，句子：“我是大学生”的全部动作过程是：,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,符号 的含义：使用一条规

7、则，代替左边的某个符号，产生右端的符号串。,17,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，那么它就不是句子。这些规则成为我们判别句子结构合法与否的依据。 换句话说，这些规则看成是一种元语言，用它描述汉语结构。这种描述语言的语法结构的形式规则称为文法。,18,王明是大学生。 他学习英语。 你是工人。,使用文法作为工具，不仅能严格定义句子结构，也能用有限的规则把语言的全部句子描述出来。 所以，文法是以有穷集合刻划无穷集合的工具。,19,上例中的局限性,对“我是大学生”作扩充“我是计算机专业的大学生。” 该句子中多了定语，相应的对前面的7条规则做相应修改。,因此，用文法描述

8、的一组规则只能描述一类句子，不同类的句子应使用不同的规则。,同理，程序设计语言也不能只用一组规则就把程序都描述完整。,20,2.2 文法和语言的形式定义,21,一、文法 二、推导 1. 直接推导（一步推导） 2. 推导序列（多步推导） 三、句型，句子 四、语言 1. 语言等价 2. 文法与语言的关系,22,如何来描述一种语言？,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示。 如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：,生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。,识别方式（自动机）：是一个过程，当输入的一任意串属于语言时，该过程经有

9、限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,23,文法是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造。 下面给出文法的四个组成部分，初步对文法的形式定义有一个初步了解。,24,1. 终结符：语言中不可再分的基本符号，通常是一个语言的字母表。如程序设计语言中的基本字、常数、运算符、分界符等。,2. 非终结符：它不像终结符代表了语法的最小元素，是一种个体记号，它是一个类、一个集合。一个非终结符代表了一定的语法概念。程序设计语言中常见的语法单位有“过程”、“赋值语句”、“表达式”等。,3. 开始符号：是一个特殊的非终结符。,4. 产生

10、式：构造某个语法时应满足的规则。,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的正

11、闭包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,9 P= 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

12、。 也称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,句型

13、、句子的定义,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，00001111 G的句子：00001111, 01,34,推导句子a+a*a,例：GE：EE+T|T TT*F|F F(E)|a E E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子：用符号a，+，*，(和)构成的算术表达式,35,语言的定义,由文法G生成的语言记为L

14、(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， 为字母表上的一个语言。,

15、是一个语言。,即 是一个语言。,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

16、+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

17、 TT*F|F F(E)|a E E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,E E E + T E + T T E E + T T F,46,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*aT+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,E E + T T T * F F F a a a 看不出句型中的符号被替代的顺序,47,语法树中的几个概念,1.一棵语法树中没有后代的结点，称为端末结。,

18、2.一棵语法树生长的任何时刻，所有没有后代的端末结自左至右排列起来就是一个句型。,3.在一棵语法树中，一个内部结点A连同它的所有后裔组成了一棵子树。 只有单层分支的子树称为简单子树。（只有父子两代，没有第三代。）,48,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)。,定理： G为上下文无关文法， 对于，有S =* ，当且仅当 文法G有以为结果的一棵语法树(推导树),49,语法树要满足的条件,1. 每个结点都有一个标记，此标记是V的一个符号。 2. 根的标记是S（开始符号）。 3. 若一结点n至少有一个它自己除外的子孙，并且有

19、标记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,SaASaAaaSbAaaSbbaaaabbaa S

20、aASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,例: GS: SaAS | a ASbA ASS Aba,52,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。 但是，一个句型是否只对应唯一的一棵语法树呢？一个句型是否只有唯一的一个最左(最右)推导呢?,53,例：GE: E i E E+E E E*E E (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,文法的

21、二义性,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。,55,文法的二义性与语言的二义性,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)。这两个文法所产生的语言是相同的。 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,56,2.4 文法的类型,57,通过对产生式施加不同的限制，将文法分为四种类型：,0型文法：

22、对任一产生式，都有(VNVT)*且至少含有一个非终结符， (VNVT)*,1型文法：对任一产生式，都有|， 仅仅 S除外。,2型文法：对任一产生式，都有VN ， (VNVT)*,3型文法(右线性文法)：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT,58,1型文法举例,例：1型（上下文有关）文法 文法GS： SCD AbbA CaCA BaaB CbCB BbbB ADaD C BDbD D AabD,59,2型文法举例,例：2型（上下文无关）文法 文法GS： SAB ABS|0 BSA|1,60,3型文法举例,GS： S0A|1B|0 A0A|1B|0S B1B|1|0,61,文法的类型,0型文法,四种文法之间的逐级“包含”关系,3型文法,62,本章小结,63,1. 本章出现的概念较多，应该重点理解文法、推导、句型、句子及语言的定义等概念。语法分析有关内容在后面章节详细讨论。 2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什么样的符号串出现。请记住文法和语言的形式定义中的“形式”的含义只涉及语言的语法不涉及语言的语义。,