编译原理笔记（1）

第一章

1. 编译程序与解释程序

   • 编辑器将源语言程序转换成目标语言程序，转换前后的两种程序在逻辑上是等价的。源语言不一定是高级语言程序，目标程序也不一定是低级语言程序。例如：汇编器的别名就是汇编语言编译器。再如：历史上存在过一种编译器将C++编译为C。
   • 解释器则是将将源程序和输入一同输入解释器，解释器一行一行按照输入执行程序，产生输出。
   • 编译程序生成的目标程序在执行时比解释器执行得快；但解释程序错误诊断的效果比编译程序更好。
   • 某些语言需要解释器（Python），某些需要编译器（C++），某些两者都需要（Java）。

2. 语言处理系统 *

   • 源程序经预处理，输入编译器，生成汇编语言程序.obj文件，再经链接程序链接库文件，生成最后的目标机器程序。

3. 为什么要对源程序使用汇编程序

   • 因为机器只能执行特定的机器语言程序，所以高级语言编制的程序，必须经过翻译加工转换为机器语言程序，才能被机器执行。
   • 这种翻译程序一共分为两种：编译程序和解释程序（解释程序是将程序一行一行翻译为机器原语言执行的，而编译程序是整篇翻译的）
   • 低级语言一样需要经过翻译，例如汇编语言，虽然低级但是同样无法被机器执行。

4. 链接程序 *

   • 链接程序两大功能：链接功能（链接库文件和其他目标程序文件）、载入功能（把可执行文件载入内存）。

5. 编译程序分类

   • 诊断编译器
   • 优化编译器
   • 交叉编译器（目标机和宿主机不同）
   • 可变目标编译器（除了和目标机相关的部分，其他部分通用）

6. 编译过程

   • 词法分许阶段
   • 语法分析阶段
   • 语义分析及中间代码生成阶段
   • 优化阶段
   • 目标代码生成阶段

7. 词法分析阶段

   • 读入字符流，将他们组织成有意义的词法单元（token）序列，每个词法单元的格式为:
     • <token-name , attribute-value>
   • token-name为词法单元名字，attribute-value为指向符号表中关于该词法单元的条目。

8. 词法分析阶段会发现的错误

   • 拼写错误
   • 非法字符

9. 语法分析阶段

   • 把词法分析阶段的词法单元序列组织成语法树

10. 语法分析阶段会发现的错误

    • 程序结构上的错误，例如括号未对齐，结尾没有分号等。
    • 所谓结构上的错误，例如赋值语句结构为：
      • <项> <=> <项> <+> <项> <;>
    • 当读入一个词法单元序列为：
      • a = b + ; 时会发现 ; 之前少了一项，这时会发现错误
      • 2 = a + b ;这个序列是符合规则的不会发现语法错误，只有到语义分析时发现将值赋给常量是不对的，才会报错。

11. 语义分析阶段

    • 语义分析阶段使用语法树和符号表中的信息来检测源程序是否符合语义，同时也收集类型信息，把这些信息存在符号表中。

12. 语义分析阶段发现的错误

    • 语义分析阶段一个重要的任务就是类型检查，函数调用的检查。例如检查数组下标是不是整形，函数调用的传参数量和类型是否正确，函数返回值类型是否正确。
    • 当然语义分析阶段是允许一些自动类型转换的。

13. 中间代码生成阶段

    • 在从源程序到目标程序的过程，会生成多种中间表示，语法树就是其中一种，中间代码也是一种，通常使用一种3地址的表示方式。

14. 优化阶段

    • 优化阶段类似于文字的编辑工作，生成更高效的代码（运行更快、内存占用更小、节省资源）

15. 目标代码生成阶段

    • 将中间代码编程特定机器上的低级语言（通常是汇编语言，然后再经汇编器），涉及到内存调度和寄存器调用。

16. 编译程序结构

    • 词法分析器
    • 语法分析器
    • 语义分析与中间代码生成器
    • 优化器
    • 目标代码生成器
    • 表格管理
    • 出错处理

17. 表格管理

    • 表格是多种表，其中最重要的符号表
    • 符号表中记录每个名字及其属性，每扫描出一个名字就填入符号表，其属性有可能在后续的语义分析阶段才填入。

18. 出错处理

    • 重要处理两种错误：
      • 语法错误：包括词法错误、语法错误
      • 语义错误：静态语义错误、动态语义错误（编译器检测不出来）

19. 遍（Pass）

    • 每一遍就是通篇扫描一次程序，生成一个中间表示。遍不是越多越好，太多的遍就会产生太多的中间表示，这些中间表示是占用内存的。
    • 通常将一些阶段组合在一起运行一遍，比如词法分析一行的结果直接送去语法分析，然后只在语法分析全部完成后产生中间表示。

20. 编译器的前端和后端

    • 前端：与目标及其无关，只与源语言和要产生的中间代码有关。主要包括词法分析器、语法分析器、语义分析与中间代码生成器以及优化器的一部分。
    • 后端：仅依赖中间代码，是与目标机器有关的部分。
    • 这样的好处：便于移植，便于编译器的构造。

21. 编译程序的编写

    • 编译程序目前大多数都是用机器语言和汇编语言写的，但是也有用高级语言编写的。这样节省程序设计时间、易于阅读、维护、移植。

22. 编译程序移植

    • 相同机器，不同高级语言的编译器
      • 假设用机器语言编写了一个A语言的编译器，那么我可以用A语言写一个B语言的编译器，这样编写起来很方便，编译时将B语言翻译为A语言，A语言再用机器语言编译运行就可以了。
    • 相同语言，不同目标机器
      • 假设我用机器语言写了一个Q语言在A机器的编译程序AQ，这时我可以用Q语言写一个将自己编译成B机器上机器语言的编译器BQ，这样Q语言通过BQ编译时，因为是在A机器上AQ会先将BQ编译运行，BQ运行起来之后就可以将Q语言翻译成B的机器语言了。

23. 自编译

    • 用机器语言构造一种程序，可以编译语言的核心部分，这时这种语言就可以运行了只不过功能很少，接着用这一部分功能去写一个编译器，编译其他功能。这是就有更多功能可以运行了。不断下去。

---

有其他知识，我再补充。