第二章 文法与语言.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 x A y B 即A中的任意符号串和B中的任意符号串的连接所构成的集合 因为有x x x 所以有 A A A 符号串集合的方幂 即同一个符号串集合的乘积 例 设A为符号串集合 则A0 A1 A A2 AA 符号串集合的闭包设A为符号串集合 则A的闭包表示为A 其定义为 A的若干次幂 包括0次幂 的并集 它表示符号串集合A上的所有可能的符号串 含 的集合 A A0 A1 A2 An 符号串集合的正闭包 A的正闭包表示为A 其定义为 A的若干次幂 不包括0次幂 的并集 它表示符号串集合A上的所有可能的符号串 不含 的集合 A A1 A2 An显然有A A0 A A A AA A A 2 2文法和语言 语言是特定字母表上具有一定语法结构的符号串的集合 若用L表示语言 用 表示字母表 则L 文法 Grammar 是定义或描述语言的语法结构的一组形式规则 即语法规则 一个程序语言的文法的目的就是用适当条数的规则把该程序语言全部成分描述出来 2 2 1文法及文法的BNF表示 1 规则即产生式 是一有序对 U x 通常记为U x 或U x 其中U为规则的左部 是一个符号 x为规则的右部 为有穷符号串 规则U x表示符号U由符号串x组成 或符号U定义为符号串x 2 文法和字汇表文法可以定义成一个四元组G S VN VT S P 其中 VT 非空有限的终结符号集 VN 非空有限的非终结符号集 S 开始符号 是文法G规定的最终目标 P 产生式的集合 V VN VT称为文法G S 的字汇表 VN VT S VN 为了方便 表示文法时只列出产生式 而不以4元组显示地表示出来 3 文法的BNF 巴科斯范式 表示即在规则中引入或者符号 将左部相同的规则缩写到一起 4 递归规则和递归文法左部和右部含有相同非终结符号的规则称为递归规则 至少含有一条递归规则的文法称为递归文法 2 2 2推导和归约 设文法G VN VT P S U u是其中的产生式 是文法任意的符号串 则有 U u 其中符号 仅表示 一步推导 即利用产生式对左边符号串中的一个非终结符进行替换 得到右边的符号串 我们称 U 直接推导出 u 也可以说 u 直接归约到 U 如果有直接推导序列 a0 a1 a2 an则说a0推导出an推导 记作 我们称这个序列是一个从到的长度为n的推导 其中表示0步或多步推导 最左 最右推导和规范推导 1 在xUy xuy直接推导中 即U是符号串xUy中最左非终结符 则称此直接推导为最左直接推导 若一个推导的每一步直接推导都是最左直接推导 那么此推导称为最左推导 2 在xUy xuy直接推导中 即U是符号串xUy中最右非终结符 则称此直接推导为最右直接推导 若一个推导的每一步直接推导都是最右直接推导 则称此推导为最右推导 最右直接推导又称为规范直接推导 最右推导又称为规范推导 最左推导的逆过程是最右归约 最右推导的逆过程是最左归约 2 2 3句型 句子和语言 等价文法 设G1和G2是两个不同的文法 若L G1 L G2 则称文法G1和G1为等价文法 2 2 4文法的递归 如果文法G S 至少含有一个递归的非终结符号 则称此文法为递归文法 2 2 5短语 简单短语 句柄 短语 简单短语 句柄 2 3语法树 在自然语言中 可通过树型表示直观地分析句子结构 在形式语言中 则是通过语法树直观地分析文法的句型结构 1 语法树 设文法G VN VT P S 对于文法G的任意一个句型都存在一个相应的语法树 树中每个结点都有一个标记 该标记是VNVT中的一个符号 树的根结点标记是文法的识别符号S 若树的一个结点至少有一个叶子结点 则该结点的标记一定是一个非终结符 若树的一个结点有多个叶子结点 该结点的标记为A 这些叶子结点的标记从左到右分别是B1 B2 Bn 则 A B1B2 Bn P 语法树的任一非叶结点连同它射下的部分称为语法树的子树 仅有父子两代的子树称为简单子树 语法树每一子树的末端结点从左到右排列起来所组成的符号串 是该句型相对与该子树根的短语 语法树每一简单子树的末端结点从左到右排列起来所组成的符号串 是该句型相对与该简单子树根的简单短语 语法树的最左简单子树的末端结点从左到右排列起来所组成的符号串 是该句型的句柄 2 语法树与短语 简单短语 句柄的关系 例已知算术表达式G E E E T TT T F FF E i通过语法树求句型F i F的短语 简单短语和句柄 3 二义性定义 一个文法 如果它的一个句子有两棵或两棵以上的语法树 则称此句子具有二义性 如果一个文法含有二义性的句子 则该文法具有二义性 例设有文法G E E E E E E E i求句子i i i的最左推导及其对应的语法树 文法二义性的判定 1 有些文法是非二义性 比如LL 1 文法 LR文法 算符优先文法 而且这些文法都是可以判定的 所以只要我们能够证明文法是属于上述某类文法 则该文法必然是非二义性的 2 如果一个文法既有左递归 又有右递归的非终结符号A 则文法必然是二义性的 值得注意的是 没有一种算法 能在有限的步骤内确切的判断一个文法是否是二义性的 文法二义性与语言的二义性关系 如果一个二义性的文法 我们可以把它变换成一个等价的但无二义性的文法 那么我们可以认为该二义性文法对应的语言中 某些句子的二义性完全是二义性文法所带来的 而语言本身是非二义性的 如果一个语言 根本就不存在非二义性的文法 则这样的语言为二义性的语言 2 4文法的扩充BNF表示和语法图 2 5文法的实用限制 2 5 1有害规则定义 文法中形如U U的规则就称为有害规则 如果文法中含有有害规则 它除了造成文法的二义性以外 对定义语言则是没有任何的意义 2 5 2多余规则定义 设文法中某一规则 其左部的非终结符号为U 若满足下列条件之一 则称该规则为多余规则 U 除文法的开始符号 不出现在该文法的任何其它规则的右部 若在规则中采用该规则 则不能由U推出终结符号串 2 5 3文法的实用限制文法的实用限制主要指 文法不含有害规则 文法不含多余规则 在具体应用中 可能还会有其他限制 比如 文法不含左递归 文法不含空规则 U 1 文法的 规则的消除 规则 即形如U 的空符号串规则 文法 规则消除的前提条件 该文法所定义的语言L G S 不含 消除文法G S 的 规则的算法 求出文法中所有能导出空符号串 的非终结符号的集合EMPTY G S 删除文法中所有 规则 删除文法中只能导出空符号串的非终结符 若文法中某规则右部含有属于EMPTY G S 的非终结符 则需扩展该规则 注意 文法的 规则消除后 不能包含有害规则和多余规则 如果有 则应该把它们去掉 2 5 4文法的变换 2 文法直接左递归的消除只要修改形如U Ux y的规则 使文法不含直接左递归的非终结符号 便可消除这类文法的左递归 具体有以下两种方法 1 采用EBNF表示法可消除文法的直接左递归 形如U Ux y的规则 采用EBNF的花括号 表示 变可得到 U y x 2 引入新的非终结符号消除文法中的直接左递归 形如U Ux1 Ux2 Uxm y1 y2 ym的规则 可引入一个新的非终结符U 则得到等价的规则 U y1U y2U ymU U x1U x2U xmU 3 文法一般左递归的检测和消除文法的递归性除了由直接左递归的非终结符引起外 还可由间接左递归的非终结符引起 对于间接左递归 它不像直接左递归那样一目了然 要消除它 首先要解决的是如何判断 1 间接左递归的判断对于文法G S 和它的任意非终结符号U 如果U HEAD U U为左递归的非终结符号 G S 为左递归文法 其中 HEAD U 是指从非终结符U出发 能够推出的所有符号串中 处于符号串头部的非终结符号的集合 简称头符号集 求头符号集的一般算法 实际上 要判断一个文法是否具有递归性 只要找到一个递归的非终结符号就可以了 求头符号集HEAD U 的一般算法 设文法G S 不含空规则 并设初值HEAD U 为空集 则 考察文法所有规则 若文法中有形如U A 的规则 则A HEAD U 若P HEAD U 则HEAD P 中的任意非终结符号属于HEAD U 重复 直到HEAD U 不再增大为止 例G A A Bcd dDB AB bC cD AD DB Ca求所有非终结符号的头符号集 2 间接左递归的消除用如下算法可以消除文法的间接左递归 只不过要注意有一个前提条件 该文法无回路 并且不含 规则 算法如下 将文法G S 的所有非终结符号按任意一种顺序排列为U1 U2 Ui Un 对于任意非终结符Ui的规则 如果存在形如Ui Ujy其中j i 则按如下方法改写Ui i从0开始 的规则 Uj x1 x2 xn则Ui x1y x2y xny当Ui的所有规则的右部都用其本身或排列在其后的非终结符开头 即使间接递归直接化 然后再消除Ui的直接左递归 直到所有的非终结符的规则改造完毕为止 例消除文法G A A Bcd dDB AB bC cD AD DB Ca的左递归 2 6文法和语言的分类 0型文法与0型语言1型文法与1型语言2型文法与2型语言3型文法与3型语言 0型文法 0型文法 无限制的文法 其产生式具有以下形式 其中 V 且至少含有一个非终结符 V 1型文法 上下文有关文法 1型文法G的产生式具有以下形式 xUy xuy其中x y V U VN u V 例如 1型文法G S VN VT P S 其中 VN S X Y Z VT x y z P S xSYZ xYZ xY xy yY yy yZ yzZY YZ zZ zz 2型文法 上下文无关文法 在1型文法的产生式中上下文x和y用空符号串 代替 则有以下形式的产生式称为2型文法 U u其中 U VN u V 例如 2型文法G E VN VT P E 其中 VN E T F VT i P E E T T T T F F F E i 3型文法 如果的产生式只含有下面的两种形式 U a或U aB其中U B VN a VT 则称该文法为右线性文法 如果文法的产生式只含有下面的两种形式 U a或U Ba其中U B VN a VT 则称该文法为左线性文法例如 右线性文法G S VN VT P S 其中 VN S A B VT 0 1 P S 0 1 1A 0B A 1A 0B B 0 1 0B 2 7正则表达式与正则集 2 7 1正则表达式与正则集正则表达式也称为正则