Part I Compilers#
一、基本了解：Compiler, Interpreter 和 Linker#
什么是 Compiler？#
什么是 Interpreter?#
- 逐条读取源代码，并一条条的翻译成机器语言并执行。
- 不会生成独立的目标代码，每次执行都要从头翻译，这个意义上，效率比编译器低
- 一个特殊的变体：Java
什么是 Linker?#
二、编译器的具体编译流程#
IR 指的是中间表示 (intermediate representation)
- 前端：读取文件信息（词法语法语义）；将代码转化成 IR
- 中端：“从 IR 到 IR”, 是 machine-independent optimization
- 后端：也有machine-independent optimization，还有最终目标代码的生成
Front End#
Lexical analysis#
词法分析
Find
lexemesaccording topatterns, and createtokens
将文件中的字符（根据预订的 pattern）分割成一个个语素 Lexeme, 创造一个个 token
- Lexeme: 人类理解的一个字符串
- Pattern: 表征字符串的性质，通常是 regex. 如果没有 pattern 匹配到文件中的某个内容，就产生
Lexical Errors - Token: 词法分析中的输出，源代码的基本单元：
Token=<token-class, attribute>如INTEGER, 42,L_PAREN, (
Syntax Analysis#
语法分析
Create the (abstract) syntax tree (AST)
创建语法树。
Symbol table, symbol tree…
Semantic Analysis#
语义分析
- 主要任务是检查程序的语义是否正确，即使程序通过了语法分析，也不一定意味着它是有效的。例如：
- 检查变量是否已声明。
- 检查类型是否匹配。
- 检查操作符是否适用于操作数。
- 添加语义信息：语义分析会为抽象语法树（AST）的每个节点添加语义信息，这些信息通常包括：
- 类型信息：变量、表达式和函数的类型。
- 作用域信息：变量和函数的作用域。
- 符号表信息：符号表中存储的变量和函数的定义。
IR Generation#
根据 AST 生成 IR, 如三地址码
Middle End#
中端针对 IR, 提供了和机器无关的优化. IR 相对源码，提供了更易处理的标准形式；相对目标码，提供了其机器无关的上层抽象。（机器无关：和硬件处理和指令集差异无关，任何 ISA 通用）
Back End#
Translate IR to machine code (Meanwhile) Perform machine-dependent optimization
- Instruction Selection
- 不同格式风格的指令各有优劣。
- Register Allocation
- 寄存器比内存快得多，但是个数有限，所以分配寄存器要有一定的优化策略，
这不是乱搞的
- 寄存器比内存快得多，但是个数有限，所以分配寄存器要有一定的优化策略，
- Instruction Scheduling (指令调度)
- 目标机器通常提供支持指令级并行（Instruction-Level Parallelism, ILP）的硬件资源，如多个执行单元、超标量架构或多发射处理器。指令调度的目标是生成能够充分利用这些并行资源的机器代码，从而提高程序的执行效率。
Part || Tools#
看你的 PPT 去,,
Programming languages#
函数式编程（Functional Programming）#
定义
- 函数式编程仅包含函数，不改变状态或数据。每个函数都是独立的，不依赖于外部状态。
- 也就是说，不存在全局变量了。
函数式编程的核心是通过组合和应用函数来解决问题。
函数可以作为参数传递，也可以返回新的函数。
以下是关于**逻辑编程（Logic Programming）**的笔记，结合了你提供的例子：
逻辑编程（Logic Programming）#
1. 定义#
逻辑编程是一种基于数学逻辑的编程范式，通过声明事实（Facts）和规则（Rules）来描述问题，而不是直接指定解决问题的步骤。
2. 核心概念#
- 事实（Facts）：表示已知的、不可改变的陈述。
- 规则（Rules）：表示基于事实推导出新结论的逻辑关系。
- 查询（Queries）：通过逻辑推理引擎验证或推导出新的事实。
3. 示例#
以下是一个逻辑编程的简单示例，使用了事实、规则和查询：
事实（Facts）#
rainy("Nanjing").
rainy("Beijing").
cold("Beijing").
声明了两个城市（南京和北京）的天气情况。
rainy("Nanjing")表示南京是多雨的，rainy("Beijing")和cold("Beijing")表示北京是多雨且寒冷的。
规则（Rules）#
snowy(C) :- rainy(C), cold(C).
规则表示如果一个城市既多雨又寒冷，那么它就是下雪的。
snowy(C)是结论，rainy(C)和cold(C)是前提条件。
查询（Queries）#
?- snowy(X).
查询所有满足
snowy条件的城市。逻辑引擎会根据事实和规则进行推理，输出符合条件的城市。
特点#
- 逻辑编程是声明式的，程序员只需要声明事实和规则，而不需要指定具体的执行步骤。
- 逻辑引擎会自动进行推理，根据事实和规则推导出新的结论。
- 逻辑编程适合解决复杂的逻辑问题，如推理、规划和知识表示。
以下是关于**类型系统（Type Systems）**的笔记，严格按照要求格式化：
Type Systems 类型系统#
Static Typing / Dynamic Typing#
- 静态类型: 在编译时获取类型信息。
例如 Java 中，
String str = “Hello”; // 被静态存储 str = 5; // 报错，因为str类型已经被staticcally(编译时)确定
- 动态类型: 在运行时获取类型信息。
Python 中，
```python
str = "Hello" # 此时是string
str = 5 # 变成整型，不会报错
Strong Typing / Weak Typing#
- 强类型: 类型区分严格，不允许隐式类型转换。
Python 中，
str = 5 + “hello” #报错，python其实是强类型
注意 py 是动态类型，编写时不要显示标注类型，但*不是弱类型*！
- 弱类型: 类型区分较宽松，允许隐式类型转换。
Php:
```php
$str = 5 + "hello" # string 在php中被隐式cast成0,所以结果是0
Scoping 作用域#
Static Scoping（静态作用域）#
根据程序的源代码结构来确定变量的作用域
- 变量的作用域在编译时确定，与程序的结构（如函数嵌套）相关。
- 函数中引用的变量在定义时就绑定到其最近的外部作用域。
- 便于代码理解和优化，现代语言（如 C、Python、JavaScript 等）大多采用静态作用域。
Dynamic Scoping（动态作用域）#
根据程序的 运行时状态（调用栈） 来确定变量的作用域。
- 变量的作用域在运行时确定，与函数调用顺序相关。
- 函数中引用的变量绑定到最近的调用环境中的变量。
- 更灵活，但难以理解和优化，主要用于某些脚本语言（如 Emacs Lisp）。
Function Invocation#
Virtual Functions 虚函数#
- 虚函数是在基类中声明的成员函数，可以被派生类重新定义
override。 - 虚函数允许实现多态（Polymorphism），即通过基类指针或引用调用函数时，会调用实际对象的版本。
- 虚函数必须是
non-private、non-static且non-final。 - 在 Java 中，任何非私有、非静态且非
final的方法都是虚函数，可以被 overridden.
示例代码#
1. void add(List<Integer> list, Integer y) {
2. list.add(y); // 调用的是ArrayList.add()还是LinkedList.add()？
3. }
- 在上述代码中，
List是一个接口，ArrayList和LinkedList是其实现类。 - 调用
list.add(y)时，实际调用的方法取决于list的运行时类型（即实际对象的类型），而不是其声明类型。这是虚函数（多态）的典型行为。
