《编译方法》第2章形式语言和文法.ppt

《《编译方法》第2章形式语言和文法.ppt》由会员分享，可在线阅读，更多相关《《编译方法》第2章形式语言和文法.ppt（40页珍藏版）》请在装配图网上搜索。

1、,2.1 形式语言,第2章 形式语言和文法,2.4 文法的二义性,2.3 文法的分类和化简,2.2 文法,2.1 形式语言,2.1.1 语言的概念,2.1.2 语言的定义方式,语言：符号串的集合。 元素 符号串该语言的一个句子。 字母表符号串中符号的来源。 句子的构成按一定规则。 程序设计语言： 程序的集合 句子程序（一个或长或短的字符串） 。 字母表固定的字符集，语言可以使用的所有符号。 编程时必须遵循一定的规则 语法规则和语义规则。 语言的描述工具文法,2.1.1 语言的概念,2.1 语言,1. 什么是语言,（1） 有穷字母表 一个元素的非空有穷集合，其中的元素也称符号。 每个语言均有一固

2、定的字母表。,例： C语言的字母表由基本字符集（字母，数字，括号，专用字符+、 *、 ）、保留字（int、 long、 if、struct、static、 typedef、 sizeof、 ）等组成。,2.1.1 语言的概念,2.1 语言,2符号串的相关概念和术语,通常用V、或其他大写字母表示。 例如V=0，1，=a，b，c，d，e等。,（2）符号串 字母表中的符号组成的任何有穷序列。,相关术语： 长度： 符号串中符号的个数。 符号串x 的长度表示为x，x= m0。 空符号串：无任何符号的串，简称空串，用表示，|=0 省略写法： z = x z = x z = x,2.1.1 语言的概念,2.

3、1 语言,【例2-1】 =a，b，c，z，x =“laugh”，则 |x|=5 =I，you，he，am，is，are，a，student， y=“I am a student”，空格不计算长度，则 |y|=4。,（3）符号串的运算,连接： 符号串x、y的连接 xy 为一个新的符号串，该串的前面部分为 x ， 后面部分为 y 。,成立的等式： | xy | = | x | + | y | x = x=x,【例2-2】若 x = “home”，y = “work” 则 | x | = 4 , | y | = 4 xy = “homework” | xy | = 4+4 = 8,2.1.1 语言的

4、概念,2.1 语言,方幂：符号串 x 的方幂就是 n个x 自身连接 次，表示为 xn 。 规定 x0 =。,【例2-3】 若 x = “ab” 则 x0 = x1 = “ab” x2 = “abab” x3 = “ababab” ,成立的等式： x1=x ， x2=xx ， x3=xxx ， 若n0，则有： xn = xxn-1 = xn-1x x* 表示 x 的任意多次方幂（可以是 0 次） x+ 表示 x 的任意非 0 次方幂。,2.1.1 语言的概念,2.1 语言,（4） 符号串的集合 若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表 上的符号串集合。,乘积： 两符号串集U、

5、V 的乘积为 UV= | U V 成立的等式： U = U = U V n = VVV （n个V） 规定： V 0 = V * = V 0V 1V 2 V + = V 1V 2 ,【例2-4】 若 U = a，b ， V = c，d 则 UV = ac，ad，bc，bd ,2.1.1 语言的概念,2.1 语言,闭包： 若指定字母表，则*表示上的所有有穷长的串的集合。 * =012n * 称为集合的闭包。 + =12n + 称为集合的正闭包。 成立的等式： * =0+ ， + =* =* 若符号串 x 是*的元素,则表示为 x* ,否则 x * 。,2.1.1 语言的概念,2.1 语言,语言的句

6、子个数有限 枚举 语言的句子有很多甚至是无穷多个 给出一些规则 说明这个语言的句子的组成结构。 规则文法规则,2.1.2 语言的定义方式,2.1 语言,【例2-5】文法规则： studentEnglish computer Iyouhe amisarehavestudy aanthe,文法规则的作用： （1）严格定义了一个语言的句子的结构； （2）用适当条数的规则描述了一个语言的全部句子。,2.1.2 语言的定义方式,2.1 语言,2.2 文法,2.2.1 文法的形式定义,2.2.2 文法的表示方法,2.2.3 相关概念,2.2 文法,表示语言中的语法单位的符号，常用尖括号“”括起。 一个非终

7、结符一般可以推导出终结符串。 一个语言可使用的所有非终结符组成的集合称为非终结符集， 用VN 表示。,1终结符,不可分割的符号串，是组成句子的最基本的单位。 一个语言允许使用的所有终结符组成的集合称为终结符集， 用VT 表示。,2非终结符,2.2.1 文法的形式定义,2.2 文法,3规则（重写规则、产生式、生成式）,形如 或 或（，）的有序对，其中 ：某字母表V 的 V + 中的一个符号串（左部） ：V * 中的一个符号串（右部）,定义：一个文法是一个四元组G（VN ，VT ，S ， P） VN ： 非终结符集（非空）； VT ： 终结符集（非空），VNVT ； S ： 识别符号或开始符号，S

