心血來(lái)潮第二波~ 這次參照了Stanford的課啦：https://courses.edx.org/courses/course-v1:StanfordOnline+SOE.YCSCS1+1T2020/course/
（再次強(qiáng)推計(jì)算機(jī)入門的CS50雖然是哈佛的）

Intro

※ Interpreters and Compilers

首先區(qū)分一下什么是interpreters（解釋器），解釋器是給它輸入program和data，它就會(huì)根據(jù)program以及data得到一個(gè)輸出output，也就是實(shí)時(shí)根據(jù)輸入給到輸出；而compilers（編譯器）是通過(guò)program得到一個(gè)可執(zhí)行程序，你可以往可執(zhí)行程序里面輸入data得到輸出，可執(zhí)行程序是靜態(tài)的，所以編譯器是offline的，不是實(shí)時(shí)的。

interpreters and compilers

所以其實(shí)解釋器就類似一個(gè)即時(shí)編譯 + 運(yùn)行的盒子，所以效率會(huì)比較低，即使執(zhí)行的program和之前的一樣也要重新跑一次。但是它可以做到跨平臺(tái)，但編譯器對(duì)不同的平臺(tái)需要輸出不同的可執(zhí)行程序。

※ Compiler的組成：

• lexical analysis
• parsing,
• semantic analysis
• optimization
• code generation

※ Step 1: recognize words

你可以很快的看出來(lái)這句話：'this is a sentence'. 但是如果這么看就會(huì)有點(diǎn)兒別捏：'thi sis ase ntence'。

The goal of lexical analysis, then, is to divide the
program text into its words, or what we call in compiler speak, the tokens.

舉個(gè)例子：if x == y then z = 1; else z = 2; 這句話就需要分出來(lái)x、y、z三個(gè)變量名；以及keyword例如if、else、then；token例如空格、分號(hào)；常量例如1 & 2；操作operators例如==以及=號(hào)。

※ Step 2: parsing（diagram圖解樹）

先舉個(gè)例子，英文句子是如何組織的，需要主語(yǔ)、動(dòng)詞和賓詞之類的：

英文句子的parse

同樣的，可以用一個(gè)樹來(lái)分解if-else這種編程語(yǔ)句，也就是parse：

parse if-else語(yǔ)句

※ Step 3: semantic analysis

semantic analysis常常是去看程序本身有什么inconsistencies的地方。

例如：Jack said Jerry left Jerry's assignment at home.這句話里面的his就有指代不清的問(wèn)題，不知道是jack還是jerry。

舉個(gè)程序的列子，語(yǔ)義分析就需要分析各種變量的綁定、作用域之類的：

int jack = 4;
{
  int jack = 3;
  cout << jack;
}

而且這個(gè)part還需要檢測(cè)一些錯(cuò)誤~

※ Step 4: optimization

優(yōu)化的目的就是run faster并且用更少的內(nèi)存。例如x = y * 0可以簡(jiǎn)化為x = 0。

※ Step 5: code generation

一般是翻譯為匯編語(yǔ)言，也可能會(huì)是其他語(yǔ)言~

※ Programming Languages

Q1: 為啥要有這么多種編程語(yǔ)言呢？
因?yàn)楹芏郃pplication Domain會(huì)有很多矛盾的需求，不能用一個(gè)語(yǔ)言滿足各種Application Domain的需求。
例如，科學(xué)領(lǐng)域和商業(yè)領(lǐng)域的需求就不一樣，科學(xué)領(lǐng)域會(huì)需要更好的計(jì)算和浮點(diǎn)支持，但是商業(yè)領(lǐng)域會(huì)對(duì)數(shù)據(jù)分析以及report之類更c(diǎn)are。

Q2: 為什么會(huì)有新的語(yǔ)言？
在信息革命的時(shí)候，因?yàn)橛懈鞣N各樣的Application Domain的需求，就誕生了很多種編程語(yǔ)言。
因?yàn)榭萍荚谧兓f的語(yǔ)言會(huì)越來(lái)越穩(wěn)定傾向于不變化，所以就伴隨會(huì)有新的語(yǔ)言，新語(yǔ)言的主要成本是需要教學(xué)使用者。但新的語(yǔ)言總是看起來(lái)有一些地方像舊的語(yǔ)言，這樣就會(huì)更容易上手，例如java比較像C++。

