编译方法 马知行 曹启君 机械工业出版社 编译原理演示文稿2.ppt

第二章文法和语言2 1文法的基本概念一个程序设计语言是一个记号系统 如自然语言一样 它的完整的定义应包括语法和语义两方面 所谓一个语言的语法其实是指一组规则 用它可以形成和产生一个合适的程序 目前在程序设计语言的识别中广泛使用的是上下文无关的文法 在这理主要介绍文法和语言的概念 语言根据所含句子数量有限 穷 与否又可分为 有限 穷 语言和无限 穷 语言 例 设有文法 G the big ate caught mouse cat 则 the thebig thebigcat thebigcat thebigcatate thebigcatate thebigcatatethe thebigcatatethemouse 2 1 1符号和符号串定义2 1字母表是有穷非空集合 用 或V表示 例 无符号二进制数的字母表为 0 1 C语言的字母表为字母 数字和若干专用符号组成的符号集定义2 2符号串是由字母表中的符号组成的有穷序列 又称字符串 串 例 a b c ba bbac caacb 等都是字母表 a b c 上的符号串 定义2 3不包含任何字符串的空符号串用 表示定义2 4符号串x的长度 即符号串x中的字符的个数用 x 表示 读作x的长度 例 abc 3 a 1 0定义2 5设非空符号串u xvy 其中v 则称v为u的子串 若 u v 则称v为u的真子串 定义2 6如果z xy是一个符号串 则x是z和头 而y是z的尾 如果x是非空的 那么y是固有尾 同样如果y非空 那么x是固有头 例 设z abc 那么z的头是 a ab abc 除abc外 其它都是固有头 z的尾是 c bc abc z的固有尾是 c bc 定义2 7设x y是同一字母表上的两个符号串 把符号串y写在符号串X的后面所得到的符号串 称为x y的连接 记为xy例 x ab y wabu则z xy abywabu显然 x y z x x x 定义2 8设x是符号串 把x自身连接n次得到符号串z 即z xx xx n个x 称为符号串x的方幂 记为z xn例 x0 x1 xx2 xxx3 xxx 定义2 9符号串集合 若集合A中的一切元素都是其字母表上的符号串 则称A为该字母表上的符号串集合 注意 和 表示空集 的区别 定义2 10两个符号串集合A和B的乘积 AB定义为 AB xy x A且y B 例 设A a bc B b c da 则集合AB ab ac ada bcb bcc bcda 注意 由于 x x x因此 A A A 但 A A 则 A0 A1 AA2 AAAn An 1A AAn 1 n 0 定义2 11A的闭包A A0 A1 A2 A的正闭包A A1 A2 A3 显然A AA A AA A0 A 由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串 而语言是该字母表上的某些符号串的集合 因此 某个字母表上的语言是这个字母表上的正闭包的子集 而且通常是真子集 例 若 0 1 则 0 1 00 01 10 11 000 001 010 例 令L A B C Z a b z D 0 1 9 1 L D2 LD3 L4 L L D 5 D 6 D L 则分别代表什么集合 1 字母或数字的集合2 由一个字母开头后面跟一个数字的集合3 由字母组成的集合4 由字母开头后面是字母数字 可省略 的集合5 数字串集合6 数字串和字母串集合 包括 当对符号串z xy的头感兴趣而对其余部分不感兴趣时 可以采用省略写法 z x 如果只是为了强调x在符号串z中的某处出现 则可表示为 z x 如果只是为了强调x在符号串z约定中的末尾出现 则可表示为 z x 2 1 2文法和语言的形式定义语言是字母表上的某些符号串集合 在这集合中的每个符号串都是按一定规则生成的 其规则最常用的是重写规则 又称产生式 它是形如 或 或 的有序对 读作 定义为 或 由 组成 其中 称为规则的左部 称为规则的右部 定义2 12文法G定义为四元组 Vn Vt P S 其中 Vn为非终结符号 或语法实体 或变量 集 Vt为终结符号集 P为产生式 也称规则 的集合 S称作识别符号或开始符号 它是一个非终结符 至少要在一条规则中作为左部出现 Vn Vt和P是非空有穷集 显然 Vn和Vt不含公共的元素 即Vn Vt 定义2 13用V表示Vn Vt V称为文法G的字汇表 例 文法G Vn Vt P S 其中 Vn S Vt 0 l P S 0 S 1 S 0S S 1S S S 该文法刻划的是无符号二进制整数 上述文法可 通过约定 简单表示为 G S S 0S 1S 0SS 1S进而可 通过引入 简单表示为 巴科斯范式BNF G S S 0 1 0S 1S 例 刻划整数的文法 G Vn Vt P S 其中 Vn Vt 0 1 2 3 4 5 6 7 8 9 P 0 1 2 3 4 5 6 7 8 9S 例 能被5整除的整数文法 G Vn Vt P S 其中 Vn Vt 0 1 2 3 4 5 6 7 8 9 P 0 1 2 3 4 5 6 7 8 9 0 5S 约定 1 用尖括号括起的是非终结符 不用尖括号括起来的是终结符号 或者用大写字母表示非终结符号 小写字母表示终结符号2 可用G Z 指出识别符号 如果文法G没有明确指出识别符号 将第一条产生式的左部的非终结符号称为识别符号3 如果A 1 A 2 A 3 A 4 A k是所有以A为左部的产生式 称它们为A的产生式 可以写成A 1 2 3 4 k 称 1 2 3 4 k为A的选择 或候选式 例 0 1 2 3 4 5 6 7 8 9定义2 14设G是一文法 如果对于符号串 2 1 1 2 v 能写出 1 1A 2 2 1 2且A 是G中的一条规则 则说符号串 1直接推导到 2 或说 2是 1的直接推导 一步推导 或说 2归约到 1 记作 1 2 例 设有文法G 0 1 2 3 4 5 6 7 8 9试推导出2012 2 20 201 2012 定义2 15若文法G存在直接推导的序列V 0 1 2 3 4 n W n 0 则称V推导出W 或称W归约到V 记作V W 其中n为推导的步数 也称推导长度 称V 推导出W 例 2012定义2 16如果对于符号串V和W有V W或V W即 n 0 则记作V W 称V 推导出W 例 对文法G 有 2006例 对文法G 有 定义2 17设G S 是一文法 若 V 且有S 则称 为文法G S 的一个句型 若 Vt 且有S 则称 为G S 的一个句子 可见句子是句型的特例例 设有文法G 0 1 2 3 4 5 6 7 8 9显然0000 2012 1234 都是G 文法的句型 其中0000 2012 1234是G的句子 而3 不是句型 因为它们不能从开始符号推导出 定义2 18文法G所产生的语言定义为 L G S 且 Vt 定义2 19若L G1 L G2 则称G1 G2是等价的例 设G1 0 1 2 3 4 5 6 7 8 9设G2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9则L G1 L G2 由此可以看出 语言是该文法描述的全部句子的集合 换言之 一个语言是在某特定字母表上按一定的规则构成的符号串集合 文法提供了三个要点 1 在语言的设计和编译器的编写方面 文法都提供了极大的优点 2 文法给出了精确的 也于理解的语言语法说明设计得漂亮的文法 把结构加于程序设计语言 这些结构对把源程序翻译成真正的目标代码和错误诊断都是有用的 3 语言也是逐步完善的 需要补充新的结构和完成附加任务 如果存在以语法为基础的语言的实现 这些新结构的加入就更方便了 语言的特征 1 一种语言需借助于另一种语言 元语言 来描述2 语法是以有穷的方式来描述潜在无穷句子集合的手段3 语法上的正确不能保证语义上的正确 2 1 推导与递归定义2 20如果每次推导最左非终结符称最左推导 记为 L 定义2 21如果每次推导最右非终结符称最右推导 最右推导又称为规范推导 记为 R 由最右推导得出的句型称为右句型又称规范句型 递归规则与递归文法由于语言通常是无穷的而文法是有限的 用有限的文法定义无穷的语言就必须使用递归定义 递归规则若文法中存在规则A A 这种左部和右部具有相同的非终结符号的规则称为直接递归规则或称递归规则 若A A 即为左递归规则 若A A 即为右递归规则 若A A 即为自嵌套规则 这种递归称为直接递归或规则递归 递归文法有时文法中不含有直接的递归规则 但通过若干推导仍能得到递归 这种递归称为间接递归或文法递归 含有递归的文法被称为递归文法 如 A B B A 则A B A 2 1 4文法的分类形式语言自1956年乔姆斯基 Chomsky 进行描述以来 得到了很大的发展 乔姆斯基从理论上讨论了语言和文法 按照文法规则的不同定义形式进行分类 并且为每一语言构造象自动机一样的识别器 形式语言的理论形成和发展对计算机科学有着深刻的影响 特别是对程序设计语言的设计技术 编译实现都有重大影响 乔姆斯基把文法分成四种类型 即0型 1型 2型和3型文法 1 设文法G Vn Vt P S 如果P中的每条规则为如下形式 u v其中u Vn Vt 且至少含有一个非终结符 v Vn Vt 则称G是0型文法或短语文法 任何0型语言都是递归可枚举的 反之 递旧可枚举集必定是一个0型语言 2 设文法G Vn Vt P S 若P中的每条规则为如下形式 xUy xuy其中U Vn u Vn Vt x y Vn Vt 则称G是1型文法或上下文有关文法 意为非终结符U在x y这样的上下文条件下 允许替换为u 3 设文法G Vn Vt P S 若P中的每条规则为如下形式 U u其中U Vn u Vn Vt 则称G称为2型的或上下文无关文法 大部分高级语言文法近似于2型文法 4 设文法G Vn Vt P S 若P中的每条规则为如下式 U aB或U a 其中U B Vn a Vt则称G为3型文法或正规文法或线性文法 与词法分析有关的文法属于3型文法三型文法又分左线性和右线性的 若P中的每条规则为如下式 U aB或U a称为右线性的若P中的每条规则为如下式 U Ba或U a称为左线性的 0型文法 1型文法 2型文法 3型文法所描述 产生 的0型 1型 2型 3型语言可分别为图灵机 TM 线性界限自动机 LBA 下推自动机 PDA 有限自动机 FA 所识别 显然 3型文法是2型文法的特例 2型文法是1型文法的特例 1型文法是0型文法的特例 例1 写出语言L aibjck i j k 1 的2型文法G S S aS aBB bB bCC cC c例2 写出语言L aibk i k 1 的2型文法G S S ABA aA aB bB b例3 写出语言L aibi i 1 的2型文法G S S aSb ab例4 写出语言L aibk i k 1 的3型文法G S S aS aBB bB b 2 2句型分析所谓句型分析是指给定一个字符串判定是否是文法上定义的句子 在日常生活中语言 无论中文 英文 都是上下文有关 实际上程序设计语言也是上下文有关的 如 GOTO GOTO无符号整数 标识符的前说明后使用问题 但程序设计语言中的大部分规则是可以写成上下文无关文法 上下文无关文法有足够的能力描述现今程序设计语言的语法结构 比如描述算术表达式 描述各种语句等等 由于上下文无关文法不必考虑这所处的上下文 计算机实现比较方便 因而在程序设计语言的识别中较多地采用下文无关文法 今后如不特别指出的文法均为上下文无关的文法 2 2 1语法树如果把推导的过程用一种直观的图形表示就形成了一棵树 即语法树 也称推导树或分析树 例 设G S S ABA aAb abB cBd cd关于句子abccdd的最右推导为 S AB AcBd Accdd abccdd其构造语法树如下 注意树中的概念和文法的关系 1 结点表示一个文法符号 V中的一个元素 2 根结点表示识别符号 S 3 上下层表示存在一个直接推导 存在这样一条产生式 4 子树表示一个直接推导序列5 直接子孙结点 下层从左往右 表示相应的句型 定义2 22如果对于某文法的同一句子存在不同的语法树 则称句子的二义性的 包含二义性句子的文法称为二义性文法 否同称该文法为无二义性的定义2 23如果对于某语言不存在无二义性文法 则称该语言是二义性的注意 目前人们已经证明 二义性问题是不可判定的 即 不存在一个算法 它能在有限步骤内 确切判定任给的一个文法是否为二义的 例 设有文法G E E E E E E E i证明该文法是二义性的由于对于句子i i i有 两种不同的语法树 故该文法是二义性的 注意 文法的二义性和语言的二义性是两个不同的概念 因为对于同一语言可能有两个不同的文法G1和G2 一个是二义性的 但另一个却不是二义性的 例 G1 E E E E E E E iG2 E E E T TT T F FF E i对于非二义性文法来说 最左 最右 推导是唯一的 消除二义性如果语言不是二义性的 那么就存在一可以定义该语言非二义性文法 通过改造文法 反之 如果语言是二义性的 就不能通过改造文法消除其二义性的 例 G S S ifEthenS ifEthenSelseS b对于句型ifEthenEthenSelseS存在二棵不同的语法树 故该文法是二义性的 在实际应用中靠近的then和else先行匹配 为了识别方便可以消去二义性把该文法改写成 G S S S1 S2S1 ifEthenS1elseS1 bS2 ifEthenS1 ifEthenS1elseS2 2 2 2文法的约定文法虽然规定的语言的形成方法 但文法中有的规则会对分析带来麻烦 有会带来灾难 为此需对文法中的规则加以限制 有害规则定义2 23文法G中形如U U的规则 称为有害规则 这种规则没有增加句子的集合 给文法增加了二义性 给今后的分析带来不必要的麻烦 删除这样的规则没有形响到文法定义的语言 例 设G S S S DS DD 0 1删除有害规则S S后的新文法G S S DS DD 0 1显然有L G S L G S 定义2 24文法G中某一规则U u 其中u Vn Vt 若满足下列条件之一 则称该规则为多余规则 1 U 除开始符号外 不出现在该文法的任何其它的规则的右部 2 若在推导中使用该规则 则不能推出终结符号串 例 设G S 1 S Be 2 B Ce 3 B Af 4 A Ae 5 A e 6 C Cf 7 D f由于非终结符D不在规则右部出现 非终结符C不能推导成终结符号串 故都是多余规则 应删除 6 7 删除后 2 也不能推导成终结符号串也删除 故G S 1 S Be 2 B Af 3 A Ae 4 A e当一个上下文无关的文法中不含有害规则和多余规则时 称这个文法是压缩了的文法 在以后各章中介绍的文法不特指都是压缩了的文法 2 2 2句型的分析方法对于一个上下文无关文法 语法树就是该文法上的句型的推导过程的几何表示 语法树能将所给句型的结构很直观地显示出来了 利用语法树可直接对句型进行分析 这里所说的句型分析问题 就是对所给定的符号串分析是否是文法定义的句型 句型的分析也就是否能构造出推导过程 或归约过程 进一步说 当给定一个符号串时 试图按照文法的规则为该符号串构造推导 或语法树 以此识别出它是该文法的一个句型 当符号串全部由终结符号组成时 就是识别输入符号串是否是某文法的一个句子 对于程序设汁语言来说 要识别输入符号串是否是程序设计语言的程序 句子 程序实际上被定义为程序设计语言的一个句子 句型分析是一个识别输入符号串是否为语法上正确的程序的过程 在语言的编译实现中 把完成句型分析的程序称为分析程序或识别程序 分析算法又称识别算法 这种分析算法又可分成两大类 即自顶向下的和自底向上的分析方法 自顶向下 推导开始符号到句子 树生长 自底向上 归约句子到开始符号 树修剪 自顶向下的分析方法自顶向下的分析方法也称为自上而下的分析方法 它是从文法的开始符号出发 反复使用各种产生式 寻找 匹配 于输入符号串的推导 例 G S S cAdA abA a识别输入串w cabd是否该文法的句子 a b c 自底向上的分析方法自底向上的分析方法又称自下而上的方法 它是从输入符号用开始 逐步进行 归约 直至归约到文法的开始符号 例 设有文法G S S cAdA abA a识别输入串w cabd是否该文法的句子 c b a 句型分析的有关问题在自顶向下的分析方法中 需解决的问题是形如A 1 2 3 4 k的规则究竟选择那一个候选式 在自底向上的分析方法中 需解决的问题是如在文法中存在形如A 和B 的规则 并在分析过程中发现形如 的符号串是把它替换成A还是B 例 设G S S aBCB ib bC DE FGD dE ehF deG t当分析句子abdet时 对于C规则很难确定先用DE还是FG 例 G S S aAcBeA bA AbB b识别输入符号串abbbcbe栈输入符号串abbcdeabbcdeaAbcdeaAbcdeaAcdeaAcdeaAcbeaAcBeaAcBeS 定义2 25设G S 是