编译原理-蒋立源第2章文法和语言.ppt

第二章文法和语言 编译过程的核心就是翻译 就是把一种语言翻译成为另一种语言 与自然语言的翻译类似 只不过其工作对象是某种程序设计语言 两个重要的前提 1 描述和定义程序设计语言2 识别或分析这种语言20世纪50年代 语言学家NoamChomsky 乔姆斯基 提出了一个用来描述语言的数学系统 把用一组数学符号和规则来描述语言的方式叫做形式描述 而把能用数学符号和规则描述的语言称为形式语言 这种理论对程序设计语言的设计和编译程序的构造有着重大的作用 程序设计语言就是形式语言 2 1文法及语言的表示 如何来描述一种语言 1 当一个语言仅含有有限个句子时 可采用枚举法来表示这种语言 对于无限的语言寻找出有限的表示 有两种途径 2 生成方式 文法 制定有限条规则 用来生成所要描述的语言中的全部句子 3 识别方式 自动机 建立一种装置 更确切的说 是构造一种算法或过程 此装置以某一字母表上的所有符号串作为输入 并识别这些符号串 当一个符号串是此字母表上某给定语言中的句子时 就接受它 反之 则拒绝接受 语言的定义 Webster定义 为相当大地区的公众所懂得并使用的 话 以及组成这些 话 的方法的统一体 另一种定义 某一字母表上符号串 句子 的集合 一种精确化的语言的要求 1 为所定义语言中的句子提供一种结构性的描述 2 提供一种手段 准确地判别什么是该语言的正确句子 而什么又不是 2 2 1基本概念和术语 字母表 元素的非空有穷集合 字母表中的每个元素称为 符号 因此 字母表 也可称为 符号集 典型的符号有字母 数字 各种标点符号和各种运算符 例如 集合 a b c 是一个含有5个符号的字母表 而字母表 0 1 只有2个符号 符号串 由字母表上0个或多个符号所组成的任何有穷序列 特别地 把不包含任何符号的符号串称为空符号串 例如有字母表 a b c 则a b c aa ab ac a a ba bb bc b b aaa bbb等等都是该字母表上的符号串 而所有二进制数都是定义在字母表 0 1 上的符号串 显然 一个字母表上的全部符号串所组成的集合是无穷的 2 2文法和语言的定义 符号串及其集合的运算1 1 符号串的长度 指符号串x中所含符号的个数 记为 x 如 abc 3 abc abc 8 2 符号串的前缀 指从符号串x的末尾删除0或多个符号后得到的符号串 如 a ab abc都是abc的前缀 符号串的后缀 指从符号串x的开头删除0或多个符号后得到的符号串 如 c bc abc都是abc的后缀 符号串的子串 指从符号串x的开头和末尾删除0或多个符号后得到的符号串 如abc的子串 符号串的前缀 后缀都是它的子串 a b c ab bc abc 0 符号串及其集合的运算2 3 符号串的连接 若x y是两个符号串 则xy表示连接 是将符号串y连接在符号串x的后面 若x y是字母表 上的两个符号串 则xy也是字母表 上的符号串 如 x ab y ba 那么xy abba注意 连接没有交换律 即xy yx对于空串 有 x x x符号串的方幂 一个符号串x与其自身的n 1次连接称为x的n次方幂 即 X0 x1 x x2 xx xn xx x xxn 1 xn 1x如 x abc x0 x1 abc x2 abcabc 符号串及其集合的运算3 4 符号串集合的乘积 令A B为两个符号串集合 A和B的乘积AB定义为 AB xy x A y B 例如 A a b B c d 则AB ac ad bc bd 对于 有 A A A符号串集合的方幂 设A为符号串集合 则A的方幂定义为 A0 A1 A A2 AA An AA A AAn 1 An 1A例如 A a b c A0 A1 a b c A2 AA aa ab ac ba bb bc ca cb cc 符号串及其集合的运算4 5 符号串集合的闭包 设A为一个集合 则集合A的正闭包用A 表示 定义为 A A1 A2 An 集合A的闭包用A 表示 定义为 A A0 A 例如 A a b c 则A a b c aa ab ac ba bb bc ca cb cc aaa aab A a b c aa ab ac ba bb bc ca cb cc aaa aab 可见 字母表A的正闭包A 就是由A中字母所构成的一切符号串的集合 而A 仅比A 多个 2 2 2文法和语言的形式定义 在学习英语时 我们知道句子由主语 谓语组成 主语由冠词 形容词及名词组成等等 这就是说明句子组成的规则 而在形式语言里 这种规则可采用 这种形式来表示 分析一个句子是否正确 就是根据这些规则进行的 实际上 文法就是描述语言语法结构的形式规则 从 产生语言 的角度出发 给出方法和语言的形式定义 产生语言 指制定出有限个规则 借助这些规则可以产生此语言的全部句子 文法形式定义1 在表示文法时 要说明语言的语法成分 语法范畴 句子中的符号以及语法结构 例如 能够描述句子 themonkeyateabanana 的文法如下 在这个文法里 其中用 符号括起来的部分 表示评议的一个语法实体 符号 是一个整体 其含义是 定义为 也就是左边的语法实体可进一步定义为右边的符号串 在推导过程中 就是一种 替换 关系 而像the ate banana这样的符号只在规则中 的右边出现 不需要进一步定义 这些符号不能用其它符号代替 我们最终需定义的语法成分是 每条规则的形式都是 1 2 the3 4 5 monkey6 banana7 ate8 has9 the10 a 表示 定义为 文法形式定义2 the the themonkey themonkeyate themonkeyatea themonkeyateabanana 如何用上述规则去产生或推导出相应语言的句子呢 themonkeyateabanana 表示一步推导 表示多步推导 文法形式定义3 文法的形式定义 文法可表示为一个四元组G S VN VT P S VN是一个非空有穷集合 该集合中的每个元素称为非终结符号 如上例中VN VT是一个非空有穷集合 该集合中的每个元素称为终结符号 如上例中VT monkey banana ate has the a 并且VN VT 而 VN VT称为该文法的字汇表 P是一个非空的有穷集合 它的每个元素叫做产生式或规则 产生式的形式为 或 是产生式的左部且不能为空 是产生式的右部 并且 V S是VN集合的一个特殊的非终结符号 称为文法的开始符号 它至少必须在某个产生式的左部出现一次 就是上例文法的识别符号 文法形式定义4 文法分4种类型 见2 5小节 程序设计语言文法主要为2型文法 这种文法也叫前后文无关文法 本书后面说的文法都是指这种文法 在前后文无关文法中 产生式的左部 是一个非终结符号 而右部 是由终结符号和非终结符号组成的有穷符号串 这样只要给出产生式集合 所有产生式的左部符号就构成了非终结符号集合VN 而只出现在产生式右部的那些符号构成终结符号集合VT 因此 在表示文法时只需给出规则集合并指定识别符号即可 为了进一步简化 在给出规则集时 可约定将左部符号为开始符号的规则作为规则集合的第一条规则 这样表示文法时只需给出规则的集合即可 显然 上例就是一个简化的文法表示 文法形式定义5 例2 2 有如下简化表示文法 只给出规则集 写出该文法的终结符号集合 非终结符号集合和开始符号 1 2 3 4 05 16 27 38 49 510 611 712 813 9 解 根据简化约定 可确定 非终结符号集合 VN 终结符号集合 VT 0 1 2 3 4 5 6 7 8 9 开始符号S 文法的EBNF表示 所谓文法的EBNF表示 就是在书写文法的规则时 可采用一些特殊的符号 和 和 和 来表示文法 这些符号叫做元符号 其中 和 和 和 这些元符号总是成对出现 下面介绍各种元符号的含义 1 元符号 表示 或 对于具有相同左部的那些规则如 1 n 可以缩写为 1 2 n例2 3 对例2 2文法的13条规则可缩写成 0 1 2 3 4 5 6 7 8 9 文法的EBNF表示 2 元符号 和 表示可重复连接 t nm表示符号串t可重复连接n到m次 而 t 表示符号串t可重复连接0到无穷次 例如 13与 相同E E T T与E T T 相同而字母打头 后面可跟数字或字母的不超过8个字符的标识符文法则为 07 文法的EBNF表示 3 元符号 和 表示括起的内容可有可无 如 t 表示符号串t可有可无 例如 IFTHEN IFTHENELSE可写成 IFTHEN ELSE 4 元符号 和 表示括号内的成分优先 常用于在规则中提取公因子 例如 U xy xw xz可写成 U x y w z 从上述有关元符号的定义和例子可看出 这些元符号为表示文法提供了很大方便 直接推导 设G S 是一文法 是该文法的一个产生式 对于符号串x y 其中x和y是该文法的任意符号串 可为空 推导就是用产生式 的右部替换左部 从而得到新的符号串x y 表示为 x y x y其中 表示一步推导 我们称x y直接推导出x y 或x y直接产生x y 若从反方向看 则称x y直接归约到x y x y V 直接推导 例如有文法1 2 3 0 1 2 3 4 5 6 7 8 9对符号串利用规则1可直接推导出 对符号串利用规则2可直接推导出 对符号串利用规则3可直接推导出2 2将上述三个推导连接起来 可得如下推导过程 2 推导 如果文法G S 存在一直接推导序列 0 1 n 其中n 0 那么我们说 0推导出 n或 n归约到 0 并记作 0 n 推导长度为n 如果有 0 n或 0 n 即n 0 则记作 0 n 可见 n 0的推导和n 0分别称为 推导 和 推导 例如 从开始 分别利用规则1 2 2 3 3 可产生如下推导过程 2 23这个推导过程可记作 23 其推导长度n 5 而从到的推导 无须使用任何规则 可记作 其推导长度n 0 句型和句子 推导产生的结果可能是句型 也可能是句子 设文法G的识别符号为S 则句型 句子的定义如下 1 如果S 且 V 则称 是文法G S 的一个句型 2 如果S 且 Vt 则称 是文法G S 的一个句子 从文法的开始符号利用规则进行推导 一旦推导出句子 推导过程就不能再继续进行 因为句子中没有非终结符号 假设符号串 是某一推导的结果 那么 是句子的必要条件是从S到 的推导长度大于等于 即S x 而不可能是S x 这是因为识别符号S是非终结符号 而 是终结符号串 显然 S不可能与 相等 所以S不可能经过 步推导就等于 为何这里是 推导 句型是从识别符号开始经过0步或多步推导出的可由终结符号和非终结符号组成的符号串而句子是从文法的识别符号推导出的完全由终结符号组成的符号串 句子是特殊的句型 是完全由终结符号组成的句型 语言 一个文法G S 所产生的所有句子的集合L G S 称为文法G S 所定义的语言 即 L G S x S x 且x Vt 一个文法所定义的语言是该文法的终结符号集合Vt上的所有符号串组成的集合的一个子集 该子集中的每个符号串都可从识别符号开始经过至少一步推导出来 即 L G S Vt 例如 对例2 1的文法G 其语言有16个句子 themonkeyatethebananathebananaatethemonkeythemonkeyatethemonkeythebananaatethebanana 而例2 3中的文法 其语言是所有无符号整数 句子是无穷的 文法和语言有如下关系 1 给定一个文法 就能从结构上唯一的确定其语言 即 G L G 2 给定一种语言 能确定其文法 但不唯一 即 L G1或G2或 语言 例2 4 已知文法G S 为 1 S aSb2 S ab或写成S aSb ab求该文法确定的语言 解 从识别符号开始推导 反复用规则1 最后用规则2可得 S aSb a2Sb2 an 1Sbn 1 anbn n 2 直接用规则2可得 S ab所以该文法确定的语言为 L G S anbn n 1 反之 试构造产生下列语言的文法 anbn n 0 S aSb 语言 例2 5 已知语言为 L G abna n 1 构造产生该语言的文法 解 根据语言的形式 可构造其文法G为 S aBaB Bb b还可以构造文法G1为 S aBaB bB b可见 G与G1是两个不同的文法 但它们都可以描述语 abna n 1 如果两个不同的文法可描述相同的语言 那么我们称这两个文法为等价文法 前后文无关文法的等价问题是不可判定的 等价文法的存在 对编译技术的实现有很大帮助 使我们能在不改变文法所确定的语言前提下 为了某种目的而改写文法 引理2 1设G Vn Vt P S 为一文法 并设A xBy是P中的一个产生式 而B 1 B 2 B k是P中的全部B 产生式 又设G1 Vn Vt P1 S 是这样的文法 其中 P1是从P中删去A xBy并添加产生式A x 1y A x 2y A x ky所组成的集合 则L G1 L G 递归规则与递归文法 递归规则是指在规则的右部含有与规则左部相同符号的规则 设文法G S x y是V上的符号串 若U xUy是文法的规则 且xy 则称U xUy为直接递归规则 称U为直接递归的非终结符 特别 若x 即这个相同的符号出现在右部的最左端 则为左递归规则 如U Uy若y 即这个相同的符号出现在右部的最右端 则为右递归规则 如U xU若文法G S 存在推导U xUy 则称U为递归的非终结符 给定了文法 就确定了语言 句子的个数是有穷还是无穷取决于文法是否是递归的 若文法G S 中至少包含一个递归的非终结符号 则称此文法是递归文法 递归文法使我们能用有穷的文法刻画无穷的语言 2 3句型的分析 所谓句型的分析 是指构造一种算法 用以判定给定的符号串是否为某一文法的句型 或句子 通常 句型分析的方法可大致分为两类 即自顶向下的分析和自底向上的分析 前者是从文法的开始符号出发 以给定的符号串为目标 试图推导出此符号串 后者恰好和前者相反 它从给定的符号串出发 反复用文法中规则的左部去替换当前符号串中的相应子串 以期最后 归约 到文法的开始符号 这与分析过程中构造句型相应语法树的方向有关 2 3 1规范推导 规范推导 最右推导 每步推导只替换最右边的非终结符号 定义为 对于直接推导xUy xuy来说 如果y只包含终结符号或为空符号串 那么就把这种推导称为规范推导或最右推导 如果 只包含终结符号或为空符号串 则为最左推导 且记作 xUy r xuy 其中y Vt 例2 6算术表达式文法G E E E T TT T F FF E i给出句子i i i的最左推导和最右推导 解 最左推导 E l E T l T T l F T l i T l i T F l i F F l i i F l i i i最右推导 E r E T r E T F r E T i r E F i r E i i r T i i r F i i r i i i 2 3 1规范推导 每一个句子都有一个规范推导 但并非每一个句型都有规范推导 只有那些能用规范推导产生的句型才是规范句型 例如 对于例2 3中的文法 有句型 2 其推导过程如下 2其中第3 步推导变换的不是最右边的非终结符号 不满足规范推导的要求 所以句型 2 不是规范句型 而对于句型 3 其推导过程如下 3 3其中的每一步推导都变换的是最右边的非终结符号 所以 句型 3 是规范句型 2 3 1规范推导 给定终结符号串w 通过语法分析判定w是否为某一语言L G 中的句子 自顶向下 试图为w建立一个从G的开始符号S到w的最左推导 显然 若某步推导中被替换的非终结符号U是由若干个后选式定义的 即有U 1 2 n 那么就会出现如何选用后选式的问题 一种办法是逐个用这些后选式试探 若用某个 i替换U能使分析继续 则沿此路径继续 若发现有错 则退回出错点再用下一个 i 1继续试探 故称为带回溯的自顶向下的分析方法 回溯效率低 应设法避免 2 3 1规范推导 自低向上 试图从w出发 以相反方向为w建立一个规范推导 从左到右扫视wi中各个符号 找到一个和G中某一产生式的右部相同的最左子串 用此产生式的左部替换此最左子串进行直接归约 例如符号串i i i的归约过程 最右推导 E r E T r E T F r E T i r E F i r E i i r T i i r F i i r i i i可见 最右 左 推导的逆过程是最左 右 归约 反之亦然 如何确定可归约的最左子串 2 3 2语法树和二义性 推导过程可用图来表示 这就是语法树 也叫分析树 语法树是一棵有序有向树 每个节点都有标记 根节点代表文法的识别符号 每个内部节点 非叶节点 表示一个非终结符号 其子节点由这个非终结符号在这次推导中所用产生式的右部各个符号代表的节点组成 每个末端节点 叶节点 代表终结符号或非终结符号 它们从左向右排列起来 构成句型 如果叶节点都是终结符号 则从左向右构成句子 推导过程不同 生成语法树的过程也不同 但最终生成的语法树是相同的 例2 8根据如下推导过程构造语法树 3 3 23 23 123 数字串 图2 1语法树 返回1 返回2 2 3 2语法树和二义性 算术表达式的运算规则是乘除高于加减 if语句规定else就近配对 为什么呢 这是为了解决文法的二义性问题 前面我们介绍语法树时说过 推导过程不同 生成语法树的过程也不同 但最终生成的语法树是相同的 这是在文法没有二义的条件下才成立 如果一个文法所定义的句子中有某个句子或句型 它存在两棵不同的语法树 那么这个句子或句型是二义性的 该文法是二义性文法 例2 9有文法G E E E E E E E i 分析该文法是否为二义性文法 解 为了判断该文法是否为二义性文法 我们找一个句子i i i 如果能够构造出两个不同的语法树 则说明该文法是二义性文法 下面两个图是为句子i i i构造的两棵语法树 如图2 2 a b 所示 由于这两棵语法树不同 所以可以肯定文法G E 是二义性文法 2 3 2语法树和二义性 图2 2 a 语法树1图2 2 b 语法树2 二义性产生的后果会导致分析结果不同 导致对句子的理解不同 在图2 2 a 语法树1中 根据规范归约构造的推导过程为 E E E E E E E E i E i i i i i在图2 2 b 语法树1中 根据规范归约构造的推导过程为 E E E E i E E i E i i i i i由于图2 2 a 语法树1中的 先作为句柄归约 可理解成 优先于 进行运算 而图2 2 b 语法树2中的 先作为句柄归约 表示 优先于 进行运算 2 3 2语法树和二义性 例2 10 IF语句文法如下 IFTHEN IFTHENELSE 说明该文法是二义性文法 解 假设有一个IF语句嵌套的句型为 IFTHENIFTHENELSE根据文法可构造两棵语法树如图2 3 a 和图2 3 b 所示 2 3 2语法树和二义性 图2 3 a IF语句语法树1 图2 3 b IF语句语法树2 由于这两棵语法树不同 所以该文法是二义性文法 图2 3 a IF语句的语法树意味着ELSE和第2个THEN配对 就近配对 而图2 3 b IF语句的语法树表示ELSE和第1个THEN配对 2 3 2语法树和二义性 文法的二义性是不可判定的 即不存在一种算法 它能够在有限步内判定一个文法是否是二义性的 第4章讨论的LL LR等几类重要文法都是无二义性的 同时 还存在这样一些算法 可判定任一前后文无关文法是否为LL LR文法 不过 文法的LL性 LR性只是文法无二义性的充分条件 另一方面 还存在一些用来检查文法二义性的其他充分条件 若一个文法G含有既是左递归又是右递归的非终结符号A 即有A AuAu V 或A A或A A 及A A则G必定是二义性文法 有时 我们还可以把一个二义性文法变换成一个等价的无二义性文法 例2 11 改写文法G E E E E E E E i 使其无二义性 解 新添非终结符号T和F 将文法写成 E T E T T F T F F E i 2 3 3短语和句柄 短语 简单短语和句柄在分析中有着重要的作用 后面介绍自底向上的语法分析时就可看到如何找句柄是非常关键的 短语是句型的子串 是在句型的推导过程中能由某个非终结符号推导出的子串 而简单短语则是能由某个非终结符号直接推导出的子串 它们的形式定义如下 1 短语 设G S 是一文法 w xuy是一句型 如果有S xUy且U u 其中U Vn u V 那么 我们称u是句型w相对于非终结符号U的短语 2 简单短语 若有S xUy且U u 那么 我们称u是句型w相对于非终结符号U的简单短语 3 句柄 任一句型的最左简单短语 即规范分析中 最先被规约的子串 称为该句型句柄 S xUy xuy 2 3 3短语和句柄 例2 7对于文法G 确定句型1的短语 简单短语和句柄 解 首先构造句型1的推导过程如下 11 由于 而 1 对照定义 子串1是由非终结符号推出的 所以是相对的短语 2 由于 而 1 所以子串1是相对的短语 3 由于 而 1 且1是由非终结符号直接推出的 所以子串1是相对的短语 而且是简单短语 在句型1中 只有一个简单短语1 所以它就是该句型的句柄 2 3 3短语和句柄 语法树的子树是由该树的某个节点 子树的根 连同它所有的后裔构成 子树与短语一一对应 要找一个句型的短语 可先画出该句型的语法树 判明语法树中的每棵子树 那么每棵子树的末端节点自左向右组成的符号串 就是相对于子树根符号的短语 原则上语法树中有多少棵子树 就有多少个短语 123的语法树 例2 8根据文法G 找句子123的短语 简单短语和句柄 解 首先画出产生句子123的语法树 见图2 1 该语法树共有7棵子树 子树1 树根 末端节点1 2 3 短语为123子树2 树根 末端节点1 2 3 短语为123子树3 树根 末端节点1 2 短语为12子树4 树根 末端节点1 短语为1子树5 树根 末端节点1 短语为1 且为简单短语 句柄子树6 树根 末端节点2 短语为2 且为简单短语子树7 树根 末端节点3 短语为3 且为简单短语 在这7个子树中 只有子树5 6 7的根节点与末端节点都是父子关系 所以这几个子树的末端节点形成的短语1 2 3都是简单短语 而子树5位于其中的最左端 所以短语1还是句柄 2 3 3短语和句柄 前面分析过 采用自底向上的语法分析时 每按一个产生式进行一次归约 就用该产生式的左部去替换当前句型中的子串 从语法树的角度来看 就是把该句型的语法树的一棵直接子树的末端节点剪去 换言之 语法分析每次所归约的符号串必然是当前句型的某一直接短语 但是 由于一个句型中的直接短语可能不止一个 故为了使语法分析按一种确定的方式来进行 通常我们只考虑最左归约即规范归约 123的规范推导 1 如何确定一个规范句型的句柄 2 应将句柄归约为哪个非终结符号 2 4文法的化简和改造 实用限制就是从实用的观点出发 对文法做一些必要的限制 本节讨论如下三个问题 1 无用符号和无用产生式的删除 2 产生式的删除 3 单产生式的删除 消除文法的左递归在后面讨论 2 4 1无用符号和无用产生式的删除 设G是一文法 我们说G中一符号X是有用的 是指X至少出现在一个句子的推导过程中 即X必须同时满足以下两个条件 X必须在某个句型中出现 即存在 V 有S X 2 必须能够从X推导出终结符号串 即存在w Vt 使 X w否则 就说X是无用的 含有无用符号的产生式称为无用产生式 2 4 1无用符号和无用产生式的删除 算法2 1用来将文法G Vn Vt P S 改造为等价的文法G1 Vn1 Vt P1 S 使得对于每个X Vn1 都有w1 Vt 满足X w1 即改造为满足条件2的文法 算法2 1分别置Vn1 P1为空 对于P中的每一产生式A 若 Vt 则将A置于Vn1中 对于P中的每一产生式A X1X2 Xm 若每一个Xi都属于Vt或Vn1 则将A置于Vn1中 重复步骤3 直到Vn1不再增大为止 对于P中的每一产生式B Y1Y2 Yn 若B及每一个Yi都属于Vt或Vn1 则将此产生式置于P1中 2 4 1无用符号和无用产生式的删除 对于给定的文法G 若执行算法2 2 便能得到一等价的文法G Vn Vt P S 使得对于每个X Vn Vt 都存在 Vn Vt 有S X 即改造为满足条件1的文法 算法2 2分别置Vn Vt P 为空 将文法G的开始符号S置于Vn 中 对于G中任何形如A 1 2 m的产生式 若A属于Vn 则将符号串 1 2 m中的全部非终结符置于Vn 中 而将其中的全部终结符置于Vt 中 重复步骤3 直到Vn 和Vt 都不再增大为止 将P中左右部仅含Vn Vt 中的符号的所有产生式置于P 中 2 4 1无用符号和无用产生式的删除 例如 对于文法G S U V W a b c P S 其中 P为S aSS WS UU aV bVV acW aW对G执行算法 步骤如下 由于U a及V ac 故Vn1 U V 对于产生式S U 由于U Vn1 故Vn1 S U V Vn1不再增大 G S U V a b c P S 其中 P1为S aSS UU aV bVV ac再对G1执行算法 步骤如下 置Vn S 由于S U及U a 故Vn S U Vt a Vn 及Vt 不再增大 G S U a P S 其中 P 为S aSS UU a 注意 两个算法的执行顺序不能颠倒 2 产生式的消除 所谓 产生式 是指右部为一空符号串 的产生式 如果一个语言L G 中不含有 则可以消除全部 产生式 而当 L G 时 G中的 产生式不能全部消除 因此 为了判断一个语言L G 中是否含有 同时也为了构造消除 产生式算法的需要 我们首先给出算法2 3 该算法能够找出所有能导出空串 即满足A 的非终结符号A 算法2 3设G是一文法 作集合W1 A A P 作集合序列Wk 1 Wk B P 且 Wk 对于此集合序列 必存在一个i 使Wi Wi 1 Wi 2 若令W Wi 则对每一个A W 有A 特别 当S W时 则 L G 否则 L G 2 产生式的消除 下面分别就 是否属于L G 来讨论消除G中 产生式的问题 1 不属于L G 设G Vn Vt P S 是一文法 则可按下述算法构造一文法G Vn Vt P S 使L G L G 且G 中不含任何 产生式 算法2 4按算法2 3求出集合W 设A X1X2 Xm是P中任一产生式 按如下规则将形如A Y1Y2 Ym的产生式放入P 中 对于一切1 i m 若Xi W 则取Yi Xi 若Xi W 则分别取Yi为Xi和 即如果X1X2 Xm中有j个符号属于W 1 j m 则将有2j个形如A Y1Y2 Ym的产生式放入P 中 但若所有的Xi均属于W 则不能把所有的Yi都取为 2 产生式的消除 例如 设有文法G S A B C a b c P S 其中 P为S aAA BCB bBC cCB C 对G执行算法2 3有W A B C 再对G执行算法2 4有P S aAS aA BCA BA CB bBB bC cCC c 2 产生式的消除 2 属于L G 算法2 5如果在原文法中 开始符号S不出现在任何产生式的右边 则可直接执行算法2 4得到P 令P1 P S Vn1 Vn S1 S 则G1 Vn1 Vt p1 S1 即为所求之文法 但若文法的开始符号S出现在某些产生式的右边 则引入新的符号S1作为前面算法2 4中G 的开始符号 并令Vn1 Vn S1 作产生式集P P S1 S P 对文法G Vn1 Vt P S1 执行算法2 4 同理 再添加产生式S1 得到P1 2 产生式的消除 例如 设有文法G S A B a b c P S 其中 P为S cSS ABA aAbB BbA B 引入新的符号S1 作产生式集P P S1 cS S1 AB 执行算法2 4并加入产生式S1 得到P1S1 cSS1 cS1 ABS1 AS1 BS1 S cSS cS ABS AS BA aAbA abB BbB b W W A B S S1 2 4 单产生式的消除 右部仅含一个非终结符号的产生式 即形如A B A B Vn 的产生式称为单产生式 例如 设有文法G S A B a b P S 其中 P为S ABS AS BA aAbA abB BbB bW S S A B W A A W B B P S AB S aAb S ab S Bb S b A aAb A ab B Bb B b 算法2 6设Vn A1 A2 An 对于每个Ai 1 i n 作集合序列W1 Ai Ai Wk 1 Ai Wk Ai D C D P C Wk Ai D Vn k 1 则必存在一个j 使Wj Ai Wj 1 Ai 令Wi Wj Ai 即Wi B Ai B B Vn 构造产生式集P i 1n Ai B P B Wi Vn 2 5文法和语言的Chomsky分类 著名的语言学家乔姆斯基在1956年对形式语言进行了定义 他把文法定义为四元组 G Vn Vt P S 其中 Vn为非终结符号集合 Vt为终结符号集合且Vt V P为有穷规则集合 S识别符号 且S Vn 文法所描述的语言为 L G x x Vt S x 根据文法中的规则的形式 可定义如下四类文法和相应的四种形式语言 2 5文法和语言的分类 0型文法 PSG 若文法中有如下形式的规则 其中 V V V Vn Vt即规则左部 可以是符号集合V上的符号串但不能为空 而规则右部 也是V上的符号串 可以是空 例如 aSb cAd0型文法描述的语言为0型语言 用L0表示 1型文法 CSG 若文法中有如下形式的规则 U u 其中U Vn V u V V Vn Vt即规则左部可为符号串 其中U为非终结符号且只有在左右为 和 的环境下U可变为u 因为规则中的 和 不发生变化 所以这种文法也叫上下文有关文法 例如 aUb aABBaab1型文法描述的语言为1型语言 用L1表示 文法中的产生式 满足条件 V 则该文法称为1型文法 2 5文法和语言的分类 2型文法 CFG 若文法中的规则都具有如下形式 U u 其中U Vn u V V Vn Vt2型文法中的规则左部只有一个非终结符号 规则右部u是V上的符号串 该文法相当于对1型文法中的规则形式加以限制 即要求 和 必须为空 2型文法也称作上下文无关文法 描述的语言为2型语言 用L2表示 2型文法是描述程序设计语言语法部分的主要文法 2 5文法和语言的分类 3型文法若文法中的规则都具有如下形式 A 或A B 左线性 或A B 右线性 其中A B Vn Vt 规则右部至多含有一个非终结符号 3型文法描述的语言为3型语言 用L3表示 高级程序设计语言的单词符号 如标识符 无符号整数等都是采用3型文法来描述的 例如 左线性3型文法 N N0 N1 N2 N3 N4 N5 N6 N7 N8 N9N 0 1 2 3 4 5 6 7 8 9这个文法定义的语言为就是无符号整数 在上述四类文法中 从0型到3型文法对规则的限制逐渐增加 产生的语言类却逐步缩小 即0型语言包含1型语言 1型语言包含2型语言 2型语言包含3型语言 因此 可以说3型文法是2型文法的特例 2型文法是1型文法的特例 1型文法又是0型文法的特例 习题2 2 1设字母表A a 符号串x aaa 写出下列符号串及其长度 x0 xx x5以及A 2 2令 a b c 又令x abc y b z aab 写出如下符号串及它们的长度 xy xyz xy 32 3设有文法G S S SS SS a 写出符号串aa a 规范推导 并构造语法树 2 4已知文法G Z Z U0 V1 U Z1 1 V Z0 0 请写出全部由此文法描述的只含有四个符号的句子 2 5已知文法G S S ABA aA B bBc bc 写出该文法描述的语言 2 6已知文法E T E T E T T F T F T F F E i 写出该文法的开始符号 终结符号集合VT 非终结符号集合VN 2 7对2 6题的文法 写出句型T T F i的短语 简单短语以及句柄 2 8设有文法G S S S S S S S a 该文法是二义性文法吗 2 9写一文法 使其语言是奇正整数集合 2 10给出语言 anbm n m 1 的文法