⑴ 編譯原理四元式
四元式的一般形式為(op, arg1, arg2, result)，其中：op為一個二元（也可以是零元或一元）運算符。arg1和arg2為兩個運算對象，可以是變數、常數或者系統定義的臨時變數名。result為運算結果。
第一步:T1=a*b，
第二步:T2=c*d，
第三步:T3=T2/e，
第四步:T4=T1-T3，
第五步：f=T4.
⑵ 什麼是*＝>星推導(編譯原理) 星推導和加推導的區別
在編譯原理中，產生式的推導可以細分為 *=> "星推導"和 +=> "加推導"，
那麼這兩個分別是什麼意思呢？
其實，'*' 和 '+' 這兩個符號是來自 正則表達式 的，正則表達式是什麼大家可以先不了解，弄懂這個問題暫時只需要知道 '*' 和 '+' 這兩個符號的意思就可以了。
符號 * ：[1, n) 1到多
符號 + ：[0, n) 0到多
則， *=> "星推導" 為對產生式進行1到多次推導； +=> "加推導" 為對產生式進行0到多次推導。
【舉例】
（1）v +＝> w：意為產生式左端的 v 經過1到多次推導後能得到右端的 w
（2）v * => w： 意為產生式左端的 v 經過0到多次推導後能得到右端的w(其實，
就是比第（1）條多了一種情況，即 v= w，當 v= w 時，v不需要推導即可得到w，所以推導的次數為0)
⑶ 關於編譯原理first follow 和select
首先要明白這三個集的作用和用途，知道了他們是用來做什麼的之後，理解起來就簡單一些
First（A）集的作用是標示在替換非終結符A的時候，替換後的文法的首字母集合，語法分析程序根據這個來判斷給定的語言是否是合法的，是符合規則的。
Follow（A）的作用是標示那些可以出現在A之後的字元，語法分析程序根據這個，在A可以被替換為e（空）的時候來進行判斷，看當前的文法是否是合法的。
這里簡單說明下，比如A->b,A->e(空) 當給定的語言是 bXXXXX的時候，根據第一句文法就可以判定句子合法，但是如果給的語言是cXXXXX的時候，因為A->可以替換為空，這時候就需要一句A的follow集來進行判斷，若A的follow集裡面含有c 則語言是合法的
Select集的作用是將first集和follow集進行合並，如果兩個文法的左端都是A，若他們的select集交集為空，表明他們是兩個無關的，不會產生不確定性的文法，反之，則表明文法不是LL(1)文法
計算的公式很繁雜，理解了意思之後，看就能看出來。。。。
⑷ 什麼是文法(編譯原理)
【定義】
文法G定義為四元組（VN，VT，P，S）
其中 VN ：非終結符號(即語法變數)集
VT ： 終結符號集
VN∩VT =Φ，令V= VN∪VT，V稱為文法G的字母表或字匯表。
P ：產生式(α→β)集
S ：開始符號，且S∈VN ，S至少要在一條規則的左部出現。
【約定】
一般地，文法G的 四元組 不用全部給出 ，而只將產生式寫出。
約定：
（1）第一條產生式的左部是開始符號
（2）用尖括弧括起來的（或 大寫字母 ）是非終結符號
（3）不用尖括弧括起來（或 小寫字母 ）是終結符號
（4）還有一種習慣寫法，即 G[S] ，其中 S 是 開始符號 。
【舉例】
例: G=（VN，VT，P，S）
其中 VN={S}，
VT ={0，1}，
P={S→0S1，S→01}
S是開始符號
⑸ 編譯原理有有符號un-1.u=un嗎
編譯程序把源程序翻譯為目標程序。根據源程序的語言種類，翻譯程序可以分為匯編程序與編譯程序。與之相對，解釋程序是對源程序進行解釋執行的程序。相應的可以將高級語言分為
編譯型 C/C++, Swift, etc.
解釋型 Python, javascript, etc.
混合型 Java, etc.
本文重點放在編譯程序的設計上。典型的編譯程序具有 7 77 個邏輯部分
對源程序掃描一次被稱為一遍 (pass)。典型的一遍掃描編譯程序有如下形式
通常將中間代碼生成前的分析部分稱為編譯器的前端，其後的綜合部分則被稱為後端。這樣就把一個編譯程序分為了與源語言相關和與目標機有關的兩個獨立的部分，降低了程序的耦合。假設 llvm 編譯器 支持 M MM 種源語言到 N NN 種目標語言的編譯
傳統的編譯器如 gcc 可能需要開發 M × N M \times NM×N 個不同的子模塊。而 llvm 使用統一的中間語言 llvm Intermediate Representation 只需要 M MM 個前端與 N NN 個後端，大大降低了開發成本。
文法
設非空有窮集合 Σ \SigmaΣ 為一字母表，則其上的符號串為 ∀ s ∈ Σ ∗ \forall s \in \Sigma^*∀s∈Σ
∗
，其中 ∗ *∗ 表示集合的閉包。特別的記 Σ 0 = ε \Sigma^0 = {\varepsilon}Σ
0
=ε 為空串組成的集合。規則通常寫作
U : : = x or U → x , ∣ U ∣ = 1 , ∣ x ∣ ≥ 0 U ::= x\text{ or }U\rightarrow x,\quad |U| = 1, |x| \ge 0U::=x or U→x,∣U∣=1,∣x∣≥0
其中左部 U UU 是符號，右部 x xx 是有窮符號串。規則的集合 P PP 即可確定一個文法 G GG
<程序> ::= <常量說明><變數說明><函數說明>
<常量說明> ::= {const<常量定義>;}
<常量定義> ::= int<標識符>=<整數>{,<標識符>=<整數>}|char<標識符>=<字元>{,<標識符>=<字元>}
<變數說明> ::= {<類型標識符><變數定義>;}
<變數定義> ::= <標識符>[<下標>]{,<標識符>[<下標>]}
<下標> ::= '['<無符號整數>']' // <無符號整數>表示數組元素的個數，其值需大於0
<函數說明> ::= {(<類型標識符>|void)<函數定義>}void<主函數>
<函數定義> ::= <標識符>'('<參數表>')'<復合語句>
<參數表> ::= [<類型標識符><標識符>{,<類型標識符><標識符>}]
<主函數> ::= main'('')'<復合語句>
<復合語句> ::= '{'<常量說明><變數說明>{<語句>}'}'
<語句> ::= <條件語句>|'{'{<語句>}'}'|<函數調用語句>;|<賦值語句>;|<讀語句>;|<寫語句>;|<返回語句>;|;
<條件語句> ::= <if語句>|<while語句>|<do語句>|<for語句>
<if語句> ::= if'('<條件>')'<語句>[else<語句>]
<while語句> ::= while'('<條件>')'<語句>
<do語句> ::= do<語句>while'('<條件>')'
<for語句> ::= for'('<標識符>=<表達式>;<條件>;<標識符>=<標識符><加法運算符><無符號整數>')'<語句>
<條件> ::= <表達式>[<關系運算符><表達式>] // 表達式為0條件為假，否則為真
<函數調用語句> ::= <標識符>'('[<表達式>{,<表達式>}]')'
<賦值語句> ::= <標識符>['['<表達式>']']=<表達式>
<讀語句> ::= scanf'('<標識符>{,<標識符>}')'
<寫語句> ::= printf'('<字元串>[,<表達式>]')'|printf'('<表達式>')'
<返回語句> ::= return['('<表達式>')']
<表達式> ::= [<加法運算符>]<項>{<加法運算符><項>} // [+|-]只作用於第一個<項>
<項> ::= <因子>{<乘法運算符><因子>}
<因子> ::= <標識符>['['<表達式>']']|'('<表達式>')'|<整數>|<字元>|<函數調用語句>
<整數> ::= [<加法運算符>]<無符號整數>
<標識符> ::= <字母>{<字母>|<數字>}
<無符號整數> ::= <非零數字>{<數字>}|0
<數字> ::= 0|<非零數字>
<非零數字> ::= 1|...|9
<字元> ::= '<加法運算符>'|'<乘法運算符>'|'<字母>'|'<數字>'
<字元串> ::= "{十進制編碼為32,33,35-126的ASCII字元}"
<類型標識符> ::= int|char
<加法運算符> ::= +|-
<乘法運算符> ::= *|/
<關系運算符> ::= <|<=|>|>=|!=|==
<字母> ::= _|a|...|z|A|...|Z
復制
上述文法使用擴充的 BNF 表示法進行描述
符號 定義 說明
∣ \vert∣ 或 作用域由括弧限定
{ t } n m \{t\}^m_n{t}
n
m
將 t tt 重復連接 n ∼ m n \sim mn∼m 次 預設時 m = ∞ , n = 0 m = \infin,\ n = 0m=∞, n=0
[ t ] [t][t] 符號串 t tt 可有可無 等價於 { t } 1 \{t\}^1{t}
1
( t ) (t)(t) 局部作用域 主要用於限定 ∣ \vert∣ 范圍
相關概念有
概念 符號 定義 示例
識別符號 Z ZZ 文法中第一條規則的左部符號 <程序>
字匯表 V VV 文法中出現的全部符號 { <程序>, <常量說明>, …, 0, 1, … }
非終結符號集 V n V_nV
n
全部規則的左部組成的集合 { <程序>, <常量說明>, <變數說明>, … }
終結符號集 V t V_tV
t
V − V n V - V_nV−V
n
{ 0, 1, …, _, a, b, … }
設 U : : = u ∈ P U ::= u \in PU::=u∈P 則對於 ∀ x , y ∈ V ∗ \forall x, y \in V^*∀x,y∈V
∗
有直接推導 x U y ⇒ x u y xUy \Rightarrow xuyxUy⇒xuy 。如果 y ∈ V t ∗ y \in V_t^*y∈V
t
∗
則 x U y ⤃ x u y xUy\ ⤃\ xuyxUy ⤃ xuy 稱為規范推導。直接推導序列 u 0 ⇒ u 1 ⇒ ⋯ ⇒ u n u_0 \Rightarrow u_1 \Rightarrow \cdots \Rightarrow u_nu
0
⇒u
1
⇒⋯⇒u
n
可簡記為
{ u 0 ⇒ + u n n > 0 u 0 ⇒ ∗ u n n ≥ 0 \begin{cases} u_0 \mathop\Rightarrow\limits^+ u_n & n > 0\\ u_0 \mathop\Rightarrow\limits^* u_n & n \ge 0\\ \end{cases}{
u
0
⇒
+
u
n
u
0
⇒
∗
u
n
n
>
0
n
≥
0
進一步定義
句型 V ∗ ∋ x ⇐ ∗ Z V^* \ni x \mathop\Leftarrow\limits^* ZV
∗
∋x
⇐
∗
Z
句子 V t ∗ ∋ x ⇐ + Z V_t^* \ni x \mathop\Leftarrow\limits^+ ZV
t
∗
∋x
⇐
+
Z
語言 L ( G ) = { x ∣ x is sentence } L(G) = \{ x| x\text{ is sentence} \}L(G)={x∣x is sentence}
如果文法 G GG 和 G ′ G'G
′
有 L ( G ) = L ( G ′ ) L(G) = L(G')L(G)=L(G
′
) ，則稱這兩個文法等價。設 w = x u y w=xuyw=xuy 為一句型，稱 u uu 為一個相對於 U ∈ V n U \in V_nU∈V
n
的
w ww 的短語 如果 Z ⇒ ∗ x U y ∧ U ⇒ + u Z \mathop\Rightarrow\limits^* xUy \land U \mathop\Rightarrow\limits^+ uZ
⇒
∗
xUy∧U
⇒
+
u
w ww 的簡單短語 如果 u uu 是短語且 U ⇒ u U \mathop\Rightarrow\limits uU⇒u
句型的最左簡單短語稱為句柄。
二義性
文法 G GG 是二義性的，如果 ∃ x ∈ L ( G ) \exist x \in L(G)∃x∈L(G) 使下列條件之一成立
x xx 可以對應兩顆不同的語法樹
x xx 有兩個不同的規范推導
⑹ 編譯原理
C語言編譯過程詳解
C語言的編譯鏈接過程是要把我們編寫的一個C程序(源代碼)轉換成可以在硬體上運行的程序(可執行代碼)，需要進行編譯和鏈接。編譯就是把文本形式源代碼翻譯為機器語言形式的目標文件的過程。鏈接是把目標文件、操作系統的啟動代碼和用到的庫文件進行組織形成最終生成可執行代碼的過程。過程圖解如下：
從圖上可以看到，整個代碼的編譯過程分為編譯和鏈接兩個過程，編譯對應圖中的大括弧括起的部分，其餘則為鏈接過程。
一、編譯過程
編譯過程又可以分成兩個階段：編譯和匯編。
1、編譯
編譯是讀取源程序(字元流)，對之進行詞法和語法的分析，將高級語言指令轉換為功能等效的匯編代碼，源文件的編譯過程包含兩個主要階段：
第一個階段是預處理階段，在正式的編譯階段之前進行。預處理階段將根據已放置在文件中的預處理指令來修改源文件的內容。如#include指令就是一個預處理指令，它把頭文件的內容添加到.cpp文件中。這個在編譯之前修改源文件的方式提供了很大的靈活性，以適應不同的計算機和操作系統環境的限制。一個環境需要的代碼跟另一個環境所需的代碼可能有所不同，因為可用的硬體或操作系統是不同的。在許多情況下，可以把用於不同環境的代碼放在同一個文件中，再在預處理階段修改代碼，使之適應當前的環境。
主要是以下幾方面的處理：
(1)宏定義指令，如 #define a b。
對於這種偽指令，預編譯所要做的是將程序中的所有a用b替換，但作為字元串常量的 a則不被替換。還有 #undef，則將取消對某個宏的定義，使以後該串的出現不再被替換。
(2)條件編譯指令，如#ifdef，#ifndef，#else，#elif，#endif等。
這些偽指令的引入使得程序員可以通過定義不同的宏來決定編譯程序對哪些代碼進行處理。預編譯程序將根據有關的文件，將那些不必要的代碼過濾掉
(3) 頭文件包含指令，如#include "FileName"或者#include <FileName>等。
在頭文件中一般用偽指令#define定義了大量的宏(最常見的是字元常量)，同時包含有各種外部符號的聲明。採用頭文件的目的主要是為了使某些定義可以供多個不同的C源程序使用。因為在需要用到這些定義的C源程序中，只需加上一條#include語句即可，而不必再在此文件中將這些定義重復一遍。預編譯程序將把頭文件中的定義統統都加入到它所產生的輸出文件中，以供編譯程序對之進行處理。包含到C源程序中的頭文件可以是系統提供的，這些頭文件一般被放在/usr/include目錄下。在程序中#include它們要使用尖括弧(<>)。另外開發人員也可以定義自己的頭文件，這些文件一般與C源程序放在同一目錄下，此時在#include中要用雙引號("")。
(4)特殊符號，預編譯程序可以識別一些特殊的符號。
例如在源程序中出現的LINE標識將被解釋為當前行號(十進制數)，FILE則被解釋為當前被編譯的C源程序的名稱。預編譯程序對於在源程序中出現的這些串將用合適的值進行替換。
預編譯程序所完成的基本上是對源程序的「替代」工作。經過此種替代，生成一個沒有宏定義、沒有條件編譯指令、沒有特殊符號的輸出文件。這個文件的含義同沒有經過預處理的源文件是相同的，但內容有所不同。下一步，此輸出文件將作為編譯程序的輸出而被翻譯成為機器指令。
第二個階段編譯、優化階段。經過預編譯得到的輸出文件中，只有常量；如數字、字元串、變數的定義，以及C語言的關鍵字，如main,if,else,for,while,{,}, +,-,*,\等等。
編譯程序所要作得工作就是通過詞法分析和語法分析，在確認所有的指令都符合語法規則之後，將其翻譯成等價的中間代碼表示或匯編代碼。
優化處理是編譯系統中一項比較艱深的技術。它涉及到的問題不僅同編譯技術本身有關，而且同機器的硬體環境也有很大的關系。優化一部分是對中間代碼的優化。這種優化不依賴於具體的計算機。另一種優化則主要針對目標代碼的生成而進行的。
對於前一種優化，主要的工作是刪除公共表達式、循環優化(代碼外提、強度削弱、變換循環控制條件、已知量的合並等)、復寫傳播，以及無用賦值的刪除，等等。
後一種類型的優化同機器的硬體結構密切相關，最主要的是考慮是如何充分利用機器的各個硬體寄存器存放的有關變數的值，以減少對於內存的訪問次數。另外，如何根據機器硬體執行指令的特點(如流水線、RISC、CISC、VLIW等)而對指令進行一些調整使目標代碼比較短，執行的效率比較高，也是一個重要的研究課題。
2、匯編
匯編實際上指把匯編語言代碼翻譯成目標機器指令的過程。對於被翻譯系統處理的每一個C語言源程序，都將最終經過這一處理而得到相應的目標文件。目標文件中所存放的也就是與源程序等效的目標的機器語言代碼。目標文件由段組成。通常一個目標文件中至少有兩個段：
代碼段：該段中所包含的主要是程序的指令。該段一般是可讀和可執行的，但一般卻不可寫。
數據段：主要存放程序中要用到的各種全局變數或靜態的數據。一般數據段都是可讀，可寫，可執行的。
UNIX環境下主要有三種類型的目標文件：
(1)可重定位文件
其中包含有適合於其它目標文件鏈接來創建一個可執行的或者共享的目標文件的代碼和數據。
(2)共享的目標文件
這種文件存放了適合於在兩種上下文里鏈接的代碼和數據。
第一種是鏈接程序可把它與其它可重定位文件及共享的目標文件一起處理來創建另一個 目標文件；
第二種是動態鏈接程序將它與另一個可執行文件及其它的共享目標文件結合到一起，創建一個進程映象。
(3)可執行文件
它包含了一個可以被操作系統創建一個進程來執行之的文件。匯編程序生成的實際上是第一種類型的目標文件。對於後兩種還需要其他的一些處理方能得到，這個就是鏈接程序的工作了。
二、鏈接過程
由匯編程序生成的目標文件並不能立即就被執行，其中可能還有許多沒有解決的問題。
例如，某個源文件中的函數可能引用了另一個源文件中定義的某個符號(如變數或者函數調用等)；在程序中可能調用了某個庫文件中的函數，等等。所有的這些問題，都需要經鏈接程序的處理方能得以解決。
鏈接程序的主要工作就是將有關的目標文件彼此相連接，也即將在一個文件中引用的符號同該符號在另外一個文件中的定義連接起來，使得所有的這些目標文件成為一個能夠被操作系統裝入執行的統一整體。
根據開發人員指定的同庫函數的鏈接方式的不同，鏈接處理可分為兩種：
(1)靜態鏈接
在這種鏈接方式下，函數的代碼將從其所在地靜態鏈接庫中被拷貝到最終的可執行程序中。這樣該程序在被執行時這些代碼將被裝入到該進程的虛擬地址空間中。靜態鏈接庫實際上是一個目標文件的集合，其中的每個文件含有庫中的一個或者一組相關函數的代碼。
(2) 動態鏈接
在此種方式下，函數的代碼被放到稱作是動態鏈接庫或共享對象的某個目標文件中。鏈接程序此時所作的只是在最終的可執行程序中記錄下共享對象的名字以及其它少量的登記信息。在此可執行文件被執行時，動態鏈接庫的全部內容將被映射到運行時相應進程的虛地址空間。動態鏈接程序將根據可執行程序中記錄的信息找到相應的函數代碼。
對於可執行文件中的函數調用，可分別採用動態鏈接或靜態鏈接的方法。使用動態鏈接能夠使最終的可執行文件比較短小，並且當共享對象被多個進程使用時能節約一些內存，因為在內存中只需要保存一份此共享對象的代碼。但並不是使用動態鏈接就一定比使用靜態鏈接要優越。在某些情況下動態鏈接可能帶來一些性能上損害。
我們在linux使用的gcc編譯器便是把以上的幾個過程進行捆綁，使用戶只使用一次命令就把編譯工作完成，這的確方便了編譯工作，但對於初學者了解編譯過程就很不利了，下圖便是gcc代理的編譯過程：
從上圖可以看到：
預編譯
將.c 文件轉化成 .i文件
使用的gcc命令是：gcc –E
對應於預處理命令cpp
編譯
將.c/.h文件轉換成.s文件
使用的gcc命令是：gcc –S
對應於編譯命令 cc –S
匯編
將.s 文件轉化成 .o文件
使用的gcc 命令是：gcc –c
對應於匯編命令是 as
鏈接
將.o文件轉化成可執行程序
使用的gcc 命令是： gcc
對應於鏈接命令是 ld
總結起來編譯過程就上面的四個過程：預編譯、編譯、匯編、鏈接。了解這四個過程中所做的工作，對我們理解頭文件、庫等的工作過程是有幫助的，而且清楚的了解編譯鏈接過程還對我們在編程時定位錯誤，以及編程時盡量調動編譯器的檢測錯誤會有很大的幫助的。