编译原理 学习笔记

因为最近跟 Babel 打交道比较多,虽然通过自定义 Babel 插件以及魔改 babel-parser 等方式能够达到随心所欲地修改 Javascript 语法树的目的,但是对于解释器的实现本身缺少系统性的认知。大学的时候学习过编译原理这门课,也用 C++ 实现过简易版的 mips 汇编器。最近打算再填新坑,重读 《编译原理 第二版》,构建完整性的知识体系。

第一章 引论

1.1 语言处理器

  • 编译器(compiler):
    源程序 -> [编译器] -> 目标程序
    输入 -> [目标程序] -> 输出
  • 解释器(interpreter): (源程序 + 输入) -> [解释器] -> 输出
  • 预处理器(preprocessor): 聚合源程序,将宏转化为源语言的语句
  • 汇编器(assembler): 生成机器码
  • 链接器: 解析未定义的符号引用,将目标文件中的占位符替换为符号的地址

1.2 一个编译器的结构

字符流 -> [词法分析器]->
符号流 -> [词法分析] ->
语法树 -> [语义分析] ->
语法树 -> [中间代码生成器] ->
中间表示形式 -> [机器无关代码优化器] ->
中间表示形式 -> [代码生成器] ->
目标机器语言 -> [机器相关代码优化器] ->
目标机器语言

第三章 词法分析

3.1 词法分析器的作用

  1. 识别词素,生成词法单元
  2. 过滤注释和分隔符
  3. 将编译器生成的错误信息与源程序位置联系起来
  4. 如果使用宏预处理器,则可以负责完成宏的扩展

示例:

词法单元非正式描述词素示例
if字符 i, fif
id字幕开头的数字 / 字符串pi, score, D2
number任何数字常量3.14159, 0, 6.02e23
literal在引号之间的部分“hello world”

词法分析器很难发现源代码中的错误,需要在语法分析阶段去处理。
当所有词法单元的模式都无法匹配剩余输入匹配的时候,就不能继续处理输入了,最简单恢复策略就是”恐慌模式“,我们从剩余的输入中不断删除字符,直到能够在剩余输入的开头发现一个正确的词法单元为之。

3.4 词法单元的识别

首先构造状态转换图,例如比较运算符 relop 的状态转换图如下:

如何区分标识符和保留字:

  1. 先将保留字存入符号表,找到一个标识符时,如果它未出现在符号表中,就调用 installID 将该标识符放入符号表,它的词法单元是 ID,否则调用 getToken 查看符号表,要么是之前存入的 ID,要么是保留字。
  2. 为每个关键字建立单独的状态转换图,但是用这种方法需要确定词法单元之间的优先级。git

未完待续 …