编译原理及其习题解答（武汉大学出版社）课件chap2.ppt

1 第二章文法和语言 要点 本章是基础 1 概念 文法 推导 直接推导 最左 右 推导 产生式 句型 短语 直接短语 句柄 语法树 规范推导 二义文法等2 4种文法的定义 文法的构造和文法的推导3 语法树的构造和最左 右 推导 4 二义文法 二义性的证明 5 句型分析 2 词法规则 自动机语法规则 上下文无关文法 3 引言 语言包括语法和语义两方面 语法是一组规则 用以判断什么样的符号序列是合法的 语义指含义 如变量的类型 作用域是否符合正确的语法 常把程序设计语言的语义分为二类 静态语义和动态语义 静态语义是一系列限定规则 并确定哪些合乎语法的程序是合适的 动态语义 或称运行语义 执行语义 表明程序要做些什么 要计算什么 阐明语法的一个工具是文法 常采用上下文无关文法作为程序设计语言语法的描述工具 4 补充 文法的直观概念 1 5 描述一种语言 无非是说明这种语言的句子 如果该语言所含的句子是有限的 那么只要一一列举出即可 若是无限的 则存在如何给出有穷表示的问题 但无论如何 某语言的句子总是存在着一种组成结构 即所谓的规则 或称文法 文法 描述语言的语法结构的形式规则 即语法规则 5 直观文法举例 2 5 例如 简单的汉语句子的构成规则 我 你 他 王明 大学生 工人 英语 是 学习 则 我是大学生 是句子 6 我是大学生 的推导过程 我我我是我是我是大学生依次可以推导出句子 王明是大学生 我学习英语 等等 推导过程 3 5 7 程序设计语言对文法的要求 4 5 这些规则必须是准确的 易于理解的 且应当有相当强的描述能力 足以描述各种不同的结构 8 文法作用 5 5 1 定义句子的结构 2 用适当条数的规则把语言的全部句子描述出来 以有穷集合刻划无穷集合 9 2符号串及其运算 1 符号串 由字母表中的符号组成的任何有穷序列 说明 字母间的顺序不同顺序组成的符号串是不同的 2 符号串长度符号串内所含符号的个数 若x string 则 x 6 其中不含任何符号的符号串称为空符号串 长度 0 2 1语言成分 1字母表 符号表 与符号元素 或称符号 的非空有穷集合 用符号 表示 不同语言有不同的字母表 如汉语包括汉字 数字 标点符号等 C语言包括字母 数字和保留字等等 10 符号串的运算 1 3 符号串的头尾 固有头和固有尾 设z xy是一个符号串 则x是z的头 y是z的尾 如果x是非空的 那么y是是固有尾 如果y是非空的 那么x是固有头 例 z abc 则z的头 a ab abc 固有头 a ab z的尾 c bc abc 固有尾 c bc 当我们对符号z xy的头感兴趣而对其余部分不感兴趣时 我们可以采用省略写法 z x 如果只是为了强调x在符号串中的某处出现 则可表示为 z x 符号t是符号串z的第一个符号 则表示为 z t 11 3 符号串的连接 设x和y是符号串 它们的连接xy是把y的符号写在x的符号之后得到的符号串 例如 x abc y DEF 则xy abcDEF 若 x n y m 则 xy n m 对任意的符号串x 有 x x x 12 4 符号串集合的乘积 设A B是两个符号串的集合 则AB表示A与B的乘积 定义为 AB xy x A y B 如 若A ab c B d efg 则AB abd abefg cd cefg 特别地 有 A A A空集 表示不含任何元素的空集 有 A A 请区别 三种表示方法的含义 13 5 符号串的方幂 同一符号串的连接可以写成方幂的形式 设x是符号串 把x自身连接n次得到的符号串z 即z xx xx 称为符号串x的方幂 记作z xn 有 x0 x1 xx2 xxx3 xxx 当n 0时 xn xxn 1 xn 1x 14 6 符号串集合的方幂 同一符号串集合的连接也可以写成方幂的形式 设符号串集合为A 则有 A0 A1 AA2 AAA3 AAA 当n 0时 An AAn 1 An 1A例如 A ab c 则AA AAA 15 7 符号串集合的正闭包 设符号串集合为A 则A的正闭包记为A 定义为 A A1 A2 An表示A上所有有穷长串的集合例如 A ab c AA AAA 8 符号串集合的自反闭包 设符号串集合为A 则A的自反闭包记为A 定义为 A A0 A1 A2 An即A A0 A A 例如 A a b 则A a b aa ab ba bb aaa A A A AA 16 2 2产生式文法和语言 2 2 1文法的形式定义 是一个四元组G VN VT P S VN 非终结符号集 非终结符号代表的是语法范畴 也就是它是一类 或集合 的记号 而不是一个个体记号 如 表达式 语句 分程序 等等 都是表达一定的语法概念 因此 每个非终结符表示一定符号串的集合 由终结符和非终结符组成 如简单汉语句子中 VT 终结符号集合 终结符是构成语言的基本符号 也就是说 它是一个语言的不可再分的基本符号 P 产生式 或称规则 重写规则 生成式 集合 所谓产生式是定义语法范畴的一种书写规则 一个产生式的形式是 或 其中 读为 是 或 定义为 产生式的左部 VN VT 且至少含有一个非终结符号 右部 VN VT 即由终结符或 与 非终结符组成的一符号串 允许是空字 17 2 2产生式文法和语言 例如 简单的汉语句子的构成规则 我 你 他 王明 大学生 工人 英语 是 学习 则 我是大学生 是句子 18 文法的形式定义 S 开始符号 即文法的第一个非终结符 开始符号代表了所定义的语言中我们最感兴趣的语法范畴 如在程序语言中 我们感兴趣的是 程序 注意 1 VN VT 即不含公共元素 2 产生式是有限的 3 开始符号S至少必须在某个产生式的左部出现一次 4 为书写方便 若干个左部相同的产生式如 P 1 P 2 P n合并成 P 1 2 n其中 i称为P的一个候选式 19 文法定义举例1 例2 1表示算术表达式的文法描述 G1 VN VT P S 其中VN E VT i P E i E E E E E E E E S E或者直接写为 G1 E i E i E E E E E E E E E 20 文法定义举例2 例2文法G VN VT P S 其中VN 标识符 字母 数字 VT a b c x y z 0 1 8 9 P a b c x y z 0 1 2 8 9 S 21 用文法定义语言的中心思想是 从文法的开始符号出发 反复连续使用产生式 对非终结符施行替换和展开 例如文法G E E E E E E i 其中唯一非终结符E可以看成是代表一类算术表达式 从E出发 进行一系列的推导 推出种种不同的算术表达式 如根据上述规则可推出 i i E E E E i E i i 我们称这样的一串替换是从E推出 i i 的一个推导 这个推导提供了一个证明 证明 i i 是文法G所定义的一个算术表达式 2 2 2文法的推导 22 有关推导的定义 定义2 3直接推导 若 A 直接推导出 即 A 当且仅当A 是一个产生式 且 VN VT 符号 指推导一步 即推导每前进一步总是引用一条规则 产生式 定义2 4长度为n n 1 的推导若存在直接推导序列a1 a2 an 则称a1可推导出an a1an表示 从a1出发经过一步或若干步 可推导出an 定义2 5长度为n n 0 的推导a1an表示 从a1出发经过0步 a1 an 或若干步 可推导出an 23 2 2 3句型 句子 语言 例1 证明终结符号串 i i i 是文法G E E E E E E i的一个句子证明 E E E E E E E i E E i i E i i i 是从开始符号E到 i i i 的一个推导 其中E E E E E E E i E E i i E i i i 都是这个文法的一个句型 1 句型 设G S 是一个文法 S是它的开始符号 若S 则称 是文法G S 的句型 2 句子 仅含终结符的句型是一个句子 即S VT 则 是句子 3 语言 文法G所产生的句子的全体是一个语言 记作L G L G S 且 VT 24 语言的例子 例2 文法G2 A A bA cc 证明cc bcc bbcc属于L G2 证明 A cc A Ba bcc A bA bbA bbcc cc bcc bbcc 是属于L G2 的 例3 文法G S 1 S 0S1 2 S 01 G S 的语言是什么 解 对第一个产生式使用n 1次 然后使用第二个产生式一次 得到 S 0S1 00S11 0n 1S1n 1 0n1n因此L G 0n1n n 1 例4 下列文法的语言是什么 G S S S S G A A A 25 2 2 4文法的等价 若L G1 L G2 则称文法G1和G2是等价的例1 G1 VN VT P S VN S VT 0 1 P由下列产生式组成 1 S 0S1 2 S 01 G2 VN VT P A VN A R VT 0 1 P由下列产生式组成 1 A 0R 2 A 01 3 R A1 26 什么是递归文法 1 递归规则 规则右部有与左部相同的符号对于U xUy若x 即U Uy 左递归 若y 即U xU 右递归 2 递归文法 文法G 存在U VN若U U 则G为递归文法 若U U 则G为左递归文法 若U U 则G为右递归文法 27 4 递归文法的优点 可用有穷条规则 定义无穷语言 例 对于前面给出的标识符的文法是有递归文法 用y有限条规则就可以定义出所有的标识符 若不用递归文法 那将要用多少条规则呢 3 左递归文法的缺点 不能用自顶向下的方法来进行语分析 会造成死循环 28 2 3文法的分类 2 3 1文法分类乔姆斯基 Chomsky 建立的形式语言对计算机科学的发展具有深刻的意义 他把文法分成四种类型 0型 1型 2型和3型 0型强于1型 1型强于2型 2型强于3型 它们的差别在于对产生式施加不同的限制 29 定义0型文法 或称短语文法 phrasestructuregrammar PSG G VN VT P S 是0型文法是指 若它的每个产生式 是这样一种结构 VN VT 且至少含有一个非终结符 VN VT 任何0型文法都是递归可枚举的 0型文法的能力相当于图灵机 计算机的一种简单的理论模型 称L为递归可枚举的 若存在一个产生L的过程 称L为递归的 若存在一个识别L的算法 30 定义1型文法 或称上下文有关文法 CSGContextSensitiveGrammar 如果对0型文法加以以下的限制 则可得到1型文法 设G VN VT P S 为一文法 若G的任何产生式 均满足 指符号串的长度 仅仅S 例外 课本P24例2 2 例 设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 求G S 的语言是什么 31 接上页例子 分析 条产生式中只有第 条具有递归性 其它的产生式最终都向终结符靠拢 注意 S aSBE与S 0S1的相似性 都可用同一模板来表示S S 使用产生式 1 n 1次 得推导序列 San 1S BE n 1 使用产生式 2 一次 得到 San BE n 使用产生式 3 的右部替换EB 使最终得到的串中 所有的B都先于所有的E 即SanBnEn 32 接上例 使用产生式 4 一次 得到SanbBn 1En 使用产生式 5 n 1次 得到SanbnEn 使用产生式 6 一次 得到SanbneEn 1 使用产生式 7 n 1次 得到Sanbnen 因此 L G anbnen n 1 说明 上述分析中 步骤 是关键一步 否则不能推导出终结符号串 例如假设n 3 SaaaBEBEBEaaaBBEEBEaaabBEEBEaaabbEEBEaaabbeEBEaaabbeeBE 33 上下文有关 顾名思义就是对非终结符进行替换时必须考虑上下文 例如 1型文法G的产生式也可写成 A 其中 都在 VN VT 中 且 A VN 则说明了非终结符A必须在 这样一个上下文环境中才可以替换 上下文有关文法能生成anbncn类特征的语言 但它不能描述L c a b 类语言 对上下文有关文法的说明 34 定义2型文法 或称上下文无关文法 CFGContextFreeGrammar 设G VN VT P S 为一文法 若G的任何产生式形似A 其中A VN VN VT 例 G S A B a b P S 其中P由下列产生式组成S aB bAA a aS bAAB b bS aBB例 G VN VT P S VN S VT 0 1 P由下列产生式组成 1 S 0S1 2 S 01 35 上下文无关文法的说明 上下文无关 顾名思义就是非终结符的替换可以不必考虑上下文 由于这种文法对程序已基本可以描述 因此 上下文无关文法常简称为文法 上下文无关文法最多能生成anbn类特征的语言 不能生成anbncn类特征的语言 36 设G VN VT P S 为一文法 若G的任何产生式A 或A B 其中A B VN VT 对任何正规文法G 都可以设计一个不确定的有穷自动机NFA 它能够而且只能够识别G的语言 定义3型文法 或称正规文法 RGRegularGrammar 例 文法G S A B 0 1 P S 其中P由下列产生式组成S 0A 1B 0A 0A 1B 0SB 1B 1 0 37 左线性文法 设G VN VT P S 为一文法 若G的任何产生式A 或A B 其中A B VN VT 左线性文法 右线性文法 非严格的转换 设左线性文法为G VN VT P S 右线性文法为G VN VT P S 其中VN VN S P 转化方式为 38 2 3 2文法分类的意义 自动机具有有穷描述的某种机器 对于给定文法 可接收某个终结符号串 并确定是否能从该文法推导出来 分析器判定 分析 一个终结符号串是否是某个文法的句子 给出给定串的推导序列 完成此工作的自动机 称为分析器 正规文法与自动机自动机由一个有穷状态集和一个状态对偶之间的转换集组成 CFG与自动机CFG可以由下推自动机来识别 39 文法分类的意义 文法的分类 对于实现程序设计语言的编译程序 具有重要意义 语言的词法规则 用正规文法 RG 描述 语言的语法规则 局部语法用CFG描述 全局语法用CSG描述 语言的语义描述 CSG 实际定义采用CFG 编译程序在实现时 一般采用CFG识别技术 易实现 高效 40 2 3 3文法举例 例2 61型文法G6 VN VT P S 其中VN S X Y Z VT x y z P S xSYZ xYZ xY xy yY yy yZ yz ZY YZ zZ zz L G6 为 例2 72型文法G7 VN VT P S 其中VN S T VT a b c d P S aTd T bT cT b c L G6 xnynzn n 0 L G7 a d b c 41 2 3 3文法举例 2 例2 82型文法G8 VN VT P B 其中VN B VT P B B BB 例2 92型文法G9 VN VT P S 其中VN S VT 0 1 P S 0S1 S 01 L G8 n n m m k k n 0 m 0 k 0 L G9 0n1n n 0 42 2 3 3文法举例 3 例2 10所有以0开头 以零个或多个10组成的符号串的语言 1 右线性文法G10 S S 0AA 10A 2 左线性文法G11 S S S10 0 3 正规文法G12 S S 0B 0B 1S 43 2 3 4文法的构造 补充 以 an anbn anbncn r 0 1 的构造为基础 以它们为依据来构造其它文法 给出下面语言相应的文法1 L1 abna n 0 2 L2 anbn mcm m n 1 3 L3 anbnci n 1 i 0 4 L4 aibncn n 1 i 0 5 L5 anbncn n 1 对文法的构造的求解要多做练习 44 文法的构造的分析 补充 类型 A A或A A 对应于 an n 1 类 A A 对应于 anbcn n 1 类 分步 先用A A 对应于 an BC n n 1 然后再通过改变排列顺序 最终实现 anbncn n 1 类 45 文法构造的方法 补充 分析所用文法的类型 对照典型的几种文法构造方法 来指导构造新的文法 利用模块化设计思想来指导构造过程 注意边界问题 46 文法的构造举例 1 3 1 L1 abna n 0 对应模板 A A或A A 划分模块 bn2 L2 anbn mcm m n 1 对应模板 A A 划分模块 对应anbn 对应bmcm 47 文法的构造举例 2 3 3 L3 anbnci n 1 i 0 对应模板 A A或A A A A 划分模块 对应anbn 对应ci4 L4 aibncn n 1 i 0 同 48 文法的构造举例 3 3 5 L5 anbncn n 1 对应模板 A A 划分模块 对应anbn 对应cn或对应an 对应bncn 49 2 4文法及其语法树 文法和语言 一 语法树 推导树 直观定义 用图表示上下文无关文法句型的推导的直观方法 语法树有助于理解一个句子的语法层结构的层次 语法树通常表示成一棵倒立的树 根在上 枝叶在下 2 形式定义对文法G VN VT P S 相关联的语法树49满足以下4个条件 1 根结点由开始符号S所标记 2 每个结点都有一个标记 此标记是V 即VN VT 的一个符号 3 若某结点至少有一个子孙结点 则该结点所标记的符号是个非终结符 4 从左到右 若结点A1 A2 Ak是结点A的孩子结点 则存在产生式A A1A2 Ak 50 从根结点S开始推导 当非终结符被它的某个候选式所替换时 这个非终结符的相应结点就产生出下一代新结点 候选式中自左向右的每个符号对应一个新结点 并用这些符号标记其相应的新结点 每个新结点与其父结点间都有一条连线 在一棵语法树生长过程中的任何时刻 所有那些没有后代的端末结自左向右排列起来就是一个句型 语法树构造的过程 例1文法G E i P E 其中P为 E E E E E E i对该文法关于 i i i 的推导的语法树如下所示 51 接语法树构造举例 E 根 E E E E E i i i 什么是树的边沿 52 文法和语言 语法树的问题分析 1 允许产生同名结点 反映递归性 2 没有后代的结点为端末结 3 语法树不能反映产生后代的先后顺序 例子在下一页 4 一棵语法树表示了一个句型种种可能的 但未必是所有的 不同推导过程 53 语法树例子 推导过程中施用产生式的顺序 例 G S S aASA SbAA SSS aA ba SaASSbAaaba S aAS aAa aSbAa aSbbaa aabbaaS aAS aSbAS aabAS aabbaS aabbaaS aAS aSbAS aSbAa aabAa aabbaa 54 2 5文法和语言的一些特性 文法和语言 2 5 1无用非终结符号 如果文法的某个非终结符不出现在文法的任何一个句型中 并且不能从它推导出终结符号串 则称该非终结符为无用非终结符 例2 13设文法G13 A A aaBbbB aBb abC cD cD Ef哪些符号是无用非终结符号 无用非终结符号 DE 对于文法G S 为了保证任一非终结符A在句子推导中出现 必须满足如下两个条件 1 A必须在某句型中出现 2 必须能从A推出终结符号串t来 55 文法和语言 2 5 2不可达文法符号 如果一个非终结符不出现在文法的任何一条产生式的右部 则称该非终结符为不可达文法符号 例2 13设文法G13 A A aaBbbB aBb abC cD cD Ef哪些符号是不可达文法符号 不可达文法符号 C 56 文法和语言 多余符号和多余规则 无用非终结符和不可达文法符号都是多余符号 包含有多余符号的规则 产生式 是多余规则 形如U U的产生式 也是多余规则 例1设文法G13 A A aaBbb aB aBb aCbC cD CD Ef应删除哪些多余规则 57 文法和语言 多余符号和多余规则 应删除哪些多余规则 例2 G S 1 S Be2 B Ce3 B Af4 A Ae5 A e6 C Cf7 D f S BeB AfA AeA e 58 文法和语言 2 5 3可空非终结符 若存在产生式A 则该产生式称为空产生式 A称为可空非终结符 空产生式有时候带来方便 所以 可以往一个文法里增加空产生式 59 2 5 4最左推导 最右推导 规范推导 最左推导 任何一步 都是对 中的最左非终结符进行替换 最右推导 又称规范推导 任何一步 都是对 中的最右非终结符进行替换 由规范推导所得到的句型称为规范句型 从一个句型到另一个句型的推导过程往往是不唯一的 例如E E i i a E E E i i i 最右推导 b E E i E i i 最左推导 60 语法树的特点 文法和语言 一棵语法树是这些不同推导过程的共性抽象 是它们的代表 一棵语法树完全等价于一个最左 右 推导 这种等价性包括树的步步生长和推导的步步展开是完全一致的 例 推导 i i i 最左推导 E E E E E E E i E E i i E i i i 最右推导 E E E E E i E E i E i i i i i 但两种推导的语法树相同 61 文法和语言 一个句型是否只对应唯一的一棵语法树 例 G E E iE E EE E EE E 句型i i i的两个不同的最左推导 推导1 E E E E E E i E E i i E i i i推导2 E E E i E i E E i i E i i i 62 文法和语言 定义2 13 一个文法 如果它的一个句子对应有两棵或两棵以上不同的语法树 则这个文法是二义的 或一个文法的某个句子有两个不同的最左 右 推导 则这个文法是二义的 2 5 5二义性 区别文法的二义性 存在两个不同文法G 二义 G 无二义 却有L G L G 即产生语言相同 语言的二义性 若不存在无二义性的文法 则该语言是二义性的 63 二义性其它问题 文法和语言 人们已证明 二义性问题是不可判定的 即不存在一个算法 它能在有限步骤内 确切地判断一个文法是否是二义的 我们所能做的就是为无二义性寻找一些充分条件 例如对文法G E E E E E E E i修改 规定运算符 与 的优先关系和结合规则 设 的优先性高于 且服从左结合 G E T E TT F T FF E i 64 文法和语言 2 6分析方法简介 句型分析的任务就是按文法的产生式 识别输入的符号是否是该文法的句型 语法树 是句型推导过程的几何表示 可以十分直观的显示某句型的结构 因此在句型时 对输入符号串构造语法树 以此识别它是否是该文法的一个句型 或句子 因此 语法树又可称为语法分析树或分析树 我们把完成句型分析的程序称为分析程序或识别程序 分析算法又称识别算法 分析算法又分为 从左到右分析算法 从右到左分析算法 自上而下的分析法自下而上的分析法 65 文法和语言 自上而下的分析法 基本思想 从文法的开始符号出发 反复使用各种产生式 寻找 匹配 输入符号串的推导 即对任何输入符号串 从文法的开始符号 根结 出发 自上而下地为输入串建立一棵语法树 直到语法树结果正好是输入的符号串为止 例如 文法G S S xAyA aa a 识别输入串xay是否是该文法的一个句子 66 文法和语言 自上而下分析法的缺陷 关键 回溯问题 其分析过程是一种试探过程 回溯问题是从各种可能的候选式中任选一个 进行推导后发现该候选式是错误的 则退回去重新选择候选式的方式 例如上例中的 3 S S S x A y 3 选用第1个候选式 a 回溯的产生使算法代价极低 效率很低 关于解决回溯问题将在第5章中介绍 a 67 自下而上的分析法 文法和语言 基本思想 从输入串开始 逐步进行 归约 直至归约到文法的开始符号 即从语法树的末端开始 步步向上 归约 直到根结 归约 若V W 是文法的产生式 如有V W 则W直接归约到V 68 自下而上的语法分析举例 例1 文法G S cAdA abA a识别输入串w cabd是否该文法的句子 SAAcabdcabdcabd规约过程 S cAd cabd 69 文法和语言 例2 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d识别abbcde是否为文法S的一个句子 解题思想 扫描abbcde 从中找出一个子串 该子串与某一产生式的右部相匹配 70 自下而上分析法举例 文法和语言 例2解 71 自下而上分析法存在的问题 文法和语言 可归约串的问题 该分析的每一步就是从当前串中找一个子串 称 可归约串 将它归约到某个非终结符号 自下而上分析法的关键就是找哪个子串是 可归约串 哪个不是 可归约串 例如上例中的 3 因此必须精确定义 可归约串 事实上存在着种种不同的方法刻画 可归约串 对这个概念的不同定义 形成了不同的自下而上的分析法 在 规范归约 的分析中 用 句柄 来刻画 可归约串 72 短语 直接短语 句柄 文法和语言 1 短语 令文法G 开始符号为S 是G的句型 即S 如果S A 且A 则称 是句型 相对于非终结符A的短语 2 直接短语如短语中有A 则称 是句型相对于规则A 的直接短语 3 句柄一个句型的最左直接短语称为该句型的句柄 73 解题方法 文法和语言 例 文法G E E T E TT F T FF E i证明i i i是G的一个句型 并指出这个句型的所有短语 直接短语 句柄 证明 EE TE T FE T iE F iE i iT i iF i ii i i 74 接上例 文法和语言 语法树 E E T T T F F F i3 i1 i2 第1层i1 i2 i3 相对于E第2层i1 相对于E i2 i3 相对于T第3层i1 i2 相对于T i3 相对于F第4层i1 i2 相对于F F i直接短语 第5层 i i i是G的一个句型 其中i1 i2 i3 i2 i3 i1 i2 i3都是句