Q3: 怎樣是一個(gè)好的編程語(yǔ)言？
沒(méi)有一個(gè)universally accepted的語(yǔ)言設(shè)計(jì)標(biāo)準(zhǔn)。一個(gè)語(yǔ)言是不是會(huì)被widely use也不完全由技術(shù)決定，也會(huì)和它的輔助開發(fā)工具是不是齊全、應(yīng)用領(lǐng)域之類的相關(guān)。

Lexical Analysis

這一步需要根據(jù)divider分割語(yǔ)句，以及識(shí)別各個(gè)字符(詞素, lexeme)的角色。例如英文句子里的主謂賓。

這些角色就是Token Class，例如identifier變量名 / keyword / whitespace / numbers /( / ) / ...

Lexical Analysis會(huì)輸出一系列的token，也就是token class和lexeme的鍵值對(duì)給parser：

tokens

下面的例子是fortran里面的一個(gè)例子，F(xiàn)ortran語(yǔ)言是不識(shí)別空格的，也就是la la和lala是一樣的變量名。

這里一個(gè)標(biāo)點(diǎn)符號(hào)完全改變了整個(gè)句子的意思，如果是,號(hào)則代表一個(gè)do loop，i的取值會(huì)是從1到25然后；如果是.號(hào)，代表的就是一個(gè)賦值語(yǔ)句，并沒(méi)有l(wèi)oop，只是賦值了1.25給do5i這個(gè)變量：

一個(gè)例子

那么要如何應(yīng)對(duì)這種狀況呢？識(shí)別到DO的時(shí)候并不確認(rèn)是一個(gè)do loop還是變量名的一部分，這個(gè)時(shí)候就需要lookahead了。

所以Lexical Analysis的一個(gè)需求就是要lookahead看一下類似這個(gè)例子里面的是逗號(hào)還是別的符號(hào)，Lexical Analysis的一個(gè)目標(biāo)也就是盡量少數(shù)量的lookahead，看的越近越好。

另一個(gè)lookahead的例子就是，==在識(shí)別的時(shí)候會(huì)不會(huì)識(shí)別成=號(hào)呢，就需要再往后看一個(gè)字符。

※ regular languages

Lexical Analysis是通過(guò)正則來(lái)識(shí)別tokens的~可以用正則識(shí)別數(shù)字、變量名、空格(whitespace & newline & tab)、keyword先~

所以操作大概是用字符串從第0位開始到第n位去匹配identifier/number/keyword/whitespace的union，然后拿匹配到以后從原字符串去掉再開始匹配新的。

• 那么有的時(shí)候第0到第1位是=，第0到第2位是==，怎么辦呢？
  以長(zhǎng)度更長(zhǎng)的為準(zhǔn)

• 如果第0到n位同時(shí)滿足了keyword以及identifier怎么辦呢？
  以keyword為準(zhǔn)，keyword的優(yōu)先級(jí)更高

• 如果什么都沒(méi)有匹配上要怎么handle error呢？
  需要一個(gè)error的正則，就是前面的幾種都不符合，優(yōu)先級(jí)最低，當(dāng)哪個(gè)都沒(méi)match就會(huì)進(jìn)入這個(gè)集合。

※ Finite Automata

有限自動(dòng)機(jī)就是正則表達(dá)的實(shí)現(xiàn)，它的原理是從狀態(tài)1讀入字符以后轉(zhuǎn)換到狀態(tài)2：S1 ---input---> S2。

例如讀入一串兒字符，每次拿其中一個(gè)做狀態(tài)轉(zhuǎn)換，如果到最后進(jìn)入了accepting state就是被接受了~

自動(dòng)機(jī)圖示

舉個(gè)栗子：

識(shí)別1...0

