编译原理第03章 文法和语言ppt课件.ppt

1 编译原理文法和语言 Tel 7046821E mail 2 第三章文法和语言 本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述 严谨 简洁 易读 形式工具 形式语言抽象地定义为一个数学系统 形式 是指这样的事实 语言的所有规则只以什麽符号串能出现的方式来陈述 3 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及其语法树3 6句型分析3 7实用说明 第三章文法和语言 4 文法的直观概念 一个程序设计语言是一个记号系统 如同自然语言一样 它的完整的定义应包括语法和语义两个方面 所谓一个语言的语法是指一组规则 用它可以形成和产生一个合适的程序 目前广泛使用的手段是上下文无关文法 即用上下文无关文法作为程序设计语言语法的描述工具 语法只是定义什么样的符号序列是合法的 与这些符号的含义毫无关系阐明语法的一个工具是文法 这是形式语言理论的基本概念之一 示例 汉语句子的描述语言概述 5 汉语句子的描述 语法规则定义字符串的判断 6 语法规则定义 句子 主语 谓语 主语 代词 名词 代词 我 你 他 名词 王明 大学生 工人 英语 谓语 动词 直接宾语 动词 是 学习 直接宾语 代词 名词 7 字符串的判断 有了一组规则以后 按照如下方式用它们导出句子 开始去找 左端的带有 句子 的规则并把它由 右端的符号串代替 这个动作表示成 句子 主语 谓语 然后在得到的串 主语 谓语 中 选取 主语 或 谓语 再用相应规则的 右端代替之 比如 选取了 主语 并采用规则 主语 代词 那么得到 主语 谓语 代词 谓语 重复做下去 句子 我是大学生 的全部动作过程是 句子 主语 谓语 代词 谓语 我 谓语 我 动词 直接宾语 我是 直接宾语 我是 名词 我是大学生 8 字符串的判断 我是大学生 的构成符合上述规则 而 我大学生是 不符合上述规则 我们说它不是句子 这些规则成为我们判别句子结构合法与否的依据 换句话说 这些规则看成是一种元语言 用它描述汉语 这里仅仅涉及汉语句子的结构描述 其中一种描述元语言称为文法 9 符号和符号串 定义 符号 可以相互区别的记号 元素 字母表 符号 元素 的非空有穷集合 符号串 由字母表 中的符号组成的任何有穷序列称为该字母表上的符号串 1 空符号串 没有符号的符号串 是 上的符号串2 若x是 上的符号串 a是 的元素 则xa是 上的符号串3 y是 上的符号串 当且仅当它可以由1和2导出 例如 a b a b aa ab aabba 都是 上的符号串符号串的运算 10 符号串的运算 既然将语言定义为一个集合 那么有关集合的运算也适合语言 即 设L是 上的 一个语言 M是 上的 一个语言 则语言L和M的并 交 差 补是一个语言 符号串的头 尾 子串符号串的长度符号串的连接符号串的方幂符号串的集合 11 符号串的头 尾 子串 符号串s的头 前缀 移走符号串s尾部的零个或多于零个符号得到的符号串 如 b是符号串banana的一个前缀 符号串s的尾 后缀 删去符号串s头部的零个或多于零个符号得到的符号串 如 nana是符号串banana的一个后缀 符号串s的子串 从s中删去一个前缀和一个后缀得到的符号串 如 ana是符号串banana的一个子串 对于每个符号串s s和 两者都是符号串s的前缀 后缀和子串 符号串s的真前缀 真后缀 真子串 任何非空符号串x 相应地 是s的前缀 后缀或子串 并且s x 12 符号串中符号的个数 符号串s的长度记为 s 的长度为0 符号串的长度 13 符号串的连接 设x y是符号串 则x y的连接是把y的符号写在x的符号之后得到的符号串xy如x ab y cd则xy abcd有 a a 14 符号串的方幂 方幂 设x是符号串 把x自身连接n次得到的符号串z 即z aa aa称为符号串x的方幂 写作z an示例 a1 a a2 aaa0 15 符号串集合 若集合A中所有元素都是某字母表 上的符号串 则称A为字母表 上的符号串集合 两个符号串集合A和B的乘积定义为 AB xy x A且y B 若集合A ab cde B 0 1 则AB ab1 ab0 cde0 cde1 使用 表示 上的所有有穷长符号串 包括 组成的集合 称为 的闭包 上的除 外的所有符号串组成的集合记为 称为 的正闭包 0 1 2 n 1 2 n 16 文法和语言的形式定义 文法和语言的形式定义文法的定义推导的定义句型 子 的定义语言的定义文法等价的定义 17 语言概述 语言是由句子组成的集合 是由一组符号所构成的集合 汉语 所有符合汉语语法的句子的全体英语 所有符合英语语法的句子的全体每个句子构成的规律语言研究每个句子的含义每个句子和使用者的关系每个程序构成的规律研究程序设计语言每个程序的含义每个程序和使用者的关系语法Syntax语言研究的三个方面语义Semantics语用Pragmatics 18 程序设计语言 研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics 19 语言研究的三个方面 语法 表示构成语言句子的各个记号之间的组合规律语义 表示各个记号的特定含义 各个记号和记号所表示的对象之间的关系 语用 表示在各个记号所出现的行为中 它们的来源 使用和影响 每种语言具有两个可识别的特性 即语言的形式和该形式相关联的意义 语言的实例若在语法上是正确的 其相关联的意义可以从两个观点来看 其一是该句子的创立者所想要表示的意义 另一是接收者所检验到的意义 这两个意义并非总是一样的 前者称为语言的语义 后者是其语用意义 幽默 双关语和谜语就是利用这两方面意义间的差异 20 文法的定义 文法G定义为四元组 VN VT P S 其中VN为非终结符号 或语法实体 或变量 集 VT为终结符号集 P为产生式 也称规则 的集合 VN VT和P是非空有穷集 S称作识别符号或开始符号 它是一个非终结符 至少要在一条产生式中作为左部出现 VN和VT不含公共的元素 即VN VT 通常用V表示VN VT 称为文法G的字母表或字汇表 规则 也称重写规则 产生式或生成式 是形如 或 的 有序对 其中 是字母表V的正闭包V 中的一个符号 是V 中的一个符号 称为规则的左部 称作规则的右部 示例 例3 1例3 2 21 例3 1 文法G VN VT P S VN S VT 0 1 P S 0S1 S 01 这里 非终结符集中只含一个元素S 终结符集由两个元素0和1组成 有两条产生式 开始符号是S 22 例3 2 文法G VN VT P S 其中VN 标识符 字母 数字 VT a b c x y z 0 1 9 P 标识符 字母 标识符 标识符 字母 标识符 标识符 数字 字母 a 字母 b 字母 z 数字 0 数字 1 数字 9 S 标识符 这里 使用尖括号 和 括起非终结符 23 推导的定义 直接推导 如 是文法G Vn VT P S 的规则 或说是P中的一产生式 和 是V 中的任意符号 若有符号串v w满足 v w 则说v 应用规则 直接产生w 或者说 w是v的直接推导 也可以说 w直接归约到v 记作v w 如果存在直接推导的序列 示例 直接推导多步推导 24 直接推导的示例 对于例3 1的文法G 可以给出直接推导的一些例子如下 v 0S1 w 0011 直接推导 0S1 0011 使用的规则 S 01 这里 0 1 v S w 0S1 直接推导 S 0S1使用的规则 S 0S1 这里 v 0S1 w 00S11 直接推导 0S1 00S11 使用的规则 S 0S1 这里 0 1 对于例3 2的文法G 直接推导的例子有 v 标识符 w 标识符 字母 直接推导 标识符 标识符 字母 使用的规则 标识符 标识符 字母 这里 v 标识符 字母 数字 w 字母 字母 数字 直接推导 标识符 字母 数字 字母 字母 数字 使用的规则 标识符 字母 这里 字母 数字 v abc 数字 w abc5 直接推导 abc 数字 abc5 使用的规则 数字 5 这里 abc 25 多步推导的示例 对例3 1的文法 存在直接推导序列v 0S1 00S11 000S111 00001111 w 即0S100001111 也可记作0S100001111对例3 2的文法 存在直接推导序列v 标识符 标识符 数字 字母 数字 x 数字 x1 w 即x1 也可记作x1 26 句型 子 的定义 设G S 是一文法 如果符号串x是从识别符号推导出来的 即有Sx 则称x是文法G S 的句型 若x仅由终结符号组成 即Sx x VT 则称x为G S 的句子 例 S 0S1 000111都是例3 1的文法G的句型 其中000111是G的句子 标识符 字母 字母 数字 a1等都是例3 2文法G的句型 其中a1是G的句子 27 语言的定义 文法G所产生的语言定义为集合 x Sx 其中S为文法识别符号 且x VT 可用L G 表示该集合 从定义可以看出两点 第一 符号串x可从识别符号推出 也即x是句型 第二 x仅由终结符号组成 即x是文法G的句子 也就是说 文法描述的语言是该文法一切句子的集合 例 例3 1G S 0S1 S 01L G 0n1n n 1 例3 3 28 例3 3 设G VN VT P S VN S B E VT a b e P由下列产生式组成 1 S aSBE 2 S aBE 3 EB BE 4 aB ab 5 bB bb 6 bE be 7 eE ee则L G anbnen n 1 29 文法的等价 若L G1 L G2 则称文法G1和G2是等价的 示例 文法G1 A A 0RA 01R A1与G2 S S 0S1S 01等价 30 文法的类型 乔姆斯基分类示例 例3 4例3 5乔姆斯基分类文法之间关系对应于乔姆斯基分类文法的语言文法和语言之间的关系 31 乔姆斯基对文法的分类 通过对产生式施加不同的限制 Chomsky 乔姆斯基 将文法分为四种类型 0型文法 对文法G VN VT P S 的任一产生式 都有 VN VT 且至少含有一个非终结符 VN VT 1型文法 上下文有关文法 对文法G VN VT P S 的任一产生式 都有 仅仅S 除外 2型文法 上下文无关文法 对文法G VN VT P S 的任一产生式 都有 VN VN VT 3型文法 正规文法 设G VN VT P S 若P中的每一个产生式的形式都是A aB或A a 其中A和B都是非终结符 a是终结符 3型文法G VN VT P S 的P中的规则有两种形式 一种是前面定义的形式 即 A aB或A a其中A B VN a VT 另一种形式是 A Ba或A a 前者称为右线性文法 后者称为左线性文法 正规文法所描述的是VT 上的正规集 32 例3 4 G S A B a b P S 其中P由下列产生式组成 S aBA bAAS bAB bA aB bSA aSB aBB或将P改写为 S aB bAA bA aA a A aSB bS B aB b则G是正规文法或3型文法 33 例3 5 文法G S A B 0 1 P S 其中P由下列产生式组成 S 0AA 1BS 1BB 1BS 0B 1A 0AB 0A 0S或将P改写为 S 0A 1B 0A 0S 1B 0AB 1B 1 0则G是正规文法或3型文法 34 乔姆斯基分类文法之间关系 2型文法 1型文法 0型文法 四种文法之间的逐级 包含 关系 3型文法 35 对应乔姆斯基分类文法的语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法 CSG 产生的语言称为1型语言或上下文有关语言 CSL 2型文法或上下文无关文法 CFG 产生的语言称为2型语言或上下文无关语言 CFL 3型文法或正则 正规 文法 RG 产生的语言称为3型语言正则 正规 语言 RL 36 文法和语言之间的关系 四种文法之间的关系是将产生式做进一步限制而定义的 语言之间的关系依次 有不是上下文有关语言的0型语言 有不是上下文无关语言的1型语言 有不是正则语言的上下文无关语言 37 上下文无关文法及其语法树 语法树句型能够构造关联语法树的条件示例 例3 7最左 右 推导二义性文法判断依据示例 例3 8二义性文法与二义性语言的区别 38 句型能够构造关联语法树的条件 给定文法G VN VT P S 对于G的任何句型都能构造与之关联的语法树 推导树 这棵树满足下列4个条件 每个结点都有一个标记 此标记是V的一个符号 根的标记是S 若一结点n至少有一个它自己除外的子孙 子结点 并且有标记A 则A肯定在VN中 如果结点n的直接子孙 从左到右的次序是结点n1 n2 nk 其标记分别为A1 A2 Ak 那么A A1A2 Ak一定是P中的一个产生式 39 例3 7 G S A a b P S 其中P为 S aAS A SbA A SS S a A ba右图是G aabbaa 的一棵推导树 40 最左 右 推导 如果在推导的任何一步 其中 是句型 都是对 中的最左 最右 非终结符进行替换 则称这种推导为最左 最右 推导 在形式语言中 最右推导常被称为规范推导 由规范推导所得的句型称为规范句型 最左推导示例S aAS aSbAS aabAS aabbaS aabbaa最右推导示例S aAS aAa aSbAa aSbbaa aabbaa 41 二义文法的判断依据 若一个文法存在某个句子对应两棵不同的语法树 则称这个文法是二义的 或者 若一个文法存在某个句子有两个不同的最左 右 推导 则称这个文法是二义的 如果产生上下文无关语言的每一个文法都是二义的 则说此语言是先天二义的 判定任给的一个上下文无关文法是否二义 或它是否产生一个先天二义的上下文无关语言 这两个问题是递归不可解的 即 不存在一个算法 它能在有限步骤内 确切判定任给的一个文法是否为二义的 我们所能做的事是为无二义性寻找一组充分条件 当然它们未必都是必要的 42 例3 8 文法G E i P E 其中P E iE E EE E EE E 是二义性的 假若规定了运算符 与 的优先顺序和结合规则 即按惯例 让 的优先性高于 且它们都服从左结合 那么就可以构造出一个无二义文法 定义表达式的无二义文法G E E T E TT F T FF E i它和上述文法产生的语言是相同的 即它们是等价的 43 二义性文法与二义性语言的区别 文法的二义性和语言的二义性是两个不同的概念 因为可能有两个不同的文法G和G 其中G是二义的 但是却有L G L G 也就是说 这两个文法所产生的语言是相同的 44 句型的分析 句型分析是识别一个输入符号串是否为语法上正确的程序的过程 在语言的编译实现中 把完成句型分析的程序称为分析程序或识别程序 分析算法又称识别算法 从左到右的分析算法 即总是从左到右地识别输入符号串 首先识别符号串中的最左符号 进而依次识别右边的一个符号 直到分析结束 句型的分析算法分类句型的分析算法反映语法树的构造过程句型分析的有关定义句型分析的有关问题 45 句型的分析算法分类 自上而下分析法 是从文法的开始符号出发 反复使用各种产生式 寻找 匹配 于输入符号串的推导 示例 例3 9自下而上分析法 从输入符号串开始 逐步进行 归约 直至归约到文法的开始符号 示例 46 两种方法反映语法树的构造过程 自上而下方法 自上而下方法是从文法符号开始 将它做为语法树的根 向下逐步建立语法树 使语法树的末端结点符号串正好是输入符号串 自下而上方法 自下而上方法是从输入符号串开始 以它做为语法树的末端结点符号串 自底向上地构造语法树 47 例3 9 自上而下分析 例 考虑文法G S S cAd A ab A a识别输入串w cabd是否该文法的句子 推导过程 S cAd cabd 48 示例 自下而上分析 例 考虑文法G S S cAd A ab A a识别输入串w cabd是否该文法的句子 SAAcabdcabdcabd规约过程构造的推导 cAd cabdS cAd 49 句型分析的有关定义 令G是一文法 S是文法的开始符号 是文法G的一个句型 如果有 S A 且A 则称 是句型 相对于非终结符A的短语 特别 如有A 则称 是句型 相对于规则A 的直接短语 也称简单短语 一个句型的最左直接短语称为该句型的句柄 示例从句型的推导树中查找方法 50 示例 文法G E 的一个句型i i i 为了叙述方便 将句型改写为i1 i2 i3 因为有 EF i2 i3且F i1则称i1是句型i1 i2 i3的相对于非终结符F的短语 也是相对于规则F i的直接短语 又有 Ei1 F i3且F i2则i2是句型i1 i2 i3的相对于F的短语 也是相对于规则F i的直接短语 还有 Ei1 i2 F且F i3则i3也是句型i1 i2 i3的相对于F的短语 也是相对于规则F i的直接短语 ET i2 i3 且Ti1则i1是句型i i2 i3的相对于T的短语 Ei1 i2 T且Ti3则i3是句型i1 i2 i3的相对于T的短语 EE i3且Ei1 i2则i1 i2是句型i1 i2 i3的相对于E的短语 EE且E i1 i2 i3则i1 i2 i3是句型i1 i2 i3相对于E的短语 即i1 i2 i3 i1 i2和i1 i2 i3都是句型i1 i2 i3的短语 而且i1 i2 i3均为直接短语 其中i1是最左直接短语 即句柄 虽然i2 i3是句型i1 i2 i3的一部分 并不是它的短语 因为尽管有Ei2 i3 但不存在从文法开始符号E到i1 E的推导 51 从句型的推导树中查找方法 从句型的推导树上很容易找出句型的短语和直接短语 设A是句型 的某一子树的根 其中 是形成此子树的末端结点的符号串 则其中 是句型 的相对于A的短语 若这个子树只有一层分支 则 是句型 的直接短语 示例 52 示例 推导树中找短语 53 句型分析的有关问题 在自上而下的分析方法中如何选择使用哪个产生式进行推导 假定要被代换的最左非终结符号是B 且有n条规则 B A1 A2 An 那么如何确定用哪个右部去替代B 在自下而上的分析方法中如何识别可归约的串 在分析程序工作的每一步 都是从当前串中选择一个子串 将它归约到某个非终结符号 该子串称为 可归约串 存在确定和不确定分析 54 实用说明 有关文法的实用限制上下文无关文法中的 规则无用符号和无用产生式的消除 产生式的消除单产生式的消除 55 有关文法的实用限制 在实用中 我们将限制文法中不得含有有害规则和多余规则 有害规则 是指形为U U的产生式 它对描述语言显然是没有必要的 说它有害 是说它只会引起文法的二义性 多余规则 是指文法中那些连一个句子的推导都用不到的规则 这类规则在文法中以两种形式出现 一种是文法中某些非终结符不在任何规则的右部出现 所以任何句子的推导中不可能用到它 对文法G VN VT P S 来说 为了保证其任一非终结符A在句子推导中出现 必须满足如下两个条件 A必须在某句型中出现 即有S A 其中 属于 VT VN 必须能够从A推出终结符号串t来 即At 其中t VT 若程序设计语言的文法包含有多余规则时 其中必定有错误存在 因此检查文法是否包含多余规则是很有必要的 56 上下文无关文法中的 规则 上下文无关文法中某些规则可具有形式A 称这种规则为 规则 规则会使得有关文法的一些讨论和证明变得复杂 有时会限制这种规则的出现 上下文无关文法的相关定理定理3 1定理3 2 57 定理3 1 若L是由文法G VN VT P S 产生的语言 P中的每一个产生式的形式均为A 其中A VN VN VT 即 可能为 则L能由这样一种文法产生 每一个产生式或者为A 形式 其中A VN VN VT 即 或者S 且S不出现在任何产生式右边 58 定理3 2 如果G VN VT P S 是一个上下文有关文法 则存在另一个上下文有关文法G1 它所产生的语言与G产生的相同 即L G L G1 其中G1的开始符号不出现在G1的任何产生式的右边 若G为上下文无关文法或正规文法 类似结论成立 59 无用符号和无用产生式的消除 定义 设G VN VT P S 是一文法 我们说G中的一个符号x VN VT 是有用的指x至少出现在一个句子的推导过程中 即x必须同时满足以下两个条件 存在 V 有S x 存在w VT x w否则就说x是无用的 如果一个产生式的左部或右部含有无用符号 则此产生式称之为无用产生式 消除算法算法1算法2示例 60 算法1 1 分别置VN 1 和P 1 为 2 对于P中的每一产生式A 若 VT 则将A置于VN 1 中 3 对于P中的每一产生式A x1x2 xm若每个xi都属于VN 1 或VT 则将A置于VN 1 4 重复步骤3 直到VN 1 不再增大为止 5 对于P中的每一产生式B y1y2 yn 若B及每一个yi都属于VN 1 VT 则将此产生式B y1y2 yn置于P 1 61 算法2 1 分别置VN VT 和P 为 2 将文法的开始符号S置入VN 中 3 对于G 1 中任何形如A x1 x2 xm的产生式 若A VN 则将符号串x1 x2 xm中的全部非终结符号置于VN 中 而将其中的全部终结符号置于VT 中 4 重复步骤3 直到VN 和VT 都不再增大为止 5 将P中左右部仅含VN VT 中符号的所有产生式置P 62 示例 文法的定义已知文法G S U V W a b c P S 产生式P的组成如下 S aSS WS UU aV bVV acW aW执行算法1执行算法2 63 执行算法1 第一步 由于产生式U a V ac的右部均为终结符号串 故置VN 1 U V 第二步 对于产生式S U 由于U VN 1 故将S置于中 所以VN 1 S U V 于是得到以下文法G1 G1 S U V a b c P 1 S 其中P 1 由如下产生式组成 S aSS UU aV bVV ac 64 执行算法2 第一步 置VN S 第二步 因为G1中含有产生式S U U a 故应将U a分别置于 即VN S U VT a 因此得到等价的且不含无用符号和无用产生式的文法为G2 S U a P S 其中 P 由如下产生式组成 S aSS UU a 65 产生式的消除 算法3算法4 不属于文法所产生的语言 算法5 属于文法所产生的语言 示例 不属于文法所产生的语言 属于文法所产生的语言 66 算法3 1 作集合W1 A 产生式A P 2 作集合序列WK 1 WKU B B P 且 WK K 1并使WK 1收敛 令W WK