编译原理

编译原理思维导图：包含编译程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。解释程序等等

编译原理

• 绪论
  • 编译程序
    • 通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。 解释程序
  • 词法分析
    • 一般也称为扫描程序（s c a n n e r）。 在这个阶段编译器实际阅读源程序（通常以字符流 的形式表示）。扫描程序将字符串变换成单词符号 流，收集到称作记号（t o k e n）的单元中
    • 词法分析所遵循的是语言的构词规则——正则表达式
  • 语法分析
    • 在词法分析基础上，根据语言的语法规则，把记号构成的符号串分解成各类语法单位，如“短语”、“句子”、“程序段”、“程序”等
    • 通过语法分析，确定整个输入串是否构成语法上正确的程序
    • 语法分析也定义了程序的结构元素及其关系，通常将语法分析的结果表示为分析树（parse tree）或语法树
    • 语法分析所遵循的是语言的语法规则——上下文无关文法
  • 语义分析与中间代码的生成
    • 对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译，产生中间代码
      • 1、对每种语法范畴进行静态语义检查。
      • 2、翻译成中间代码
  • 代码优化
    • 其主要任务是对中间代码进行等价的加工变 换，以期产生更高效的目标代码。 优化的主要方法有常量合并、公共子表达式提 取、循环优化等。
  • 目标代码生成
    • 把经过优化处理后的中间代码变换成特定机器 上的低级语言代码。这个阶段实现了最后的翻 译，它的工作有赖于硬件系统结构和机器指令 的含义。
    • 目标代码的优化工作比较复杂，涉及到硬件系 统功能部件的运用、机器指令的选择、各种数 据类型变量的存储空间分配、以及寄存器的分 配等。
• 词法分析
  • 词法分析概述
    • 词法分析是编译过程中的第一个阶段
      • 子主题
    • 主要任务
      • 从左到右逐个字符地对源程序进行扫描，产生单词符号，通常用记号（token）表示。最后生成并输出一个单词符号序列，或直接将单词符号作为语法分析模块的输入。
    • 记号（token）及其描述
      • 记号（单词符号）是程序语言的基本语法单位
      • 分类
        • 关键字（基本字）
        • 标识符：常量、数组、变量、过程或函数名等
        • 常数：各种类型的常数
        • 运算符：如+、-、*、/、<、>等
        • 分界符：如，、；、（、） 等
        • 空白符：如空格符、换行符等
        • 注释
      • 识别
        • 在词法分析中，可以用状态转换图来识别单词
        • 状态转换图是有限的有 向图，结点表示状 态，用圆圈表示；结 点之间可以用有向边 连接，有向边上可标 记字符
      • 表示形式
        • 词法分析程序输出的记号通常用二元式表示： （单词种别，单词自身的值）
        • 单词种别：表示单词种类，常用整数编码，它供语法分析使用。
        • 单词自身的值：是编译中其他阶段所需要的信息。 如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。 如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值。
    • 状态转换图
      • 转换图：是一张有限方向图。在状态转换图中，结点代表 状态，用圆圈表示。状态之间用箭弧连接。箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类
      • 状态转换图的功能:用于识别一定的字符串
      • 初态：一张转换图的启动条件，至少有一个,用圆圈表示
      • 终态：一张转换图的结束条件，至少有一个，用双圈表示
      • * ：表示多读进了一个字符
  • 正规表达式与有限自动机
    • 正规表达式
      • 是一种适合描述符号串的表示法，可由它定义正规集
      • 正规集即为正规式所描述的串的集合。一般用L()表示
      • 采用正规表达式的原因
        • 词法规则简单，容易被理解
        • 从它容易构造高效识别程序
        • 可由正规表达式自动构造词法分析程序
        • 可用于其他各种信息流的处理
      • 正规表达式的性质
  • 词法分析程序的自动生成
    • 用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言直接编写词法分析程序
    • 利用自动生成工具LEX自动生成词法分析程序
