編譯器的工作步驟
在開始說任何東西之前，我們先來大緻看一下編譯器是怎麼工作的——從代碼到程式，大概要經過下面這樣的步驟——這裡用粗淺的語言進行解釋，先有個印象即可，後面還會提到
- 詞法分析：程式設計語言的語句，由一堆堆的單詞組成——比如變量類型名、變量名、函數名、值、符号等。既然我們要讓機器來分析源程式然後編譯，那麼就需要首先讓計算機能夠明白我們寫的語句是什麼意思，而了解語句的第一步就是了解每個詞。所謂文法分析，進行的工作就是讓計算機識别單詞；
- 文法分析：完成詞法分析，就要通過文法分析來識别語句的結構；
- 語義分析：該步驟的目标，就是确定“某一條語句是什麼意思”，檢查一下說的有沒有不合法的地方；
- 符号表管理：相當于字典。符号表用于各個階段查找、填寫；
- 出錯處理：在出現錯誤時的處理。種類可分詞法錯誤、文法錯誤、靜态/動态語義錯誤；
- 中間代碼（可選）可以為優化提供支援。中間代碼接近于目智語言，卻又與具體硬體對應的機器指令無關，便于優化和代碼生成。中間代碼優化是對指令進行等價變化，提高運作效率；
- 中間代碼經過優化，就可以生成目标代碼了。比如二進制程式的機器碼，或者各種 VM 用的位元組碼。
詞法分析器 Lex 和詞法分析器 Yacc：
Lex（Lexical Analyzar） 是詞法分析器， Yacc（Yet Another Compiler Compiler） 是文法分析器。
雖然從名字上看，這兩個東西就已經是“分析器”了，然而實際上并不是，他們是用來生成“分析器”的工具。Lex 是用來生成詞法分析器的工具，Yacc 是用來生成文法分析器的工具。
這兩個工具可以根據我們輸入的詞法 / 文法規則，自動生成相應的文法分析器、詞法分析器，然後這些分析器就可以幫助我們簡單地完成對源代碼的詞法、文法分析。
因這兩樣工具的存在，開發編譯器、解釋器的詞文法分析器的難度被極大降低。在現代編譯器、解釋器的開發中，真正有難度的地方在于語義分析和後期優化。
Lex正規式示例：
在 Lex 中，我們可以使用一種被稱為“正規式”的字元串，來簡單地定義“某種符号應該長成什麼樣子”。
我們先直接體驗一下。
比如下面這個實際定義 Number 和 Identifier 的例子：
Yacc 的産生式示例：
Yacc 用如下這種形式來定義“一個表達式應該長成什麼樣子”：
E : E '+' E | E '*' E | id
這段代碼說明，一個表達式 E 可以有三種情況組成：最簡單的情況就是 id 。一個變量 x ，他自己就是一個表達式，兩個表達式相加是一個表達式，兩個表達式相乘還是一個表達式。
對于這個産生式，如果我們寫
x-y
就是不合法的——因為我們并沒有定義兩個表達式可以被 ‘-‘ 連接配接
例：對于 Yacc 而言，-x–y也是合法的。對于表達式“-2–3”，這裡的減号有一進制操作也有二進制操作，實際計算的情況是這樣的：(-2)-(-3 )
語言之間的翻譯
進階語言之間可以實作跨語言的翻譯。
預編譯的例子：sql、c 混合程式設計。
sql、c 混合程式設計，實際上的運作方式是先把 sql 變成 c 語言，再對由 sql 轉換來的 c 和本來就是 c 的部分進行整體編譯。把 sql 轉成 c 的過程就叫“預編譯”，Lex、Yacc 就是這樣的。
在 UltraGram 中，就可以把我們寫的 Lex、Yacc 變成合法的 C 代碼。我們就可以把這兩份代碼和我們自己寫的 C 代碼一起編譯，實作開發自己的解釋器/編譯器。（lex yacc 就是開發解釋器編譯器這種東西的工具，将曾需要手工實作的詞法文法分析自動化實作）。
對于反彙編，編譯器為了防止反彙編會在編譯時加入一些無效代碼。
編譯器與解釋器
語言翻譯
語言翻譯分為兩種，分别是先翻譯後執行和邊翻譯邊執行。二者基本功能相同。且在翻譯的角度來看，兩種方式涉及的原理、方法、技術都是類似的
先翻譯後執行
比如 C 這種需要編譯的語言。特點是效率高、省空間。但互動性、動态性差，可移植性也差。。多數語言都是這種。
邊翻譯邊執行
比如 py、js、java 這種使用解釋器工作的語言。跟上面的基本相反。
生成位元組碼然後運作。從進階語言到位元組碼實際上是翻譯，在運作時再從位元組碼轉化成機器碼執行。
編譯器的工作原理和基本組成
通用程式設計語言的主要成分
語言都由聲明、操作兩大部分組成，聲明+操作=語言的完整定義。
例：過程式語言：
過程式語言有兩種語句：聲明性語句和操作性語句。前者提供操作對象的性質（比如資料類型、資料值、對象的作用域）。後者則描述各個操作（比如指派）的次序，進行實際操作。
編譯器對上述兩種語句使用不同的方式進行處理。對于聲明性的，就是給被聲明的對象配置設定一塊空間（稱為“環境”）。操作則是生成針對環境的可執行代碼序列，比如從某個被聲明的空間中取值，進行某些運算後将結果放到某個空間中。
是以，“先聲明後引用”的規則，能夠友善編譯器對語言進行處理，也能提升執行效率。
例如，一些語言支援如下操作：
i=10; // 在沒有對 i 進行聲明的情況下直接賦整數值
i="abcdefg"; // 直接重新賦字元串值 雖然看起來是兩行代碼，但是在實際執行中，執行過程是：為整型配置設定空間->寫入整數值10->重新配置設定空間->寫入字元串值。将導緻效率的降低。
以階段劃分編譯器
編譯器的工作過程可以大緻劃分為四步：詞法分析、文法分析、語義分析、目标代碼生成。
這個圖要背下來。。。。
其中，中間代碼生成及其之前的步驟，編譯器和解釋器可以是一緻的。
- 詞法分析：相當于識别每個詞代表什麼。進行的工作就是識别單詞。單詞至少分為：關鍵字、辨別符、字面量、特殊符号；
- 文法分析：識别語句的結構。通常以樹的形式表示；
- 語義分析：前兩者正确的情況下，語義未必正确。確定“什麼語句是什麼意思”——檢查結構正确的句子是否語義合法，也可以修改文法樹的結構；
- 中間代碼（可選）可以為優化提供支援。中間代碼接近于目智語言，卻又與具體硬體對應的機器指令無關，便于優化和代碼生成。中間代碼優化是對指令進行等價變化，提高運作效率。
例：編譯器各階段工作：
- 詞法分析：将源程式轉化為記号流（記号流是線性結構的），源代碼中的變量名在記号流中被替換為id1、id2這樣的辨別符。若我們隻寫一個
real x
- 文法分析：該步驟，我們将記号流分析為兩個文法樹。因為句子是有層次關系的，樹又可以用于描述層次關系，是以我們使用文法樹來描述句子的文法結構。右下角文法樹的意思是：對 id3 和 60 使用 * 進行運算，再将結果和 id2 使用 + 進行操作…… 最後指派給 id1；
- 語義分析：對文法分析生成的兩個文法樹進行分析。
編譯原理筆記1：概述編譯相關的基本知識
語義分析這一步，要看文法結構正确的文法樹的含義是否正确——這一步也可以做些附加的操作，比如這裡對60的轉換，這就是編譯器為了簡化語言而自動進行的附加工作——對類型進行了自動轉換。另又如C語言中，我們可以寫
1+2.0
這樣的式子，與此同理，也是編譯器自動在語義分析時進行了類型轉換。
- 中間代碼優化：将4條語句轉為了兩條；
- 目标代碼生成，解決彙編、可重定位、記憶體形式（Load-and-Go）問題
編譯器的分析/綜合模式
編譯器可分為前後端，前端進行語言結構和意義的分析，後端進行語言意義的處理。
中間代碼是前後端的分界。編譯器的基礎架構就分為前端、源代碼的中間表示和後端。
編譯器掃描遍數
在編譯原理中有個術語，叫做“掃描”，“一遍掃描”是指：在編譯的每個階段中，編譯程式将程式代碼完整分析一遍的工作模式。
比如：
- 詞法分析階段，把整個程式轉化為記号流，這叫一遍；
- 詞法分析，對記号流（記号流本身就是一種程式的變體）分析得到文法樹，這又叫一遍；
- 語義分析，對文法樹（文法樹是記号流的變體，也就是程式的變體）進行修改，分析得到中間代碼，這又叫一遍；
掃描遍數的影響因素：
- 軟硬體條件：如記憶體太小或者要做全局優化。想要做比較好的優化就需要全面了解程式，掃描的遍數就要增加；
- 語言結構：如果先聲明後引用，就隻需要掃描一遍；但如果先引用後聲明，處理起來就比較複雜，需要多掃描一遍；
- 編譯技術，比如拉鍊-回填
goto lab1; ... goto lab2; ... lab1:...
拉鍊-回填實際上也是先引用後聲明，但隻需要掃描一遍——當第一次讀到引用時，先把後面的目标位置填個問号，讀到多次也都填上問号——因為引用了相同的東西，是以這個問号可以“拉成一條鍊”。當我們确定了lab1的具體标号位置時，就回頭把那一串的内容都填上。這并不是第二次掃描，叫做“拉鍊-回填”
編譯器的編寫
- 直接用語言寫；
- 使用編譯器編寫工具：包括文法/詞法分析工具、文法制導翻譯、代碼生成、資料流分析等；
- 基于編譯器基礎架構的編譯器構造系統。也就是開放式編譯器，比如LLVM、GCC、SUIF等。這樣開發，就是自己用工具搞定詞法分析、文法分析，再用這玩意做後端，就能開發出來自己的編譯器了