编译原理

编译原理相关知识点

编译器具有非常模块化的高层结构,可以看成多个阶段构成的”流水线”结构

编译器主要包含五个部分

1. 词法分析 字符序列 -> 记号序列
2. 语法分析 记号序列 -> 抽象语法树(AST)
3. 语义分析 抽象语法树 -> 中间表示(intermediate representation)
4. 优化
5. 代码生成 中间表示(IR) -> 目标代码

词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成

目前进度:https://www.bilibili.com/video/BV1m7411d7iS?p=11&vd_source=f235f2108c2a3afdf8d1609bde0b4591 2.4.1继续,有限状态自动机

词法分析

任务:从字符流到记号流

• 字符流:和被编译的语言密切相关(ASCII,Unicode,or …)
• 记号流:编译器内部定义的数据结构,编码所识别出的词法单元

词法分析例子如下:

if (x>5)
  y="hello";
else
  z=1;

词法分析器的两种实现方法

• 词法分析器的生成器

  快速原型,代码量较少,但较难控制细节

• 手工编码实现法

  相对复杂,且容易出错

  目前流行的实现方法,如:GCC,LLVM,…

手工编码实现

记号的数据结构定义

enum kind {IF,LPAREN,ID,INTLIT, ...};
struct token{
  enum kind k;
  char *lexeme;
};

关键字识别算法

• 转移图算法
• 关键字表算法
  1. 对给定语言中所有的关键字,构造关键字构成的哈希表H
  2. 对所有的标识符和关键字,先统一按标识符的转移图进行识别
  3. 识别完成后,进一步查看H看是否是关键字
  4. 通过合理构造哈希表H(完美哈希),可以O(1)时间完成

关键词和if部分的转移图:

词法分析器自动生成

声明式规范(正则表达式) –> 如lex,flex,jlex等 –> 词法分析器

正则表达式

正则表达式的语法糖

语法分析

语义分析