• 语法分析
  • 语言概述
    • 语言
      • 某一字母表上符号串（句子）的集合
      • 语言研究的三个方面
        • 语法—构成语言句子的各个记号之间的组合规 律
        • 语义—按照各种表示方法所描述的各个记号的 特定的含义
        • 语用—在各个记号所出现的行为中，它们的来 源、使用和影响
    • 符号与字母表
      • 字母表：由若干元素（符号、字母）所组成的有限非空集合。常用大写英文字母A,B…或希腊字母Σ 表示
      • 符号：可以相互区别的记号（元素）
  • 形式语言
    • 人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言
    • 形式语言，只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言如英语的语法
    • 形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性
  • 语言的描述方法
    • 形式化描述
      • 指定有限个规则，用于产生所要描述的语言的全部句子， 这些规则构成了该语言的文法
    • 自动机方法
      • 建立一种装置（算法或过程），它以某字母表上的符号 串为输入，判别该符号串是否为其所描述的语言的句子， 此装置即为自动机
  • 文法的形式化定义
    • 规则的非空有穷集合，用G[S]表示，G是文法名， S是识别符号。文法通常表示成四元组的形式： 　　　G=(VN,VT,P,S) 其中：VN—非终结符，用来表示语法范畴。 　　　VT —终结符，语言中不可再分的基本符号。 　　　S —开始符号或识别符号，一个特殊的非终 结符，表示所定义的最大的语法范畴。 P —规则
    • 形式语言分类
      • 0型文法（PSG）  0型语言或短语结构语言
      • 1型文法（CSG）  1型语言或上下文有关语言
      • 2型文法（CFG） 2型语言或上下文无关语言
      • 3型文法（RG）3型语言或正则（正规）语言
  • 句型分析的相关基本概念
    • 短语和直接短语
      • 设G[S]是一个文法， w= αβδ是该文法的一个句型， 如果有S * αAδ， A∈VN , 且 A  + β ,β∈V+, 则称β是句型w中相对于A的短语。 如果有S * αAδ ， A→β, 则称β是句型w中相对于A的直接短语
    • 句柄
      • 句型的句柄：一个句型的最左直接短语。 任何句型的句柄总是存在，且惟一
    • 素短语
      • 含有终结符的短语，如果它不存在也具有同样性质的真子串，则该短语为素短语
    • 文法的二义性
      • 如果一个文法中存在某个句子，对应有两棵 不同的语法树，则说明这个文法是二义的
  • 自上而下语法分析方法
    • 自上而下分析法
      • 从文法的开始符号出发，向下推导(使用最左推导) ，尽可能使用各种产生式，推导出与输入串匹配的句子
      • 自上而下分析面临的主要问题是左递归和回溯，而左递归和回溯问题的产生直接与描述语言的文法有关
      • 解决方法
        • 若要对文法进行确定的自上而下分析，应该改造文法，使其不含左递归和回溯
      • 回溯的消除
        • 回溯产生的原因
          • 某非终结符对应多个侯选式，这些产生式右部的第一个终结符相同，即候选式存在公共的左因子,从而导致语法分析器选择了错误的侯选式
          • 方法
            • 反复使用“提取公共左因子”的方法来改造文法，使得文法的每个非终结符号的各个候选式的首终结符两两不相交，来避免回溯
      • 左递归的消除
        • 直接左递归的消除
        • 间接左递归的消除
          • (1) 代入 (2) 消除直接左递归
    • 自下而上分析法
      • 从输入符号串开始，逐步进行归约(最右推导的逆过程)，直至归约到文法的开始符号
      • “移进-归约”分析法
        • 句型表示
        • 分析器结构
        • “移进- 归约”分析法的栈实现
          • “移进–归约”分析器使用一个栈和一个存放输入符号串w的缓冲器。分析器的初始状态为: 栈 输入 ＃ w＃