8、VN， 且至少在一条规则中作为左部出现； P ： 规则（产生式）的集合。 用V表示 VNVT ，称G的字母表或词汇表。,4文法,2.2.1 文法的形式定义,2.2 文法,G：S0S1 或 GS：S0S1 或 G： S0S1 | 01 S01 S01 注意：左部相同的产生式可合并，用“|”表示“或”。,简化表示只写出规则（产生式），且第一条 规则的左部 是开始符号，用“”括起的或大写字母表示非终结符， 不用“”括起的或小写字母表示终结符。 文法 G 也常写成GS，方括号中的S为开始符号。,【例2-6】 有一文法G（VN ，VT ，S ， P） 其中: VN = S VT = 0，1 开始符号是

9、S P = S0S1， S01 ,2.2.1 文法的形式定义,2.2 文法,【例2-7】文法G=(VN，VT，S ，P)为： VN= ， ， ， VT= student，computer，sister，English，I，you，he ， am，is，are，have，study， a，an，the 开始符号是 P= studentcomputersisterEnglish Iyouhe amisarehavestudy aanthe ,2.2.1 文法的形式定义,2.2 文法,【例2-8】FORTRAN语言中对标识符的规定是字母开头、长度小于等于8的 字母数字串，则标识符的规则可以描述为：,

10、1. BNF表示法 巴科斯-诺尔范式（巴科斯范式） 采用四个元符号描述文法：“”（或“”）、“”，“|” 2. 扩展的BNF表示法 增加三对元符号： （1）“ ” 表示符号串t的多次重复，n为重复的最小次数，m为重 复的最大次数，省略n、m表示t可以重复0到任意多次。,2.2.2 文法的表示方法,2.2 文法,（2）“( )” 用于提取产生式的公共因子，从而可以简化产生式。 若有文法规则 Ax1| x2| xn 表示为 Ax(1| 2| n) 【例2-9】文法规则 S0S1|01 简化为 S0(S1|1) 或 S(0S|0)1 或 S0(S| )1 （3）“ ”：t表示符号串t可选（即可有可无

11、）。 【例2-10】C程序设计语言的条件语句的文法规则 BNF表示：if () ； | if () ；else ； 扩展BNF表示： if () ；else ；,2.2.2 文法的表示方法,2.2 文法,3. 语法图表示法 【例2-11】C语言条件语句的语法图,2.2.2 文法的表示方法,2.2 文法,终结符,非终结符,【例2-13】 对文法G： S 0S1 S 01 有直接推导序列： S 0S1 00S11000111,定义：如是文法G（VN ，VT ，S ， P）的一条规则， 、V * ， 若有符号串 v、w 满足 v =， w = 则称v（应用规则）直接产生w ，或称 w 是 v 的直接

12、推导，反过 来称 w 直接归约 到 v ，记作 v w 。,1推导和归约,2.2.3 相关概念,2.2 文法,定义：如果存在直接推导序列： v = w0 w1 w2 wn = w 则称v 推导（产生）出w，推导长度为n ，反过来称w 归约到v， 记作 v w。 如果有 v w ，或 v = w ，则记作 v w。,2.2.3 相关概念,2.2 文法,【例2-15】 推导 S 0S1 00S11 000111,定义： 文法G（VN，VT，S ，P），若符号串x可由开始符号S推导出 （S x），则称 x 是 G 的一个句型，若x仅由终结符组成， 则称 x 为G 的一个句子。,*,2句型和句子,句型

13、,句子,2.2.3 相关概念,2.2 文法,注意：句型和句子都必须由开始符号S推出！,定义：文法描述的语言是该文法的所有句子的集合， 记作 L(G)。集合形式表示： L(G) = | S VT* ,【例2-16】文法G： S 0S1 S 01 描述的语言：L(G)= 0n1n | n1 ,3形式语言,+,2.2.3 相关概念,2.2 文法,【例2-17】有文法 GA： A0R A01 RA1,定义：若有文法G1、G2，它们描述的语言相同，即 L( G1 ) = L( G2 ) 则称两文法 G1 和 G2 等价。,描述的语言 L(G) = 0n1n | n1 。,4文法的等价性,2.2.3 相关

14、概念,2.2 文法,2.2.3 相关概念,2.2 文法,5. 递归规则和递归文法,递归文法：含有递归规则的文法称递归文法。,递归规则：形如P1P2的规则称递归规则。 若1=则称左递归规则; 若2=则称右递归规则。,P1P2的递归称间接递归,含间接递归的文法也是递归文法。,+,2.3 文法的分类和化简,2.3.1 文法的分类,2.3.2 两个定理,2.3.3 文法的化简,2.3 文法的分类和化简,1. 0型文法（无限制文法或短语文法）,2.3.1 文法的分类,定义2-7 设G=(VN，VT，P，S)，如果它的每个产生式满足、 (VNVT)*，且至少含有一个非终结符，则G是一个0型文法。,结论 0