非常難過(guò)的是我之前這里有寫NFA/DFA以及如何轉(zhuǎn)換之類的，以及對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換table，以table來(lái)考量輸入，實(shí)現(xiàn)正則表達(dá)式。這一系列都被簡(jiǎn)書吞了。。。（好氣啊！

其實(shí)最開始我們都是把正則轉(zhuǎn)為NFA，然后轉(zhuǎn)DFA，然后得到table。

轉(zhuǎn)化過(guò)程

• 確定有限自動(dòng)機(jī)(Deterministic Finite Automaton) 簡(jiǎn)稱DFA。DFA是匹配速度，是確定的。

• 非確定有限自動(dòng)機(jī)(Nondeterministic Finite Automaton) 簡(jiǎn)稱NFA，NFA是匹配結(jié)果，是不確定的。從一個(gè)狀態(tài)輸入同樣的字符會(huì)有多種結(jié)果，但表占用內(nèi)存少。

※ 正則轉(zhuǎn)NFA

正則轉(zhuǎn)NFA其實(shí)就是有一系列的套路，就是有幾個(gè)公式，畢竟正則也就幾個(gè)邏輯，and or not啥的，按照規(guī)定轉(zhuǎn)NFA即可：

從RegExp到NFA

舉個(gè)栗子

※ NFA轉(zhuǎn)DFA

然后就是NFA轉(zhuǎn)DFA啦，用到的主要概念就是Epsilon Closure，就是找到所有通過(guò)空操作可以到達(dá)的狀態(tài)點(diǎn)們，從這些點(diǎn)出發(fā)輸入同樣一個(gè)字符又會(huì)到達(dá)一些狀態(tài)點(diǎn)，把這些點(diǎn)設(shè)為一個(gè)就成為了DFA：

舉個(gè)栗子

※ DFA到implement

DFA就是確定狀態(tài)機(jī)了，輸入一個(gè)字符就會(huì)跳轉(zhuǎn)到一個(gè)固定的新?tīng)顟B(tài)，故而我們可以創(chuàng)建一個(gè)狀態(tài) & 輸入的新字符 & 轉(zhuǎn)換到新的狀態(tài)是啥的一個(gè)table，根據(jù)table來(lái)code。其實(shí)也可以從NFA直接到轉(zhuǎn)換table哈~

DFA impl

所以其實(shí)DFA會(huì)更快，但是NFA會(huì)更c(diǎn)ompat~ 但根本還是通過(guò)input看到哪個(gè)狀態(tài)，然后再根據(jù)下一個(gè)input做狀態(tài)轉(zhuǎn)換。

Parsing

We need some way of describing the valid strings of tokens and
then some kind of algorithm for distinguishing the valid and invalid
strings of tokens from each other.

※ Context Free Grammars 上下文無(wú)關(guān)文法

可以參考：http://www.itdecent.cn/p/e1d47de41331

CFG組成

CFG由非終結(jié)符集合、非空有限的終結(jié)符集、開始符號(hào)（非終結(jié)符）、產(chǎn)生式集合組成，產(chǎn)生式就類似我們的語(yǔ)法，而CFG其實(shí)就是根據(jù)語(yǔ)法，把一個(gè)句子轉(zhuǎn)換成符合語(yǔ)法的各個(gè)part，以此來(lái)確認(rèn)這個(gè)句子是不是符合語(yǔ)法。

示例

※ Derivation

Derivation

Derivation就是通過(guò)tree的方式，把CFG分解的過(guò)程表示出來(lái)~ 最底層的葉子都是終結(jié)符，里面的節(jié)點(diǎn)都是非終結(jié)符，并且如果做inward reversal of the leaves我們將得到輸入的表達(dá)式~

left-most和right-most derivation其實(shí)就是parse的方向不一樣，從左開始o(jì)r從右開始，但parse tree結(jié)果都是一致的。

left-most derivation舉例

※ Ambiguity

A grammar is ambiguous if it has more than one Parse tree for some string.

