编译原理ch2.ppt

2020 1 25 华东师大计算机科学技术系 1 第二章文法与语言的基本知识 2 1概述程序设计语言是一种形式语言 与自然语言既有相似的性质又有本质的不同 最主要的区别是 形式语言的规则简单 严格 无例外 无二义性 编译程序的正确转换建立在对程序设计语言的精确定义和描述基础上 语法 文法是描述语言语法的形式规则语义 语言中各语句的含义语用 从使用者的角度对语言的描述本章将介绍形式语言和形式文法的基本概念 这是整个编译原理的基础 2020 1 25 华东师大计算机科学技术系 2 基本概念 2 2基本概念2 2 1符号与符号串用程序语言书写的程序一般由一些基本符号组成 下面是一些常见的基本符号 字母 a b c x y z数字 0 1 9其他符号 等在这些符号的基础上 组成如if then else for等关键字 程序的标识符和常量 并进一步组成用户程序 定义1符号的非空有限集合称为字母表 常用V 表示 2020 1 25 华东师大计算机科学技术系 3 符号与符号串 例1 1 0 1 1是二进制数的字母表 2 a b z 2是英文小写字母 3 A Z 0 9 3是FORTRAN4语言的字母表注意 符号可能是字符的组合如 5 ASCII码 则 为一个符号再如 pascal语言的 C语言的 等等 2020 1 25 华东师大计算机科学技术系 4 符号与符号串 定义2 字母表 符号的非空有限集合 V上的符号串的递归定义如下 空串 一个不含任何元素的符号串 是字母表V上的符号串 空串用希腊字母 表示 字母表V中任何一个元素a 是字母表V上的符号串 若x y是字母表V上的符号串 则它们的并置 将符号串y的符号依次写在符号串x后面所得的符号串 也是字母表V上的符号串 记以xy 注意 与 的不同 2020 1 25 华东师大计算机科学技术系 5 2 2 2符号串的运算符号串x中的元素的个数称为符号串x的长度 记以 x 设z xy是字母表V上的符号串 则x是符号串z的头 或符号串z的前缀 而y是符号串z的尾 或符号串z的后缀 若 x 1 则x是符号串z的头符号 同样 若 y 1 则y是符号串z的尾符号 注意 空串 是任何一个符号串的头和尾 当y 称x是z的真前缀 当x 称y是z的真后缀 并置 连接 是一种运算 满足结合律 但不满足交换律 2020 1 25 华东师大计算机科学技术系 6 例2 字母表 1 0 1 0 1 00 11 10 01 是 1上的符号串如x 1001y 010则连接xy 1001010yx 0101001都是 1上的符号串 x 4 y 3 1 10 100 1001都是x的头 1是x的头符号 1 01 001 1001都是x的尾 1是x的尾符号 1 10 100 1001都是x的前缀 1 10 100是真前缀1001 001 01 1 都是x的后缀 001 01 1 是真后缀 2020 1 25 华东师大计算机科学技术系 7 定义3 设A B是二个符号串集合 定义 A B a a A且a B A B a a A或者a B A0 An AAn 1 n 0 A A0 A1 A2 An 称为A的闭包A A1 A2 An 称为A的正闭包 2020 1 25 华东师大计算机科学技术系 8 由定义可知 A AA A A例3 令A 1 0 1 A 0 1 00 10 01 11 A 0 1 00 10 01 11 令A 3则任一FORTRAN4语言所编写的程序P 有P A 2020 1 25 华东师大计算机科学技术系 9 2 3文法和语言2 3 1文法形式语言是字母表V上所有符号串的集合 当该集合为有限集时可以枚举其全部句子 如为无限集则需找出句子的规律 用文法来表示 定义4 上下文无关文法G是一个四元组 G VT VN P 其中 VT是非空有限集合 元素称为终结符 VN是非空有限集合 元素称为非终结符 P是由产生式组成的非空有限集合 VN 是文法G的开始符号 常把文法G记为G 2020 1 25 华东师大计算机科学技术系 10 产生式 又称复写 产生规则 产生式是一有序对偶 U x 一般记以U x 或U x 其中 U称为产生式左部 x称为产生式的右部 符号 或 称为元符号含义为 由 构成 或 被定义为 记V VN VT一般要求 VN VT U V x V 特别 U VNx V 且至少在某产生式左部出现一次 称文法G 为上下文无关文法 2020 1 25 华东师大计算机科学技术系 11 例4 简单算术表达式文法G 定义为 VT i VN P i文法G是上下文无关文法 2020 1 25 华东师大计算机科学技术系 12 扩展的BNF表示 见P59 扩展的BNF BackusNaurForm 表示引入一些元符号 表示 或 对 x y 可表示为 x y z z 2020 1 25 华东师大计算机科学技术系 13 表示重复出现n次 如 表示 连续出现i次 0 与 等价 表示重复出现0次或1次 表示提取公共符号后留下的例6 与 等价 2020 1 25 华东师大计算机科学技术系 14 语言 2 3 2语言定义5 设G是一个文法 如果v xy w xuy其中 x y V 且 u P 则称字符串v直接推导出字符串w 有时候也称为w是v的一个直接推导 或者称w直接归约为v 记为v w 如果存在一个直接推导序列 v u0 u1 u2 un w 则称v推导出字符串w 或者称w归约为v 记为v w 若v w或v w 则为以v w 2020 1 25 华东师大计算机科学技术系 15 直接推导与推导 例7 设有文法G1 的产生式集P为 0 1 2 9对如下推导 0 02 028称这样的推导为最左推导 2 8 8 28 28 028称这样的推导为最右推导 2020 1 25 华东师大计算机科学技术系 16 直接推导与推导 最右推导又称规范推导 记为 规范推导的逆过程称为规范归约 R 2020 1 25 华东师大计算机科学技术系 17 句型 句子与语言 定义6 设G 是一文法 若 w w VN VT 则称w为文法G 一个句型 特别 若w VT 称w是文法G 一个句子 文法G 句子的全体所组成的集合称为该文法所产生的语言 记以L G 即L G w w 且w VT 例8 对例7的G1 0 028是文法的句型028是G1的一个句子 语言L G1 是什么 如何表示一个语言 2020 1 25 华东师大计算机科学技术系 18 语言 语言L G1 是一个具有无限多句子的集合 称为无限语言 可以用有限的集合的形式来定义一个无限多句子的语言 给定一个文法 就能唯一确定其语言 给定一种语言 能确定其对应的文法 但文法不唯一 对给定的文法G及任意的符号串w 能否用有限的方法来判定w是否是G的一个句子 句型 2020 1 25 华东师大计算机科学技术系 19 语言 语言L G 有无限多个句子 这与G的产生式集合P中某些产生式的递归性有关 1 若 P称为直接左递归若 P称为直接递归若 P称为直接右递归2 若 称为左递归若 称为递归若 称为右递归对文法G1 G2 如L G1 L G2 称文法G1 G2等价 2020 1 25 华东师大计算机科学技术系 20 短语与句柄 2 3 3短语与句柄定义7 设G 是一个文法 并设w xuy是该文法的一个句型 若 xy且 u 则称u为句型w xuy对非终结符的一个短语 若 xy且 u 则称u为句型w xuy相对于非终结符的一个简单 直接 短语 任何一个句型的最左简单短语称为柄短语 句柄 含有终结符的短语 并且不存在也具有这种性质真子串的短语称为素短语 2020 1 25 华东师大计算机科学技术系 21 P30习题22 12 22 32 42 72 10补充题 试为如下的语言构造二个 或二个以上的 等价文法 它们接受相同的语言 L1 a2nb n 1 L2 aibjck i j k 1 习题 2020 1 25 华东师大计算机科学技术系 22 语法树 推导树 2 4语法树与二义性2 4 1语法树 又称推导树 分析树 用特殊的树的形式来表示推导一个推导一棵推导树注意 这是一种专为推导的表示而设计的特殊的树 2020 1 25 华东师大计算机科学技术系 23 推导树的构造与表示方法 对文法G VT VN P 树的每个结点对应一个文法符号 v V 根结点是文法开始符号对 VN为标记的结点 其所有的子结点 若有的话 则从左至右标记为x1 x2 xn 且 x1 x2 xn P若某结点标记为 则必为叶结点 且为其父结点的唯一子结点 2020 1 25 华东师大计算机科学技术系 24 例1 表达式文法G i对句型i 的推导为 i i 2020 1 25 华东师大计算机科学技术系 25 对应的推导树为 注意推导树的特殊性 2020 1 25 华东师大计算机科学技术系 26 语法树与短语 使用推导树计算句型 句子 的短语简单 明了推导 xy u等价于 等价于 xyu 2020 1 25 华东师大计算机科学技术系 27 因此称u是句型xuy 对 的一个短语等价于 xyu 以为子树根的叶结点的全体 2020 1 25 华东师大计算机科学技术系 28 若子树高度为1 则u还是简单短语 最左简单短语为句柄 若u是含有终结符的最小的短语 则为素短语 句型最左边的素短语称为最左素短语 P72 例2 例1的文法G 和句型i 容易从推导树中看出 短语 i i 简单短语 i 句柄 i素短语 i 2020 1 25 华东师大计算机科学技术系 29 文法的二义性 2 4 2文法的二义性定义8 若文法G的一个句子有两棵 或两棵以上 的分析树 则称该句子是二义性的 若文法含有二义性句子 称该文法是二义性文法 否则称该文法是无二义的 例3 文法G1 i对句子i i i有两棵不同的推导树 2020 1 25 华东师大计算机科学技术系 30 文法的二义性 i i i 表示先 后 表示先 后 2020 1 25 华东师大计算机科学技术系 31 对文法的二义性讨论 一个句子有两棵不同的推导树 说明其含义 语义 是不唯一的 这给编译带来问题 不确定 对某些二义性文法 如果确定其中一种含义 语义 而排除另一种 或多种 含义 称为消除二义性规则 则可将其改造成等价的无二义性文法 例4 若规定先 后 及 都是左结合的 则文法G1 可改造为算术表达式文法G 这样句子i i i只能有一棵推导树 2020 1 25 华东师大计算机科学技术系 32 对文法的二义性讨论 续 对二义性文法所产生的语言 有的可找到等价的无二义性文法 因此只说文法的二义性 而不说语言的二义性 当然存在这样的语言 不存在它们的无二义性文法 例如 L aibjck i j或j k i j k 1 文法的二义性是不可判定的 即不存在一种算法能在有限步内判定该文法是否是二义性的 通常的做法是 找出无二义性文法的一个充分条件 即满足条件的一定是无二义性文法 2020 1 25 华东师大计算机科学技术系 33 形式语言分类 2 5形式语言分类1956年Chomsky将文法分成四类 0型 1型 2型和3型文法G VT VN P VN VT V VN VT P中产生式的一般形式是 V 至少含有一个非终结符 V 可以是空串 称文法G为0型文法 短语结构文法 2020 1 25 华东师大计算机科学技术系 34 形式语言分类 在0型文法的基础上 再规定 中至少含有一个非终结符 不能为 称文法G为1型文法 上下文有关文法 等价定义 w z w zw z V VN V 2020 1 25 华东师大计算机科学技术系 35 形式语言分类 在0型文法的基础上 再规定 其中 VN V 称文法是2型文法 上下文无关文法 任何含有 的产生式 称为 产生式 的文法不是1型文法 但是含有 产生式的2型文法可以转化为不含 产生式的2型文法 转化前后的两个文法所生成的语言至多相差一个 2020 1 25 华东师大计算机科学技术系 36 例1 试将如下的含有 产生式的上下文无关文法 2型文法 G 转换成等价的不含 产生式的上下文无关文法 a b c 解 引入非终结符与 表示不可空 而表示可空 随后消除可空的产生式以及在产生式的右部去除非终结符即可 因此G 可等价表示为 a a b c 2020 1 25 华东师大计算机科学技术系 37 最后得到等价的无 产生式的文法G1 为 a a b c注意 两文法不同 但等价 语言相同 问题 什么情况下转换前后的二个文法的语言会相差 呢 2020 1 25 华东师大计算机科学技术系 38 在2型文法的基础上 再规定 产生式形式是 x x VN x VT 则称文法是右线性文法 若规定 x VT即 a b VN a b VT则称文法是3型文法 正则文法 正则文法也可以是左线性文法的特例 适当地引入新的非终结符可以把一个右线性文法转换为等价的正则文法 2020 1 25 华东师大计算机科学技术系 39 例2 试将如下文法G 转换为等价的正则文法 3型文法 a abb A c a解 按正则文法的定义 只需对产生式 进行等价变换 对产生式 用 a b b来替代 2020 1 25 华东师大计算机科学技术系 40 对产生式 则用 a c a来替代 因此与G 等价的正则文法G1 为 a a c a a c a b b其中 是新引入的非终结符 2020 1 25 华东师大计算机科学技术系 41 实用限制 文法的实用限制从实用的角度一般规定 文法中不含任何如下形式的产生式 是可达的 即从开始符号出发 存在推导 V 是有用的 即存在终结符号串 VT 使得 2