第2章形式语言

编译原理简明教程 21世纪高等学校计算机学科系列教材 第一章引言第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析 自顶向下分析方法第六章语法分析 自底向上分析方法第七章语义分析及中间代码的生成第八章符号表第十章代码优化 目录 第二章形式语言理论基础 学习目标学习形式语言理论中的一些基本概念和基础知识掌握程序设计语言的语法描述方法需要着重掌握的内容为字母表产生式 上下文无关文法推导 句型 句子 语言语法树二义性Chomsky文法分类 语法 程序的结构形式语义 语言所代表的含义语用 语言的实际应用例如 x a b c语法 变量 表达式v e语义 对e求值 再赋给变量语用 计算和保存e的值以上非形式化的描述不够清晰明确 程序设计语言 探讨形式化方法 用一套带有严格规定的符号体系来描述问题的理论和方法 形式语言 是一种不考虑含义的符号语言 只谈语法不谈语义 形式语言理论 主要研究组成这组符号串的集合 它们的表示法 结构及特性 只能用于程序语言的语法描述和语法分析 1956年著名语言学家NoamChomsky首先描述形式语言 已成为计算机科学的一个重要组成部分 是编译理论重要基础 2 1形式语言的基本概念2 2文法和形式语言的定义2 3语法树和二义性2 4文法的实用限制2 5文法和语言的Chomsky分类 目录 2 1形式语言的基本概念 2 1 1符号和符号串形式语言和编译技术中两个主要概念任何一种语言都是由该语言的基本符号组成的基本符号串集合 英文 26个字母 数字 标点符号等PASCAL 字母 数字 关键字 专用符号等中文 汉字 数字 标点符号等 1 字母表 是一个非空的有限集合 用 表示 例 a b c a b c均为字符或符号 是字母表中的元素 2 符号串 符号的有序序列 用小写希腊字母表示如 a b ab abc等 表示空字符串 不包含任何符号的符号串 空格另外ab ba3 符号串集合 字母表上若干符号串的组成集合 用大写字母表示 例 A a ab bc 4 语言 形式语言 字母表上所有符号串组成的集合的子集 用L表示 L L可抽象地看成所有句子的集合 句子又可抽象看成是某个有限字母表 的符号串 字母表上的符号串不可能都是句子 例 a L a2k k 0 0 1 L1 01 n n 0 01 0101 L2 0n1n n 0 01 0011 空集或者空语言 不含任何符号串的语言 2 1 2符号串的运算 1 符号串相等 同一字母表的两个符号串所有符号依次相等 如 a b c abc abc 则 若 abc cba 则 2 字符串长度 符号串中包含的字符的个数 记 例 abc 3 0 a a 1 a 3 符号串的连接 把符号串 的所有符号相继写在 之后 记 或 ab bc 则 abbc4 符号串的逆 符号串 的倒置 记 1如 abc则 1 cba 1 1 1 1 1 1 5 符号串的前缀 后缀和子串设 是字母表 上的字符串 则 为符号 的前缀 为字符串 的后缀 是字符串 的子串 前缀和后缀都是子串 但子串不一定是前缀或者后缀 前缀 a ab abc后缀 bc c abc子串 a b c ab bc abc 例 abc 6 符号串集合的乘积A B A B 例 A ab ba B bc b 则AB abbc abb babc bab 特别 A A A 7 符号串的幂 一个符号串与它自己的n次连接 0 1 2 n n 1 例 ab 0 1 ab 2 abab n abab ab 8 符号串集合的幂A0 A1 AA2 AA An An 1A AAn 1 n 0 例 A ab c A0 A1 ab c A2 abc cab abab cc 9 集合A的闭包和正闭包 A A0 A1 正闭包A A1 A2 A A0 A A AA A A 字母表 上所有符号串的集合 上所有非空符号串的集合例 A 0 1 则A1 0 1 A0 A2 00 01 10 11 A 0 1 00 01 10 11 000 A 0 1 00 01 10 11 000 2 2文法和语言的形式定义 语言L 可抽象地看成是所有句子组成的集合 有限集 用枚举 无限集 文法 句子 可抽象地看成是某个有限字母表 上的符号串 例 英语 26个字母 数字 标点符号 文法 在形式上用以描述和规定语言结构的方法 是用有限的手段描述无限的句子集合的方法之一 L 例 我爱祖国 从结构上看符合中文文法 是中文句子 例 Thebigcatateamouse 见课本12页 1 10 mouse 又如 1 无符号整数 数字串 2 数字串 数字串 数字 3 数字串 数字 4 数字 2 5 数字 5 6 数字 6256是一个句子 文法中必须有三部分 1 终结符号集VT 句子中的字母 2 非终结符号集VN 大写字母 一般出现在左部 不属于字母表 3 文法规则集合U X或U X定义 文法是一个四元组G VN VT S P 记为G S V是字汇表 V VT VN S VN VT VN 例2 1VN A VT a b c S A P A aAb A c 构成文法G A a b c A P 例2 2G 标识符 字母 数字 0 1 2 9 a b c 标识符 P 引进BNF 巴科斯范式 I L IL INL a b cN 0 1 9定义 句型文法G S G VN VT S P 由S推出的符号串X VT VN 称为句型 a 直接推导 直接归约 长度 1 b 推导 归约 推导长度 n 1 定义 语言 句子文法G VN VT S P 所产生的语言L G L G S VT 其中 称为句子 空语言 由文法开始符号推不出任何句子 结论 给定一个文法 就能从结构上唯一地确定其语言 给定一个语言 能确定相应文法 但不唯一 例 G1 S 0S1S 01L G1 0n1n n 1 G2 S 1S 1AL G2 10 n1 n 0 A 0SG3 S 1S A1L G3 1 01 n n 0 A S0L G2 L G3 所以 G2和G3为等价文法 又如 已知语言L G Z abna n 1 则 G1 Z aBaG2 Z aBG3 Z BaB b BbB ba bBB ab Bb例2 3G VN VT S P VN S B C VT a b c P 1 S aSBC 5 bB bb 2 S aBC 6 bC bc 3 CB BC 7 cC cc 4 aB ab 解 1 S aBC abC abc 2 4 6 2 S aSBC aaBCBC aabCBC aabBCC 1 2 4 3 aabbCC aabbcC aabbcc 所以 L G anbncn n 1 2 例 G VN VT S P VN A B S VT 0 1 P S 0BS 1AA 0B 1A 0SB 1SA 1AAB 0BB所以 L G 由相同个数的0和1所组成的VT 中所有符号串的集合 2 3语法树和二义性 2 3 1语法树和推导1 语法树 用直观方法描述句型或句子的语法结构 已知文法G S 满足下列条件的树称为G的语法树 a 结点 终结符or非终结符b 树根 Sc 分枝 非终结符d 若结点A有B1B2 Bn分枝 则A B1B2 Bn是G的一个规则 例 G S S aABSSA Ba aaABaABB bdBaBabdbd 2 由推导生成语法树 句型or句子的推导用图解表示 语法树生成例 G G A A BB BC CC 0 1 2 9推导 3 由语法树构造推导 上一步的逆过程 由分枝建立直接推导 然后剪去分枝 直到无分枝可剪 ABBCBCCCCC2CC25C256或先进行归约 再倒过来 4 子树和短语 定义 子树 某个结点与它的分枝结点 BBCC5简单子树 单层分枝的子树 BCC5 定义 短语 简单短语 句柄 设SaBc Bb 则SaBcabcS则b称为句型abc相对于B的短语 aBcb结论 1 子树的末端结点组成的符号串是相对于子树根的短语 2 简单子树的末端结点组成的符号串是相对于简单子树根的简单短语 3 最左简单子树的末端结点组成的符号串为句柄 例 E句型 短语 E T简单短语 句柄 TFi T i T i T i T i T 2 3 2文法的二义性 1 二义性定义 如果一个文法所定义的句子中 有某个句子存在两棵不同的语法树 则称文法是二义性的 或 若文法所定义的某个句子 有两种不同的最左 or最右 推导 或 若文法所定义的某个句子 有两种不同的最左 or最右 归约 例 G E E E E E E E iEEE EE EiE EE EiiiiiEE E E E Ei i iEE E E E Ei i i文法的二义性产生句子语义上的不确定性 例 G s S ifBthenS ifBthenSelseS AS 语句B 布尔表达式A 其它语句句型 ifBthenifBthenSelseSSifBthenSifBthenifBthenSelseSSifBthenSelseSifBthenifBthenSelseS SSifBthenSifBthenSelseSifBthenSelseSifBthenS 2 二义性解决方法 1 修改编译算法例 G E E E E E E E I在编译方法中规定运算之间的优先级 如 高于 同级先左后右 2 修改文法G E E E T E T TT T F T F FF E iG S S C UC 完全语句U 不完全语句C ifBthenCelseS AU ifBthenS 注 规则左部的符号在右部同时出现两次or两次以上 导致二义性 先天二义性文法 不存在等价的非二义性文法 二义性问题是不可判定的 即不存在一种算法在有限步内判断二义性 2 4文法的实用限制 2 4 1有害规则定义 文法中凡是形如A A的规则 造成文法的二义性 2 4 2多余规则 定义 文法G 在某句型中出现的符号 可推出符号例 G E E T F i 例 S aAB aA aAb b S A B a b d B dC aBf 定义 G S 若A VN 存在 V 有S A 则称A为活的非终结符 例N D 定义 多余规则 左部符号为A的规则 若不满足条件 A为可推出符号 从A能推出句子例 G S S Be D不是可推出符号A Ae e D f多余B Ce Af B CeC CfC Cf多余D f 在程序设计语言中若包含多余规则 必定有错误句子 a A为可推出符号 即S A V b 必须能从A推出句子 即 A VT 定理1 如果一个文法G S 中所有规则均满足下列两个条件 则该文法不包含 设 A为任一规则的左部符号 G S S Be多余规则 D fA Ae e B CeB Ce AfC CfC CfD f 2 4 3文法的实用限制 定义 文法G S 所有规则均满足下列实用限制条件 a 没有有害规则b 没有多余规则则称G S 是压缩or化简过的 上例化简后 G S S BeA Ae eB Af 2 4 4文法的等价变换 在语法分析中 各种分析方法都有一定的局限性 对文法进行种种限制 为了使某一语言能用某一种分析方法 常常根据限制条件对文法进行变换 算法1 使文法的开始符号不出现在规则的右部 G S 引进S 扩充S S G S 为扩充文法 例 G N N ND DG N N ND 0 1 9N ND DD 0 1 9 算法2 使文法每个非终结符均能推导出一个终结符号串 G VN VT S P G VN VT S P 一 构造新的非终结符号集合VN 令VN A A P VT 递归扩充VN VN B B P VN VT 二 在G中删去左 右部含有不属于VN 中的符号的规则 例 G S S aABS bDADdA bAB dSA dDDB bAB dSBD dS d第一步 VN D D d P d VT D VN VN A A dDD P dDD VN VT D A VN VN S S bDADd P bDADd VN VT A D S 第二步 删去含有B的规则 得P S bDADdA dSA dDDD dS d 算法3 使文法的每个非终结符均出现在某个句型中一 构造新的非终结符号集 VN S 递归扩充VN VN B A B P A VN 即VN B S B B VN VN VT 二 从G中删去左部不在VN 中的非终结符的规则 例 G1 S S ad bAA dBDB aSAD bD e由算法2 VN D S 去掉含A B的规则 G2 S S adD bD e由算法3 VN S 不能扩充 删除左部含D的规则于是G3 S S ad 算法4 消除特殊规则A B第一步 构造新的非终结符号集合VN 对于VN中每个非终结符 如A 构造VNA B AB B VN 第二步 若有AB G中有B 则在G 中扩充A 第三步 删除特殊规则A B和无用规则 例 G A A B dEB A D bD B dE e Ea 第一步 AAdEABbVNA A B D ADd同理 VNB VND A B D VNE 第二步 对AA B b扩充A bD dA d 对BA dE扩充B dED dB d 对DA dE扩充D dEB bD b 第三步 删去特殊规则 于是得到A dE b dB dE b dD dE b dE e Ea由算法3 B D不在任何句型中出现 删去 得到A dE b dE e Ea 算法5 消去空规则A 第一步 构造新的非终结符号集VN VN A A P 递归扩充VN VN U B B x P x VN 第二步 从G中删去空规则第三步 从规则中删去只能导出空串的非终结符第四步 扩充新规则对于A B D B D VN V VN 扩充A D B B D 例 G A A aBbDB DDD b 第一步 VN D P D VN VN U B B DD P DD VN D B 第二步 删去D 第三步 无第四步 扩充新规则 对于A aBbDB D VN A ab abD aBb对于B DD D VN B D于是G A A ab abD aBb aBbDB D DDD b 算法6 消除左递归 G S 中有 A A 其中 V 不以A开头修改为 A A A A 例 E E T E T TE TE T T F T F F E TE TE F E iT FT T FT FT F E i 2 4 5扩充的BNF表示法 在BNF上发展起来 相同表达效力 结构上更简单 清晰 一 专用符号 t t可重复任意次 t t可出现0次或1次 提因子例 G N N ND DN D D D 0 1 9D 0 1 9 例 G E E T T EE T E T F F TT F T F i E F i E 例 A 1 2 nA 1 2 n 二 扩充BNF表示法的用途 消除左递归 使文法在自顶向下分析过程中 能进行分析处理 例 G E E T T T F F F i E 2 5文法和语言的Chomsky分类 四类文法对应四类语言 2 5 10型文法与0型语言 图灵机 定义 文法G S P中每条规则形如 V V 则称G为0型文法 or短语结构文法or无限制性文法 记PSG 产生的语言为0型语言 or短语结构语言or无限制性语言 记L0 G 例 2 5 P S ACaB Ca aaC CB DBCB E aD Da AD AC aE Ea AE SACaBAaaCBAaaEAaEaAEaaaa SaaaaL0 G a2n n 0 尽管0型文法不足以描述自然语言 但对程序设计语言的描述而言又太一般化 所以须对规则的形式加以限制 2 5 21型文法与1型语言 线性界限自动机 定义 文法G S 中每个规则即为 W W VN V V 则称G为1型文法 或上下文有关文法 CSG产生的语言称为1型语言L1 G 或上下文有关语言 前后文有关语言 在自然语言中 一个句子或一个单词的语法性质往往和它所处的上下文有密切的关系 所以描述自然语言的文