一種消除的方式就是重寫語(yǔ)法保持語(yǔ)法樹唯一，另外一種方式是增加precedence and associativity declaration (優(yōu)先權(quán)和可結(jié)合性聲明)，后者是比較常用的方式，例如if else里面 if 總是和最近的else match的。

如何消除if-else二義性

left先結(jié)合消除二義性

※ Error Handling

例如Panic mode恐慌模式：從剩余的輸入中不斷刪除字符，直到詞法分析器能夠在剩余輸入的開頭發(fā)現(xiàn)一個(gè)正確的詞法單元為止；以及Error production，用error產(chǎn)生式識(shí)別error。

※ Abstract Syntax Trees

抽象語(yǔ)法樹是源代碼的抽象語(yǔ)法結(jié)構(gòu)的樹狀表示，樹上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)，這所以說(shuō)是抽象的，是因?yàn)槌橄笳Z(yǔ)法樹并不會(huì)表示出真實(shí)語(yǔ)法出現(xiàn)的每一個(gè)細(xì)節(jié)，比如說(shuō)，嵌套括號(hào)被隱含在樹的結(jié)構(gòu)中，并沒(méi)有以節(jié)點(diǎn)的形式呈現(xiàn)。

※ Recursive Descent Parsing

循環(huán)產(chǎn)生式，直到發(fā)現(xiàn)錯(cuò)了就回退，窮盡所有可能性的方式parse。

舉個(gè)例子：
??→??′ | ??′+??
??′→???′ | ???? | (??)

E
E’
-E’
id
(E)
E’ + E
-E’ + E
id + E
id + E’
id + -E’
id + id

※ Recursive Descent Algorithm

Recursive Descent實(shí)現(xiàn)

Start the parser up, we have to initialize the next pointer to point to the first token in the input stream and we have to invoke the function that matches anything derivable from the start symbols.

栗子

但是注意哦，如果輸入是int * int，那么在int match了T()的第一個(gè)int就return了，但實(shí)際上T()的第二個(gè)表達(dá)式才是真正match的，所以會(huì)涉及一個(gè)backtrace的問(wèn)題。

※ Left Recursion

Left Recursion的就是如果做Recursive Descent會(huì)不斷地循環(huán)，因?yàn)橛疫呑钭蟮腟和左邊的S一致。

左循環(huán)

解決這個(gè)問(wèn)題的方式就是改成Right Recursion的產(chǎn)生式：

left to right recursive

Predictive Parsing

這個(gè)part是如何能predict要用哪個(gè)產(chǎn)生式而不出錯(cuò)0.0

主要還是通過(guò)lookahead來(lái)實(shí)現(xiàn)的，也就是LL(K)語(yǔ)法，left-to-right scan，a leftmost derivation，K tokens of look ahead。也就是從左到右看，提前看K個(gè)字符。

int * int就很不容易predict的產(chǎn)生式

上面的問(wèn)題是，T可以轉(zhuǎn)換成int開頭的兩種方式，那么就面臨選擇，所以下面通過(guò)改寫避免了這種問(wèn)題：（類似合并同類項(xiàng)）

改寫成只有一種選擇的

LL(1) TABLE

根據(jù)table借助stack記錄parse的產(chǎn)生式，如果棧頂是終結(jié)符則pop，如果是非終結(jié)符則根據(jù)LL(1) table看下一個(gè)的輸入決定替換為哪個(gè)產(chǎn)生式：

示例

※ First set & Follow set

First集：該關(guān)于該符號(hào)的所有產(chǎn)生式右部第一個(gè)遇到終結(jié)符

用上面那句話：關(guān)于S的產(chǎn)生式有兩個(gè)：S->AB,S->bC

先看簡(jiǎn)單的情況：S->bC，明顯右部第一個(gè)終結(jié)符是b, 那關(guān)于這個(gè)產(chǎn)生式的終結(jié)符就是b 了。

然后是S->AB，這時(shí)右部的第一個(gè)是A，非終結(jié)符，所以不成立。這時(shí)你就要再把A的產(chǎn)生式引進(jìn)來(lái)（因?yàn)锳有關(guān)于他的產(chǎn)生式）。

