编译原理与技术

第一章 编译概述

1.1 编译和解释

翻译程序分为两类：编译器和解释器

• 编译器
  • 将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序
  • 先编译，再执行
• 解释器
  • 解释程序解释执行源程序，不生成目标程序
  • 同时处理程序和数据
  • 边解释，边执行

Java语言处理器：编译+解释

1.2 编译的阶段和任务

1. 分析阶段：根据源语言的定义，分析源程序的结构
   1. 词法分析
      对构成源程序的字符串进行分解，识别出每个具有独立意义的字符串（即单词，lexeme），将其转化为记号（token），形成记号流。
   2. 语法分析
      把记号流按语言的语法结构层次地分组，以形成语法短语，常用语法树表示。
      
   3. 语义分析
      对语句的意义进行检查分析，确定类型。一个重要任务：类型检查。
      • 运算符和运算对象是否符合要求
      • 数组下标是否合法
      • 形参与实参的个数和类型是否匹配
2. 综合阶段：根据分析结果构造出所要求的目标程序
   1. 中间代码生成
      • 易于产生
      • 易于翻译成目标代码
      • 三地址代码：除了等号之外至多只有一个运算符；编译程序生成临时变量保存中间结果；有些三地址指令少于3个操作数

        // total:=total+rate*4 的三地址代码
        temp1 := inttoreal(4)
        temp2 := id2 * temp1
        temp3 := id1 + temp2
        id1 := temp3

   2. 代码优化
      对中间代码进行改进，使之占用空间更少，运行更快。

      // 优化后的代码
      temp1 := id2 * 4.0
      temp2 := id1 + temp1
      id1 := temp2

   3. 目标代码生成
      生成可重定位的汇编代码或机器代码
      1. 对程序中每个变量指定内存单元
      2. 对变量进行寄存器分配
3. 符号表管理
   在编译的各个阶段记录源程序用的标志符和他们的属性信息
4. 错误处理
   • 词法分析程序可以检测出非法字符错误。
   • 语法分析程序能够发现记号流不符合语法规则的错误。
   • 语义分析程序试图检测出具有正确的语法结构，但对所涉及的操作无意义的结构。
   • 代码生成程序可能发现目标程序区超出了允许范围的错误。
   • 由于计算机容量的限制，编译程序的处理能力受到限制而引起的错误。
   • 发现错误后，要确定错误发生的位置和性质并进行适度的恢复。

第三章 词法分析

3.1 词法分析程序和语法分析程序之间的3种关系

1. 词法分析作为单独的一遍
   先对程序进行词法分析，生成中间文件存储在磁盘中，再进行语法分析
2. 词法分析作为语法分析的子程序
   
3. 词法分析程序和语法分析程序作为协同程序

• *分离词法分析程序的好处
  1. 可以简化设计
  2. 可以改进编译程序的效率
  3. 可以加强编译程序的可移植性

3.2 词法分析程序的输入与输出

输入

在进行词法分析的时候，为了确定一个符号的意义和作用，往往需要超前扫描若干个字符，比如C语言中的==，/*，++等。所以就必须在词法分析程序读入源程序时设置缓冲区。
然而单一的缓冲区无论如何都无法避免一个单词被缓冲区的边界打断，因此设立了配对缓冲区。

• 配对缓冲区
  
• 每半区带有结束标记的缓冲区
  

输出

词法分析程序的输出是记号，记号和它的属性是一个二元组。

• 在词法分析阶段，对记号只能确定一种属性
  • 标识符：单词在符号表中入口的指针
  • 常数：它所表示的值
  • 关键字：（一符一种、或一类一种）
  • 运算符：（一符一种、或一类一种）
  • 分界符：（一符一种、或一类一种）

// total:=total+rate*4 的词法分析结果
<id，指向标识符total在符号表中的入口的指针>
<assign_op，- >
<id，指向标识符total在符号表中的入口的指针>
<plus_op，- >
<id，指向标识符rate在符号表中的入口的指针>
<mul_op，- >
<num，整数值4>

3.3 记号的描述和识别

线性文法，自动机

3.4 词法分析程序的设计与实现

• 步骤：

  1. 给出描述该语言各种单词符号的词法规则
  2. 画出状态转换图
  3. 根据状态转换图构造词法分析器

• 输出形式：二元式

第四章 语法分析

4.1 语法分析简介

• 输入：记号流
• 输出：分析树
• 常用的分析法：
  • 自顶向下
  • 自底向上
• 处理语法错误
  1. 紧急方式恢复：直接忽略掉出错的语法结构
  2. 短语级恢复：局部纠正错误
  3. 出错产生式：扩充文法，补充出错的产生式
  4. 全局纠错：代价太大，只有理论上的意义

4.2 自顶向下语法分析

4.2.1 递归下降分析

• 试图为输入符号串创建一个最左推导序列
• 每次遇到一个匹配输入串的产生式，就按照这个产生式展开
• 效率低，代价高

4.2.2 递归调用预测分析

1. 如何克服回溯
   • 根据所面临的符号流选择一个唯一的产生式
   • 如果这个产生式可以匹配，那么最后正确匹配的结果必定用到这个产生式
   • 如果这个产生式不能匹配，那么其他的产生式也不可能匹配
   • 如何实现？
     • 让每一个产生式开头的字符各不相同
2. 对文法的要求
   • 不含左递归
   • 首符集（开头的几个符号）不相交
3. 具体操作ppt上有，略。
4. 这一块ppt上讲的全是方法，没有理论和概念，建议面向题目学习。关键词：消除左递归，构造转换图，化简转换图