编译原理课件汇总.ppt

编译原理 主讲 闫健恩Email yanjianen 写在课程之前 木桶原理 一个木桶由许多块木板组成 如果组成木桶的这些木板长短不一 那么这个木桶的最大容量不取决于长的木板 而取决于最短的那块木板 蝴蝶效应 1963年12月 洛伦兹 Lorenz 在华盛顿的美国科学促进会的一次讲演中提出 一只蝴蝶在巴西扇动翅膀 有可能会在美国的德克萨斯引起一场龙卷风 他的演讲和结论给人们留下了极其深刻的印象 马太效应 马太福音 第二十五章由这么几句话 凡有的 还要加给他叫他多余 没有的 连他所有的也要夺过来 1968年 美国科学史研究者罗伯特 莫顿 RobertK Merton 提出这个术语用以概括一种社会心理现象 相对于那些不知名的研究者 声名显赫的科学家通常得到更多的声望即使他们的成就是相似的 同样地 在同一个项目上 声誉通常给予那些已经出名的研究者 例如 一个奖项几乎总是授予最资深的研究者 即使所有工作都是一个研究生完成的 学时与参考教材 学时 44 16学时参考教材 1 AlfredAhoect 编译原理 赵建华等译 机械工业出版社 2009 10 2 KennethC Louden 编译原理及实践 冯博琴等译 机械工业出版社 2001 2 3 金成植 编译程序构造原理和实现技术 高等教育出版社 2000 7 4 陈火旺等 程序设计语言编译原理 国防工业出版社 2003 8 印刷 学时与参考教材 5 何炎祥等 编译原理 华中理工大学出版社 2000 10 6 蒋立源 编译原理 西北工业大学出版社 2000 7 7 肖军模 程序设计语言编译方法 大连理工大学出版社 2000 88 蒋宗礼等 形式语言与自动机理论 清华大学出版社 2003 1 主要内容 编译系统及其设计概述 总体结构 设计方法 语言与文法 文法 推导 归约 分类 分析树 词法分析 词法分析 正规式与正规文法 DFA的状态转移图 语法分析 自顶向下 LL 1 递归子程序 自底向上 LR 语义分析 属性文法 各种语句的语法制导翻译 运行环境 存储分配 过程调用 符号表管理 代码优化 基本块的优化 循环优化等 代码生成 目标机器模型 基本块和流图 寄存器分配 基本块的DAG表示 从DAG生成目标代码 教学目的 编译原理 是一门非常好的课程 AlfredV Aho 编写编译器的原理和技术具有十分普遍的意义 以至于在每个计算机科学家的研究生涯中 本书中的原理和技术都会反复用到涉及的是一个比较适当的抽象层面上的数据变换 既抽象 又实际 一些具体的表示和变换算法 自顶向下的方法 和 自底向上的方法 系统设计方法 思想 方法 实现全方位讨论 一个相当规模的系统的设计 含总体结构 计算机专业最为恰当 有效的知识载体之一 教学要求 掌握编译程序总体结构在系统级上认识算法 系统的设计具有把握系统的能力学习有关的原理 实现方法和技术 了解计算学科的基本方法 思想掌握典型方法 在每一个计算机科技工作者的职业生涯中 这些原理和技术都被反复用到 兼顾语言的描述方法 设计 应用 形式化能形式化就能自动化进一步培养 计算机思维能力 软件系统的非物理性质 学习成果 以学生为中心 理解和掌握编译过程各个阶段的工作原理理解标准编译器各个组成部分的任务熟悉编译过程各阶段所要解决的问题及其采用的方法和技术应用一些标准的技术解决编译器构造过程中所产生的相关问题理解编译器在生成代码时如何充分利用特定处理器的特征 第1章引论 1 1计算机语言的发展1 2翻译系统1 3编译系统的功能分析1 4编译程序总体结构1 5编译程序的生成1 6编译技术的应用 1 1计算机语言的发展 机器语言 MachineLanguage 与汇编语言 AssembleLanguage 0 1代码与助记符 更接近于计算机硬件指令系统的工作高级语言 HighLevelLanguage 其表示方法更接近于待解问题的表示方法定义数据 描述运算 控制流程 传输数据如 C FORTRAN PASCAL C JAVA SQL 数据定义 数据操作 命令语言 CommandLanguage 控制系统的工作 以功能封装为特征如UNIX上的shell 1 2翻译系统 翻译程序 Translator 将某一种语言描述的程序 源程序 SourceProgram 翻译成等价的另一种语言描述的程序 目标程序 ObjectProgram 的程序 翻译程序 源程序 目标程序 C PAS OBJ EXE 1 2翻译系统 解释程序 Interpreter 口译与笔译 单句提交与整篇提交 源程序 输入数据 计算结果 解释程序 1 2翻译系统 编译程序 Compiler 高级语言程序 汇编 机器语言程序 源程序 目标程序 编译程序 1 2编译系统 SPCompilerS SourceO ObjectOPP ProgramInputRSRS RunSys Output 编译系统 CompilingSystem 编译系统 编译程序 运行系统 支撑环境 运行库等 1 2翻译系统 其它 诊断编译程序 DiagnosticCompiler 优化编译程序 OptimizingCompiler 交叉编译程序 CrossCompiler 可变目标编译程序 RetargetableCompiler 并行编译程序 ParallelizingCompiler 汇编程序 Assembler 交叉汇编程序 CrossAssembler 反汇编程序 Disassembler 1 2翻译系统 汇总 MLMLPAssemblerDisassemblerALALPTranslatorCompilerDataHLHLPInterpreterResult M MachineL LangugeP ProgramA AssembleH HighLevel 1 3编译系统的功能分析 程序分析词法 语法 语义分析综合语句的翻译 代码生成标识符处理 左值与右值的绑定 binding 变量 存储单元函数 目标代码序列 1 4编译程序总体结构 目标代码生成器 代码优化器 语义分析与中间代码生成器 语法分析器 1 词法分析 例 main printf hello 结果IDNmain IDNprintf STRhello 1 词法分析 词法分析由词法分析器完成 LexicalAnalyzer 词法分析器又叫做扫描器 Scanner 词法分析器从左到右扫描源程序 发现一个字符串 则将该字符串转换成单词 记号 Token 串 同时要 查词法错误 进行标识符登记 符号表管理 输入 字符串输出 种别码 属性值 序对属性值 token的机内表示 2 语法分析 语法分析由语法分析器 SyntaxAnalyzer 完成 语法分析器又叫Parser 功能 Parser实现 组词成句 将词组成各类语法成分 表达式 因子 项 语句 子程序 构造分析树指出语法错误指导翻译输入 Token序列输出 语法成分 2 语法分析 res fact term1 term2 赋值语句 表达式 fact 表达式 res 表达式 表达式 表达式 表达式 term1 term2 3 语义分析 功能 分析由语法分析器识别出的语法单位的语义获取标识符的属性 类型 作用域等语义检查 运算的合法性 取值范围等子程序的静态绑定 代码的相对地址变量的静态绑定 数据的相对地址 4 中间代码生成 中间代码 intermediateCode 例 id1 id2 id3 后缀表示 逆波兰Anti PolishNotation id1id2id3 前缀表示 波兰PolishNotation id1 id2id3 四元式表示 三地址码 1 id1 id2 T1 2 id3 T1 T2 三元式表示1 id2 id3 2 id1 1 4 中间代码生成 中间代码的特点简单规范与机器无关易于优化与转换 三地址码的另一种表示形式T1 id2 id3T2 id1 T1 其它类型的语句例 printf hello x s 赋值 paramx 参数 callf 函数调用 注释s是hello的地址f是函数printf的地址 对中间代码的优化处理 对代码进行等价变换以求提高执行效率 提高运行速度和节省存储空间与机器无关的优化与机器有关的优化 5 代码优化 与机器无关的优化 局部优化常量合并 常数运算在编译期间完成 如8 9 4公共子表达式的提取 基本块内循环优化强度削减用较快的操作代替较慢的操作代码外提将循环不变计算移出循环 与机器有关的优化 寄存器的利用将常用量放入寄存器 以减少访问内存的次数体系结构MIMD SIMD SPMD 向量机 流水机存储策略根据算法访存的要求安排 Cache 并行存储体系 减少访问冲突任务划分按运行的算法及体系结构 划分子任务 MPMD 6 目标代码生成 CodeGenerator 将中间代码转换成目标机上的机器指令代码或汇编代码确定源语言的各种语法成分的目标代码结构 机器指令组 汇编语句组 制定从中间代码到目标代码的翻译策略或算法目标代码的形式具有绝对地址的机器指令汇编语言形式的目标程序模块结构的机器指令 需要链接程序 7 表格管理 管理各种符号表 常数 标号 变量 过程 结构 查 填 登记 查找 源程序中出现的符号和编译程序生成的符号 为编译的各个阶段提供信息 辅助语法检查 语义检查完成静态绑定 管理编译过程Hash表 链表等各种查 填表技术 8 错误处理 进行各种错误的检查 报告 纠正 以及相应的续编译处理 如 错误的定位与局部化 词法 拼写 语法 语句结构 表达式结构 语义 类型不匹配 编译系统 模块分类 分析 词法分析 语法分析 语义分析 中间代码生成综合 代码优化 目标代码生成辅助 符号表管理 出错处理8项功能对应8个模块 例一个语句的翻译 9编译的遍 Pass 根据系统资源的状况 运行目标的要求 等 可以将一个编译程序设计成多遍扫描的形式 在每一遍扫描中 完成不同的任务 如 首遍构造语法树 二遍处理中间表示 增加信息等 遍可以和阶段相对应 也可无关单遍代码不太有效 10 编译的前端与后端 前端与源语言有关 与目标机无关的部分词法分析 语法分析 语义分析与中间代码生成 与机器无关的代码优化后端与目标机有关的部分与机器有关的代码优化 目标代码生成 1 5编译程序的生成 设计目标目标程序小 执行速度快 编译程序小 执行速度快 诊断能力强 可靠性强 可移植性 可扩充性 如何实现编译器 直接用可运行的代码编制 太费力 自举 使用语言提供的功能来编译该语言自身 第一个编译器是怎样被编译的 问题 直接在一个机上实现C语言编译器 还有别的技术么 解决 用汇编语言实现一个 子集的编译程序 P0 人 用汇编程序处理该程序 得到 P2 可直接运行 用 子集编制 语言的编译程序 P3 人 用P2编译P3 得到P4 1 编译程序的自展技术 2 利用编译程序自动生成器 词法分析器的自动生成程序 词法规则说明 词法分析程序 C程序 输入 词法 正规表达式 识别动作 程序段 输出 yylex 函数 语法分析器的自动生成程序 语法规则说明 语法分析程序 C程序 输入 语法规则 产生式 语义动作 程序段 输出 yyparse 函数 1 6编译技术的应用 把复杂数据看作一条语句数据格式的分析利用词法分析 语法分析方法数据处理的框架基于语法制导的语义处理框架编译技术可以用于各种复杂数据的分析处理 1 6编译技术的应用 语法制导的结构化编辑器程序格式化工具软件测试工具程序理解工具高级语言的翻译工具 例1 1 DOS命令date的输出格式例 9 2 1993 09 03 1993 9 03 93语法date month day year词法month DIGITDIGIT DIGITday DIGITDIGIT DIGITyear DIGITDIGIT DIGIIDIGITDIGITDIGIT 例1 1 续 语义year 年 month 月 day 日 语义约束条件0 month value 130 day value 32 31 300 year value 10000 小结 计算机语言的发展翻译系统及其功能编译的总体结构编译的各个阶段编译的生成及应用相关概念 习题 1 试分析一个简短的C程序 找出几个属于语法 词法 语义的语言现象 2 试分析例1 1的date输出数据的处理中 应该做哪些词法分析 语法分析 语义处理 高级语言及其文法 2 1语言概述2 2基本定义2 3文法 Grammar 的定义2 4CFG的分析树 ParseTree 2 5文法的分类2 6文法的构造 本章主要内容 2 1语言概述 什么是语言 2 1语言概述 语言特征自然语言 NaturalLanguage 是人与人的通讯工具语义 semantics 环境 背景知识 语气 二义性 难以形式化计算机语言 ComputerLanguage 计算机系统间 人机间通讯工具严格的语法 Grammar 语义 semantics 易于形式化 严格 2 1语言概述 语言的描述方法 现状自然语言 自然 方便 非形式化数学语言 符号 严格 准确 形式化形式化描述高度的抽象 严格的理论基础和方便的计算机表示 2 1语言概述 语言 形式化的内容提取语言 Language 满足一定条件的句子集合句子 Sentence 满足一定规则的单词序列单词 Token 满足一定规则的字符 Character 串语言是字和组合字的规则例 自然语言 第译始一天课今开编上节 今天开始上第一节编译课 2 1语言概述 程序设计语言 形式化的内容提取程序设计语言 ProgrammingLanguage 组成程序的所有语句的集合 程序 Program 满足语法规则的语句序列 语句 Sentence 满足语法规则的单词序列 单词 Token 满足词法规则的字符串 例 变量 表达式if条件then语句while条件do语句call过程名 参数表 2 1语言概述 描述形式 文法语法 语句语句的组成规则描述方法 BNF范式 语法 描述 图词法 单词单词的组成规则描述方法 BNF范式 正规式 形式语言于自动机理论的产生与作用 语言学家Chomsky最初从产生语言的角度研究语言 1956年 通过抽象 他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合 可以在字母表上按照一定的规则定义一个文法 Grammar 该文法所能产生的所有句子组成的集合就是该文法产生的语言 克林 Kleene 在1951年到1956年间 从识别语言的角度研究语言 给出了语言的另一种描述 克林是在研究神经细胞中 建立了自动机 他用这种自动机来识别语言 对于按照一定的规则构造的任一个自动机 该自动机就定义了一个语言 这个语言由该自动机所能识别的所有句子组成 形式语言于自动机理论的产生与作用 1959年 Chomsky通过深入研究 将他本人的研究成果与克林的研究成果结合了起来 不仅确定了文法和自动机分别从生成和识别的角度去表达语言 而且证明了文法与自动机的等价性 20世纪50年代 人们用巴科斯范式 BackusNourForm或BackusNormalForm 简记为BNF 成功地对高级语言ALGOL 60进行了描述 实际上 巴科斯范式就是上下文无关文法 ContextFreeGrammar 的一种表示形式 这一成功 使得形式语言在20世纪60年代得到了大力的发展 形式语言于自动机理论的产生与作用 形式语言与自动机理论除了在计算机科学领域中的直接应用外 更在计算学科人才的计算思维的培养中占有极其重要的地位计算思维能力的培养 主要是由基础理论系列课程实现的 该系列主要由从数学分析开始到形式语言结束的一些数学和抽象程度比较高的内容的课程组成 它们构成的是一个梯级训练系统 在此系统中 连续数学 离散数学 计算模型等三部分内容要按阶段分开 三个阶段对应与本学科的学生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤 计算思维能力的培养过程 中学数学数学分析离散数学具体 静止变量 运动离散 抽象形式 模型 基本运算系统 计算系统 实数抽象集合单一 具体的计算一般 形式化的计算 实例计算 模型化计算 高水平计算专业人才的计算思维能力的渐进培养 2 2基本定义 字母表 Alphabet 是一个非空有穷集合 字母表中的元素称为该字母表的一个字母 Letter 也叫字符 Character 例以下是不同的字母表 a b c d a b c z 0 1 4 ASCII字母表 2 2基本定义 符号串的定义由字母表中的符号所组成的任何有穷序列被称之为该字母表上的符号串 也称作 字 1 是 上的一个符号串 2 若x是 上的符号串 而a是 的元素 则xa是 上的符号串 3 y是 上的符号串 当且仅当它由 1 和 2 导出 2 2基本定义 设s是符号串 则s的前缀 移走s的尾部的零个或多于零个符号后缀 删去s的头部的零个或多于零个符号子串 从s中删去一个前缀和一个后缀子序列 从s中删去零或多于零个符号 这些符号不要求连续 逆转 将S中的符号按相反次序写出而得到的符号串长度 是该符号串中的符号的数目 例如 aab 3 0 2 2基本定义 符号串的连接和方幂1 连接 设x和y是符号串 它们的连接xy是把y的符号写在x的符号之后得到的符号串 例如 x ba y nana xy banana 2 方幂 x0 x1 x x2 xx xn xn 1x 例如 设x ba 则x1 ba x2 baba x3 bababa 2 2基本定义 定义1设 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设 是一个字母表 的n次幂 Power 递归地定义为 0 n n 1 n 1例 13 000 001 010 011 100 101 110 111 2 2基本定义 定义3设 是一个字母表 的正闭包 PositiveClosure 定义为 2 3 4 的克林闭包 KleeneClosure 为 0 0 2 3 2 2基本定义 例 0 1 0 1 00 01 11 000 001 010 011 100 0 1 0 1 00 01 11 000 001 010 011 100 2 2基本定义 定义5设 是一个字母表 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 2 3文法的定义 如何实现语言结构的形式化描述 考虑一个句子 文法要素的提取 分析 Thegreywolfwilleatthegoat 句子 主语 谓语 1 主语 冠词 形容词 名词 2 冠词 the 3 形容词 grey 4 谓语 动词 直接宾语 5 动词 助动词 动词原形 6 助动词 will 7 动词原形 eat 8 直接宾语 冠词 名词 9 名词 wolf 10 名词 goat 11 句子的组成规则 问题 如何用符号来描述 即如何形式化 终结符号集VT the grey wolf will eat goat 非终结符号集VN 句子 主语 谓语 冠词 形容词 名词 动词 直接宾语 助动词 动词原形 语法规则集P 句子 主语 谓语 开始符号S 句子 定义句子的规则的语法组成 终结符号集 非终结符号集 语法规则 开始符号 问题 有了定义句子的规则 如何判定某一句子是否属于某语言 句子 主语 谓语 冠词 形容词 名词 谓语 the 形容词 名词 谓语 thegrey 名词 谓语 thegreywolf 谓语 thegreywolf 动词 直接宾语 thegreywolfwilleatthegoat 句子的派生 推导 从产生语言的角度句子的归约 从识别语言的角度 均根据规则 句子 thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthegrey符合语法且符合语义的句子仅是 thegreywolfwilleatthegoat 句子的语义要求 文法G的形式定义 文法G为一个四元组 T N T 终结符 Terminal 集 N 非终结符 Variable 集 T N 语法成分 代表某个语言的各种子结构 开始符号 StartSymbol S N代表文法所定义的语言 至少在产生式左侧出现一次 文法G的形式定义 产生式 Product 集合 被称为产生式 定义式 读作 定义为 其中 T N 且 中至少有 N中元素的一个出现 T N 称为产生式 的左部 LeftPart 称为产生式 的右部 RightPart 产生式定义各个语法成分的结构 组成规则 例2 1算术表达式的文法 递归定义 中缀表示标识符 id 常数 变量 是表达式 E 表达式加一个表达式是表达式 表达式减一个表达式是表达式 表达式乘一个表达式是表达式 表达式除一个表达式是表达式 表达式加上括号后是表达式 例2 1算术表达式的文法 考虑简单算术表达式组成的语言G id E P E P E E EE E EE E E id约定 只写产生式简写E E E E E E id 2 1 产生式的简写 对一组有相同左部的产生式 1 2 n可以简单地记为 1 2 n读作 定义为或者 1 或者 2 或者 n 并且称它们为 产生式 1 2 n称为候选式 Candidate 基于产生式的变换 推导或归约 E E E E E E idE由第一个候选式可以变成E EE E中的第一个E由第二个候选式可以变成E E 从而E E变成E E E根据第4个候选式 E E E中的E都可以变成id E E E变成id E Eid E E变成id E idid E id变成id id id也就是说 根据第4个候选式 E E E经3步变换变成id id id 直接推导与归约 根据产生式对符号串进行变换的过程 是文法 的一个产生式 且 T N 称 直接推导 派生 Derive 出 也称 直接归约 Reduce 为 记为 例 id E id E E 多步 推导 0 1 2 n记为 0 n n 恰用n步 0 n 至少一步 0 n 若干步 零步或多步 推导 归约举例 E E E 1 串中含有变量 id E 4 串中含有变量 id E E 2 串中含有变量 id id E 4 串中含有变量 id id id 4 串中没有变量到此串中已经没有 语法 变量了 不能再推导了 1 E E E2 E E E3 E E 4 E id 句型与句子 E 5id id id句子 如果S x 且x T 则称x是G产生的一个句子 Sentence E E E E E EE 4id id E句型 如果S T N 则称 是G产生的一个句型 SententialForm 文法G产生的语言 x xandx T 文法E E E E E E id可以派生出多少个句子 文法G的作用 语言的有穷描述以有限的规则描述无限的语言现象有限 产生式集合 终结符集合 非终结符集合无限 可以导出无穷多个句子 L也可是有穷 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 id id 最左推导与最右推导 最左推导 Left mostDerivation 每次推导都施加在句型的最左边的语法变量上 与最右归约对应最右推导 Right mostDerivation 每次推导都施加在句型的最右边的语法变量上 与最左归约 规范规约 对应的规范 Canonical 句型 例2 2标识符的文法1 S L LTT L N TL TNL a b c dletterN 0 1 2 3 4 5digit问题 正整数的文法 正实数的文法 2 文法的分类 Chomsky体系 根据语言结构的复杂程度 形式语言 涉及文法的复杂程度 分析方法的选择反映文法描述语言的能力如果G满足文法定义的要求 则 是 型文法 短语结构文法PSG PhraseStructureGrammar L G 为PSL 上下文有关文法 CSG 若产生式集合中所有 除 外 则 是 型文法即 上下文有关文法 CSG ContextSensitiveGrammar L G 为1型 上下文有关 敏感语言 CSL 上下文无关文法 CFG 若 N N T 则 是 型文法即 上下文无关文法 CFG ContextFreeGrammar L G 为2型 上下文无关语言 CFL CFG能描述程序设计语言的多数语法成分 例2 3标识符的文法2 S L LTT L N TL TNL a b c dN 0 1 2 3 4 5 S a b c dS aT bT cT dTT a b c d 0 1 2 3 4 5T aT bT cT dT 0T 1T 2T 3T 4T 5T 正规文法 RG 设 N T或为 右线性 RightLinear 文法 或 左线性 LeftLinear 文法 或 都是 型文法 正规文法RegularGrammar RG L G 为3型 正规集 正则集 正则语言 RL 能描述程序设计语言的多数单词左 右线性文法不可混用 例非CFL的文法 L anbncn n 0 的文法S aBC aSBCCB BCaB abbB bbbC bc 可以证明 不存在CFGG 使L G L 在我们使用的程序设计语言中 有些语言结构不能用上下文无关文法来描述 例2 4L1 wcw w a b 例 aabcaab就是L1的一个句子 这个语言是检查程序中标识符的声明应先于引用的抽象 例2 5L2 anbmcndm n m 0 它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象 非上下文无关的语言结构 Chomsky体系 总结 T N 是一个文法 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型语言 其识别系统是有穷自动机 文法的类型 四种文法之间的关系是将产生式作进一步限制而定义的 四种文法之间的逐级 包含 关系如下 范式 Backus NaurFormBackus NormalForm 表示为 非终结符用 括起来终结符 基本符号集其他 1 2 n 1 2 n 范式 BackusNormalForm 例简单算术表达式 只写产生式 id即 id哪些是终结符 哪些是变量 例2 6句子结构的表示 文法E E E E E E id E E E id E id E E id id E id id id 一棵树 2 5CFG的分析树 ParseTree用树的形式表示句型的生成树根 开始符号中间结点 非终结符叶结点 终结符或者非终结符每个推导对应一个中间结点及其儿子 一个二级子树 直接短语又称为语法分析树 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 短语 二义性文法与先天二义性语言 对同一句子存在两棵语法分析树在理论上不可判定 1 描述一个句子的文法不是唯一的 2 对于一个句子的分析应是唯一的 考虑表达式下面的文法G E 其产生式如下 E E E E E E a对于句子a a a 有如下两个最左推导 E E E a E a E E a a E a a aE E E E E E a E E a a E a a a 文法的二义性 E E E a E a E E a a E a a a E E E E E E a E E a a E a a a E E E E E a a a E E E E E a a a 最左推导 E E E E E E E E a E a a a a a E E E E a E E a E a a a a a E E E E E a a a E E E E E a a a 最右推导 如果一个文法的句子存在两棵分析树 那么 该句子是二义性的 如果一个文法包含二义性的句子 则称这个文法是二义性的 否则 该文法是无二义性的 几点说明 1 一般来说 程序语言存在无二义性文法 对于表达式来说 文法 2 1 是二义性的 对于条件语句 经常使用二义性文法描述它 S ifexprthenS ifexprthenSelseS other二义性的句子 ife1thenife2thens1elses2 二义性 歧义性 ambiquity 的定义 下面是S matched s unmatched smatched s ifexprthenmatched selsematched s otherunmatched s ifexprthenS ifexprthenmatched selseunmatched s它显然比较复杂 因此 2 在能驾驭的情况下 使用二义性文法 描述if语句的无二义性文法的产生式 3 对于任意一个上下文无关文法 不存在一个算法 判定它是无二义性的 但能给出一组充分条件 满足这组充分条件的文法是无二义性的 4 存在先天二义性语言 例如 aibicj i j 1 aibjcj i j 1 存在一个二义性的句子akbkck 抽象 语法树与分析树不同 2 6文法的构造 明确描述对象 语言合法的语言结构确定基本符号集 T引入非终结符各种语法成分的结构定义句子的组成规则BNF范式或产生式 文法举例 x x是长度为偶数的0 1串 S 00S 01S 10S 11S 0m1n m n 1 RLS 0S 0AA 1A 1 0n1n n 1 CFLS 0S1 01 ww w a b PSLS aCAE bCBEAa aAAb bAAE aRERE DaR RabR RbCR aCA bCBBa aBBb bBBE bREaR RabR RbCR aCA bCBaD DabD DbED 值得注意的问题 文法描述描述句子的组成规则 不涉及语义文法正确不能保证语义正确 例 明确目标要描述语言的结构确认基本符号集合理引入非终结符 语义明确 本章小结 几个基本概念文法是语言的一种有穷描述 它严格 准确 简洁 文法的形式定义句型 句子 语言文法的分类 的分析树 词法分析 第三章词法分析 词法分析器 Scanner 的功能正则表达式状态转换图词法分析器的设计与实现有穷自动机FA 3 1词法分析 扫描 器的功能 功能 输入源程序 输出单词符号 token 即 把构成源程序的字符串转换成单词符号的序列单词符号的形式按照最小的语义单位设计通常表示为二元组 单词种别 属性值 关键 找出符号的分割符 1 单词符号的表示 常用单词种别 分类 肖军模P53 杜P46 各关键字 保留字 基本字 各种运算符 各种分界符 各用一个种别码标识标识符 用一个种别码标识整 实 字符常数 各用一个种别码标识属性 值 单词的值常数的值 标识符的名字等保留字 运算符 分界符的属性值可以省略 例3 1 单词符号序列while pointer 0 pointer while WHILE SLP FETCH pointer IDN 符号表入口指针 RELOP NE 0 CONST 0 SRP LP pointer IDN 符号表入口指针 INC SEMI RP 跟实现有关 2 相关问题 超前扫描双字符运算符 DO90k 1 10DO90k 1 10预处理问题剔除源程序中的无用符号 空格 换行 注释等扫描器的运行方式作为独立的遍 简单 但需增加额外的开销作为独立的子程序 节省内存 扫描器作为独立的子程序 2 相关问题 符号表的查填兼顾问题兼顾 token自身值作为符号表的入口Token串长度统一 可放宽对标识符的限制 但要增加额外负担不兼顾 token自身值就是标识符 常数本身的符号串速度快 但要限制标识符的长度 2 相关问题 错误处理行 列计数发现并定位词法错误处理方法恐慌模式删除剩余输入中的一个字符向剩余输入插入一个字符字符替换等 3 符号表的作用 符号表是一张表格 由编译程序建立 存在于内存或磁盘中 用于存储程序编译或运行过程中所使用的变量 标识符 和常量 数字常数 字符常数 等信息 词法分析阶段 建立符号表 查填符号表 将不重复的标识符 数字常数和字符常数的性质填入符号表中 如 名字 类型 数值等 并且将变量 或常数 在符号表中的入口地址写到其自身的TOKEN字中 语法分析阶段 主要是使用符号表 在分析过程中 需要用到某个标识符 或常数 时 就从符号表的指定入口处查找出该符号 语义分析及中间代码生成阶段 主要是查填符号表 在生成四元式时 通常不使用变量的名字 而是使用它们在符号表中的入口位置 另外 在翻译说明语句时 要向符号表中填入变量的类型信息等 符号表的作用 2 数据存储分配 将变量 或常数 所使用的数据区映像地址写入符号表中的地址 ADDR 栏 若数据区是动态数据 则在符号表中存储过程层号和位移量等信息 待运行时再计算具体地址 代码优化阶段 使用符号表 一方面 遇到变量时 要到符号表中查找它的具体信息 另一方面 在优化过程中 也有可能要使用符号表 例如在进行合并已知量的优化时 要检查变量是否有常数值 这时要使用符号表的数值 VAL 栏进行判断 目标代码生成阶段 在此过程中主要是查找符号表 为最终生成目标代码提供必要的信息 如建立DAG节点标记时使用符号表暂存变量的引用活跃信息 4 符号表的内容 符号表中包括名字 NAME 类型 TYPE 种属 KIND 数值 VAL 和地址 ADDR 等栏 还带有一个字符串表 其中名字栏包括两个子栏 一个用于存放标识符在字符串表中的起始位置 另一个存放该标识符的长度 类型栏表示该标识符的类型 整 实 布尔和字符型四者之一 种属栏表示该标识符属于哪一种类的名字 简单变量 常数名 数组名 过程名等 数值栏存放常数标识符的值 地址栏存放分配给该符号的地址 5 一种符号表的数据结构 6 输入缓冲 每次移动向前指针都需要做两次测试 双缓冲区问题 超前扫描导致的效率问题 如何设计和实现扫描器 大小问题128Byte 2 1024Byte 2 4096Byte 2 ifforward在缓冲区第一部分末尾thenbegin重装缓冲区第二部分 forward forward 1endelseifforward在缓冲区第二部分末尾thenbegin重装缓冲区第一部分 将forward移到缓冲区第一部分开始endelseforward forward 1 forward forward 1 ifforward eofthenbeginifforward在第一部分末尾thenbegin重装第二部分 forward forward 1endelseifforward在第二部分末尾thenbegin重装第一部分 将forward移到第一部分开始endelse eof在表示输入结束 终止词法分析end 6 输入缓冲 1 3 2词法单元的识别 词法分析器要求能够检查输入字符串 在前缀中找出和某个模式匹配的词素 通过正则定义来描述各种词法单元的模式 1 正则表达式 RE 设 是一个字母表 是 上的RE L 是 上的RE L 对于 a a是RE L a a 如果r和s是RE L r R L s S 则 r与s的 和 r s 是RE L r s R S r与s的 乘积 rs 是RE L rs RS r的克林闭包 r 是RE L r R 只有满足 的才是RE 2 正则定义的例子 C语言标识符的正则定义letter A B Z a b z digit 0 1 9id letter letter digit id对应的正则表达式为 A B Z a b z A B Z a b z 0 1 9 3 正则表达式的扩展 基本运算符 并 连接 Kleen闭包扩展的运算符 一个或多个实例 单目后缀 r 等价于rr 零个或一个实例 r 等价于 r字符类 a1a2 an 等价于a1 a2 an a e 等价于a b c d e用来使得正则表达式更加简洁 但是不会使得正则表达式能够描述更多的语言 4 运算的优先级 运算优先级和结合性 高于 连接 和 连接 高于 具有交换律 结合律 连接 具有结合律 和对 的分配律 指定优先关系意义清楚时 括号可以省略例 L a a b a b a b a a b a b a b 5 状态转换图 状态转换图是词法分析器的重要组件之一状态转换图 transitiondiagram 状态 state 表示了可能在识别词素的过程中可能出现的情况状态看作是已处理部分的总结 某些状态为接受状态或最终状态 表明已经找到词素 加上 的接受状态表示最后读入的符号不在词素中 开始状态 初始状态 用start边表示 边 edge 从一个状态指向另一个状态 边的标号是一个或者多个符号 如果当前符号为s 下一个输入符号为a 就沿着从s离开 标号为a的边到达下一个状态 状态转换图的例子 6 保留字和标识符的识别 在很多程序设计语言中 保留字也符合标识符的模式 识别标识符的状态转换图也会识别保留字 解决方法在符号表中预先填写保留字 并指明它们不是普通标识符 为关键字 保留字建立单独的状态转换图 并设定保留字的优先级高于标识符 3 3词法分析器的设计和实现 从转换图构造词法分析器的方法变量state记录当前状态一个switch根据state的值转到相应的代码每个状态对应于一段代码 这段代码根据读入的符号 确定下一个状态如果找不到相应的边 则调用fail 进行错误恢复进入某个接受状态时 返回相应的词法单元 注意状态有 标记时 需要回退forward指针 状态转换图的例子 Relop对应的代码概要 处理多个模式的方法 词法分析器需要匹配多个模式解决方法顺序地尝试各个词法单元对应的状态转换图 如果引发fail 回退并启动下一个状态图 可以根据优先级确定尝试顺序 并行地 运行各个状态转换图 通过greedy策略 识别最长的和某个模式匹配的输入前缀预先把各个状态转换图合成一个状态转换图 然后运行这个状态转换图 3 4有穷自动机FA 本质上和状态转换图类似 分为两类 不确定的有穷自动机 NondeterministicFiniteAutomata NFA 边上的标号没有限制 一个符号可出现在离开同一个状态的多条边上 可以做标号确定的有穷自动机 DeterministicFiniteAutomata DFA 对于每个状态以及每个符号 有且只有一条边 两种自动机都识别正则语言 1 不确定的有穷自动机 NFA由以下几部分组成一个有穷的状态集合S一个输入符号集合 inputalphabet 转换函数 transitionfunction 对于每个状态和 U 中的符号 给出相应的后继状态集合一个状态s0被指定为开始状态 初始状态 有些定义中可以有多个开始状态 S的一个子集被指定为接受状态 2 NFA的例子 状态集合S 0 1 2 3 开始状态0接受状态集合 3 转换函数 0 a 0 1 0 b 0 1 b 2 2 b 3 相应的图形表示 3 输入字符串的接受 一个NFA接受输入字符串x 当且仅当对应的转换图中存在一条从开始状态到某个接受状态的路径 该路径中各条边上的标号组成x 标号不考虑 前面的NFA接受aabb 因为 NFA接受的语言 从开始状态到达接受状态的所有路径上的标号串的集合 就是它接受的所有符号串的集合 4 确定有穷自动机 一个NFA被称为DFA 如果没有 之上的转换动作对于每个状态s和每个输入符号 有且仅有一条标号为a的离开s的边可以高效判断一个串能否被一个DFA接受 每个NFA都有一个等价的DFA 即它们接受同样的语言 5 从正则表达式到自动机的转换 正则表达式可以简洁 精确地描述词法单元的模式但是在进行模式匹配时需要模拟DFA的执行 因此 需要将正则表达式转换为DFA步骤 正则表达式到NFANFA到DFA 6 正则表达式到NFA 基本思想根据正则表达式的递归定义 按照正则表达式的结构递归地构造出相应的NFA 算法分成两个部分 基本规则处理 和单符号的情况对于每个正则表达式的运算 建立组合组合相应NFA的方法 转换算法 1 基本规则部分表达式 表达式a 归纳部分s rsr 转换算法 2 归纳部分s 转换算法 3 7 转换得到的NFA的特性 状态数量最多为r中的运算符和运算符分量总数的两倍因为每个步骤只引入两个状态有且只有一个开始状态和有关接受状态除接受状态之外 每个状态要么由一条标号不等于 的出边 要么有两条标号为 的出边 正则表达式到NFA的例子 1 正则表达式 a b abb第一个a对应的NFA第一个b对应的NFA a b 的NFA第二个a的NFA 正则表达式到NFA的例子 2 a b 的NFA 正则表达式到NFA的例子 3 8 NFA合并的方法 合并方法 引入新的开始状态 并引入从这个开始状态到各个原开始状态的 转换 词法分析程序的设计与实现 状态转移图 教材P68状态转移图的实现 教材P68 72子程序scan 输入 字符流输出 Symbol 单词种别Attr 属性 全局变量 数据结构与子例程 数据结构ch当前输入字符token输入缓冲区 字符数组 symbol单词种别 子程序的返回值 attr属性 全局变量 子例程Lookup token 将token存入符号表 返回入口指针isKeyword token 判别token是关键字 返回关键字种别或 1getchar 从输入缓冲区中读入一个字符放入chisLetter isalpha 状态图的实现算法 1 getchar 2 WHILEch是空格 跳过空格2 1DOgetchar 3 CASEchOF4 isdigit ch 4 1ch token getchar 4 2WHILEisdigit ch DOch token getchar 4 3输入指针回退一个字符 4 4将token中的字符串变成数值 attr4 5返回NUM 5 isalpha ch 5 1ch token getchar 5 2WHILEisalpha ch ORisdigit ch DOch token getchar 5 3输入指针回退一个字符 5 4key isKeyword token 5 5IFkey 0THEN返回key5 6Lookup tok