00-编译原理概述

Donald E. Knuth

Donald E. Knuth (1938~), the "father of the analysis of algorithm", Turing Award, 1974

For his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the "Art of Computer Programming" through his well-known books in a continuous series by this title.

编译器

“高级”语言 \(\implies\)（通常）“低级”语言（如，汇编语言）

汇编语言经过汇编器生成机器语言。

Q：机器语言是如何跑起来的？

作业（P1 ~ P8）：https://www.bilibili.com/video/BV1EW411u7th

广义编译器：语言类应用程序

配置文件解析（.properties）
CSV 文件
JSON 文件
SQL 引擎
TLA⁺/TLAPS（TPaxos.tla）
（Java）字节码解释器
C/C++ 语言编译器
排版工具（\(\LaTeX\)）
绘图工具
L-System

编译器工作

IR：Intermediate Representation（中间表示）

前端（分析阶段）：分析元语言程序，手机素有必要的信息
后端（综合阶段）：利用收集到的信息，生成目标语言程序

1	`position = initial + rate * 60`

作为一名程序员，你看到了什么？

词法：标识符、数字、运算符
语法：包含算术运算的赋值语句
语义：position, initial, rate 是数值类型
物理定律：当前位置 = 初始位置 + 速度 * 时间

但是作为编译器，它仅仅看到了一个字符串。

词法分析器

词法分析器（Lexer/Scanner）：将字符流转化为词法单元（token）流。

\[ token : \left \langle token-class, attribute-value\right \rangle \]

\[ \left \langle id, 1\right \rangle \left \langle ws\right \rangle \left \langle assign\right \rangle \left \langle ws\right \rangle \left \langle id, 2\right \rangle \left \langle ws\right \rangle \\ \left \langle +\right \rangle \left \langle ws\right \rangle \left \langle id, 3\right \rangle \left \langle ws\right \rangle \left \langle *\right \rangle \left \langle ws\right \rangle \left \langle num, 4\right \rangle \]

（此处，1，2，3，4 是指向符号表的指针）