01_编译原理概述

1. 历史

Donald E.Knuth

• 算法分析之父
• the Art of Computer Programming
• Tex
  • 后来出现LaTex (Lamport Tex)在Tex的基础上增加了宏包的支持
• LR Parser语法分析算法
• Attribute Grammer属性文法 语义分析

2. 编译器

• 工作：高级语言=>低级语言（如，汇编语言）
• 注意：汇编语言经过汇编器变成机器语言
  ![A][https://chillcharlie-img.oss-cn-hangzhou.aliyuncs.com/Screenshot%20from%202023-03-01%2020-35-54.png]
• 机器语言是如何跑起来的？
  【计算机科学速成课】[40集全/精校] - Crash Course Computer Science_哔哩哔哩_bilibili

2.1. 名词

• LR Parser (语法)
• Attribute Grammar (语义)
• IR: Intermediate Representation (中间表示)

3. 语言类的应用程序

1. 配置文件
2. CSV
3. JSON
4. SQL引擎
5. TLA+/TLAPS （数学逻辑）
6. （java）字节码解释器
7. C/C++解释器
8. 排版工具Latex
9. 绘图工具TikZ
10. L-System

4. 编译系统结构

• 前端 (分析阶段): 分析源语言程序, 收集所有必要的信息
• 中端：中间表示IR
  • 加一层兼容层，减少工作量
  • 方便前端后端协作
  • 优化中间语言（与后端优化无关）
  • 机器无关的中间表示优化
• 后端(综合阶段)：和特定的硬件平台有关

• Clang: a C language family frontend for LLVM
  •  / klæŋ/
• 在设计实际生产环境中的编译器时, 优化通常占用了大多数时间
• 代码在编译器视角都是字符串

4.1. 具体组成

4.1.1. 词法分析器 (Lexer/Scanner)

• 词法分析器 (Lexer/Scanner): 将字符流转化为词法单元 (token) 流
• token: <token-class,attribute-value>

4.1.2. 语法分析器 (Parser)

• 语法分析器 (Parser): 构建词法单元之间的语法结构, 生成语法树

4.1.3. 语义分析器

• 语义分析器: 语义检查, 如类型检查、“先声明后使用” 约束检查
  • 通过遍历语法树完成

4.1.4. 中间代码生成器

• 中间代码生成器: 生成中间代码, 如 “三地址代码”
  • 与硬件无关

4.1.5. 中间代码优化器

• 中间代码优化器

4.1.6. 代码生成器

• 代码生成器: 生成目标代码, 主要任务包括指令选择、寄存器分配

4.1.7. 符号表

• 符号表: 收集并管理变量名/函数名相关的信息
  • 变量名：类型、寄存器、内存地址、行号
  • 函数名：参数个数、参数类型、返回值类型
• 为了方便表达嵌套结构与作用域, 可能需要维护多个符号表

4.2. 过程