關(guān)于A的產(chǎn)生式為：A->#,A->b,分別代入S->AB的產(chǎn)生式得：S->B(應(yīng)該是S->#B，但是#可以省略) 和S->bB，看第二個(gè)S->bB ，馬上就可以知道遇到的第一個(gè)終結(jié)符是b

然后看第一個(gè)S->B，這個(gè)時(shí)候B不是終結(jié)符，所以不成立，這時(shí)就要把B的產(chǎn)生式導(dǎo)進(jìn)來(lái)，變成S->aD ,S->#。

則這個(gè)時(shí)候first(S)={b, a , #}

first集就是所有第一個(gè)終結(jié)符 and 所有非終結(jié)符的first集的并集~ 如果第一個(gè)非終結(jié)符可能是空，則再并上后面的終結(jié)符的first集以此類推

Follow集：該符號(hào)后面跟著的第一個(gè)終結(jié)符

follow set

※ LL1 Parsing Tables

Our goal is to construct a parsing table T for
a context free grammar G.

規(guī)則

很多table是不能做到每個(gè)move（每個(gè)格子）里只有一個(gè)選項(xiàng)的，也就是不是LL(1)的。

If any entry is multiply defined in the parsing table, then the grammar is not LL(1). And in fact, this is the definition of an LL(1) grammar, so the only way to be sure that the grammar is LL(1) or the mechanical way to check that the grammar is LL(1), is to build the LL(1) parsing table and see if all the entries in the table is unique.

※ Bottom-Up Parsing

Bottom up parsing is more general
than deterministic top down parsing.

自底向上parse

a bottom up parser traces a rightmost derivation in reverse，也就是parse的時(shí)候都是去parse最右側(cè)的非終結(jié)符

※ Handlers

一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄，句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它規(guī)約成該產(chǎn)生式左部的非終結(jié)符，句柄代表了最右推導(dǎo)過(guò)程的逆過(guò)程的一步。

Semantic Analysis

前端parse

因?yàn)橛行〆rror不是context free的也就是上下文有關(guān)的，語(yǔ)法是不能夠發(fā)現(xiàn)的error，所以需要Semantic Analysis這一步去做類似的check：

check list

※ Scope

有些是static scope，也有些language是dynamic scope。scope容易引起的問(wèn)題就類似定義了一個(gè)class但是先于定義使用了這個(gè)class。

※ Symbol Tables

可以通過(guò)遇到一個(gè)變量就壓棧的方式，每次找都在棧里面找到最近的變量，并且如果出了這個(gè)變量的作用域就彈棧，來(lái)check是不是有define這個(gè)變量。

用table來(lái)看scope

class的是不是已經(jīng)define過(guò)了是不能這么做的，只能一開始先pass一遍程序拿到所有的class definition，然后再check一遍。

※ Types

types

不同語(yǔ)言的type check

type check就類似如果e1是int，e2也是int，那么e1+e2就還是應(yīng)該是int。

※ Type Environments

So what is a free variable, a variable is free in an expression if it is not defined within that expression.

The type environment encodes this information so a type environment is a function from object identifiers from variable names to types.

※ Implementing Type Checking

實(shí)現(xiàn)

※ Static vs. Dynamic Typing

The static type of a variable will be its given type. The dynamic type of that variable will depend on what is assigned to it during program execution.

※ Self Type

self就是runtime的時(shí)候?qū)嶋H的type，有的時(shí)候如果你寫死了返回父類的type，就不能用這個(gè)方法賦值給子類，但是如果你return self就可以了~

但是self是static type不是dynamic type哦~~

The best way to think of an occurrence of self-type is that it's a type variable that ranges over all the sub-classes of the class in which it appears.

※ Error Recovery

如果沒(méi)有聲明類型的會(huì)當(dāng)做Object類型的，然后去做檢查：

沒(méi)有聲明的都當(dāng)做object

