编译器设计读书笔记

Published: by Creative Commons Licence

  • Tags:

基本概念

  • 编译器是将源程序转换为目标程序的工具。
  • 解释器是将源程序解释为执行结果的工具。
  • 虚拟机是针对某种处理器的模拟器,它可以解释执行该机器指令集。
  • 编译器需要负责理解源程序,并将其转换为目标程序。因此编译器架构一般分为前后端,前端负责前者,后端负责后者。
  • 可以在前端和后端之间插入一个优化器阶段,其输入和输出都为IR,负责生成效率更高但是语义上等价的IR。
  • 前端的输出结果要让后端容易了解,前端输出的结果称为IR(Intermediate Representation)。
  • 语法范畴可以认为是满足一类规则的字符串组成的集合,其中的元素称作词素。

前端

前端根据语法和语义判断输入代码是否是良构的。如果代码是有效的,则会建立对应的IR格式的一个表示,否则报告错误信息。

要检查语法,需要将程序的结构和语言的定义进行比较。这需要一种形式化定义,一种是检测输入是否满足该定义的高效机制,和如何继续处理无效输入的相关规划。

数学上,源语言是一个字符串的集合,通常是无限集。由某种规则的有限集所定义,后者称为语法。前端有两趟独立的处理,分别称为词法分析器和语法分析器,来判断输入代码是否是属于语法定义的有效程序集合。

程序设计语言语法通常基于词类来引用单词,词类有时也称作语法范畴,将语法规则基于词类划分可以使得单一规则能够描述多个句子。

词法分析器负责对输入程序的单词切分为不同的单词,并对每个单词进行归类,已归类的词类的形式为$(t,s)$,其中$t$是词类,$s$是具体的单词。

通过组合单词可以的到满足语法规则的句子,这种自动查找推倒的流程称为解析。语法分析器会遍历一遍单词,并判断输入流是否是源语言的一个句子。

但是即使满足语法规则,句子本身的逻辑依旧可能是错误的,比如“Rocks are green vegetable”这个句子是正确的英文句子,但是内容却是错误的。要理解句子中的错误,需要编译器有相关的上下文知识,这需要额外的一些检查。