编译原理课件第2章.ppt

2020 2 22 1 第2章高级语言及其文法 2 1语言概述2 2基本定义2 3文法的定义2 4文法的分类2 5CFG的语法树2 6CFG的二义性2 7本章小结 2020 2 22 2 2 1语言概述 什么是语言 语言是一定的群体用来进行信息交流的工具 2020 2 22 3 2 1语言概述 信息交流的基础是什么 按照共同约定的生成规则和理解规则去生成 句子 和理解 句子 例 今节日上课始开译第一编 今日开始上第一节编译课 2020 2 22 4 2 1语言概述 语言的特征自然语言 NaturalLanguage 是人与人的通讯工具语义 semantics 环境 背景知识 语气 二义性 难以形式化计算机语言 ComputerLanguage 计算机系统间 人机间通讯工具严格的语法 Grammar 语义 semantics 易于形式化 严格 2020 2 22 5 2 1语言概述 语言的描述方法 现状自然语言 自然 方便 非形式化数学语言 符号 严格 准确 形式化形式化描述高度的抽象 严格的理论基础和方便的计算机表示 2020 2 22 6 2 1语言概述 语言 形式化的内容提取语言 Language 满足一定条件的句子集合句子 Sentence 满足一定规则的单词序列单词 Token 满足一定规则的字符 Character 串语言是字和组合字的规则例 自然语言 第译始二天课今开编上节 今天开始上第二节编译课 2020 2 22 7 2 1语言概述 语言是字及其组合规则的统一体 2020 2 22 8 2 1语言概述 程序设计语言 形式化的内容提取程序设计语言 ProgrammingLanguage 组成程序的所有语句的集合 程序 Program 满足语法规则的语句序列 语句 Sentence 满足语法规则的单词序列 单词 Token 满足词法规则的字符串 例 变量 表达式if条件表达式then语句while条件表达式do语句call过程名 参数表 2020 2 22 9 2 1语言概述 描述形式 文法语法 语句语句的组成规则描述方法 BNF范式 语法 描述 图词法 单词单词的组成规则描述方法 BNF范式 正规式 2020 2 22 10 形式语言与自动机理论的产生与作用 语言学家Chomsky最初从产生语言的角度研究语言 1956年 通过抽象 他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合 可以在字母表上按照一定的规则定义一个文法 Grammar 该文法所能产生的所有句子组成的集合就是该文法产生的语言 2020 2 22 11 形式语言与自动机理论的产生与作用 克林 Kleene 在1951年到1956年间 从识别语言的角度研究语言 给出了语言的另一种描述克林是在研究神经细胞中 建立了自动机对于按照一定的规则构造的任一个自动机 该自动机就定义了一个语言 这个语言由该自动机所能识别的所有句子组成 2020 2 22 12 形式语言与自动机理论的产生与作用 1959年 Chomsky通过深入研究 将他本人的研究成果与克林的研究成果结合了起来 不仅确定了文法和自动机分别从生成和识别的角度去表达语言 而且证明了文法与自动机的等价性 2020 2 22 13 形式语言与自动机理论的产生与作用 20世纪50年代 人们用巴科斯范式 BackusNourForm或BackusNormalForm 简记为BNF 成功地描述ALGOL 60促进形式语言在20世纪60年代的大发展巴科斯范式就是上下文无关文法 ContextFreeGrammar 的一种表示形式 2020 2 22 14 2 2基本定义 定义2 1字母表 Alphabet 是一个非空有穷集合 字母表中的元素称为该字母表的一个字母 Letter 也叫字符 Character 例以下是不同的字母表 a b c d a b c z 0 1 4 t n 2020 2 22 15 2 2基本定义 定义2 2设 1 2是两个字母表 1与 2的乘积 Product 定义为 1 2 ab a 1 b 2 例 1 0 1 2 a b 1 2 0a 0b 1a 1b 定义2 3设 是一个字母表 的n次幂 Power 递归地定义为 0 n n 1 n 1例 13 000 001 010 011 100 101 110 111 14 0000 0001 0010 0011 0100 1111 2020 2 22 16 2 2基本定义 定义2 4设 是一个字母表 的正闭包 PositiveClosure 定义为 2 3 4 的克林闭包 KleeneClosure 为 0 0 2 3 2020 2 22 17 2 2基本定义 例 0 1 0 1 00 01 11 000 001 010 011 100 a b c d a b c d aa ab ac ad ba bb bc bd aaa aab aac aad aba abb abc 2020 2 22 18 2 2基本定义 例 0 1 0 1 00 01 11 000 001 010 011 100 a b c d a b c d aa ab ac ad ba bb bc bd aaa aab aac aad aba abb abc 2020 2 22 19 2 2基本定义 定义2 5设 是一个字母表 x x称为字母表 上的一个句子 sentence 叫做 上的一个空句子 定义2 6设 是一个字母表 对任意的x y a 句子xay中的a叫做a在该句子中的一个出现 occurrence 定义2 7设 是一个字母表 x 句子x中字符出现的总个数叫做该字符串的长度 length 记作 x 2020 2 22 20 2 2基本定义 定义2 8设 是一个字母表 x y x y的并置 concatenation 是这样一个串 该串是由串x直接连接串y所组成的 记作xy 并置又叫做连结 对于n 0 串x的n次幂 power 定义为 x0 xn xn 1x 2020 2 22 21 2 2基本定义 定义2 9设 是一个字母表 对 x y z 如果x yz 则称y是x的前缀 prefix 如果z 则称y是x的真前缀 properprefix z是x的后缀 suffix 如果y 则称z是x的真后缀 propersuffix 字母表 a b 上的句子abaabb的前缀 后缀 真前缀和真后缀如下 前缀 a ab aba abaa abaab abaabb真前缀 a ab aba abaa abaab后缀 b bb abb aabb baabb abaabb真后缀 b bb abb aabb baabb 2020 2 22 22 2 2基本定义 定义2 10设 是一个字母表 对 x y z w v 如果x yz w yv 则称y是x和w的公共前缀 commonprefix 如果x和w的任何公共前缀都是y的前缀 则称y是x和w的最大公共前缀 maximalcommonprefix 如果x zy w vy 则称y是x和w的公共后缀 commonsuffix 如果x和w的任何公共后缀都是y的后缀 则称y是x和w的最大公共后缀 maximalcommonsuffix 2020 2 22 23 2 2基本定义 定义2 11设 是一个字母表 对 w x y z 如果w xyz 则称y是w的子串 substring 定义2 12设 是一个字母表 对 t u v w x y z 如果t uyv w xyz 则称y是t和w的公共子串 commonsubstring 如果y1 y2 yn是t和w的公共子串 且 yj max y1 y2 yn 则称yj是t和w的最大公共子串 maximalcommonsubstring 2020 2 22 24 2 2基本定义 定义2 13设 是一个字母表 L L称为字母表 上的一个语言 Language x L x叫做L的一个句子 例 字母表 0 1 上的语言 0 1 00 11 0 1 00 11 0 1 00 11 01 10 00 11 01 10 2020 2 22 25 2 2基本定义 2 14设 1 2是字母表 L1 1 L2 2 语言L1与L2的乘积 product 是字母表 1 2上的一个语言 该语言定义为 L1L2 xy x L1 y L2 2020 2 22 26 2 2基本定义 定义2 15设 是一个字母表 L L的n次幂 power 是一个语言 该语言定义为 当n 0是 Ln 当n 1时 Ln Ln 1L L的正闭包 positiveclosure L 是一个语言 该语言定义为 L L L2 L3 L4 L的克林闭包 Kleeneclosure L 是一个语言 该语言定义为 L L0 L L2 L3 L4 2020 2 22 27 2 3文法的定义 如何实现语言结构的形式化描述 考虑赋值语句的形式 左部量 右部表达式 a a ab m 3 bm 1 a m 2 2020 2 22 28 a b c m 1 m 2 m 3 问题 如何用符号来描述 即如何形式化 句子的组成规则 2020 2 22 29 非终结符号集V 终结符号集T a b c m 1 m 2 m 3 语法规则集P 开始符号S 赋值语句 定义句子的规则的语法组成 终结符号集 非终结符号集 语法规则 开始符号 2020 2 22 30 文法G的形式定义 定义2 16文法G为一个四元组 T 非终结符 Variable 集语法变量 成分 代表某个语言的各种子结构T 终结符 Terminal 集语言的句子中出现的字符 T 开始符号 StartSymbol S 代表文法所定义的语言 至少在产生式左侧出现一次 2020 2 22 31 文法G的形式定义 产生式 Product 集合 被称为产生式 定义式 读作 定义为 其中 T 且 中至少有 中元素的一个出现 T 称为产生式 的左部 LeftPart 称为产生式 的右部 RightPart 产生式定义各个语法成分的结构 组成规则 2020 2 22 32 例2 9赋值语句的文法 V T a b c m 1 m 2 m 3 P a b c m 1 m 2 m 3 S 2020 2 22 33 例2 9赋值语句的文法 续 符号化之后 G A B E C D P a b c m 1 m 2 m 3 P A 其中 P A B E B C B D C a C b C c D m 1 D m 2 D m 3 E COC E COD E DOC E DOD O O 2020 2 22 34 产生式的简写 对一组有相同左部的产生式 1 2 n可以简单地记为 1 2 n读作 定义为或者 1 或者 2 或者 n 并且称它们为 产生式 1 2 n称为候选式 Candidate 对一个文法 只列出该文法的所有产生式 且所列的第一个产生式的左部是该文法的开始符号 问题 有了定义句子的规则 如何判定某一句子是否属于某语言 2020 2 22 35 句子的派生 推导 从产生语言的角度 赋值语句 左部量 右部表达式 简单变量 右部表达式 a 右部表达式 a 简单变量 a a a a a a a 2020 2 22 36 句子的归约 从识别语言的角度 a a a a a a a a 简单变量 a 右部表达式 简单变量 右部表达式 左部量 右部表达式 赋值语句 派生与均根据规则 2020 2 22 37 基于产生式的变换 推导或归约 定义2 17设G V T P S 是一个文法 如果 P V T 则称 在G中直接推导出 记作 读作 在文法G中直接推导出 在不特别强调推导的直接性时 直接推导 可以简称为推导 derivation 有时我们也称推导为派生 与之相对应 也可以称 在文法G中直接归约成 在不特别强调归约的直接性时 直接归约 可以简称为归约 reduction 由于这里实际是将 中的 变成了 而 和 都没有变化 所以又称将 归约成 2020 2 22 38 多步 推导 0 1 2 n记为 0 n 恰用n步 0 n 至少一步 0 n 若干步 零步或多步 2020 2 22 39 文法G产生的语言 设G V T P S 是一个文法 对于 A V 令L A x Ax x T 不难看出 L A 就是语法变量A所代表的集合 定义2 19设有文法G V T P S 则称L G w Sw w T 为文法G产生的语言 language w L G w称为G产生的一个句子 sentence 显然 对于任意一个文法G G产生的语言L G 就是该文法的开始符号S所对应的集合L S 2020 2 22 40 文法G产生的语言 续 x xandx T 文法 可以派生出多少个句子 文法 的作用 语言的有穷描述以有限的规则描述无限的语言现象有限 产生式集合 终结符集合 非终结符集合无限 可以导出无穷多个句子 L也可是有穷 2020 2 22 41 推导 归约举例 A B E有产生式A B E 所以可以将A换成B E C E有产生式B C 所以可以将B E中的B换成C a E有产生式C a 所以可以将C E中的C换成a a COD有产生式E COD 所以可以将a E中的E换成COD a bOD有产生式C b 所以可以将a COD中的C换成b a b D有产生式O 所以可以将a bOD的O换成 a b m 1 有产生式D m 1 所以可以将a b D的D换成m 1 A B EB C DC a b cD m 1 m 2 m 3 E COC COD DOC DODO 2020 2 22 42 句型与句子 定义2 20设文法G V T P S 对于 V T 如果S 则称 是G产生的一个句型 sententialform 简称为句型对于任意文法G V T P S G产生的句子和句型的区别在于句子满足w T 而句型满足 V T 2020 2 22 43 句型与句子 句子w是从S开始 在G中可以推导出来的终结符号行 它不含语法变量 句型 是从S开始 在G中可以推导出来的符号行 它可能含有语法变量 句子一定是句型 但句型不一定是句子 2020 2 22 44 2 文法的分类 Chomsky体系 根据语言结构的复杂程度 形式语言 涉及文法的复杂程度 分析方法的选择反映文法描述语言的能力如果G满足文法定义的要求 则 是 型文法 短语结构文法PSG PhraseStructureGrammar L G 为PSL 2020 2 22 45 1 上下文有关文法 CSG 如果对于 P 均有 成立 除外 则称 为 型文法即 上下文有关文法 CSG ContextSensitiveGrammar L G 为1型 上下文有关 敏感语言 CSL 其他定义方法 设文法G S 若P中任一产生式 的形式为 1A 2 1 2 其中 1 2 V T A V 2020 2 22 46 2 上下文无关文法 CFG 如果对于 P 均有 并且 V成立 则称G为 型文法即 上下文无关文法 CFG ContextFreeGrammar L G 为2型 上下文无关语言 CFL CFG能描述程序设计语言的多数语法成分 2020 2 22 47 例标识符的文法 S L LTT L N TL TNL a b c dN 0 1 2 3 4 5 2020 2 22 48 3 正规文法 RG 设 w T 或为 如果对于 P 均具有如下形式 右线性 RightLinear 文法 w 或 w左线性 LeftLinear 文法 w或 w都是 型文法 正规文法RegularGrammar RG L G 为3型 正规集 正则集 正则语言 RL 能描述程序设计语言的多数单词左 右线性文法不可混用 2020 2 22 49 文法举例 正规文法 RG G1 S 0 1 00 11G3 S 0 1 0A 1B A 0 B 1G5 S 0 0SG8 A aS bS cS a b c 2020 2 22 50 文法举例 上下文无关文法 CFG G2 S A B AA BB A 0 B 1G4 S A B BB A 0 B 1G14 S 0 1 2 3 0S0 1S1 2S2 3S3 2020 2 22 51 文法举例 上下文有关文法 CSG G S CDC aCACA CaCaD daDdAc dec 2020 2 22 52 Chomsky体系 总结 T 是一个文法 P G是0型文法 L G 是0型语言 其能力相当于图灵机 G是1型文法 L G 是1型语言 除 其识别系统是线性界限自动机 N G是2型文法 L G 是2型语言 其识别系统是不确定的下推自动机 A aB或A a G是右线性文法 L G 是3型语言A Ba或A G是左线性文法 L G 是3型语言 其识别系统是有穷自动机 2020 2 22 53 文法的类型 四种文法之间的关系是将产生式作进一步限制而定义的 四种文法之间的逐级 包含 关系如下 2020 2 22 54 范式 Backus NaurFormBackus NormalForm 表示为 非终结符用 括起来终结符 基本符号集其他 1 2 n 1 2 n 2020 2 22 55 范式 Backus NaurFormBackus NormalForm 例简单算术表达式 只写产生式 id即 id哪些是终结符 哪些是变量 2020 2 22 56 2 5CFG的语法树 为了形象的表示推导过程 如果在某一步中的推导中根据产生式A X1X2 Xn 做出推导 AX1X2 Xn则表示为 2020 2 22 57 语法树 ParseTree用树的形式表示句型的生成树根 开始符号中间结点 非终结符叶结点 终结符或者非终结符每个推导对应一个中间结点及其儿子 一个二级子树 直接短语又称为分析树 parsetree 推导树 derivationtree 派生树 derivationtree 2020 2 22 58 语法树定义 设G V T P S 为一上下文无关文法 若对于G的任何句型都能构造与之关联的语法树 推导树 这棵树满足下面四个条件 每个结点都有一个标记X X V T 根的标记是S如果一个非叶子结点v有标记A 其直接子孙结点从左到右的次序是v1 v2 vk 其标记分别为A1 A2 Ak 那么A A1A2 Ak一定是P中的一个产生式若一结点v至少有一个它自己除外的子孙 并且有标记A 则肯定A V语法树的结果 从左至右读出推导树的叶子标记 2020 2 22 59 例句子结构的表示 文法E E E E E E id E E E id E id E E id id E id id id 一棵树 2020 2 22 60 短语 Phrase 定义2 27设有CFGG V T P S V T S A A 则称 是句型 的相对于变量A的短语 phrase 如果此时有A 则称 是句型 的相对于变量A的直接短语 immediatephrase 在无意义冲突时 简称为句型 的直接短语 直接短语也叫做简单短语 simplephrase 定义2 28设有CFGG V T P S G的句型的最左直接短语叫做句柄 handle 2020 2 22 61 例 直接 短语 E E T T T F T E T E T T E T T T T T F T T id T T a T F T a F F T a b F T a b c T a b c F a b c d E E T TT T F FF E id 2020 2 22 62 句柄 Handle 最左直接短语 T T F FE E T TF E idE E T T T F T E T E T T E T T T T T F T T id T T a T F T a F F T a b F T a b c T a b c F a b c d 2020 2 22 63 用子树解释短语 直接短语 句柄 短语 一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语 直接短语 仅有父子两代的一棵子树 它的所有叶子自左至右排列起来所形成的符号串 句柄 一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列 例如 对表达式文法G E 和句子a1 a2 a3 挑选出推导过程中产生的句型中的短语 直接短语 句柄 2020 2 22 64 E E T T T F T a1 T a1 T F a1 F F a1 a2 F E T T T T F F T a1 a1 T a1 T F a1 T F a1 F F F a1 F F a1 a2 a1 a2 F a2 F a1 a2 a3 a2 a3a1 a2 a3 E E T T F a1 T F F a2 a3 a1 a2 a3 短语 2020 2 22 65 例短语与分析树 文法E E E E E E id 一棵子树的叶子 2020 2 22 66 id id id的不同推导E E E E E E id E E E id E id E E id id E id id id E E E E E E E E id E id id id id id E E E E E E E id E id id E id id id 不做限制句型 sententialForm 归约 E id id id 施于最右变量右句型 规范句型 canonical 最左 规范归约 E id id id 施于最左变量左句型 left 最右归约 E 5id i