但是上面這種方式會(huì)引發(fā)一連串的error，比如x假設(shè)為object，那么x+2就是illegal的操作，然后x+2又被作為object，然后y身為int被賦值就又有問(wèn)題了。

另一種方式是引入No_Type，可以作為任一種類型的子類：

No_Type

Runtime Organization

The main thing we're going to cover in this sequence of videos is the management of Runtime resources and in particular I'm going to be stressing the correspondence and the distinction between static and dynamic structures. So static structures are things that exist to compile time and dynamic structures, those are the things that exist or happen at Runtime.

內(nèi)存中低地址畫在top，高地址在bottom醬紫：

code gen

※ Activations

Activations就是函數(shù)被調(diào)用~

the activation tree depends on the runtime behavior of the program. So it depends on the runtime value who's exactly which procedures are called and what the activation tree turns out to be.

Now, this was not illustrated in our examples but it
should be obvious that the activation tree can be different for different inputs.

當(dāng)procedure被調(diào)用會(huì)push到棧里面，當(dāng)執(zhí)行結(jié)束返回會(huì)pop棧。code下面就是activations stack用于記錄函數(shù)調(diào)用棧。

memory

※ Activation Records

An activation record is all the information that's needed to manage the execution of one procedure activation And often, this is also called a frame that means exactly the same thing as activation record. These are just two names for the same thing.

棧幀

※ Globals and Heap

globals是全局有效的，所以不能存在activation record里面。 So. The way that little variables are implemented is that all global are signed the fix address once And these variables with fixed addresses are said to be statically allocated because they're allocated essentially at compiled times.

增加了static變量的memory布局

布局

Now many lang uage implementations use both the heap and the stack and there is a little bit of an issue here because both the heap and the stack grow. And so we have to take care that they don't grow into each and step on each other's data And there is a very nice and simple solution to this and as a start to heap and the stack at opposite ends of memory and let them grow towards each other.

memory

※ Alignment

32bit和64bit分別對(duì)應(yīng)4/8 byte的內(nèi)存boundary，也就是內(nèi)存的單位是4/8 byte，如果內(nèi)容沒(méi)有滿一個(gè)單位，則會(huì)填充空bit：

內(nèi)存對(duì)齊

※ Stack Machines

比如7+5，會(huì)先把7和5壓棧，然后彈棧相加，把result 12壓棧：

stack

如果op = e1 + e2 + …… + en，那么會(huì)先把e1彈棧，壓棧e1的結(jié)果，以此類推，到en的時(shí)候只是計(jì)算en不壓棧，然后彈棧n-1個(gè)之前的result，相加后再壓棧。accumulator會(huì)用來(lái)存儲(chǔ)計(jì)算的值~

多個(gè)相加

Code Generation

MIPS架構(gòu)（MIPS architecture，為Microprocessor without interlocked piped stages architecture的縮寫，亦為Millions of Instructions Per Second的雙關(guān)語(yǔ)），是一種采取精簡(jiǎn)指令集（RISC）的處理器架構(gòu)，最早的MIPS架構(gòu)是32位，最新的版本已經(jīng)變成64位。

code gen其實(shí)就是用MIPS實(shí)現(xiàn)Stack Machines。寄存器a0就是acc用于存儲(chǔ)，sp指向下一條指令地址：

實(shí)現(xiàn)

※ Temporaries

the improvement that we're going to make Is have the co-generator assign a fixed location In the activation record for each temporaries.

We're going to pre-allocate memory or a spot in the activation record for each temporary and then we will be able to save and restore the temporary without having to do the stack pointer manipulations.

if we know how many temporaries that needs in advance then we could allocate the space for those in the activation record rather having to do push and pop, pushing and popping from the stack at runtime. 常量區(qū)的存在避免了頻繁push/pop。

※ Object Layout

cool里面的object

Now the class tag is an integer which just identifies the class of the object. So the compiler will number all of the classes.

object size is also an integer which is just a size of the object in words and the dispatch pointer.

Dispatch pointer is a pointer to a table of methods so the methods are stored off to the side and the dispatch pointer is a pointer to that table.

