《文法与语言》PPT课件.ppt

第二章 文法和形式语言 本章主要介绍形式语言理论中的一些最基本的概 念和基础知识，它是学习以后各章节的基础。 2.1 符号和符号串 2.1.1 字母表与符号串 字母表 :元素的非空有穷集合，习惯上用大写字母表示。 符号 ：字母表中元素。 符号串 ：符号的有穷序列。 空符号串 ：不含任何符号的符号串，记为 。 符号串集合 ：字母表 上的符号串组成的集合。 2.1.2 符号串的运算 符号串的长度 ：符号串中所包含的符号个数。设符号串为 x， 则其长度记为 |x|。 例：空符号串长度为 0，即 | |=0。 符号串的连接 ：设有符号串 x和 y，把 y的所有符号相继写在 x的符号串之后所得到的符号串即称为 x和 y的连接，记为 xy. 例 ： x = x =x 符号串的方幂 ：设 x是符号串，则 x的 n次连接称为 n次方幂， 记为 xn. 例： x0= 符号串的前缀、后缀、子串 假设 x是一个符号串，则有： 符号串 x的前缀 是指：从符号串 x的尾部删除若干（含 0个） 符号后得到的符号串； 符号串 x的后缀 是指：从符号串 x的头部删除若干（含 0个） 符号后得到的符号串； 符号串 x的子串 是指：删除了 x前缀（或删除 x的后缀或删除 x的前缀和后缀）后得到的符号串； 对任意的符号串 x， x的前缀、后缀都是 x的子串，但 x的子 串不一定是 x的前缀或后缀。 对任意的符号串 x， x和 都是符号串 x的前缀、后缀，也是 x的子串。 2.1.3 符号串集合的运算 符号串集合的乘积 ：设 A、 B为符号串集合，则符号串集 合的乘积表示为 AB=xy|xA, yB ，即 A中的任意符号串 和 B中的任意符号串的连接所构成的集合。 因为有 x = x =x ,所以有 A= A=A 符号串集合的方幂 ：即同一个符号串集合的乘积。 例：设 A为符号串集合，则 A0= ， A1=A， A2=AA， 符号串集合的闭包 设 A为符号串集合，则 A的闭包表示为 A ，其定义为： A的若干次幂（ 包括 0次幂）的并集。它表示符号串集合 A 上的所有可能的符号串（含 ）的集合。 A =A0A 1A 2 A n 符号串集合的正闭包 ： A的正闭包表示为 A ，其定义 为： A的若干次幂（ 不包括 0次幂）的并集。它表示符号 串集合 A上的所有可能的符号串（不含 ）的集合。 A =A1A 2 A n 显然有 A = A0A = A A = AA = A A 2.2 文法和语言 语言是特定字母表上具有一定语法结构 的符号串的集合。若用 L表示语言，用 表 示字母表，则 L 文法 (Grammar)是定义或描述语言的语 法结构的一组形式规则 (即语法规则 )。一个 程序语言的文法的目的就是用适当条数的规 则把该程序语言全部成分描述出来。 2.2.1 文法及文法的 BNF表示 1、规则 即产生式，是一有序对（ U， x） ,通常记为 Ux (或 U=x) 其中 U为规则的左部，是一个符号， x为规则的右部，为 有穷符号串。 规则 Ux 表示符号 U由符号串 x组成（或符号 U定义为符 号串 x ） 2、 文法和字汇表 文法可以定义成一个四元组 GS=(VN， VT， S， P)。 其中 ， VT:非空有限的终结符号集； VN:非空有限的非终结符号集； S:开始符号 ， 是文法 G规定的最终目标； P:产生式的集合 。 V=VNV T称为文法 GS的字汇表 。 VNV T= ， SVN。 为了方便 ， 表示文法时只列出产生式 ， 而不以 4元组显示 地表示出来 。 3、文法的 BNF（巴科斯范式）表示 即在规则中引入或者符号 “ ” ，将左部相同的规 则缩写到一起。 4、递归规则和递归文法 左部和右部含有相同非终结符号的规则称为递归规 则，至少含有一条递归规则的文法称为递归文法。 2.2.2 推导和归约 设文法 G=(VN， VT， P， S)， Uu 是其中的产生式， 是 文法任意的符号串，则有 U u 其中符号 “ ” 仅表示 “ 一步推导 ” ，即利用产生式对左 边符号串中的一个非终结符进行替换，得到右边的符号串。我 们称 U 直接推导出 u ，也可以说 u 直接归约到 U 。 如果有直接推导序列： a0 a1 a2 an 则说 a0推导出 an推导，记作： ，我们称这个序列是一个 从到的长度为 n的推导，其中 表示 0步或多步推导。 a0 an a0 an 最左、最右推导和规范推导 1、在 xUyxuy直接推导中，即 U是符号串 xUy中最左非终结符， 则称此直接推导为最左直接推导。若一个推导的每一步直接推 导都是最左直接推导，那么此推导称为最左推导。 2、在 xUy:=xuy直接推导中，即 U是符号串 xUy中最右非终结符， 则称此直接推导为最右直接推导。若一个推导的每一步直接推 导都是最右直接推导，则称此推导为最右推导。 最右直接推导又称为规范直接推导，最右推导又称为规范推导。 最左推导的逆过程是最右归约，最右推导的逆过程是最左归约。 2.2.3 句型、句子和语言 定义： 设 GS是字汇表 V上的一个文法，如果符号串 u是由文 法的开始符号推导出来的，则称 u是文法 GS的 句型 。如果 u仅 由终结符号组成，则称 u是文法 GS的 句子 。 即： 若 ,uV* ，则称 u是文法 GS的句型； 若 ,uVT* ，则称 u是文法 GS的句子； S u S u+ S u + 定义： 文法 GS所产生的所有句子的集合，称为该文法所 定义的语言，记为 L(GS)。 即： L(G)=u| ,且 uVT* 等价文法 ：设 G1和 G2是两个不同的文法，若 L(G1)=L(G2),则称文法 G1和 G1为等价文法。 2.2.4 文法的递归 如果文法 GS至少含有一个递归的非终结 符号，则称此文法为递归文法。 2.2.5 短语、简单短语、句柄 短语、简单短语、句柄 2.3 语法树 在自然语言中 ， 可通过树型表示直观地分析句子 结构；在形式语言中 ， 则是通过语法树直观地分析文 法的句型结构 。 句 子 主语 系词 定语 名词 Ph y s ics 冠词 th e 前置词 ofa reT h e y 连接词 a n d 名词 s tu d e n ts 名词 tea c h e rs 名词 De p a rtm e n t. 表语 代词 1、语法树 设文法 G=(VN， VT， P， S)， 对于文法 G的任意一个句型 都存在一个相应的语法树： 树中每个结点都有一个标记 ， 该标记是 VNVT中的 一个符号； 树的根结点标记是文法的识别符号 S； 若树的一个结点至少有一个叶子结点 ， 则该结点 的标记一定是一个非终结符； 若树的一个结点有多个叶子结点，该结点的标记 为 A，这些叶子结点的标记从左到右分别是 B1， B2， ， Bn，则 (AB 1B2 Bn)P。 语法树的任一非叶结点连同它射下的部分称为语法树 的子树，仅有父子两代的子树称为简单子树； 语法树每一 子树 的末端结点从左到右排列起来所组成 的符号串，是该句型相对与该子树根的 短语 ； 语法树每一 简单子树 的末端结点从左到右排列起来所 组成的符号串，是该句型相对与该简单子树根的 简单短语 ； 语法树的 最左简单子树 的末端结点从左到右排列起来 所组成的符号串，是该句型的 句柄 ； 2、语法树与短语、简单短语、句柄的关系 例 已知算术表达式 GE: EE+T|T TT*F|F F(E)|i 通过语法树求句型 F*i+F的短语、 简单短语和句柄。 3、二义性 定义 ：一个文法，如果它的一个句子有两棵或两棵 以上的语法树，则称此句子具有二义性。如果一个 文法含有二义性的句子，则该文法具有二义性。 例 设有文法 GE: EE+E|E*E|(E)|i 求句子 i+i*i的最左推导及其对应的语法树。 文法二义性的判定： 1）有些文法是非二义性，比如 LL（ 1）文法、 LR 文法、算符优先文法，而且这些文法都是可以判定 的，所以只要我们能够证明文法是属于上述某类文 法，则该文法必然是非二义性的； 2）如果一个文法既有左递归，又有右递归的非终 结符号 A，则文法必然是二义性的。 值得注意的是，没有一种算法，能在有限的步 骤内确切的判断一个文法是否是二义性的。 文法二义性与语言的二义性关系： 如果一个二义性的文法，我们可以把它变换 成一个等价的但无二义性的文法，那么我们可以 认为该二义性文法对应的语言中，某些句子的二 义性完全是二义性文法所带来的，而语言本身是 非二义性的。 如果一个语言，根本就不存在非二义性的文法， 则这样的语言为二义性的语言。 2.4文法的扩充 BNF表示和语法图 2.4.1 文法的扩充 BNF表示（即 EBNF） EBNF就是在原来 BNF的基础上引入了三对专用符号 、 、 ()，它的表达能力与原 BNF表达方式相同。 优点： 在结构上更简洁、清晰，并可消除文法的左递归。 三对专用符号的用途如下： 花括号 ：表示花括号里面的符号串可重复 0次或任意多次。 若有上下界，可表示为 ,表示花括号里面的符号串可重复 m到 n次。 方括号 ：表示方括号里面的符号串可有可无 (出现 0次或 1 次 )。 圆括号 ( )：利用圆括号可提取各侯选式的共因子。 n m 2.5 文法的实用限制 2.5.1 有害规则 定义 :文法中形如 UU 的规则就称为有害规则。 如果文法中含有有害规则 ,它除了造成文法的二义性 以外，对定义语言则是没有任何的意义。 2.5.2 多余规则 定义 : 设文法中某一规则，其左部的非终结符号为 U,若满 足下列条件之一 ,则称该规则为多余规则。 U (除文法的开始符号 )不出现在该文法的任何其它规 则的右部； 若在规则中采用该规则，则不能由 U推出终结符号串。 2.5.3 文法的实用限制 文法的实用限制主要指： 文法不含有害规则； 文法不含多余规则； 在具体应用中，可能还会有其他限制，比如： 文法不含左递归； 文法不含空规则： U (1) 文法的 -规则的消除 -规则，即形如 U 的空符号串规则； 文法 -规则消除的前提条件： 该文法所定义的语言 L(GS)不含 ； 消除文法 GS的 -规则的算法： 求出文法中所有能导出空符号串 的非终结符号的集合 EMPTY(GS) ； 删除文法中所有 -规则； 删除文法中只能导出空符号串的非终结符； 若文法中某规则右部含有属于 EMPTY(GS) 的非终结 符，则需扩展该规则。 注意： 文法的 -规则消除后，不能包含有害规则和多余规 则，如果有，则应该把它们去掉。 2.5.4 文法的变换 (2)文法直接左递归的消除 只要修改形如 UUx y的规则，使文法不含直接左递 归的非终结符号，便可消除这类文法的左递归。具体有以 下两种方法： 1)采用 EBNF表示法可消除文法的直接左递归； 形如 UUx y的规则，采用 EBNF的花括号 表示， 变可得到： U y x 2)引入新的非终结符号消除文法中的直接左递归； 形如 UUx 1 Ux2 Uxm y1 y2 ym 的规则，可引入一个新的非终结符 U，则得到等价的规则： U y 1 U y2U ymU U x 1U x2U xm U (3)文法一般左递归的检测和消除 文法的递归性除了由直接左递归的非终结符引起外，还可由 间接左递归的非终结符引起。对于间接左递归，它不像直接左递 归那样一目了然，要消除它，首先要解决的是如何判断！ 1) 间接左递归的判断 对于文法 GS和它的任意非终结符号 U，如果 U HEAD(U) U为左递归的非终结符号， GS为左递归文法。 其中， HEAD(U)是指从非终结符 U出发，能够推出的所有符 号串中，处于符号串头部的非终结符号的集合，简称头符号集。 求头符号集的一般算法： 实际上，要判断一个文法是否具有递归性，只要找到一个递 归的非终结符号就可以了。 求头符号集 HEAD（ U）的一般算法： 设文法 GS不含空规则，并设初值 HEAD（ U）为空集，则 考察文法所有规则，若文法中有形如 UA 的规则，则 A HEAD（ U）； 若 P HEAD（ U），则 HEAD（ P）中的任意非终结符号 属于 HEAD（ U）； 重复，直到 HEAD（ U）不再增大为止。 例 GA： ABcd|dD BAB|b Cc DAD|DB|Ca 求所有非终结符号的头符号集。 2) 间接左递归的消除 用如下算法可以消除文法的间接左递归，只不过要注意有 一个前提条件：该文法无回路，并且不含 -规则。 算法如下： 将文法 GS的所有非终结符号按任意一种顺序排列为 U1、 U2、 U i U n ； 对于任意非终结符 Ui 的规则，如果存在形如 Ui U j y 其中 j i，则按如下方法改写 Ui(i从 0开始 )的规则： Uj x 1 x2 xn 则 Ui x 1 y x2 y xn y 当 Ui 的所有规则的右部都用其本身或排列在其后的非终结 符开头（即使间接递归直接化），然后再消除 Ui的直接左递归， 直到所有的非终结符的规则改造完毕为止。 例 消除文法 GA： ABcd|dD BAB|b Cc DAD|DB|Ca 的左递归。 2.6 文法和语言的分类 0型文法 与 0型语言 1型文法 与 1型语言 2型文法 与 2型语言 3型文法 与 3型语言 0型文法 0型文法 (无限制的文法 )。 其产生式具 有以下形式： 其中 ， V+， 且至少含有一个非终结符； V* 1型文法（上下文有关文法） 1型文法 G的产生式具有以下形式： xUy xuy 其中 x,yV*;UVN; uV+。 例如： 1型文法 GS =(VN， VT， P， S) 其中， VN=S， X， Y， Z VT=（ x， y， z） P=SxSYZ xYZ, xYxy ， yYyy, yZyz ZYYZ, zZzz 2型文法（上下文无关文法） 在 1型文法的产生式中上下文 x和 y用空符号串 代替 ， 则有以下形式的产生式称为 2型文法： U u 其中， UVN， uV+。 例如： 2型文法 GE =(VN， VT， P， E) 其中 ， VN=E， T， F VT=+， *， (， )， i P=EE+T T， TT FF， F(E) i 3型文法 如果的产生式只含有下面的两种形式 ： Ua 或 UaB 其中 U， BVN， aVT*，则称该文法为右线性文法，如果 文法的产生式只含有下面的两种形式 ： Ua 或 UBa 其中 U， BVN， aVT* ，则称该文法为左线性文法 例如：右线性文法 GS=(VN， VT， P， S) 其中 ， VN=S， A， B VT=0, 1 P=S0 11A0B， A1A 0B， B0 10B 2.7 正则表达式与正则集 2.7.1 正则表达式与正则集 正则表达式也称为正则式或正规式，与其对应，它所描述 的语言又称为正则集或正规集。 设 为一字母表，则 上的正则式及其所表征正则集可递 归的定义如下： 1.是一个正则式 ,相应的正则集为空集； 2.是一个正则式 ,相应的正则集为 ； 3. 对于每一 a ,a是一个正则式，相应的正规集为 a； 4.若 r,s是正则式 ,且相应的正规集分别记为 L r 及 L s， 则： rs是正则式，相应的正规集为 L r L s ； r s是正则式，相应的正规集为 L r L s ； r *是正则式，相应的正规集为 L r * ； 2.7.1 正则表达式与正则文法 将正则文法转换成正则表达式 将正则表达式转换成正则文法 The end.