• 语法分析和中间代码的表示
  • 语义分析的概念
    • 语义分析：即审查每个语法成分的静态语义
    • 优点
      • 使编译程序各组成部分功能更单一
      • 使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件
  • 属性文法
    • 产生式的语义是由组成该产生式的文法符号的语义所决定的
    • 可将文法符号的语义以“属性”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求值规则，从而形成一种附带有语义属性的前后文无关文法，即属性文法
    • 定义
      • 属性文法=上下文无关文法+属性+求值规则
        • 属性用来描述文法符号的语义特征，如常量的“值”、变量的类型和存储位置等
        • 求值规则（属性计算规则） 与产生式相关联的反映文法符号属性之间关系的 “规则”
        • 求值规则还可进一步扩展为语义规则（语义动作）
    • 属性的分类
      • 综合属性
        • 如果属性b是产生式左部符号A的属性， c1 , c2 , …, ck 是产生式右部文法符号的属性或A的其它属性,则称其为A的综合属性
      • 继承属性
        • 如果属性b是产生式右部符号Xi的属性， c1 , c2 , …, ck 是产生式右部文法符号的属性或A的属性则称其为Xi的继承属性
      • 终结符仅有综合属性,如i.lex_val。通常由词法程序提供。而开始符号没有继承属性
  • 几种常见的中间语言
    • 抽象语法树
      • 语法树是分析树的浓缩表示：算符和关键字作为内部结点
      • 语法制导翻译可以基于分析树，也可以基于语法树
      • 在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象（本质部分），而其他内部结点则表示运算符和关键字等（非本质部分）
    • 逆波兰式
      • 波兰逻辑学家J.Lukasiewicz于1929年提出的一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示
      • 表达式E的后缀表示递归定义如下
        • （1）如果E是变量或常数，则E的后缀表示即E自身。 （2）如果E为E1 op E2形式，则它的后缀表示为E1’E2’op；其中E1’、E2’分别是E1和E2的后缀表示。若op是一元运算符，则视E1和E1’为空。 （3）如果E为(E1)形式，则E1的后缀表示即为E的后缀表示
      • 特点
        • 操作数出现的顺序与原来一致，而运算符则按运算先后的顺序放到相应的操作数之后，即运算符先后的顺序发生了变化，表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序
    • 三地址代码（四元式）
      • 是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用
      • 是一种“三地址语句”（注：三地址语句的种类见课本P98）的等价表示
    • 其它表示法
      • 除前面所述的抽象语法树、逆波兰式、四元式外，常见的中间语言还有接近PASCAL形式的P-代码，接近C格式的C-代码等等
• 代码优化
  • 概念
    • 代码优化
      • 对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。 空间效率和时间效率有时是一对矛盾，有时不能兼顾。
    • 优化要求
      • 必须是等价变换(保持功能) 为优化的努力必须是值得的
  • 分类
    • 机器相关性
      • 机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。 机器无关优化：对中间代码的优化
    • 优化范围
      • 局部优化：单个基本块范围内的优化，包括常量合并、公共子表达式删除、计算强度削弱和无用代码删除等。 全局优化：主要是基于循环的优化，包括循环不变量代码外提、删除归纳变量、计算强度削弱等
    • 优化语言级
      • 优化语言级：针对中间代码，针对机器语言
  • 主要完成的工作
    • 控制流分析的主要目的是分析出程序的循环结构。 循环结构中的代码的效率是整个程序的效率的关键
    • 数据流分析进行数据流信息的收集，主要是变量的值 的获得和使用情况的数据流信息
    • 代码变换：根据上面的分析，对内部中间代码进行等 价变换
  • 局部优化
    • 指基本块内的优化
    • 基本块
      • 是指程序（本课本中假设已经是四元式表示的程序了）中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句
      • 划分
        • 入口语句
          • （1）四元式语句序列的第一个语句； （2）条件转移语句或无条件转移语句转移到的目标语句； （3）紧跟在条件转移语句后面的语句
        • 出口语句
          • （1）下一个入口语句的前导语句； （2）转移语句（包括其自身）； （3）停语句（包括其自身）
        • 基本块的划分
          • 1、求出四元式程序之中各个基本块的入口语句。 2、对每一入口语句，构造其所属的基本块。即由该入口语句到出口语句之间的语句序列。 3、凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。