All of this is laid out in the continuous chunk of memory.

class的屬性會(huì)跟在方法列表pointer的后面~

Q: 為什么屬性是直接embed在class里面，而方法列表用pointer指出去呢？
A: 因?yàn)閷傩詫?duì)于有100個(gè)對(duì)象有相同名字的屬性，也不能用一個(gè)位置存儲(chǔ)，他們都是獨(dú)立的。但是方法列表如果有100個(gè)類都有相同的，那么其實(shí)他們可以用同一個(gè)method pointer，因?yàn)榉椒ú簧婕皵?shù)據(jù)，是可以共用的，可以節(jié)約空間。

Local Optimization & Global Optimization

※ Intermediate Code

Intermediate Language is just that, it's a language that's intermediate between the source language and the target language

應(yīng)該類似bitcode叭~ 中間代碼和匯編target語(yǔ)言的生成非常類似~

The main difference between generating assembly code and generating intermediate code is that we can use any number of registers in the Intermediate Language to hold intermediate results.

中間語(yǔ)言的優(yōu)點(diǎn)：

• 中間語(yǔ)言與具體機(jī)器特性無(wú)關(guān)，一種中間語(yǔ)言可以為生成多種不同型號(hào)的目標(biāo)機(jī)的目標(biāo)代碼服務(wù)。

• 可對(duì)中間語(yǔ)言進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化，有利于提高目標(biāo)代碼的質(zhì)量。

• 把源程序映射成中間代碼表示，再映射成目標(biāo)代碼的工作分在幾個(gè)階段進(jìn)行，使編譯算法更加清晰。

對(duì)于中間語(yǔ)言，要求其不但與機(jī)器無(wú)關(guān)，而且有利于代碼生成。

※ Optimization Overview

應(yīng)該在哪個(gè)語(yǔ)言層次實(shí)施優(yōu)化

優(yōu)化距離t = 2 * x; s = t + x其實(shí)可以簡(jiǎn)化為s = 3 * x如果要是t在其他地方木有使用~

優(yōu)化啥

三種優(yōu)化

※ Local Optimization

主要是常量替換 & dead code elimination。

例如x = x + 0; x = x * 1; x = x * 0，都可以不用跨函數(shù)的local優(yōu)化，x = x * 8還可以優(yōu)化為x = x << 3

if 2 < 0 jump P可以被刪除優(yōu)化掉，因?yàn)閕f的條件永遠(yuǎn)是false的。還有例如if DEBUG then在debug的時(shí)候是有的，release的時(shí)候就會(huì)被優(yōu)化刪掉。

優(yōu)化舉例

沒(méi)用過(guò)的變量可以刪掉

Each local optimization actually does very little by itself. And some of these optimizations, some of these transformations that are presented actually don't make the program run faster at all. They don't make it run slower either but by themselves they don't actually make any improvement to the program. But, Typically, the optimizations will interact. So performing one optimization will enable another. 有些優(yōu)化看起來(lái)沒(méi)啥用，但可以幫助后面的優(yōu)化，優(yōu)化是一步一步互相影響的。

※ Peephole Optimization

Peephole Optimization是直接優(yōu)化匯編代碼的一種tech。

Peephole

※ Global Optimization

在dataflow過(guò)程中，如果if-else兩邊都木有修改x，那么之后的x還是可以用最初的賦值替換：

control flow用常量替換

"global dataflow analysis," and it's designed specifically to check conditions like this. And essentially, global dataflow analysis is called "global" because it requires an analysis of the entire control-flow graph.

Register Allocation

中間代碼的一個(gè)問(wèn)題就是用了無(wú)限個(gè)寄存器，如何解決這個(gè)問(wèn)題呢，就是用多對(duì)一的方式：

many temp to one reg

舉個(gè)例子

So, if I have two temporaries t1 and t2, I want to know when they can share register. So, they're allowed to share a register and they're allowed to be in the same register if they are not live at the same time.

※ Graph Coloring

control