15、型文法的能力相当于图灵机，它所定义的语言为0型语言。 任何0型语言都是递归可枚举的，反之，递归可枚举集也必定是 一个0型语言，可由图灵机来识别。,2.3 文法的分类和化简,定义2-8 设G=(VN，VT，P，S)，如果它的每个产生式满足 |（仅S除外），则G是一个1型文法。 另一种描述：文法的产生式形如 1A2 12 其中AVN，、(VNVT)*且。,【例2-18】1型文法GS： S xSYZ | xYZ yZyz xYxy ZYYZ yYyy zZzz,21型文法,（上下文有关文法）,2.3.1 文法的分类,2.3 文法的分类和化简,32型文法 （上下文无关文法）,【例2-19】 2型文法G

16、S： SE TP | TP Fi | (E) ET | ET PF | FP,定义2-9 设G=(VN，VT，P，S)，如果它的每个产生式中的 是一个非终结符，则G是一个2型文法或上下文无关文法。,2.3.1 文法的分类,2.3 文法的分类和化简,43型文法 （正规文法或正则文法）,【例2-20】 3型文法GS ： S aA A aA A a S a A dA A d,定义2-10 设G=(VN，VT，P，S)，如果它的每个产生式均形如 AaB 或 Aa 其中A、BVN，aVT。,2.3.1 文法的分类,2.3 文法的分类和化简,描述句法,描述词法,|,VN, = aB | a,2.3 文法的

17、分类和化简,2.3.1 文法的分类,定理2-1：含有A的文法产生的语言也可由不含 A的另一个 文法产生（S除外）。 定理2-2：若存在一个上下文有关文法 G，则必存在另一个上下文有 关文法 G1，使得 L(G1) = L(G) ，且 G1 的开始符号不出现在 任何产生式的右边。 在使用上下文无关文法描述语言时不限制产生式的使用。,2.3 文法的分类和化简,2.3.2 两个定理,文法应没有多余的或有害的规则。 化简：(1) 删除形如AA的产生式。 (2) 删除不可到达的文法符号及其相应的产生式。 (3) 删除不可终止的非终结符及其相应的产生式。,【例2-21】 文法G： S aS | W | U

18、 U a V bV | ac W aW,W 是不可终止的 V 是不可到达的。,化简后的文法G： S aS | U U a,2.3.3 文法的化简,2.3 文法的分类和化简,1. 语法树,2.4 文法的二义性,2.3 文法的二义性,定义：语法树是 一棵数据结构意义上的“树”，满足四个条件： （1）每个结点都有一个标记 （字母表V的一个符号）； （2）根的标记是S（文法的开始符号）； （3）若一个结点n至少有一个它自身除外的子孙，且有标记 A，则A必在VN中（是非终结符）； （4）若标记为A的结点n的直接子孙从左到右的次序是结点 n1、n2、nk ，其标记分别为A1、A2、 Ak， 则AA1A2A

19、k 必是文法产生式集P中的一个产生式。 对给定文法G，它的任何句型均能构造与之相关的语法树。,2.4 文法的二义性,2.3 文法的二义性,i*ii 的语法树,【例2-22】对算术表达式文G： Ei EE+E EE*E E(E),“i*ii ” 的推导过程可以是： (1) E E+E E*E+E i*E+E i*i+E i*i+i (2) E E+E E+i E*E+i E*i+i i*i+i (3) E E+E E+i E*E+i i*E+i i*i+i,2.4 文法的二义性,2.3 文法的二义性,可见：（1）一棵语法树表示了一个句型的多种可能的不同推导过程， 但未必是所有的。 （2）一个句型

20、未必只有一棵语法树。,最左推导：在推导的任何一步（、是句型）都是对中的最左 非终结符进行替换。 最右推导：在推导的任何一步（、是句型）都是对中的最右 非终结符进行替换。也称规范推 导，推出的句型称规范句型。,例如 最左推导： E E*E i*E i*E+E i*i+E i*i+i 最右推导： E E*E E*E+E E*E+i E*i+i i*i+I,显然，一棵语法树表示的最左（右）推导是唯一的！,2.4 文法的二义性,2.3 文法的二义性,i*ii 的语法树：,定义：若一个文法存在某个句子，它对应两棵（或以上）不同的语法树，或 它有两个不同的最左（右）推导，则该文法是二义的（具有二义性）。,若产生某一上下文无关语言的每个文法 均是二义的，则说 该语言先天二义。,【例2-23】与例2-22等价的非二义文法 G： ET | E+T TF | T*F F(E)| i,愿望：文法非二义！,2.4 文法的二义性,2.3 文法的二义性,Thank You !,