沒什麼想說的，只是今天刷步行街的時候綠帽男頻出，希望天下的女人能夠善待自己的男友，特別是當你的男朋友是個jrs的話，請珍惜他們，他們都是好男人。
（一）lexical analysis（詞法分析）1. 詞法分析的作用首先提幾個概念
keyword 關鍵字，如for，do，while，if else等Identifier 標識符，如 a，a1，a_1等（譬如變量名）Operator 關係運算符，如 +，-，*，=等把一個字符串轉換為為一種詞法單元（token），一個token的形式是這樣*<token class, lexeme>*, 上面的提到的那些概念在一個token中我們可以把它們當作token class, 而具體的字符子串則被是這裡的lexeme
舉個🌰
if(i == j)
t = 0
else
t = 1
首先在詞法分析器看到的並不是人類肉眼看到的東西，在詞法分析器的識別中，字符串首先是如下的格式 "\n"代表的是換行符，"\t"代表的是空格
if(i==j)\n\t\tt=0\nelse\n\t\tt=1
經過了詞法解析器的解析後得到的就是一個個的詞法單元（token）
2.詞法分析要解決的東西所以詞法分析是要解決什麼事兒呢，下面的例子都是出於龍書
(1) Amazing whiteSpace考慮Fortran這種情況，在遠古Fortran語法中，Do 5 l = 1,25 是一個常規的loop循環語句，代表了從now開始執行5行，執行1-25共25次，而Do 5 l = 1.25代表的含義是標識符 Do 5 l的值是float1.25，所以在現代語言的編譯器中，對這種情況的處理是編譯器要解決的一類事
Do 5 l = 1,25
Do 5 l = 1.25
編譯器在對程序片段進行詞法分析的時候需要一個概念 "Lookahead"，進行掃描的時候一般是left to right，看下面的🌰，針對這個程序片段，當掃描到第一行的 "="，它需要Lookahead地明白，到底這裡的 「=」 是一個簡單的賦值符號，還是和 「==」 一起表示 「等於」 的含義，再簡單一些針對 第三行的第一個「e」單詞，它需要lookahead地明白，「e」 代表是一個標識符，還是和 「else」 一起表示一個標識符
if(i==j)
z=0;
else
z=1;
看下面這個🌰，結合標題，懂了嗎？這個還是不要解釋了，怕吐。
IF ELSE THEN THEN = ELSE;ELSE ELSE=THEN
正則語言，想必姐妹們，學安全的，學開發的，熟的不能再熟了吧。
4.Formal Language（形式語言）形式語言，在編譯器中也擔任著非常重要的看角色，在編譯器中往往使用著好幾種不同的形式語言，譬如正則表達式就是其中一種形式語言，簡單的舉兩個🌰
我們在表示形式化語言的時候有三個基本的元素 ，一個具有meaing意義的function，一個Map關係，一個Expression例如正則表達式
Function('c')={"c"}代表正則表達式c代表了一個map {"c"}
而其中比較核心的就是這個meaning function，所以為什麼需要這個meaning function呢
expression和meaning往往不是一對一的關係，而是多對一的關係，這就可以極大程度的提高效率5. Lexical Specifications(詞法規範)詞法規範就是定義了接受怎麼樣的輸入，以及輸入的內容與什麼token class進行關聯，以下是一些簡單的🌰，值得注意的是在一般的Lexical Specifications，keyword比較特殊，會直接定義為本身。
image-20211212224514835在程式語言中值得注意的還有whitespace（也就是🌰中的skip），還有Comment（注釋），它們分隔了其他的tokens，例如 if a本身代表了一個keyword和一個Identifier和一個如果沒有對Skip的解釋，那就你變成了一個Identifier if a，由此也可以看出單純的用正則表達式去解析輸入流為tokens，他的結果往往是不明確的。
這裡就引入了一個新的概念，disambiguation rule消歧規則，而一個常用的規則就是「最長可能匹配原則」，其中有兩個內容
舉個🌰，下面的程序片段，如果不使用最長可能匹配原則，for_b中的for就會被匹配為Keyword for，這顯然是不符合語義的。
if a = for_b
詞法是由正則進行定義，然後，往往通過finite automata（有限狀態機）進行實現，一個字母表Σ由以下的元素實現
一個集合∆，由Σ中的字母進行標記的由state -> state的edge邊，空集€也可以作為一個edge上的標記，也就是說，(q,€,q')代表了q狀態到q'狀態是一個自發的不需要條件的過程舉個🌰，下面就是一個接受實數的有限狀態機，無非就是判斷本位是0-9還是"." ,如果是"."則到另外一個狀態，如果是0-9，則循環這個狀態繼續添加為實數總的一位數字，便於理解，0狀態有兩種可能，一個非0實數，或者為0。
如果此時解析的片段為3.1415920-3+x，那麼在生成token的時候可以把已經是別為實數的3.1415826,我們把這個值和token class一起儲存為一個token
上類的這種狀態機被稱之為 deterministic finite automaton（DFA）可確定有限狀態機。還有一種有限狀態機為nondeterministic finite automata（NFA）不確定的有限狀態機，當一個input會有多種路徑進行狀態轉換，有的路徑會成功，而有的路徑會失敗，這時會出現這種情況。為了讓「最長可能匹配原則」能夠正常實現，需要追蹤狀態轉換的接受狀態，如果不被接受則重設狀態轉換。
舉個🌰，當一個語法中包含了INT和FLOAT（🌰中的REAL），那情況就是下面這種NFA，對於q0要猜測（一般情況下可能是遍歷）會被那種type接受。
image-202112122341409137. 由正則表達式到NFA正則表達式可以非常方便的轉換為有限狀態機，舉個🌰，此時我們定一個利用正則表達式作為標記的遞歸過程（其中的兩個圈的qf，代表這裡是可遞歸的），一個正則表達式就可以被轉換為有限狀態機的轉換條件（edge，鄙人還是說狀態轉換條件比較順嘴兒），因為在轉換為NFA的過程中可能會出現新的temp狀態，所以會引如p1，q1，其中第三個r*的轉換有點難懂，那就對了，難懂說明他是NFA。
8. 由NFA到DFANFA的規範定義其實是很簡單的，但實現起來會非常的麻煩；實現DFA非常的簡單的，首先我們把程序當前的狀態儲存在一個初始化為q0的程序變量中，然後根據接下來輸入的character，根據狀態轉換錶轉換到下一個狀態，因為要符合最大匹配原則，需要持續的進行分析。如果要實現NFA，我們有一個問題，我們往往會碰到很多的choice，但卻不一定知道去選擇哪一個choice進而進行狀態轉換分析，這時NFA在遇到任何的choice的時候，它需要遵循任何一個choice，我們實現的方式就是在預計算的階段遵循之前一樣的法則，而不是在運行時。
這裡的處理就涉及到了一個離散數學中的知識
首先我們需要去定一個€-transition的情況，來包括所有從{q0}狀態發生狀態轉移的情況，下面的S指的是所有的狀態Q的中符合上面符合€-transition的子集，下面的核心式子指的就是不需要任何狀態輸入消耗的狀態轉移情況。image-20220110132738915下面定義一個需要一個狀態輸入"a", 得到的所有情況，(q,a) → (q′,ε) 也可以表達為 (q,a,q′) ∈ ∆，簡單的來說就是在整個狀態轉移表中q -> q'的狀態轉移存在一個edge a，也就是這裡所需要的狀態輸入（不是輸入狀態，其實就是狀態轉移條件，鄙人喜歡這麼說）。
image-202201101345042509. 最小確定性有限自動機閉包！
10. 由正則表達式到DFA這裡提出一種 Brzozowski derivatives and Antimirov’s partial derivatives 提出的一種精妙的方式，有兩篇論文，準備抽空看了。
(二)Liveness Analysis1. WHY LIVENESS ANALYSIS活躍變量是數據流分析中的一種，在編譯器的設計中，活躍變量分析是為了優化編譯器的性能，主要是在指令選擇的時候使用，在靜態分析中也可以幫助理解用的最多的數據流分析。
2. WHAT IS LIVENESS ANAYLYSIS活躍變量分析，顧名思義就是分析出還活著的變量，複雜的來說就是，給定一個live的屬性，當一個變量在數據流輸入輸出的過程中不會再使用，那麼此時它就是一個活躍變量，live的屬性值就是 fucking yes
3. 如何判斷一個變量是否是live假設一個三地址碼x <- y ⊕ z
要判斷變量是否live，有兩個可能
immediate
例如y和z兩個變量，在這個二元操作⊕執行之前就被使用（取值）
next
在下一條指令中一個變量是live的，那在當前指令中他就是live的，這個情況相對上面的略微難理解一些。這樣假設，有兩個聯繫的三地址碼
x <- y ⊕ z
a <- u
這裡可以看到在第二條指令中，u根據imediate來看是live的，所以它在x <- y ⊕ z中也是live的，即使插入一個常量的操作u依舊是live的，例如這個情況
x <- y ⊕ z
x <- 100
a <- u
有一個例外, 此時x是一個賦值的操作，所以說原有的x變量在這條指令執行之後就不是live的了，雖然下一條指令的時候x是live的，但這個x已經不是之前的那個x了，之前那個x已經變成了no live並釋放掉了
x <- y ⊕ z
a <- x
除此之外還有一種情況較為特殊，當return x這種情況下，x一定是live的，我們用邏輯形式來表達上面的情況下的規則，live(l,x)代表在行號為l時，x變量是live的，現在常用的一種工具 Datelog 就是可以基於二元決策圖（BDD）進行活躍變量的分析，這裡的實現路徑，就不詳細講了，我的讀者們應該只能看懂下面的了，講實話，具體的實現到時候在油管上找一些國外課程的視頻看看，在視頻裡對這種東西更容易理解
image-20211215221814000image-20211215223336364當被分析的程序語言允許循環的存在時，上面的四條邏輯規則明顯是無法使用,此時引入以下的邏輯規則（這裡的「？」指的是二元比較符），如果上面的例子看懂的話，對下面的規則應該也是挺好理解的。
image-20211215224354240上面的所有例子中只用到了live一個謂語，可以看出在性能上規則具有一定的重複性，例如L2和L4，規則上非常的相近，從性能上來說，可以添加其他的謂語來更好的抽象出合理的邏輯規則。下面提出三種新的謂語
succ(l,l') 代表行號l時，當前指令執行後，執行的行號也許是l'利用這三種謂語，可以把所有的規則變成兩條新的邏輯規則
image-20211215225904309K2，在l行，u不是被進行了賦值操作，l之後執行的指令是l'，在l'時，u是live的，則l行時u是live的
由上面的學習可以得到，在進行活躍變量分析時，def謂語應該是要最先飽和的，因為它的分析結果不會對其他的謂語有影響，不會影響到整個分析的膨脹，然後再飽和所有live謂語
在K1，K2的規則前提上可以引入以下的規則
image-20211215231025406OK，關於活躍變量的知識應該就講這些，在課程中後續的內容是一些控制流分析，個人覺得拿活躍變量舉例從目的上來說，意義不大，未來直接做控制流分析的文章吧。