编译原理绪论
??之前一直在寫程序，了解到運行程序的兩個步驟：編譯，運行。在Microsoft visual C++中編譯和運行是分開的兩部分。在DEV C++中集成為一個按鍵。在之前的印象中，編譯就是尋找語法錯誤的過程。只要程序語法有錯誤，程序就無法通過編譯。并會提示相應的信息，告訴寫程序的人去哪里修改什么類型的錯誤。這學期開始，開設了編譯原理課程。按照之前的習慣，通過寫博客，及時梳理自己的思路并希望能在某些方面有所提高。下面開始吧！
??學東西先問自己幾個問題：什么是編譯原理？為什么需要編譯原理？怎么才能實現編譯原理？
??剛開始學習，對編譯原理的理解不是那么深刻。簡單談一談自己的看法。如果后續學習過程中發現自己理解有誤，也會及時修改。
??為什么需要編譯原理？
????了解計算機的人都知道對于計算機來說，它所能識別的只是機器代碼。就是我們常說的0，1串。但對于編寫程序的人來說，如果利用機器語言編寫程序，那過程必將是痛苦且低效的。程序員為了讓生活對自己好點，慢慢的開發出了高級語言，如C，C++，python等等。抽象來看，輸入是高級語言，輸出是機器語言，那中間的轉化器就是編譯器，其原理就是編譯原理?，F在知道為什么需要編譯原理了吧！它是我們和計算機更好溝通的橋梁。
?? 什么是編譯器？
????由之前的問題了解到，編譯器的作用是把高級語言轉換成低級語言（機器語言）。其實這簡單的解釋了編譯器的定義。運用編譯原理編寫的程序，并能起到編譯作用的程序叫做編譯程序。把編譯程序做一個推廣：翻譯程序。翻譯程序的定義是：把某一種語言程序（稱為源語言程序）轉換成另一種語言程序（稱為目標語言程序），而兩種程序在邏輯上等價。對翻譯程序的源語言（高級語言）和目標語言（機器語言）加以限制就成為了編譯程序。
??怎么才能實現編譯原理？
????問題有點抽象。轉換的直接一點：編譯程序怎么寫？編寫程序自然有它的步驟，下面會陸續介紹到編譯過程的五大步驟。只有了解編譯過程，才能對應去寫如何實現這些編譯過程的代碼。
??回答完剛才的問題，想必對編譯原理和編譯程序有了少許的了解。下面開始進入正文：通過本篇文章，想解釋明白下面幾個問題：
??1.編譯程序的五大步驟及各步驟的主要工作
??2.有關編譯程序的幾個名詞解釋，包括：表格管理、出錯處理、遍、編譯前端/后端
??3.編譯程序的生成，自展和移植。
??注意：因為作者對C語言比較熟悉，所以編譯程序的舉例都以C語言作為基準。
一、編譯程序的五大步驟及各步驟的主要工作
??先對五大步驟做一個說明，再詳細介紹各個步驟：
??1） 詞法分析
??2） 語法分析
??3） 語義分析及中間代碼生成
??4） 優化
??5） 目標代碼生成
??它們的順序其實已經說明其關系，但為了便于理解，這里附上一張關系圖：
??下面對各個步驟進行詳細說明：
??1） 詞法分析
??詞法分析就是從頭到尾掃描，識別出語法單元，并查看是否存在詞法錯誤。那什么是詞法錯誤呢？舉個例子：在部分編程語言中，要求變量名只能由下劃線或字母打頭而不能使用數字。比如在C語言中的int 3a;就一個不合法的聲明，這種錯誤會在詞法分析是被檢測出來。再舉一個例子，作為編程新手常犯的錯誤：總是把英文的;寫成中文的；這個在編譯過程中都會報錯，錯誤的階段屬于詞法分析。
??在詞法分析的過程中不止會尋找錯誤，也會對正確的詞進行一個分類。包括以下幾個類別：
?????1. 基本字（保留字）：主要指語言中已經定義好的那些字符，例如:int double typedef return等等
?????2. 標識符：主要指在程序中定義的變量名。如int a;/double b;中a，b就屬于標識符
?????3. 界符：界符用于分隔程序，常見的界符有; { } 等
?????4. 算符：主要指進行運算的字符，運算包括數值運算和邏輯運算。例如：+,-,*,/和&,|;
?????5. 賦值符：完成的功能就是賦值，例如：=，+=，-=等
??舉個例子，說明詞法分析干的事情：
??2） 語法分析
??語法分析主要作用是根據語法規則識別語法單位并分析語句中有沒有語法錯誤（這句話聽起來很抽象，啥算語法錯誤？）識別語法錯誤，就像a=+c其實本來應該是a=b+c，b沒有寫，對于詞法分析過程只認定出是兩個連續的算符。對于加號的語法是左右都要有變量，這就是語法錯誤。另一個作用是識別語法單位，。舉個例子：A=B+C*60;是一個賦值語句，可以構建以下語法分析樹，說明這是一個正確的賦值語句：
??使用語法分析樹的好處有什么呢？
????好處在于能夠表示出語句的層次結構，同時也可以用于輔助對語句的翻譯。
????從下往上看，經歷的算符分別是*到+再到賦值符=。這正好符合我們運算過程中對于優先級的體現（想想在運算中是不是先乘除，再加減，最后把結果賦值給左邊）。
??對于詞法分析和語法分析的總結：詞法分析是一種線性分析，語法分析是一種層次結構分析。
??3） 語義分析與中間代碼產生器
??語義分析在語法分析之后，所以能到語義分析說明程序中已不存在語法錯誤。還用之前的a=b+c舉例。對于+語義來說，要求左右兩個操作數的類型應當相同。對其的檢測就屬于語義分析的部分。還有一些與具體語言相關的，典型情況包括：變量在使用前先進行聲明、每個表達式都有合適的類型、函數的調用和函數的定義相關。（參考博客：https://blog.csdn.net/hit_shaoqi/article/details/83120448link，該博客中列舉很多語義分析的錯誤例子）
??中間代碼生成的步驟要先理解什么是中間代碼？中間代碼就是用簡單表達式表示你要進行的操作，舉個例子就明白：
??對于A = B+C60;這個表達式生成的中間代碼如下：
????temp1 = C60
????temp2 = B+temp1
????A = temp2
??對中間代碼常用四元式表示，四元式的結構如下：
??所以對于上面的中間代碼轉換為四元式如下：
??4） 優化
??優化的意思很明顯，就是對代碼進行調整使其運行時效率更高（體現在時間/空間上）。優化主要有三個方面：公共子表達式的提取，循環優化（主要優化對象），刪除無用代碼。
??下面對三種優化分別舉例：
??公共子表達式的提取優化：
???優化前
?????A = B + C;
?????…
?????D = B + C;
???優化后
?????T = B + C;
?????A = T;
?????…
?????D = T;
??循環優化：
???優化前
?????for k=1 to 100
??????M=I+10k;
??????N=J+10k;
???優化后
?????M=I;
?????N=J;
?????For k=1 to 100
??????M=M+10;
??????N=N+10;
??從上面可以看出，循環優化的主要思想是把乘除法優化為加減法。（我們都知道乘除運算所用時間遠大于加減法）。
??刪除無用代碼：
????無用代碼就是對程序的結果沒有影響的代碼。主要可分為兩部分
???1. 復制傳播
?????如果存在語句y=x，并且下面有許多語句在使用y。由于x,y在數值上相等，所以可利用x代替所有的y。這樣就可以減少y=x這條語句。這種思想就叫做復制傳播。
???2. 無用代碼（死code）
?????在程序編寫過程中，可能出現對一個變量賦值，但后面并沒有使用該變量，就認為該賦值無效，將其刪除。
??5） 目標代碼生成：
??目標代碼生成的過程非常復雜，就是把優化好的中間代碼轉換成指定的低級語言代碼（匯編語言或者機器語言等等）。比如上面所舉例子最終轉換的匯編代碼如下圖：
??從以上五個步驟可以看出一個明顯的分界線，就是第三步中語義分析和中間代碼生成之間。在中間代碼生成之前，都沒有對代碼的任何翻譯，所做的只是分析，故又稱為分析部分。語義分析之后都是對代碼的翻譯調整，故又稱為綜合部分。
二、有關編譯程序的幾個名詞解釋，包括：表格管理、出錯處理、遍、編譯前端/后端
??表格管理：
????在編譯程序中的表格主要的指的是符號表。符號表內存儲的內容就是標識符（變量）的各種信息。例如：變量類型，存儲位置等等。而對符號表的維護是貫徹在整個階段的。（即每個階段對符號表都會增添或刪改）
??出錯處理：
????在編寫程序過程中難免出錯，所以對于錯誤的處理就至關重要。出錯可分為兩大類：語法錯誤和語義錯誤。對于錯誤處理分幾個層次，由壞到好分別為：檢測到錯誤并暫停報錯、檢測到錯誤提示報錯信息并繼續執行程序以發現更多的錯誤、檢測到錯誤并由對應的辦法對錯誤進行處理校正。
??遍（趟）：
????平時總說一遍，兩遍。但這里的“遍”定義為對源程序或源程序的中間結果從頭到尾掃描一次并作有關的加工處理，生成新的中間結果或目標程序。一遍即可以對一個階段而言（比如把詞法分析單獨作為一遍），也可以包括多個階段（比如把詞法分析、語法分析、語義分析和中間代碼產生和為一遍）。
??遍的作用是什么？
????“遍”可以使編譯程序結構更清晰，每一遍可以集中處理關鍵問題
??編譯前端/后端：
????在概念上一個編譯程序可劃分為編譯前端和編譯后端。
????編譯前端主要由與源語言有關但與目標機無關的那部分組成的。這些部分通常包括詞法分析，語法分析，語義分析與中間代碼生成。
????編譯后端主要由與目標機有關的那部分組成的。這些部分通常包括優化和目標代碼生成。
????那為什么需要劃分編譯前端和后端呢？
????從上面的概念可以看出，中間代碼處于編譯前端和編譯后端的過渡位置。做這樣一個圖：
??從這個圖看出，高級語言變成中間代碼這部分叫前端。前端可以由不同的部分引起。同樣也可以產生不同的后端。這樣不同的前端可以對應相同的后端，相同的前端可以對應不同的后端。就可以很好的體現代碼的移植性。對于移植性的介紹會在后面說明。
??在這里解釋下為啥會有機器A,機器B的區分。在不同機器上的架構是不同的，據兩個方面的例子。一方面是手機和pc機（一大一小，實現方式肯定不同），另一方面是指令集體系結構的不同，像CISC和RISC的實現結果肯定也不相同。
三、編譯程序的生成、自展和移植
??編譯程序的生成有三大組成部分：源語言、編譯程序、目標語言。編譯程序的作用就是把源語言變成目標語言。更為具體：如果想讓編譯程序在目標機上運行，那么編譯程序的編寫語言需要是目標語言。（是不是很繞？這語言，那語言的）。為了更方便的說明，做了圖形的規定（還是拿圖說話！）取名為T形圖：
(s代表源語言，T代表目標語言，I代表編譯程序)
??編譯程序的自展
??給定一個目標：在機器A（目標機）上，用語言A（編譯程序實現語言），構造高級語言L（源語言）的編譯程序。T形圖表示為：
??Step1:可以考慮使用L的子集S，在機器A上用語言A構造S的編譯程序。T形圖如下：
??Step2:再在機器A上，用語言S構造L的編譯程序。T形圖如下：
??再將兩者結合，step1中s可編譯成A，step2中可以利用S對L進行編譯并在A機器上執行。我們所希望的是L以A的機器語言在A機器上運行，由step1可將S轉換成A機器代碼，所以L語言就可以用A的機器代碼在A的機器上運行（是不是很繞？你如果第一次學那肯定是一臉懵的）我們用圖說話：
??寫完以上過程，我有個疑問：為什么需要s是L的子集？上網找到一種說法發現可以接受，也更為貼切于自展的名字。（下圖中的L1就是L的子集，從子集出發才能夠慢慢擴展為L）
（節選于博客：https://blog.csdn.net/NameOfBlog/article/details/82857644link
??編譯程序的移植：
??什么叫編譯程序的移植呢？就是在A機器上已有的高級語言L編寫一個在B機器上運行的高級語言L的編譯程序。（簡單來說就是L目前已經能使用A機器語言在機器A上運行，想要L能使用B機器語言在機器B上運行）T形圖如下:
??過程簡記為一次編程兩次編譯
???一次編程：使用L語言編寫能夠讓L語言產生B機器代碼的編譯程序R
???第一次編譯：把R在A機器代碼下編譯使其變為A機器代碼的語言，記為編譯程序I，作用是把L編譯成B
???第二次編譯：用編譯程序I對R進行編譯，成功完成L使用B機器語言完成的匯編程序在機器B上運行。
???就單單這三段話就能讓人找不著北!!!我們還是看圖說話：
??文字配圖，事半功倍：
??第一次編程，我們用L語言實現了編譯程序R。注意R的本質是L語言，只不過功能是把L翻譯成B。既然是L語言，通過已知L->A，我們可以把L語言變成A語言。這里的變成只是實現方式的改變，并沒有改變原有的功能，還是一次編程的圖，作用還是變成B語言，區別在于原來是用L語言實現的，現在用了A語言。也可以這樣理解：
??原來是L1-(L2)->B,又因為L2-(A)->A1。于是L1-(A1)->B。由一次編程知L通過R可變成B，現在只要R變成B就可以了。R的本質是L，第一次編譯實現了L變成B，利用第一次的編譯程序就可以把L變成B。這樣R就變成了B就實現L-(B)->B。
??剛學了緒論，對于編譯原理的各個部分了解還過于粗淺。用了將近5000字才完成這篇文章。隨著后面的學習，會更深層次的剖析每一個部分的。繼續加油哈！
??致謝：感謝編譯原理課程謝老師對文章的耐心修改，同樣感謝網上各位博主的優秀博文，為我不懂的地方提供解決辦法。
因作者水平有限，如有錯誤之處，請在下方評論區指正，謝謝！
總結
- 上一篇： 排序算法：快速排序算法实现及分析（递归形
- 下一篇： 初识ROS