编译器入门(CS143课程)#
概况#
编译有必要学习一下。
分为两部分。前半部分看[Engineering a Compiler]这本书，了解编译器整体流程/基本概念，记录重点内容。
后半部分记录斯坦福的编译器课程，实际的CS143作业，写代码。
https://web.stanford.edu/class/cs143/
这个课程并不是完全从0写代码，而是在一套小框架上填入最重要的一部分代码，再借助flex/bison等工具完成整个编译器。
认真看看书/完成作业足够入个门。
后续的小目标是写一个C的编译器，中目标是从0写完整的编译器，大目标可以是做一个新的语言及其编译器，并跑在自己实现的cpu上。
课程有配套视频。前4个作业看看书/代码/文档可以硬来。最后的作业得详细看看视频。
其他资料:
[Compilers Principles]等
1. 编译概况#
1.1 介绍#
编译器的工作就是把一种语言翻译成另一种语言。
编译器需要知晓输入语言的格式(语法)和上下文(含义)。同样需要知晓输出语言的相应规则。 最后需要一套方案，把输入语言map到输出语言。
┏━━━━━━━━━━━┓ ┏━━━━━━━━━━━━━━━━━━━━━━━ Compiler ━━━━━━━━━━━━━━━━━━━━┓ ┏━━━━━━━━━━━┓
┃ source ┃ ┃ ┏━━━━━━━━━━━┓ IR ┏━━━━━━━━━━━┓ IR ┏━━━━━━━━━━━┓ ┃ ┃ target ┃
┃ ┣━━━━━╋━━━>┃ front end ┣━━━>┃ optimizer ┣━━━>┃ back end ┣━━╋━━━>┃ ┃
┃ program ┃ ┃ ┗━━━━━━━━━━━┛ ┗━━━━━━━━━━━┛ ┗━━━━━━━━━━━┛ ┃ ┃ program ┃
┗━━━━━━━━━━━┛ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┗━━━━━━━━━━━┛
典型的three-phase编译器架构。
前端处理输入语言，后端处理输出语言。
中间的数据称为intermediate representation(IR)，具体的内容和具体语言高度关联。
一般编译器都会在其中安排优化器，把原始IR在各种层面上进行优化。
编程语言和一般自然语言不同，它必须尽可能严谨、明确、简洁。
编译器一般把代码翻译成目标机器的代码。
也有的把代码翻译成另一种人类有好的语言。比如翻译成c语言。这种称为source-to-source translators。
有的形态称为interpreter，与compiler有很多相似之处。
大体的区别是compiler会生成低级代码，最终转成可执行文件之类。工作是事先完成的。
interpreter一般是online，运行时现读代码，一行行执行。不生成可执行文件。
just-in-time(JIT) compiler
编译器的基本原则
忠于输入程序
对输入程序进行优化
1.2 编译器结构#
IR可以看作是另一个版本的输入程序。
对于two-phase compiler，前端需检查输入程序的格式，把代码map到IR。
后端把IR map到目标机器的指令集并做资源的整理。
后端不用考虑前端生成的IR有错。
编译器可以对IR做多遍(multiple passes)操作。
two-phase可以简化retargeting(为不同的处理器架构编译)。
在IR中间插入一个优化器，就变成了three-phase。优化器本质上是一个IR-to-IR的转换器。
1.3 TRANSLATION#
考虑代码
a = a * 2 * b * c * d
下面看下编译的过程
1.3.1 前端#
首先必须明白代码的语法和语义。如果语法错，要报错。
┏━━━━━━━━━━━━━ Front End ━━━━━━━━━━━━┓
┃ ┏━━━━━━━━━━━┓ ┏━━━━━━━━━━┓ ┃
━━━╋━━━>┃ scanner ┃<━━>┃ parser ┣━━━╋━━>
┃ ┗━━━━━━━━━━━┛ ┗━━━━━━━━━━┛ ┃
┃ ↕ ┃
┃ ┏━━━━━━━━━━━━┓ ┃
┃ ┃ elaborator ┃ ┃
┃ ┗━━━━━━━━━━━━┛ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
scanner把输入文本转成一系列word，检查拼写。
parser检查syntax。把word装入语法模型(grammer)。
parser可不断调用scanner，得到后续的word。
parser可调用elaborator做一些其他计算，比如创建IR，检查类型一直，整理储存数据。
scanner和parser应用非常广泛。比如html、sql等的解析
检查语法#
检查语法就是比较程序的结构和这门语言的语法模型。
一套grammar定义一套word。在word和变量之上，规定一套规则，称为production。
例如一般英语句子的语法
sentence -> subject verb object endmark
那么对于Compilers are engineered systems.
scanner要找到一个个word，并知道它的属性。
scanner最终可能生成这样的数据
(noun, "Compilers"), (verb, "are"), (adjective, "engineered"), (noun, "systems"), (endmark, ".")
下一步把这些word往grammar匹配。
grammer
1. sentence -> subject verb object endmark
2. subject -> noun
3. subject -> Modifier noun
4. Object -> noun
5. Object -> Modifier noun
6. Modifier -> adjective
Compilers are engineered systems.对应的grammer解析
sentence
使用规则1 subject verb object endmark
使用规则2 noun verb object endmark
使用规则5 noun verb Modifier noun endmark
使用规则6 noun verb adjective noun endmark
parser就是要出这样的推演路径，从而保证语法正确。
语法正确并不代表有意义，比如Rocks are green vegetables.。
确认语法正确后，开始创建一系列IR等相关的后续数据。
Intermediate Representations#
编译器根据语言和功能，包含各种类型的IR。有的IR生成图结构，有的生成汇编代码。
例如
a = a * 2 * b * c * d
变成
t0 = a * 2
t1 = t0 * b
t2 = t1 * c
t3 = t2 * d
a = t3
1.3.2 优化器#
接下来一条一条处理IR生成的语句。可进行代码的优化。
优化一般包含分析和转换(analysis and transformation)。
分析包括Data-flow分析和Dependence分析。
根据分结果对代码进行转换。转换是一个大课题，可以出好多本书。
1.3.3 后端#
后端扫描IR，生成目标机器的代码。
把IR操作转换为ISA对应的操作。11章细说
指令调度。确定操作的顺序。12章细说
寄存器的安排。13章细说
整个工作称为code generation。
这三个问题都是困难问题。指令选择有大量的可选项，而指令调度和寄存器的安排都是NP-complete。
Instruction Selection#
本书的低级语言用ILOC。
第一步把IR操作转成机器指令。见图1.4。用了四种ILOC指令。
Register Allocation#
指令选择阶段，编译器会假想硬件的寄存器是无限数量。
此阶段要考虑实际情况。
Instruction Scheduling#
演示指令的顺序如何影响所需的指令周期。
1.4 ENGINEERING#
一些工程角度的讨论
2. Scanners#
到此可以完成作业2。
3. Parsers#
以scanner输出的words作为输入，确定语法是否合法。
3.1 介绍#
parsing是前端的第二阶段。
table-driven parsers
direct-coded parsers
hand-coded parsers
scanner是hand-coding更常用。
而parser更倾向于用工具生成。
Context-free grammars(CFGs)用来描述context-free语言。
有两种算法对其进行解析，top-down和bottom-up。
两者风格和实现都有很大不同，都很重要。
两者都有大量工具支持。
有一个正式的语法G，如果一串词语s符合语法G，就说G derives s。
parser尝试证明某个s符合语法G，这个就叫parsing。
Top-down语法分析
用预测下一个词，来匹配语法。
对于有限的语法，top-down准确且高效。
Recursive-descent属于top-down/hand-coded。
LL(1)属于top-down/table-driven。Bottom-up语法分析
从底层往上走，从输入的具体词语开始，网上匹配语法。
LR(1)属于bottom-up/table-driven。
3.2 语法的表示#
3.2.1 为什么不用正则表达式#
3.2.2 Context-Free Grammars#
传统方法就是用CFG表示。它又有很多高效的变种。
例如一条规则 stmt -> if ( expr ) stmt else stmt
一条规则称为一个production。
其中的if/else/括号称为terminal。
expr/stmt这种带变量性质可以再展开的称为non-terminal。
3.3 top-down PARSING#
从语法树的顶层开始往下分析，直到叶子与输入的词语完全匹配。
一个使top-down高效的特性。分析过程中，CFG的大部分子集是不用回溯的。
top-down是做一个leftmost的推理。
Left Recursion问题
Backtrack-Free Parsing
Left-Factoring
3.3.2 Top-Down Recursive-Descent Parsers#
3.3.3 Table-Driven LL(1) Parsers#
3.4 BOTTOM-UP PARSING#
自底向上。
3.4.1 The LR(1) Parsing#
A->B表示一个规则。
(A->B, k)称为一个handle。k表示位置。
有action和goto两个表。
看懂图3.17/3.18/3.19和下面的伪代码就基本懂了LR(1)的逻辑。
这个例子语法是一个可嵌套的小括号list。比如()，()(), (())()()。
LR(1):
栈.push(invalid, invalid)
栈.push(start_symbol, s0) # 压入start_symbol和状态s0
# 栈中的数据类型是(sybmol, 状态)，比如(A, s1)。
word = 取下一个word()
while(1):
state = 栈顶状态
if action(state, word) == "shift Si": # 决定拿着word。继续往下看。
栈.push(word, si) # 压入word
word = 取下一个word()
elif action(state, word) == "reduce A -> B": # 采用A->B这个规则，也就是把B往上缩减到A。
栈.pop(|B|) # 把栈上B包含的sybmol都弹出
state = 栈顶状态
栈.push(A, Goto(state, A))
elif action(state, word) == "accept" and word == EOF: # 匹配到了根状态而且输入完毕。成功。
break
else:
报语法错误
成功
解析(())()的例子
操作顺序 |
state |
当前word |
当前栈 |
handle(匹配) |
action |
说明 |
|---|---|---|---|---|---|---|
0 |
- |
- |
(Goal, 0) |
初始状态 |
||
1 |
0 |
取得( |
(Goal, 0) |
shift 3 |
状态0取到(。查表0->s3。栈压入(。 |
|
2 |
3 |
取得( |
(Goal, 0) ((, 3) |
shift 7 |
状态3取到(。s3->s7。 |
|
3 |
7 |
取得) |
(Goal, 0) ((, 3) ((, 7) |
shift 12 |
状态7取到)。s7->s12。 |
|
4 |
12 |
(Goal, 0) ((, 3) ((, 7) (), 12) |
( ) |
reduce 5 |
存在handle，把栈顶的()拿掉。 |
|
5 |
6 |
(Goal, 0) ((, 3) (Pair, 6) |
Pair |
reduce |
Pair存在handle可缩减为List。 |
|
6 |
5 |
取得) |
(Goal, 0) ((, 3) (List, 5) |
shift 10 |
状态5取得(转到10。 |
|
7 |
10 |
(Goal, 0) ((, 3) (List, 5) (), 10) |
(List) |
reduce 4 |
reduce弹出后栈顶状态为0，查0的Pair得到2 |
|
8 |
2 |
(Goal, 0) (Pair, 2) |
Pair |
reduce 3 |
reduce为List。查0的List得到1。 |
|
9 |
1 |
取得( |
(Goal, 0) (List, 1) |
shift 3 |
状态0取得(转到3。 |
|
10 |
3 |
取得) |
(Goal, 0) (List, 1) ((, 3) |
shift 8 |
状态3取得)转到8。 |
|
11 |
8 |
EOF |
(Goal, 0) (List, 1) ((, 3) (), 3) |
( ) |
reduce 5 |
reduce为Pair，查1的Pair得到4。 |
12 |
4 |
EOF |
(Goal, 0) (List, 1) (Pair, 4) |
List Pair |
reduce 2 |
reduce为List，查0的List得到1。 |
13 |
1 |
EOF |
(Goal, 0) (List, 1) |
List |
accept |
此时已经为EOF状态。整个流程成功。 |
问题是如何生成action和goto两个表。
这是一个繁重且极其细致的工作。手写一个个状态是不现实的。
下一节介绍生成LR(1) parse表的算法。
这里实际是在学parser generator的原理，和bison是一个层面，最后生成一个parser实体。
程序员大多时候只是用parser generator生成一个parse，然后解析某个语言，而不是经常去写parser generator。
LR是一个家族。一个LR(k) parser采用k个lookahead，往后看k个symbol。
矛盾的是，增加k并不能让parser识别更多语言。LR(1)能识别的语言跟LR(k>1)一样多。
LR(1)的语法甚至可以比LR(2)或LR(3)还多。
3.4.2 Building LR(1) Tables#
需要一种模型。称为canonical collection of sets of LR(1) items。
描述所有的状态和其转移。
学习两个例子。一个就是之前的括号解析，另一个是下一节的if-then-else。
LR(1) Items#
一个LR(1) item用[A->B*Y, a]表示。
a是lookahead symbol。
A->B*Y意思就是语法里的BY归成A。
*指出匹配处于什么状态。有三种可能。
[A->*BY, a]
表示目前可能能匹配到A，如果lookahead是B，那么可以向A更近一步。
这个item叫做possibility。[A->B*Y, a]
已经从上个状态匹配了B，向A更近了一步。
这个item叫做partially complete。[A->BY*, a]
parser已经找到了BY。这时如果lookahead是a，就能得到一个handle。
这个item叫做complete。
可以看出*左边是已经匹配到的数据(left context)。和之前流程中的当前栈上数据差不多？
图3.21是括号语法的LR(1) item集合。
Constructing the Canonical Collection#
3.4.3 Errors in the Table Construction#
到此可以完成作业3。甚至可以不用看具体的算法就能完成。
4. Intermediate Representations#
IR的总体介绍
4.1 介绍#
编译器一般有几个pass。前面pass的数据传给后续的pass。
整个这其中的数据就叫intermediate representation。
可能只有一个IR，也可能有多个。编译器就是依赖这些IR来工作，并不会中途返回去查源代码。
编译器会生成各种辅助数据来提高效率或者优化等等，这些都属于IR。
在一个pass结构的编译器里，IR是一个程序的主要表示方法。
几乎所有的阶段都是在操作IR。所以IR的结构/性能等直接关系到整个编译器的效率。
总之IR是各种重要。
4.2 IR的种类#
以三个维度来分类：组织结构/抽象层次/使用模式
组织结构#
Graphical IR
把信息转成图结构Linear IR
重组伪指令Hybrid IR
上面两种的结合
抽象层次#
编译器需要选择某个IR对数据处理到什么深度。可以只是简单处理到一个树状表示，也可深到生成机器指令。
near-source level
更靠近源码near-machine level
更靠近机器
使用模式#
Definitive IR
确定的IR。IR的主要形态。一般转到下一个pass时会有确定的IR。Derivative IR
用来完成一些特殊的/临时性的任务。可作为确定IR的补充。
一般是在一个pass内生成。
命名很重要。
4.3 GRAPHICAL IR#
4.3.1 syntax相关的树#
parse树/ast/有向无环图(DAG)
parse tree#
见图4.2。
Abstract Syntax Trees#
ast和parse树结构一样的。但是去掉了一些相对无关的节点。比如去掉了nonterminal，直接展开到terminal。
Directed Acyclic Graphs#
ast虽然精简，但仍然是终于源码的。
dag是对ast的一种压缩，去掉了ast中重复的部分。
一个节点可以有多个父节点。重复的部分得到复用。
主要使用原因：
减少IR内存的消耗
减小冗余
4.3.2 图#
Control-Flow Graph#
Block Length#
Dependence Graph#
Call Graph#
4.4 LINEAR IRS#
线性IR用一串有序的指令表示程序。汇编指令是一个例子。
线性IR一般用来生成汇编代码。
背后的逻辑很简单。输入的源码就是线性的，输出的指令必然也可以是线性的。
One-address
Two-address
Three-address
4.4.1 Stack-Machine Code#
one-address形式。
cs143的作业用stack machine code。
4.4.2 Three-Address Code#
i <- j op k的形式
4.4.3 Linear Code的表示#
4.4.4 从Linear Code生成CFG#
4.5 SYMBOL TABLES#
4.6 NAME SPACES#
4.7 PLACEMENT OF VALUES IN MEMORY#
5. Syntax-Driven Translation#
scan/parse过后，为了translation/优化/生成指令等，需要生成IR code。
5.1 介绍#
基本的IR会记录一些信息，比如变量的类型和大小，存在什么位置等等。
创建IR及其辅助数据的方法
syntax-driven translation
对IR继续遍历并做一些更复杂的计算
这一章主要讲从源代码生成IR的机制。
编译器需要实现一个机制，把信息收集和IR生成绑定到输入程序的syntax结构。
编译器需要维护好命名，给定一个名字，必须知道它绑定的具体数据。
编译器针对语言结构需要有一个方案，从变量引用到函数调用到内存分配，等等都要考虑。
5.2 BACKGROUND#
5.3 SYNTAX-DRIVEN TRANSLATION#
对于自底向上的LR(1)，每次parser进行reduction，也就是匹配到了一条规则，就进行一堆相关操作。
这个就叫syntax-driven。
5.3.1 例子#
解析一个整数为例。根据我们的bison知识，每次匹配到一个尾部的digit时，可以把当前值x10再加上digit值。最后可得到正确的整数值。
如果语法写成单个digit放在前面。也可以解析，每次匹配到DList时需要多记录当前的层级相关数据，最后依靠层级信息得到正确的整数值。
5.3.2 Translating Expressions#
图5.4。用AST来做syntax-driven translation。
图5.5。在AST基础上可以做三地址码的生成。
Implementation in an LR(1) Parser#
syntax-driven可在基本的LR(1)基础上实现。
修改1:栈数据加一个值value，变为3个元素。
修改2:reduce之前做一个操作PerformActions(A->B)得到value。
如果操作是reduce，value是赋给$$的值。
如果操作是shift，value就是lexeme值。
LR(1):
栈.push(invalid, invalid, new_invalid)
栈.push(start_symbol, s0, new_invalid) # 压入start_symbol/状态s0/new_invalid
# 栈中的数据类型是(sybmol, 状态, value)，比如(A, s1, 0)。
word = 取下一个word()
while(1):
state = 栈顶状态
if action(state, word) == "shift Si": # 决定拿着word。继续往下看。
栈.push(word, si, lexeme) # 压入word
word = 取下一个word()
elif action(state, word) == "reduce A -> B": # 采用A->B这个规则，也就是把B往上缩减到A。
new_value = PerformActions(A->B)
栈.pop(|B|) # 把栈上B包含的sybmol都弹出
state = 栈顶状态
栈.push(A, Goto(state, A), new_value)
elif action(state, word) == "accept" and word == EOF: # 匹配到了根状态而且输入完毕。成功。
break
else:
报语法错误
成功
Handling Nonlocal Computation#
到此为止，只看到语法的local计算。每条规则的计算只用了自己范围内的数据。
而编译器中有很多计算需要用到其他部分的数据。
一个例子是语言中变量/函数/object等的类型/生命周期等信息。这些必须是全局的而不是local的。
编译器第一次碰到某个entity时，要确定它的各种属性。后续要随时随地能获取。
一个声明变量的例子。
Form of the Grammar#
声明变量的另一种写法，把int/float之类的匹配和list写到一起。省去了type的全局变量。
Tailoring Expressions to Context#
5.3.3 Translating Control-Flow Statements#
if then else的例子
5.4 命名环境#
现代编程语言可创建复杂的命名空间。很多语言支持词法的命名层级。
很多语言支持面向对象的命名层级。
当编译器碰到一个名字时，syntax-driven translation必须把这个名字map到一个entity(变量/函数等)。
name-to-entity binding。
命名空间可以有多个子空间或者scope。
Static binding
Dynamic binding
5.4.1 Lexical Hierarchies#
原则:在程序的某一点p，一个名字n一定是关联到一个，与p在词法层面最近声明的一个n。
简单讲就是n会关联到当前scope，如果当前scope没有n，不断往上一级scope找。
最外层的scope通常包含全局名字。
Modeling Lexical Scopes#
symbol table
Building the Model#
Examples#
5.4.2 Inheritance Hierarchies#
5.4.3 Visibility#
5.5 TYPE INFORMATION#
一个type是一系列属性的集合。同一type的实例拥有相同的属性。
5.6 STORAGE LAYOUT#
有了命名空间和类型信息，可以做storage layout了。
编译器给每个entity分配一个所属的逻辑数据区域。
根据其声明周期和可见性。给每个entity确定所属的逻辑数据区域的offset。
5.6.1 Storage Classes and Data Areas#
三种storage class
automatic
static
irregular
Automatic Variables#
automatic变量a的生命周期和它的声明scope一样。所以可以存在scope的local data area。
Static Variables#
static变量s生命周期是从定义到最后一次使用。
Irregular Entities#
生命周期为程序控制。比如动态分配内存。
Temporary Values#
程序运行过程中，会产生很多临时的值，并不会跟某个名字相关。
比如数学运算的一些中间值。
5.6.2 Layout Within a Virtual Address Space#
运行时如何使用memory。大多数系统中，程序运行在一个自己的虚拟地址空间。
操作系统会把虚拟地址映射到真实的地址。
编译器只需关注虚拟地址空间。
一个进程的虚拟地址空间的layout
┏━━━━━━━━━━━━━┓ Low
┃ Code ┃
┣━━━━━━━━━━━━━┫
┃ Static ┃
┣━━━━━━━━━━━━━┫
┃ Heap ┃
┣━━━━━━━━━━━━━┫
┃ ... ┃
┃ ┃
┃ Free ┃
┃ Memory ┃
┃ ┃
┃ ... ┃
┣━━━━━━━━━━━━━┫
┃ Stack ┃
┗━━━━━━━━━━━━━┛ High
Code
存放可执行文件。运行时一般不变。Static
存放static entity。包括全局变量、static变量。
大小可在link阶段获知。Heap
可变的内存区域。动态分配的内存在这里。Stack 其他各种数据。
heap和stack往中间对着涨，这样可以最大利用空间。
不同程序可能表面上用了同个地址，但是操作系统一定会把他们映射到不同的地址，保证不会出乱子。
5.6.3 Storage Assignment#
Internal Layout for Arrays#
Internal Layout for Strings#
Internal Layout for Structures#
Internal Layout for Object Records#
Object Record Layout for Multiple Inheritance#
5.6.4 Fitting Storage Assignment into Translation#
5.6.5 Alignment Restrictions and Padding#
5.7 ADVANCED TOPICS#
6 Procedures#
主要讲函数调用相关
6.1 介绍#
procedure是一般语言中的核心。这里单独用一章来讨论。
每个procedure有自己存储空间。一个程序基本上是以系列procedure的组合。
有了procedure就可以支持分部分编译，从而实现大型软件的开发。否则代码动一个字就要全部重编，是不能接受的。
调用函数时保存调用者的环境，初始化被调函数的环境。
6.3 RUNTIME SUPPORT FOR NAMING#
6.3.1 Runtime Support for Algol-Like Languages#
Activation record
AR是为函数的调用创建的一块数据。就是上面说的环境。
每次调用都生成一个。
编译器必须
生成函数的返回地址，存在被调的环境。
map调用参数到被调环境。
创建local变量所需的内存空间
其他与外界交互所需的数据
AR数据
parameter area
参数寄存器数据
储存在调用过程中需要保存的寄存器数据返回值
返回地址
addressability
让被调者可以access到其他scope的数据ARP
指向调用者的ARlocal data area
其他本地数据
看到这里思考了一下，这些数据的维护逻辑在哪实现？
是编译器中的某一部分代码？
再看标题Runtime Support，难不就是常听到的运行时库么。
大概猜测总结一下，比如c程序。
一般用户层面是不关心runtime的，就写写逻辑完事。但是编译时几乎都会link对应的c运行时库。
这个运行时库的基本功能就是实现了上述的环境维护，让你能启动程序/花样调函数/分配数据等等。
其实它是一门语言的基础设施。可能是用高级语言比如c写，也可能用汇编写。
我猜它可能在生成机器指令的过程中检测你的代码行为，一旦你调函数或者其他操作，它就用runtime的预定流程对你的操作进行封装，生成维护调用环境的机器指令，最后整合成一份完整机器指令。
如果不带上runtime，你c代码根本跑不了。当然你也可以不用它的，自己写runtime！
那么可能和写汇编的形式差不多了，可能是得在c代码里做各种汇编操作？有点像实现协程那种感觉，就是对调用过程做hack。本质也就是做一个runtime。
所以简单说，这个runtime就是实现了高级语言的函数调用等等功能。
人们能用很简单的语句写逻辑并运行，费劲做出runtime是一个要付出的代价。
它本质是嵌在编译器的生成机器指令的流程中。然后可以把这部分抽出来，因为它较为通用。
把它抽出来做成单独的库，方便维护，方便针对跨平台做修改。
runtime可以包括更大的功能比如线程库之类。
区分操作系统和cpu架构。
再查查资料，整体大差不差。
https://en.wikipedia.org/wiki/Runtime_library
https://en.wikipedia.org/wiki/Runtime_system
6.3.2 Runtime Support for Object-Oriented Languages#
比如C++功能繁多，runtime自然比C之类复杂得多。
object record(OR)
6.4 PASSING VALUES BETWEEN PROCEDURES#
6.5 STANDARDIZED LINKAGES#
链接是编译器/操作系统/目标机器三方达成的协议。
6.6 ADVANCED TOPICS#
7 Code Shape#
这一章开始讲指令生成。
7.1 介绍#
对同一个代码，有较多的指令生成方式。有的快，有的耗内存少，有的耗寄存器少，有的耗电少。
代码形状直接影响后续的优化器等组件的工作。
比如c语言switch一个字符，有256个case。
最简单是生成256个比较指令，运行时如果输入是均匀分布，平均需要比较128次才能匹配到，n/2的速度。
如果编译器对256个字符做预处理，做成二叉搜索，那么就是log(n)的速度。
再如果做成一个数组的形式，直接按index就能得到结果。那么就是O(1)的速度。
x+y+z的例子。优化需要依赖上下文。
7.2 算术操作#
四则运算的例子。
7.2.1 Function Calls in an Expression#
7.3 ACCESS METHODS FOR VALUES#
7.3.1 Access Methods for Scalar Variables#
Scalar变量。先确定是存在寄存器还是存在内存中。
寄存器中
直接可用。对于add r1, r2 => r1一般机器都能在一个周期完成。
寄存器的一个主要优化就是把常用的变量存到寄存器里。内存中
有多种原因导致主要存在内存中。
可用(scope_level, offset)的形式存。其他scope中的local变量
得用addressability机制去找。Static and Global Variables
其地址用一个assembly-level的label表示。
isa会决定怎么取值。作为参数的变量
heap中的变量
7.3.2 Access Methods for Aggregates#
Aggregate objects就是类/类实例/struct/string/array之类数据。
struct
根据symbol table找object member 找OR。再找内部member。
vector
根据起始地址和下标找string
多维数组
根据排列方式计算
7.3.3 Range Checks#
有的语言需要检查数据的范围。越界报错。
7.4 BOOLEAN AND RELATIONAL OPERATORS#
bool操作相关的汇编
7.5 CONTROL-FLOW CONSTRUCT#
if else/循环等等的汇编
7.6 OPERATIONS ON STRINGS#
string相关
7.7 PROCEDURE CALLS#
函数调用相关
8 Introduction to Optimization#
8.1 介绍#
代码经过前端生成某种IR，后端把IR转成机器指令。
中间是优化器，把IR进行转换以生成更高质量的机器指令。
本书只讨论单线程。并行计算相关内容也同样重要但超纲。
8.2 BACKGROUND#
一些历史
8.2.1 例子#
cs143编译器课程作业#
https://web.stanford.edu/class/cs143/
为cool语言写一个编译器。并不是从0写代码，是用一系列工具整合起来。
包括flex/bison/spim等等。
flex对代码进行scan，从代码中按规则识别出所有token(word)。
bison对token进行parse，组成语法树。
这里面的底层原理都是大课题。在这个课程里不细说。
编译器相关的实际工作内容可能更多集中在IR优化相关，而不是前端的scan/parse细节。
主要目的是掌握编译器的各部分基本原理，有能力自己搞一个新语言，并为其整合出一个编译器。
环境#
win11
virtualbox里ubuntu22.04
包含课程初始代码，作业说明等。如果链接失效，可到github上找。
这个课程文件应该是2011年左右的，和cs143官方最新的文件有不同。我用的最新版本的flex，有的地方需要修改。
最新的文件貌似不公开，所以只能用老的文件。实际大同小异，可以相互参考。
语言基本用c++
作业1#
用cool语言写一个小的栈模拟程序。
需要看他的语言手册和examples目录的代码。
没有数组。代码里起名也恶心，什么cdr，car，Cons。缩进是一塌糊涂。
但是到后续阶段懂了更多原理以后就习惯了，不那么恶心了。
主要看list.cl和sort_list.cl。
编译运行
../../bin/coolc stack.cl atoi.cl
../../bin/spim -file stack.s
64位系统无法运行32位的spim，安装libc6-i386。
sudo apt install libc6-i386
运行测试输入
make test
我的做法是模仿他的list写一个list和一个stack。
不知道怎么做空数据，list可以做一个永久的假数据当作尾巴。
写的比较松散，整了200行。
最后的结果为4。
作业2#
作业2要做一个scanner。
最后的效果是把输入的cool代码打碎成一个个token。
cool.flex是我们要完成的flex代码。
test.cl是一个输入例子，需要对这个文件做scan。这个文件可能包含错误，需要能识别。
最好的状态是对这个文件进行扩充，涵盖尽可能多的测试用例。
详见readme。
安装flex#
flex用来帮我们写scanner。我们编写语言的规则，和一些辅助逻辑。flex生成匹配算法，实现输入文件和语言规则的匹配。
git clone https://github.com/westes/flex.git
sudo apt install flex
flex文档
https://westes.github.io/flex/manual/
flex默认安装的版本为2.6.4，可能是2017年的版本，而文档版本为2.6.2。而且默认文档是分成多个页面的，有点烦。
如果不爽，自己编。
sudo apt install make
sudo apt install autoconf
sudo apt install libtool
sudo apt install m4
sudo apt install autopoint
sudo apt install texinfo
sudo apt install bison
sudo apt install g++
进入flex目录
./autogen.sh
./configure
make
sudo make install
进入flex/examples/manual
makeinfo --html --no-split -o flex.html ../../doc/flex.texi
这样获得了最新的flex程序和文档。
使用flex#
flex例子
/* scanner for a toy Pascal-like language */
%{
/* need this for the call to atof() below */
#include <math.h>
%}
DIGIT [0-9]
ID [a-z][a-z0-9]*
%%
{DIGIT}+ {
printf( "An integer: %s (%d)\n", yytext,
atoi( yytext ) );
}
{DIGIT}+"."{DIGIT}* {
printf( "A float: %s (%g)\n", yytext,
atof( yytext ) );
}
if|then|begin|end|procedure|function {
printf( "A keyword: %s\n", yytext );
}
{ID} printf( "An identifier: %s\n", yytext );
"+"|"-"|"*"|"/" printf( "An operator: %s\n", yytext );
"{"[^{}\n]*"}" /* eat up one-line comments */
[ \t\n]+ /* eat up whitespace */
. printf( "Unrecognized character: %s\n", yytext );
%%
int main( int argc, char **argv ) {
++argv, --argc; /* skip over program name */
if ( argc > 0 ) {
yyin = fopen( argv[0], "r" );
} else {
yyin = stdin;
}
yylex();
}
大致的格式#
整个文件用两个%%分成三大部分。最终生成c代码。
%{
Declarations
%}
Definitions
%%
Rules
%%
User subroutines
第一部分的%{和%}之间可写c代码，进行一些初始化之类。
接着写名称的定义。比如DIGIT [0-9]，给后面的正则表达式起个名。
第一个%%之后是规则(pattern action)。例如
{DIGIT}+ {
printf( "An integer: %s (%d)\n", yytext,
atoi( yytext ) );
}
意思是一旦匹配到了{[0-9]}+，就执行后面的代码。
第二个%%之后是flex的启动逻辑。
具体细节看作业2说明和文档第6节。
写代码#
直接进行编译make lexer
会报错因为这个课程代码用的是老版本flex。
先看下makefile，会编五个代码
lextest.cc utilities.cc stringtab.cc handle_flags.cc cool-lex.cc
cool-lex.cc
由flex cool.flex生成的代码，就是flex把cool.flex中我们写的规则嵌到它的逻辑中生成一个scanner。
其中有个默认的yylex()函数，用来scan出下一个token。
基本模式就是我们不断地调这个函数，直到把文件scan完毕。lextest.cc 此文件包含main函数。文档中main是直接放在cool-lex.cc最后的。这里它分开写，再一起编。
在cool.flex中有定义#define yylex cool_yylex，所以换了个名字。在while循环里不断调用cool_yylex来做scan。handle_flags.cc
scan之前处理一些选项utilities.cc
辅助函数，比如打印一些信息。stringtab.cc
string相关的小操作
yy_flex_debug这个在flex最新代码里，貌似变成了yyflexdebug。在这几个文件里替换成yyflexdebug。
cool.flex里加上%option noyywrap
可以编过了。
make dotest或lexer test.cl进行scan。
此时cool.flex里只定义了一个DARROW =>，而test.cl末尾加里没有=>，所以啥也没scan出来。
往test.cl末尾加个=>再运行，可以看到dump_cool_token()的打印#1 DARROW。
下面就要往cool.flex填cool语言的规则，进行scan。
课程要求看cool的手册第10节，和include目录中的cool-parse.h。
行号问题#
要打开%option yylineno，这样flex会自动维护yylineno。
然后把lextest.cc里的curr_lineno替成yylineno。
需要添加\n的匹配，否则不生效。
https://stackoverflow.com/questions/13317634/flex-yylineno-set-to-1
yylval问题#
define为cool_yylval
存储见第5节。代码见stringtab.h/stringtab_functions.h等等。
数字要这样存
{DIGIT}+ {
// printf( "xcc found An integer: %s (%d)\n", yytext, atoi( yytext ) );
cool_yylval.symbol = inttable.add_string(yytext);
return (INT_CONST);
}
注释问题#
注释开始\(\*
注释结束\*\)
进入注释后，只有匹配注释结束或者EOF才能退出，其他的都不能去匹配。
需要有个状态机制，见flex手册第10节。
做一个comment状态，再做<comment>[^*]*这种匹配消耗注释中的数据。
再匹配结束字符，转到初始状态yybegin(INITIAL);。
string的规则#
见flex手册第10节的例子。
测试#
google可以搜到cs143的grading脚本。可直接运行perl pa2-grading.pl。
必须通过63个测试。
作业3#
完成parser。用parser生成ast。
看课程文档、readme和makefile。
最终会生成一个parser程序。
实际编译的文件是
CSRC= parser-phase.cc utilities.cc stringtab.cc dumptype.cc \
tree.cc cool-tree.cc tokens-lex.cc handle_flags.cc
CGEN= cool-parse.cc
cool.y
填写语法规则。编译时对其调用bison，生成cool-parse.cc，cool-parse.h和cool.tab.h。
bison cool.y会使生成的cool-parse.cc里#include "cool.tab.h"
-b参数能指定名字的替换，生成#define yyparse cool_yyparse这样的代码。
那么cool_yyparse函数就存在了，就是原始的yyparse。cool-tree.aps
待分析 生成cool-tree.h和cool-tree.cc。tokens-lex.cc
即flex生成的lexer。是课程自带的正确的lexer，所以只要考虑本次作业的parser。而不是联动之前我们自己做的lexer。
yylex()函数在parser仍然需要，见手册第4.3节等。
所以需要把flex生成的lexer代码拿过来一起编。parser-phase.cc
main入口。调用cool_yyparse()。cool_yyparse在cool-parse.cc中定义。dumptype.cc
辅助功能。遍历并打印ast。handle_flags.cc
处理一些选项
bison#
https://www.gnu.org/software/bison/manual/bison.html
内容非常多，得耐心看。
bison基本#
输入语言必须是context-free grammar(CFG)。
CFG有很多继承者。bison对于LR(1)优化最好。
LR(1)的parser具有确定性(deterministic)。 意思是下一条匹配的语法规则一定是由之前的输入和剩余的输入唯一决定的。
也就是说给定同样的数据状态，让parser去跑，永远会匹配出同样的结果。
一个CFG是允许有歧义/模棱两可的，一个输入可能存在多种匹配。
而无歧义的语法又可能是不确定的(nondeterministic)。
bison把terminal称为token。nonterminal称为grouping。
简单来说terminal就是不可分的一个语法单元，比如c语言的变量名/关键字/操作符等。
nonterminal就是可再分的，比如一个表达式(expression)，比如x * x。
那么对于nonterminal，必须为其定规则，如何拆分为更小的单元。
比如一个statement。可以拆分为一个return加一个expression加一个分号。
整个输入，到最后一定是向上匹配到一个根nonterminal。形成一个完整的程序。
bison语法规则#
详见文档第3节。
按习惯nonterminal写成小写字母单词。terminal写为大写字母单词。
关键字terminal是把关键直接转成大写，比如FOR。
stmt: RETURN expr ';' ;
这里最后的;是bison的规则结尾。里面的';'是匹配代码里的分号。
bison语义值#
详见文档第3.4节。
对于语法来说x+4和x+66666是一样的。它只关心分类。
语义值(semantic value)需要记录其他信息，比如它的值和名字。
nonterminal也可以按需赋予语义。
bison语义回调#
详见文档第3.4.6节。
和flex一个意思，每当匹配到一个规则，进行预定的操作。
GLR parser#
bison的LR(1)parser，在有些状态下无法给出结果。
Reduce/Reduce Conflicts
有两个规则都合法，不知道怎么选。
https://www.gnu.org/software/bison/manual/bison.html#Reduce_002fReduce
例如
sequence:
%empty { printf ("empty sequence\n"); }
| maybeword
| sequence word { printf ("added word %s\n", $2); }
;
maybeword:
%empty { printf ("empty maybeword\n"); }
| word { printf ("single word %s\n", $1); }
;
现在要匹配word
可以走word->maybeword>sequence。
也可以走word->%empty word->sequence word->sequence。
也可以走word->%empty word->maybeword word->sequence word->sequence。
都可以匹配到sequence。
Bison优先选择先出现的规则来解决这种冲突。但我们不能依赖于此。
这种冲突一般必须手动消除。否则有隐患。
Shift/Reduce Conflicts
不知道是确定一个规则，还是继续获取一个输入再考虑匹配规则。
https://www.gnu.org/software/bison/manual/bison.html#Shift_002fReduce
if_stmt:
"if" expr "then" stmt
| "if" expr "then" stmt "else" stmt
;
当lookahead token读到else时，此时之前的输入能匹配第一个规则，但同时也有希望匹配第二个规则。
形成冲突。
例如对于
if x then if y then win; else lose;
如果选择先匹配，结果为
if x then (if y then win;) else lose;
如果选择继续读，结果为
if x then (if y then win; else lose;)
根据目前普遍的约定，bison默认会选择继续读输入，除非有其他优先级规定。
这样的效果就是把else优先匹配到最近的if上。
对于一些无法符合LR(1)的语法，%glr-parser选项可以生成一个Generalized LR (GLR) parser。
这种parser遇到冲突时直接”分裂”成两个parser，把两种可能都执行。后续还可能继续分裂。最后是一种分支形状。
一条分支只有两种结果。要么走不下去了，解析出错，直接杀掉。要么成功并和其他分支合并。
GLR具体内容较多，貌似也用不到。略过。
位置#
可获取语法单位的行号。
bison的输出文件(即parser代码)#
讲了一些基本流程/约定。
bison文件基本格式#
%{
Prologue
%}
Bison declarations
%%
Grammar rules
%%
Epilogue
bison例子1#
Reverse Polish Notation计算器语法
/* Reverse Polish Notation calculator. */
%{
#include <stdio.h>
#include <math.h>
int yylex (void);
void yyerror (char const *);
%}
%define api.value.type {double}
%token NUM
%% /* Grammar rules and actions follow. */
input:
%empty
| input line
;
line:
'\n'
| exp '\n' { printf ("%.10g\n", $1); }
;
exp:
NUM
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
| exp exp '*' { $$ = $1 * $2; }
| exp exp '/' { $$ = $1 / $2; }
| exp exp '^' { $$ = pow ($1, $2); } /* Exponentiation */
| exp 'n' { $$ = -$1; } /* Unary minus */
;
%%
%define api.value.type {double}
定义语义值的类型。
%token NUM
terminal(除了单字符的)都要用%token定义。
%empty意思是空
input: input xxxx 这种称为左递归。如果右边的input放在最后，称为右递归。文档有说只允许用左递归，右递归存在隐患。
{}里是匹配到规则时执行的c代码
$$是语义值
$x是展开的第x项。
必须要提供yylex()
lexer的yylex()的返回值是一个数，即作业2中我们写的return (STR_CONST);之类。
bison中共用STR_CONST等等这一套枚举量。
必须要提供一个yyerror()来报错。
bison例子2#
Infix Notation计算器
/* Infix notation calculator. */
%{
#include <math.h>
#include <stdio.h>
int yylex (void);
void yyerror (char const *);
%}
/* Bison declarations. */
%define api.value.type {double}
%token NUM
%left '-' '+'
%left '*' '/'
%precedence NEG /* negation--unary minus */
%right '^' /* exponentiation */
%% /* The grammar follows. */
input:
%empty
| input line
;
line:
'\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
exp:
NUM
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1, $3); }
| '(' exp ')' { $$ = $2; }
;
%%
%left和%right指定左关联右关联
越晚定义优先级越大。所以^优先级最大。
%precedence NEG定义一个优先级标签，占个位。后续的%prec NEG赋予这个优先级。
其他例子自行学习。
写代码#
make parser编译直接能成功。因为它用的tokens-lex.cc是老版本的flex生成的，所以不用像之前做lexer时做一些修改代码。
如果要把lexer替换成我们的，就需要修改了。
不过有很多warning。
用正确的lexer做scan并传给parser
../../bin/lexer good.cl | ./parser
报错。然后就要开始完善cool.y。
可以用正确的parser看看是什么样子。
../../bin/lexer good.cl | ../../bin/parser
看cool.y
%union
待分析。
定义可作为结果的类型。会把代码复制到cool.tab.h。
对%union中定义的类型，可以用%type给nonterminal指定类型。
%type <program> program
%token可以定义token的类型(%union中定义)和语义值。
比如%token <boolean> BOOL_CONST 277
然后可以写具体的语法。
makefile里bison加参数–graph可以生成gv文件。是你parser的图示。
非常庞大的图。如文档所说，用来debug的话价值不大，因为过于繁琐。初学可以看看。
下载Graphviz程序
.\Graphviz\bin\dot.exe -Tsvg .\cool.gv > ./out.svg
目前能生成但是打开报错。
https://dreampuf.github.io/GraphvizOnline/
可在线生成。
let的问题#
let先初始化一堆变量，再in一个expr，执行这个expr。
这个语法中间是一个list，但是cool-tree.cc中的创建函数只能单个创建。有点不正常。
看example/lam.cl中用了list的语法，初始化多个变量，而且用课程自带的parser能编过，说明他确实是实现了的。
看看自带的parser的输出，是一个树状结构。
dumptype.cc会打印各种类型，但dump_type我看了一圈全是打印_no_type，也没看出来什么名堂。
接续看打印结构和let_class::dump_with_types()的逻辑。
可以发现他是在每个let类里只放一个初始化，然后把其他的初始化放在这一个let的body里。
那么极大概率，需要把let的list的语法做成嵌套的结构。有几个初始化就要套几层，就要创建几个let。
然后let在cool语言中又可以嵌套。最简单的想法搞个栈。每次碰到let就往里压，每次结束一个let就释放。
这样嵌套的let不会相互干扰。
我是先匹配一个let，进栈。再从in expr往前匹配，这样可以先创建最底层的let，每组let只存一个最新的实例即可，代码比较简洁。
如果从前往后，可能要折腾数组。
冲突问题#
优先级问题#
https://en.wikipedia.org/wiki/Operator_associativity
https://www.gnu.org/software/bison/manual/bison.html#Precedence
Error Recovery问题#
比如当一个类中的某个函数有错，需要Error Recovery，继续往下检查其他函数。
对于class列表/expr列表等都需要。
https://www.gnu.org/software/bison/manual/bison.html#Error-Recovery
基本原理就是在一个列表形式的匹配中加error的匹配。
类似这样
feature_list:
{}
| feature_list feature {}
| feature_list error {}
正常情况是不断把新的feature加到list中。现在如果某个feature报错，会产生一个error，也可以加到list中。
这样就不会造成整个feature_list失败，而是能继续查后续的feature。
测试#
google可以搜到cs143的grading脚本。可能需要改脚本，见下面作业4中的说明。
可能还要把lexer的链接复制过来。
list的顺序问题可导致通不过测试。比如类的feature list，写法不同导致顺序颠倒。 比如把feature list改成左递归，一下子通过了很多测试。
‘~’是neg not是comp
通过70条测试。
作业4#
经过parse后，得到了ast。需要在这个ast上进行semantic的检查。包括type/scope等各种cool手册中的规定。
并做一些补全。
用课程自带的程序运行看看效果
../../bin/lexer ./bad.cl | ../../bin/parser | ../../bin/semant
../../bin/lexer ./good.cl | ../../bin/parser | ../../bin/semant
首先bad和good的基本词法都是对的。
但对比空白程序，正确的程序会改正一些no_type，会检测各种语义的细节。
看makefile。
文件:
semant-phase.cc
main入口。ast_root是Program类型，在.y的最终program规则中赋值。
ast_root的semant()在semant.cc中实现。ast-lex.cc
课程自带的正确的lexer代码。ast-parse.cc
课程自带的正确的parser代码。semant.cc
主要要改这个代码。cool-tree.h
包含各种语法的定义。重要。cool-tree.handcode.h
需要给有些语法组件添加函数，在这添加。
写代码#
ast#
看懂semant的整个输出，看懂dumptype.cc，就懂了怎么遍历ast。
string table相关#
把id/int/string分别存在三个list里，各自不允许有重复。可进行查找等操作。
其实就是个hash表之类的东西，把所有出现的名字记录一下而已。
symbol table#
见symtab.h，symtab_example.cc和list.h。
基本是一个二维的结构，然后做一些添加查找。scope做成栈的效果。
它代码较为恶心，添加scope的逻辑配合它那个list，给我看呆了。而且只有new没有delete。
自己重写把。
每个symbol的名字和类型都可以采用Symbol类，一起放进symbol table。
从ast_root也就是program_class开始遍历ast。对于不同的语句都要实现一个check_symbol之类的函数，在里面根据语法操作symbol table。
测试#
我是到这个作业才找的测试脚本，前面的作业没测试。
到此可以把前面的测试也跑一下，改正茫茫多的错误。
最后的目标是把lexer和parser都换成自己的，仍能跑通所有测试。
google可以搜到cs143的grading脚本。可能需要改改才能跑。
在作业目录运行脚本perl pa4-grading.pl -v，生成grading文件夹并自动运行case，但输出都是找不到命令。
跟踪它的perl逻辑，最终会调其中的mysemant。
它是csh脚本，而我的环境是bash，所以出错。
改为bash格式，再运行加参数-r不再次解压，否则文件又会被它覆盖。
perl pa4-grading.pl -v -r可以得到评分了。
#!/bin/bash
# echo $1
../lexer $1 | ../parser | ../semant
报错要按照它的格式来。
filename:line: 错误原因bblaaallal
Compilation halted due to static semantic errors.
类的继承问题#
类默认继承自Object。继承中attr不能重复定义，method可重写，参数必须一样。
类的定义顺序可以随意，可以先使用某个类型，后续再定义。
这样可能造成循环继承，不允许出现循环继承。可以最先单独检查是否存在循环继承。
子类里不能改父类函数的参数。
课程代码的install_basic_classes()是生成内置的基本类。
ClassTable的构造函数里传入了program的class列表，即ast中的所有class。
那么可以在构造函数中检查类相关的错误。
self问题#
直接调函数时，调用者实际为self。
SELF_TYPE可用于定义基类函数中返回自己，这样派生类new之后可以直接赋给派生类的变量，不用严格匹配类型。
代码按需要把dispatch返回的SELF_TYPE转成new出来的类型。见basic.test。
有很多地方需要转SELF_TYPE。
LCA问题#
lowest common ancestor经典的最近公共父节点问题。
可简单暴力算。也可研究lca系列算法。
有的语句如case/if有多个返回分支，需要定一个static type。
把多个分支的LCA作为static type，并检查上下文。
其他工作#
遍历时可判断重复定义/名字在scope中不存在/类型不匹配等错误。
检查函数的返回类型。
要根据symbol table，用set_type()补全一些数据的类型。见输出中的no_type。
见测试。非常多的例子。
共74条测试。
它的loop永远会返回Object而不是body的类型。没搞懂。
因为这个原因有2个测试过不了。
最后semant.cc整了1700行代码。
作业5#
看完课程视频的后半部分，看到书本第八章可以开始最后一个作业。
make cgen得到我们需要的cgen。
像之前的作业一样，从lexer/parser/semant一直输入到cgen。
用bash的话需要改造一下mycoolc脚本。
#!/bin/bash
./lexer $1 | ./parser | ./semant | ./cgen $@
./mycoolc example.cl -o wtf.s -c
编译生成.s汇编。-c参数可控制cgen_debug打log。
../../bin/spim ./wtf.s
mips模拟器运行生成的汇编。
cgen.cc
主要要修改的代码。
我是把之前重写的symbol table拿过来改造一下。然后不用它的list，改为std::list。指针改为std::shared_ptr。顺便熟悉了它的node逻辑。cgen-phase.cc main函数。调用ast_root->cgen()。
汇编架构#
这个文档很好，快速扫盲。 建议通读一遍。
https://web.stanford.edu/class/cs143/materials/SPIM_Manual.pdf
参考
https://www.cs.csub.edu/~eddie/cmps2240/doc/britton-mips-text.pdf
cgen生成汇编代码，assembler把汇编代码转成object文件。最后linker把所有obj转成可执行文件。
object文件的格式
┏━━━━━━━━┳━━━━━━━━━┳━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━┳━━━━━━━━━━━┓
┃ header ┃ text ┃ data ┃ relocation ┃ symbol ┃ debugging ┃
┃ ┃ segment ┃ segment ┃ info ┃ table ┃ info ┃
┗━━━━━━━━┻━━━━━━━━━┻━━━━━━━━━┻━━━━━━━━━━━━┻━━━━━━━━┻━━━━━━━━━━━┛
header
文件各部分的大小和位置text
routine的机器指令。可能因为unresolved reference而无法执行。data
一些二进制数据。可能因为unresolved reference而不可用。relocation info
依赖于绝对地址的一些指令和数据symbol table
外部的label和unresolved referencedebugging info
描述此程序的编译信息，以便debugger找到相应信息并正常工作。
单个obj本质上是可执行的？但如果有依赖外部就有问题。
linker把所有obj link起来，解决相互的依赖问题，生成可执行文件。
操作系统运行程序时先做loading。
读header，确定各种信息比如大小。
创建足够大的地址空间
程序内容copy过去
初始参数
安排好寄存器等
开始运行
调用栈#
https://en.wikipedia.org/wiki/Call_stack
https://courses.cs.washington.edu/courses/cse410/09sp/examples/MIPSCallingConventionsSummary.pdf
https://web.archive.org/web/20130111161107/http://pages.cs.wisc.edu/~cs354-2/beyond354/conventions.html
调用栈大致流程(栈往下方生长)
caller正常运行中 准备调用 被调函数运行 被调函数结束
┏━━━━━━━━━━━━━┓ ┏━━━━━━━━━━━━━┓ ┏━━━━━━━━━━━━━┓ ┏━━━━━━━━━━━━━┓
┃ parent ┃ ┃ parent ┃ ┃ parent ┃ ┃ parent ┃
┃ data ┃<-fp ┃ data ┃<-fp━┓ ┃ data ┃<━━┓ ┃ data ┃<-fp<-saved fp
┣━━━━━━━━━━━━━┫ ┣━━━━━━━━━━━━━┫ ┃ ┣━━━━━━━━━━━━━┫ ┃ ┣━━━━━━━━━━━━━┫
┃ ┃<-sp(init) ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ caller data ┃ ┃ caller data ┃ ┃ ┃ caller data ┃ ┃ ┃ caller data ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┣━━━━━━━━━━━━━┫ ┣━━━━━━━━━━━━━┫ ┃ ┣━━━━━━━━━━━━━┫ ┃ ┣━━━━━━━━━━━━━┫
┃ ┃<-sp(now) ┃ saved fp ┃<━━━━┛ ┃ saved fp ┣━━━┛ ┃ ┃<-sp
┃ ┃ ┣━━━━━━━━━━━━━┫ ┣━━━━━━━━━━━━━┫ ┃ ┃
┃ ┃ ┃ arg1 ┃ ┃ arg1 ┃ ┃ ┃
┃ ┃ ┣━━━━━━━━━━━━━┫ ┣━━━━━━━━━━━━━┫ ┃ ┃
┃ ┃ ┃ arg2 ┃ ┃ arg2 ┃ ┃ ┃
┃ ┃ ┣━━━━━━━━━━━━━┫ ┣━━━━━━━━━━━━━┫ ┃ ┃
┃ stack ┃ ┃ ┃<-sp ┃ saved ra ┃<-fp ┃ stack ┃
┃ ┃ ┃ ┃ ┣━━━━━━━━━━━━━┫ ┃ ┃
┃ ┃ ┃ ┃ ┃ callee ┃<-sp ┃ ┃
┃ ... ┃ ┃ ┃ ┃ data ┃ ┃ ... ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ ┃ ┃ stack ┃ ┃ stack ┃ ┃ ┃
┃ ┃ ┃ ... ┃ ┃ ... ┃ ┃ ┃
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┗━━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━━┛
初始时sp与fp值相等 调用者负责存fp和参数 callee一开始必须把fp指向当前sp的位置 函数结束
然后caller正常跑 然后jal跳转到被调函数 并把ra存到栈上 sp根据fp值退到初始位置
sp涨到某位置 jal会自动把返回地址存到ra 这样完成了嵌套的fp和ra的维护 把最开始记录的fp值还原到fp
此时形成了被调函数的初始状态 最后用saved ra跳转回去
和第一步的结构一样 此时完全还原到调函数前的状态
仿佛什么也没发生
sp指向下一个可用的stack位置。
fp指frame pointer。用来记录某个关键时刻的sp值(一般是当前函数的起始sp值附近)，这样等后续操作(可能是茫茫多的指令/嵌套函数等)完成时能方便地找到来时的路，帮助完成调用函数的流程。
jal指令会自动把当前地址存到ra，以便后续跳转回来。
调函数的流程:
0. 准备调函数。此时sp是下一个可用的地址。fp是当前函数的起始sp值。
当前fp存到栈上
所有参数存到栈上
jal指令跳转
fp设为sp
ra存到栈上
函数开始正常运行
函数结束
返回值存商量好的寄存器
还原sp/fp
以栈上的ra跳转回原地
写代码#
默认能编过，能启动，但spim报语法错。因为StringEntry::code_def这里面缺dispatch table相关信息，word后面是空的。
看课程资料https://web.stanford.edu/class/cs143/materials/cool-runtime.pdf
看视频的object layout相关。
dispatch pointer指向dispatch table。可以先填0后续再改。
为什么做成指针的结构。因为可以拿出来公用。
先把code_constants里几个空的word随便填0。还报错Main_protObj找不到。
看trap.handler。这个是cool的运行时代码，一定要大致看懂。
看里面的__start，是程序入口。会取Main_protObj，这是我们代码里的，目前缺逻辑，所以它报错找不到。
同时有一堆globl找不到，都需要实现。
runtime#
怎么实现，不知道。看看runtime到底干了啥。
可选择gc方式。我们先只看默认的无gc。
__start:
li $v0 9
move $a0 $zero
syscall # sbrk请求系统分配内存，改变data segment大小。参数为0返回当前heap end/program break到$v0。
# https://stackoverflow.com/questions/6338162/what-is-program-break-where-does-it-start-from-0x00
# https://linux.die.net/man/2/sbrk
move $a0 $sp # initialize the garbage collector
li $a1 MemMgr_REG_MASK # 写死了0x007F0000。挑选一批特定的寄存器。
move $a2 $v0 # 保存heap end
jal _MemMgr_Init # sets $gp and $s7 (limit)
la $t9 _exception_handler # 异常流程放到$t9
la $a0 Main_protObj # 把Main_protObj的地址存到$a0
jal Object.copy # Call copy
# 此时完成了为新obj申请heap内存，并把Main_protObj的数据copy到heap。
# 最后a0仍指向新obj的起始位置。
# 相当于new了一个Main_protObj的实例。
addiu $sp $sp -4
sw $a0 4($sp) # 把new出来的地址存栈上。
move $s0 $a0 # s0 = a0 s0专门存self
jal Main_init # initialize the Main object
jal Main.main # Invoke main method
.globl __main_return
__main_return: # where we return after the call to Main.main
addiu $sp $sp 4 # restore the stack
la $a0 _term_msg # show terminal message
li $v0 4
syscall # 打印
li $v0 10
syscall # syscall 10 (exit)
_MemMgr_Init:
addiu $sp $sp -4
sw $ra 4($sp) # save return address
la $t0 _MemMgr_INITIALIZER # 加载了我们代码的_MemMgr_INITIALIZER。
lw $t0 0($t0)
jalr $t0 # 跳转。实际默认走了我们配置的_NoGC_Init。
lw $ra 4($sp) # restore return address
addiu $sp $sp 4
jr $ra # return
_NoGC_Init:
la $gp heap_start # heap_start在我们的代码中定义。存到gp
li $v0 9 # get heap end
move $a0 $zero
syscall # sbrk。还是获取heap end
move $s7 $v0 # set limit pointer
jr $ra
Object.copy:
addiu $sp $sp -8 # 栈往下生长8字节。即分配8字节。
sw $ra 8($sp) # 保存ra
sw $a0 4($sp) # 保存Main_protObj地址
jal _MemMgr_Test # 可先忽略。进行一些gc操作再回到此处。默认代码_MemMgr_TEST数据为0，实际啥也没干。
lw $a0 4($sp) # 拿回Main_protObj地址到$a0
lw $a0 obj_size($a0) # obj_size为4。根据object layuot规则，是取obj的大小。见我们已生成的汇编，size排在第二个word，即offset为4。
blez $a0 _objcopy_error # 如果size小于等于0。报错退出。
sll $a0 $a0 2 # 左移2位。乘以4。word数转成byte数。
addiu $a0 $a0 4 # gc相关。加4字节。
jal _MemMgr_Alloc # 给obj分配内存。
addiu $a1 $a0 4 # 此时a0为分配前的gp值，即新分配的obj的起始地址。+4存a1。
lw $a0 4($sp) # 拿回Main_protObj地址到$a0
lw $ra 8($sp) # 拿回ra
addiu $sp $sp 8 # 栈退回到Object.copy初始状态
lw $t0 obj_size($a0) # t0 = object大小
sll $t0 $t0 2 # convert words to bytes
b _objcopy_allocated # get on with the copy
_MemMgr_Alloc:
add $gp $gp $a0 # heap_start增加obj大小
# 测试当前gp是否在heap end之内。如果是说明实际内存够用。直接成功。
# 否则走sbrk
blt $gp $s7 _MemMgr_Alloc_end
sub $gp $gp $a0 # 还原$gp
addiu $sp $sp -4
sw $ra 4($sp) # 存ra
move $a1 $a0 # a1 = obj大小
addiu $a0 $sp 4 # a0 = sp + 4。 这步对于_NoGC_Collect没用。
la $t0 _MemMgr_COLLECTOR
lw $t0 0($t0)
jalr $t0 # 走_NoGC_Collect
lw $ra 4($sp) # restore return address
addiu $sp $sp 4
move $a0 $a1 # put size into $a0
add $gp $gp $a0 # allocate storage
_MemMgr_Alloc_end:
sub $a0 $gp $a0 # a0变为分配前的gp值。是个地址。
jr $ra # return
_NoGC_Collect:
la $a0 _NoGC_COLLECT # show collection message
li $v0 4
syscall # 打印
_NoGC_Collect_loop:
add $t0 $gp $a1 # a1 = obj大小。gp加上需要的size作为目标t0。
# s7 = heap end。
# sbrk分配后，heap是往上涨。
# 如果t0比s7小说明s7超过了预定目标，分配够了。否则继续循环sbrk请求内存。
blt $t0 $s7 _NoGC_Collect_ok # stop if enough
li $v0 9 # expand heap
li $a0 NoGC_EXPANDSIZE # 请求分配大小NoGC_EXPANDSIZE=0x10000
syscall # sbrk
li $v0 9 # get heap end
move $a0 $zero
syscall # sbrk 查询结果
move $s7 $v0 # 存s7
b _NoGC_Collect_loop # 循环
_NoGC_Collect_ok:
jr $ra # return
_objcopy_allocated:
# 此时t0为object大小。a0为Main_protObj地址。a1为新分配的obj起始地址+4。
addiu $t1 $0 -1
sw $t1 obj_eyecatch($a1) # 写个-1
add $t0 $t0 $a0 # find limit of copy
move $t1 $a1 # save source
_objcopy_loop:
# 把Main_protObj处的数据copy到heap。
lw $v0 0($a0)
sw $v0 0($t1)
addiu $a0 $a0 4 # update source
addiu $t1 $t1 4 # update destination
bne $a0 $t0 _objcopy_loop # loop
_objcopy_end:
move $a0 $a1 # 最后a0仍指向obj的起始位置
jr $ra
到此理清了一些问题。
Main_protObj是类的定义，要给他生成一批.word之类的数据。
__start里会申请内存，把Main_protObj定义的数据复制过去。
$gp存heap start即heap最新的可用地址。$s7存heap end即可用heap的末尾。之间为可用的heap。
如果想要分配的大小加上$gp超出了$s7，就需要先sbrk分配更多的heap空间。
申请成功后$gp加上obj的size。
再看cgen.cc的install_basic_classes。用install_class创建了基本类到class table。
这些类的实现都在runtime里。
继续看runtime
# 调用前a0存obj
.globl Object.abort
Object.abort:
move $s0 $a0 # save self
li $v0 4
la $a0 _abort_msg
syscall # 打印"Abort called from class "
la $t1 class_nameTab # 取class_nameTab地址
lw $v0 obj_tag($s0) # object tag是类的第一个word。每个类必须不同，以区分自己。
sll $v0 $v0 2 # 转成字节
addu $t1 $t1 $v0 # class_nameTab加上tag。指向自己专属的位置。
lw $t1 0($t1) # Load class name string obj.
addiu $a0 $t1 str_field # Adjust to beginning of str
li $v0 4 # 打印
syscall
la $a0 _nl
li $v0 4
syscall # print new line
li $v0 10
syscall # Exit
我们得实现class_nameTab，按类的tag把所有类名装进去。一旦调用abort()，就会在里面找自己得类名，并打印退出。
cgen的数据结构#
CgenNode是一个ast的class类，能获取cool语言某个类中的所有数据。
CgenNode中会设置好parent和children，是继承关系。
CgenClassTable包含所有类的指针的list。那么会形成一个树型结构。
all class list : 1(3) ---- 2 ---- 3 ---- 4(1) ---- 5(1) ---- 6(5) ---- 7(6) ---- 8(6) ...
4 - 5 1 6 7 - 8
children
6 4 - 5 7 - 8
7 - 8 6
7 - 8
同时CgenClassTable又是一个symbol table。可以通过名字找scope中的CgenNode。
object的size问题#
定义object需要填它的size。
一个attribute到底是算4字节当作一个指针？还是要算它的类型的大小？
如果要算类型大小，又出现一个循环引用的问题。如果A包含B型变量，B又包含A型变量怎么办。来回算size？无穷无尽。
这就是循环包含变量的问题，写c/c++代码一定会碰到。是不允许的，一般用指针来解决。
现在从编译器的角度碰到了这个问题。
https://stackoverflow.com/questions/8526819/c-header-files-including-each-other-mutually
本课程并没有检测这种循环包含。故意写一个循环包含，它是能编过的。
如果把每个类型的大小都算出来，就要有个递归的过程。
我们先用貌似简单的方法试试。把每个attribute当作指针，算1word。
然后在实际初始化obj的时候再递归下去进行分配。
课程文档里也都是把attribute当指针。
生成函数#
Main.main
Main_init
Bool_init
Int_init
String_init
这几个是特殊的函数，我们需要实现。除了Bool_init，runtime会直接调用。
Main.main得当作正常的类函数来生成。
函数调用的汇编可以都用jal A.b的形式。
先让每个函数直接jr $ra。先让让spim把程序跑起来。成功后会打印_term_msg:COOL program successfully executed。
接下来就要写具体的指令生成了。
尝试打印#
先尝试在Main.main里加打印out_string("Hello, World.\n");。
# runtime中out_string的流程
.globl IO.out_string
IO.out_string:
addiu $sp $sp -4 # 分配4字节
sw $a0 4($sp) # 保存a0的值
lw $a0 8($sp) # sp+8的位置存的是唯一参数(一个String_protObj数据)
addiu $a0 $a0 str_field # 根据String_protObj的layout，字符串offset为16。
li $v0 4 # syscall打印
syscall
lw $a0 4($sp) # 还原a0
addiu $sp $sp 8 # sp+8。把string参数也删掉。
jr $ra # 返回
Main首先需要inherits IO。
然后从dispatch_class::code这里进入生成流程。
最终要能找到实际定义out_string的类也就是IO。
然后分析参数，起一个String_protObj参数，把其地址放到sp上，再jal IO.out_string。
runtime的out_string里面会自动还原sp。调用者不用还原sp。
发现不太行，还需要做一系列工作。
IO.out_string是特殊的函数，我们要做通用的调用流程。就得先做dispatch table。
dispatch table#
看一下例子把结构画出来就清楚了。
# 假设有3个类。
# A有f1和f2。
# B继承了f1和f2，新增了f3。
# C重写了f1，继承了f2，新增了f3。
A: f1 f2
B(A): f1 f2 f3
C(A): f1(重写) f2 f3
# 最终的函数定义应该为
A.f1:
... # 函数逻辑
A.f2:
...
B.f3:
...
C.f1:
...
C.f3:
...
# dispatch table为
A_dispTab:
.word A.f1 # 新增
.word A.f2 # 新增
B_dispTab:
.word A.f1 # 继承
.word A.f2 # 继承
.word B.f3 # 新增
C_dispTab:
.word C.f1 # 重写
.word A.f2 # 继承
.word C.f3 # 新增
dispatch table就是要从ast里把上面的汇编结构生成出来。
每个类都要有自己的dispatch table。其中每个函数要维护好自己的offset。调用时直接按自己的table和offset，走实际的函数定义。
每个函数只有唯一一份定义，继承得来的函数都指向唯一的那一个定义。
函数的唯一定义只需遍历一遍所有类，定义了就生成就行。
String问题#
String_protObj:
.word 4 # tag
.word 5 # class_size
.word 4 # dispatch table
.word Int_protObj
.word 0 # _prim_slot
string结构目前是这样。是否正确？
const string的实际字符数据可以用.ascii写死，但动态的string怎么搞，最后一个word目前是不确定的。
把runtime里的string操作看一下。
# 输入字符串的流程
.globl IO.in_string
IO.in_string:
addiu $sp $sp -8 # 栈上新入8字节
sw $ra 8($sp) # save return address
sw $0 4($sp) # init GC area
jal _MemMgr_Test # test GC area 忽略
la $a0 Int_protObj # 获取Int结构
jal _quick_copy # 和Object.copy类似。分配内存。返回时$a0为新分配obj的地址
jal Int_init
sw $a0 4($sp) # 新的Int地址存到sp+4
li $a0 str_field # 16。也就是String的基本数据3word，加上string长度1word。
addiu $a0 $a0 str_maxsize # 一个String数据的最大size
jal _MemMgr_QAlloc # 确定目前可分配这么大的空间
la $a0 String_protObj # 获取String结构
jal _quick_copy # 新建一个String。这里重要的是实际分配的并不是刚才的最大size。
# 而是String_protObj结构的size，而这个原型并不能知道运行时时应该分配多少。
# 所以String_protObj的size应该是5？5个确定的数据加一个指针指向字符数据。
# 或者就是4个word，紧跟着所有字符数据。
# 和const string的结构不一样。
jal String_init # 初始化。
lw $t0 4($sp) # 之前的Int地址拿出来
sw $t0 str_size($a0) # 设置新String的size，指向新Int。
sw $a0 4($sp) # 新的String地址存到sp+4
addiu $gp $gp -4 # overwrite last word
# 到此分配了一个String。并且确保内存够写一个最大的字符串。继续往下走。
_instr_ok:
li $a1 str_maxsize # largest string to read
move $a0 $gp
li $v0, 8 # read string
syscall # 系统调用。用户输入字符串。gp为heap start。
move $t0 $gp # 保存gp
_instr_find_end:
lb $v0 0($gp) # 测试gp上的输入字符串。直到碰到0。
addiu $gp $gp 1
bnez $v0 _instr_find_end
# $gp points just after the null byte
lb $v0 0($t0) # is first byte '\0'?
bnez $v0 _instr_noteof # 如果第一个不是0
# 如果第一个是0
# we read nothing. Return '\n' (we don't have '\0'!!!)
add $v0 $zero 10 # load '\n' into $v0
sb $v0 -1($gp)
sb $zero 0($gp) # terminate
addiu $gp $gp 1
b _instr_nonl
_instr_noteof:
# Check if there really is a '\n'
lb $v0 -2($gp)
bne $v0 10 _instr_nonl
# Write '\0' over '\n'
sb $zero -2($gp) # Set end of string where '\n' was
addiu $gp $gp -1 # adjust for '\n'
_instr_nonl:
lw $a0 4($sp) # 拿出新String的地址
lw $t1 str_size($a0) # 获取String的size指针
sub $t0 $gp $a0 # gp减a0得到整个String的数据长度
subu $t0 str_field # 再减基本数据16字节。得到字符串的实际长度。
addiu $t0 -1 # adjust for '\0'
sw $t0 int_slot($t1) # 存Int的实际值。为字符串实际长度。
addi $gp $gp 3 # was already 1 past '\0'
la $t0 0xfffffffc
and $gp $gp $t0 # word align $gp
sub $t0 $gp $a0 # calc length
srl $t0 $t0 2 # divide by 4
sw $t0 obj_size($a0) # set size field of obj
lw $ra 8($sp) # restore return address
addiu $sp $sp 8
jr $ra # return
根据此代码和Object.copy，可以推出String_protObj默认包含4word基本数据和一个word的默认0。也就是默认是个空字符串，有个结尾的0。 因为out_string一定会直接找第五个word进行打印，直到碰到0。
如果有初始化字符串，新做字符串长度Int，string里的int数据指向新做的Int，紧接着存所有字符串。
size为整块数据的大小。
把hello world调出来需要费一番功夫。此时可以说已经熟悉了基本流程。
接下来就是补全所有语句。
后续。hello world并不需要费一番功夫，其实可以直接用Object.copy。一开始我没搞懂这些，自己写了一遍初始化。
调试问题#
直接spim运行.s文件报segment fault。很难调试。
xspim我跑不起来。有个qtspim但很难用，莫名其妙的。
最后只能用spim命令来调。
新版本
spim -exception_file ../../lib/trap.handler
课程版本
../../bin/spim -trap_file ../../lib/trap.handler
加载我们的代码
read "wtf.s"
然后可step xx运行一定行数。print可打印寄存器或地址的内容。
测试#
SPIM Version 6.5 of January 4, 2003
Copyright 1990-2003 by James R. Larus (larus@cs.wisc.edu).
All Rights Reserved.
See the file README for a full copyright notice.
Loaded: /usr/class/cs143/cool/lib/trap.handler
输出的开始部分必须和这个一模一样。
测试脚本里执行mycoolc的地方可能要改改参数。
可能要添加链接。反正想办法弄成一样。
然后就开始根据测试用例完善指令。
scope问题#
碰到一个变量名时，需要找到它的地址，有可能在当前scope有可能在外部。
一定能找到，因为已经经过了语法检测。
如果是函数的参数，参数是会压到栈上的，在pf附近并且数量已知。那么在函数中用pf加上参数的offset就能找到。
其他情况要往外部去找。可能出现大量的嵌套scope。
问题就是如何在汇编中把scope体现出来。
考虑在函数或者attr的定义里，每当进入新scope，都当作函数一样处理，起新的fp，把需要的变量都压上栈。这样等于在汇编中用fp跟踪了每个scope。
压上栈的同时插入symbol table，带上当前scope中的压入顺序即offset。
查询symbol table时可获取scope距离当前的层数和offset。那么根据层数用fp往上反，再根据offset即可取出变量地址。
如果找不到，说明是class的attr，根据self的地址和class的定义可找到变量。
发现不太行。新旧fp之间隔着不定数量的数据，不好找到旧fp。
看课程视频的Temporaries这一节。
它是以函数为分界，用一套方法算出一个函数所需临时变量总个数，然后在函数开始的地方事先占好空间。
最后把这块数据当作一个独立的栈使用。这样就可以单独用来存变量，不会和其他的栈操作起冲突。
不过我是直接找变量的思路。不过本质思想是差不多的，可以借用。
其实最开始的想法就是能不能有个独立的空间，不和其他栈操作冲突就可以实现。他正是用预分配这个办法实现了独立的空间。
本质貌似就是找到代码里使用栈深度最深的那个点。以这个深度预先分配空间，保证任何时候栈不会溢出。
最后的做法就是先算函数的最大栈深度，在函数的fp处先占好空间，把local变量按scope放入symbol table，同时映射到这块空间。
函数的参数映射负值。如果symbol table找不到就是class attr，用self找。
其他问题#
原则上某个操作用到的寄存器都先存栈上，操作完了还原。
碰到会修改寄存器的函数就要非常注意了，会出现数据被搞乱。
大部分指令都只能操作对齐的数据，否则报异常。
比如先分配一个string类，整个长度没对齐。再分配时操作$gp就会报异常。
eq比较可用runtime的equality_test。
外部尽量减少准备操作，内部保存好数据，最后还原，不要影响外部。
调类函数前把实体地址放在a0。进函数后保存s0，把s0设为a0，完成后还原s0。这样维护好self。
尾声#
最后的作业5有63分。我调了两天从0到30分决定结束，因为最后基本是一些cool的特定语法相关问题，不想再纠结。
gc应该值得一看，我没看。后续会回顾。
目前已经知道了编译器的基础流程。不如直接开始尝试制作C编译器。