首先RIG圖會(huì)把同時(shí)出現(xiàn)的變量連起來(lái)（例如同時(shí)在等式右側(cè)，左右側(cè)是不算共存的），所以沒(méi)有connection的兩個(gè)點(diǎn)才可以放到同一個(gè)reg里面。

然后我們可以用圖著色(graph coloring)方法解決寄存器分配問(wèn)題。我們可以用N個(gè)顏色，也就是有多少個(gè)寄存器來(lái)著色：

著色圖示例

用reg實(shí)現(xiàn)

如何著色，首先先找到neighbor少于k的節(jié)點(diǎn)，一個(gè)一個(gè)放入堆棧并移除，然后直到所有都放入以后，從棧頂一個(gè)一個(gè)pop然后分配顏色，原則就是不能和已經(jīng)分配的neighbor同色：

著色規(guī)則

※ Managing Caches

寄存器訪問(wèn)很快，所以比較少，很expensive；cache訪問(wèn)比較慢，也會(huì)相對(duì)多一點(diǎn)；內(nèi)存訪問(wèn)會(huì)更慢一點(diǎn)，但大小會(huì)更大；硬盤就會(huì)更大的容量了。

存儲(chǔ)對(duì)比

把最忙的循環(huán)放在內(nèi)層也是一種編譯優(yōu)化~

※ Automatic Memory Management

如果有unused內(nèi)存，會(huì)被釋放掉。哪些是unused的呢，其實(shí)和java里面的GC很像，就是引用數(shù)無(wú)法找到它了，他成為了一個(gè)孤島unreachable。

※ Mark and Sweep

當(dāng)內(nèi)存用光，就會(huì)進(jìn)行Mark and Sweep標(biāo)記-清除算法。

• 標(biāo)記：從根集合進(jìn)行掃描，對(duì)存活對(duì)象進(jìn)行標(biāo)記（每個(gè)object有一個(gè)bit是用于mark的）
• 清除：對(duì)堆內(nèi)存從頭到尾進(jìn)行線性遍歷，回收不可達(dá)對(duì)象內(nèi)存
• 缺點(diǎn)：碎片化，產(chǎn)生內(nèi)存碎片

※ Stop and Copy

將所有存貨的對(duì)象從當(dāng)前的堆復(fù)制到另一個(gè)堆，沒(méi)有被復(fù)制的全部都是垃圾。

這種方式效率會(huì)降低，原因有兩個(gè)。

1. 得有2個(gè)堆，在這2個(gè)堆之間來(lái)回使用。也就是需要多使用一個(gè)堆的空間。

2. 當(dāng)程序進(jìn)入穩(wěn)定狀態(tài)后，可能只會(huì)產(chǎn)生少量、甚至沒(méi)有垃圾，但是仍然會(huì)來(lái)回復(fù)制，就顯得很浪費(fèi)。

※ Reference Counting

每個(gè)object存一下有多少指向它的指針，當(dāng)歸零的時(shí)候就應(yīng)該被回收了。

引用計(jì)數(shù)

這種的優(yōu)點(diǎn)是好實(shí)現(xiàn)，回收快；缺點(diǎn)是循環(huán)引用無(wú)法釋放以及每次assign都要操作計(jì)數(shù)比較慢。相比之下GC的可以并行就會(huì)效率更高一些。

原諒我如此劃水。。。最后一個(gè)小問(wèn)題，編譯器是用什么語(yǔ)言寫的？

第一個(gè)C語(yǔ)言編譯器應(yīng)該是用匯編寫的，但是第一個(gè)成熟的C語(yǔ)言編譯器應(yīng)該是由匯編和C語(yǔ)言共同寫的。

編譯原理講到了“自舉編譯器”。大意就是先用底層語(yǔ)言（應(yīng)該是匯編）寫一個(gè)能運(yùn)行，但效率極低的C語(yǔ)言編譯器（底層語(yǔ)言不好優(yōu)化），有了C語(yǔ)言的編譯器以后，就可以用C語(yǔ)言好好寫一個(gè)編譯器了。