編譯原理句型語法樹怎麼畫

『壹』 簡述利用推導構造語法樹的過程

語法樹，是針對上下文無關文法，用來表示一個句型的生成過程的一種描述手段。
對於給定的句型，依據文法構造它的語法樹，是語法分析的任務。
編譯原理課程中重點學習的各種語法分析方法，都是解決語法樹的構造的具體分析方法。
在學習並掌握各種語法分析方法之前，一般只能依據直覺印象，通過猜測、拼湊等手段，去試著推演，湊出符合要求的句型的語法樹。所以這個階段練慣用的題目一般也不很復雜，通過多多練習也能找到一些技巧（其實主要是後面將要學習的自頂向下語法分析中的一些原則）。
對於給定的文法，有一些句型可能能構建出兩棵甚至多棵結構不同的語法樹，結果不一定是唯一的。這樣的文法就是所謂的二義性文法。
對於非二義性文法而言，任意一個句型的語法樹都是唯一的。

『貳』 正在學習編譯原理，語法圖應該用什麼軟體畫會比較簡單一點

一般用YACC畫，不過建議用GOLD PARSER。畫起來最快，不要編程。
步驟：
1）寫出正確的文法。
2）在測試窗口中輸入要分析的字元串。

『叄』 編譯原理：小題如下，求學霸幫忙

短語：1a,2Sb,3ba,4baSb
句柄：a
直接短語：a,Sb
語配大法樹推導：
S=>AB
=>bBB
=>baB
=>baSb
語法樹貌似在培友豎告嘩這里粘貼不上。

『肆』 編譯原理 題目

習題一、單項選擇題
1、將編譯程序分成若干個「遍」是為了 。
a．提高程序的執行效率
b．使程序的結構更加清晰
c．利用有限的機器內存並提高機器的執行效率
d．利用有限的機器內存但降低了機器的執行效率
2、構造編譯程序應掌握 。
a．源程序 b．目標語言
c．編譯方法 d．以上三項都是
3、變數應當 。
a．持有左值 b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、編譯程序絕大多數時間花在 上。
a．出錯處理 b．詞法分析
c．目標代碼生成 d．管理表格
5、 不可能是目標代碼。
a．匯編指令代碼 b．可重定位指令代碼
c．絕對指令代碼 d．中間代碼
6、使用 可以定義一個程序的意義。
a．語義規則 b．詞法規則
c．產生規則 d．詞法規則
7、詞法分析器的輸入是 。
a．單詞符號串 b．源程序
c．語法單位 d．目標程序
8、中間代碼生成時所遵循的是- 。
a．語法規則 b．詞法規則
c．語義規則 d．等價變換規則
9、編譯程序是對 。
a．匯編程序的翻譯 b．高級語言程序的解釋執行
c．機器語言的執行 d．高級語言的翻譯
10、語法分析應遵循 。
a．語義規則 b．語法規則
c．構詞規則 d．等價變換規則
解答
1、將編譯程序分成若干個「遍」是為了使編譯程序的結構更加清晰，故選b。
2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。
3、對編譯而言，變數既持有左值又持有右值，故選c。
4、編譯程序打交道最多的就是各種表格，因此選d。
5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選d。
6、詞法分析遵循的是構詞規則，語法分析遵循的是語法規則，中間代碼生成遵循的是語義規則，並且語義規則可以定義一個程序的意義。因此選a。
7、b 8、c 9、d 10、c
二、多項選擇題
1、編譯程序各階段的工作都涉及到 。
a．語法分析 b．表格管理 c．出錯處理
d．語義分析 e．詞法分析
2、編譯程序工作時，通常有 階段。
a．詞法分析 b．語法分析 c．中間代碼生成
d．語義檢查 e．目標代碼生成
解答
1．b、c 2. a、b、c、e
三、填空題
1、解釋程序和編譯程序的區別在於 。
2、編譯過程通常可分為5個階段，分別是 、語法分析 、代碼優化和目標代碼生成。 3、編譯程序工作過程中，第一段輸入是 ，最後階段的輸出為 程序。
4、編譯程序是指將 程序翻譯成 程序的程序。 解答
是否生成目標程序 2、詞法分析 中間代碼生成 3、源程序 目標代碼生成 4、源程序 目標語言
一、單項選擇題
1、文法G：S→xSx|y所識別的語言是 。
a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*
2、文法G描述的語言L(G)是指 。
a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}
c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(VT∪VN*)}
3、有限狀態自動機能識別 。
a. 上下文無關文法 b. 上下文有關文法
c.正規文法 d. 短語文法
4、設G為算符優先文法，G的任意終結符對a、b有以下關系成立 。
a. 若f(a)>g(b)，則a>b b.若f(a)<g(b)，則a<b
c. a~b都不一定成立 d. a~b一定成立
5、如果文法G是無二義的，則它的任何句子α 。
a. 最左推導和最右推導對應的語法樹必定相同
b. 最左推導和最右推導對應的語法樹可能不同
c. 最左推導和最右推導必定相同
d. 可能存在兩個不同的最左推導，但它們對應的語法樹相同
6、由文法的開始符經0步或多步推導產生的文法符號序列是 。
a. 短語 b.句柄 c. 句型 d. 句子
7、文法G：E→E+T|T
T→T*P|P
P→(E)|I
則句型P+T+i的句柄和最左素短語為 。
a.P+T和i b. P和P+T c. i和P+T+i d.P和T
8、設文法為：S→SA|A
A→a|b
則對句子aba，下面 是規范推導。
a. SÞSAÞSAAÞAAAÞaAAÞabAÞaba
b. SÞSAÞSAAÞAAAÞAAaÞAbaÞaba
c. SÞSAÞSAAÞSAaÞSbaÞAbaÞaba
d. SÞSAÞSaÞSAaÞSbaÞAbaÞaba
9、文法G：S→b|∧(T)
T→T,S|S
則FIRSTVT(T) 。
a. {b,∧,(} b. {b,∧,)} c.{b,∧,(,，} d.{b,∧,),，}
10、產生正規語言的文法為 。
a. 0型 b. 1型 c. 2型 d. 3型
11、採用自上而下分析，必須 。
a. 消除左遞歸 b. 消除右遞歸 c. 消除回溯 d. 提取公共左因子
12、在規范歸約中，用 來刻畫可歸約串。
a. 直接短語 b. 句柄 c. 最左素短語 d. 素短語
13、有文法G：E→E*T|T
T→T+i|i
句子1+2*8+6按該文法G歸約，其值為 。
a. 23 B. 42 c. 30 d. 17
14、規范歸約指 。
a. 最左推導的逆過程 b. 最右推導的逆過程
c. 規范推導 d. 最左歸約的逆過程
[解答]
1、選c。
2、選a。
3、選c。
4、雖然a與b沒有優先關系，但構造優先函數後，a與b就一定存在優先關系了。所以，由f(a)>g)(b)或f(a)<g(b)並不能判定原來的a與b之間是否存在優先關系：故選c。
5、如果文法G無二義性，則最左推導是先生長右邊的枝葉：對於d，如果有兩個不同的是了左推導，則必然有二義性。故選a。
6、選c。
7、由圖2-8-1的語法樹和優先關系可以看出應選b。

8、規范推導是最左推導，故選d。
9、由T→T,…和T→(… 得FIRSTVT(T))={(,，)}；
由T→S得FIRSTVT(S)⊂FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即
FIRSTVT(T)={b,∧,(,，}； 因此選c。
10、d 11、c 12、b 13、b 14、b
二、多項選擇題
1、下面哪些說法是錯誤的 。
a. 有向圖是一個狀態轉換圖 b. 狀態轉換圖是一個有向圖
c.有向圖是一個DFA d.DFA可以用狀態轉換圖表示
2、對無二義性文法來說，一棵語法樹往往代表了 。
a. 多種推導過程 b. 多種最左推導過程 c.一種最左推導過程
d.僅一種推導過程 e.一種最左推導過程
3、如果文法G存在一個句子，滿足下列條件 之一時，則稱該文法是二義文法。
a. 該句子的最左推導與最右推導相同
b. 該句子有兩個不同的最左推導
c. 該句子有兩棵不同的最右推導
d. 該句子有兩棵不同的語法樹
e.該句子的語法樹只有一個
4、有一文法G：S→AB
A→aAb|ε
B→cBd|ε
它不產生下面 集合。
a. {anbmcndm|n,m≥0} b. {anbncmdm|n,m>0}
c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0}
e. {anbncndn|n≥0}
5、自下而上的語法分析中，應從 開始分析。
a. 句型 b. 句子 c. 以單詞為單位的程序
d. 文法的開始符 e. 句柄
6、對正規文法描述的語言，以下 有能力描述它。
a.0型文法 b.1型文法 c.上下文無關文法 d.右線性文法 e.左線性文法
解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e
三、填空題
1、文法中的終結符和非終結符的交集是 。詞法分析器交給語法分析器的文法符號一定是 ，它一定只出現在產生式的 部。
2、最左推導是指每次都對句型中的 非終結符進行擴展。
3、在語法分析中，最常見的兩種方法一定是 分析法，另一是 分析法。
4、採用 語法分析時，必須消除文法的左遞歸。
5、 樹代表推導過程， 樹代表歸約過程。
6、自下而上分析法採用 、歸約、錯誤處理、 等四種操作。
7、Chomsky把文法分為 種類型，編譯器構造中採用 和 文法，它們分別產生 和 語言，並分別用 和 自動機識別所產生的語言。
解答 1、空集 終結符 右
2、最左
3、自上而上 自下而上
4、自上而上
5、語法 分析
6、移進 接受
7、4 2 型 3型 上下文無關語言 正規語言 下推自動機 有限
四、判斷題
1、文法 S→aS|bR|ε描述的語言是(a|bc)* ( )
R→cS
2、在自下而上的語法分析中，語法樹與分析樹一定相同。 （ ）
3、二義文法不是上下文無關文法。 （ ）
4、語法分析時必須先消除文法中的左遞歸。 （ ）
5、規范歸約和規范推導是互逆的兩個過程。 （ ）
6、一個文法所有句型的集合形成該文法所能接受的語言。 （ ）
解答 1、對 2、錯 3、錯 4、錯 5、錯 6、錯
五、簡答題
1、句柄 2、素短語 3、語法樹 4、歸約 5、推導
[解答]
1、句柄：一個句型的最左直接短語稱為該句型的句柄。
2、素短語：至少含有一個終結符的素短語，並且除它自身之外不再含任何更小的素短語。
3、語法樹：滿足下面4個條件的樹稱之為文法G[S]的一棵語法樹。
①每一終結均有一標記，此標記為VN∪VT中的一個符號；
②樹的根結點以文法G[S]的開始符S標記；
③若一結點至少有一個直接後繼，則此結點上的標記為VN中的一個符號；
④若一個以A為標記的結點有K個直接後繼，且按從左至右的順序，這些結點的標記分別為X1,X2,…,XK，則A→X1,X2,…,XK，必然是G的一個產生式。
4、歸約：我們稱αγβ直接歸約出αAβ，僅當A→γ 是一個產生式，且α、β∈(VN∪VT)*。歸約過程就是從輸入串開始，反復用產生式右部的符號替換成產生式左部符號，直至文法開始符。
5、推導：我們稱αAβ直接推出αγβ，即αAβÞαγβ，僅當A→ γ 是一個產生式，且α、β∈(VN∪VT)*。如果α1Þα2Þ…Þαn，則我們稱這個序列是從α1至α2的一個推導。若存在一個從α1αn的推導，則稱α1可推導出αn。推導是歸約的逆過程。
六、問答題
1、給出上下文無關文法的定義。
[解答]
一個上下文無關文法G是一個四元式（VT,VN,S, P），其中：
●VT是一個非空有限集，它的每個元素稱為終結符號；
●VN是一個非空有限集，它的每個元素稱為非終結符號，VT∩VN=Φ；
●S是一個非終結符號，稱為開始符號；
●P是一個產生式集合（有限），每個產生式的形式是P→α，其中，P∈VN，
α∈(VT∪VN)*。開始符號S至少必須在某個產生式的左部出現一次。
2、文法G[S]：
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
（1）它是Chomsky哪一型文法？
（2）它生成的語言是什麼？
[解答]
（1）由於產生式左部存在終結符號，且所有產生式左部符號的長度均小於等於產生式右部的符號長度，所以文法G[S]是Chomsky1型文法，即上下文有關文法。
（2）按產生式出現的順序規定優先順序由高到低（否則無法推出句子），我們可以得到：
SÞabQÞabc
SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbcc
SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞ
aaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc
……
於是得到文法G[S]生成的語言L={anbncn|n≥1}
3、按指定類型，給出語言的文法。
L={aibj|j＞i≥1}的上下文無關文法。
【解答】
（1）由L={aibj|j＞i≥1}知，所求該語言對應的上下文無關文法首先應有S→aSb型產生式，以保證b的個數不少於a的個數；其次，還需有S→Sb或S→bS型的產生式，用以保證b的個數多於a的個數；也即所求上下文無關文法G[S]為：
G[S]：S→aSb|Sb|b
4、有文法G：S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）寫出句子acabcbbdcc的最左推導過程。
【解答】（1）分別畫出對應兩句型的語法樹，如圖2-8-2所示
句柄:AaB Bd

圖2-8-2 語法樹
（2）句子acabcbbdcc的最左推導如下：
SÞaAcBÞaAaBcBÞacaBcBÞacabcBÞacabcbScAÞacabcbBdcA
ÞacabcbbdcAÞacabcbbdcc
5、對於文法G[S]：
S→（L）|aS|a L→L, S|S
（1）畫出句型（S,（a））的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。
【解答】
（1）句型（S,（a））的語法樹如圖2-8-3所示

（2）由圖2-8-3可知：
①短語：S、a、(a)、S,(a)、(S,(a))；
②直接短語：a、S；
③句柄：S；
④素短語：素短語可由圖2-8-3中相鄰終結符之間的優先關系求得，即；

因此素短語為a。
6、考慮文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i
證明T*P↑（T*F）是該文法的一個句型，並指出直接短語和句柄。
【解答】
首先構造T*P↑（T*F）的語法樹如圖2-8-4所示。

由圖2-8-4可知，T*P↑（T*F）是文法G[T]的一個句型。
直接短語有兩個，即P和T*F；句柄為P。

一、單項選擇題
1、詞法分析所依據的是 。
a. 語義規則 b. 構詞規則 c. 語法規則 d. 等價變換規則
2、詞法分析器的輸出結果是 。
a. 單詞的種別編碼 b. 單詞在符號表中的位置
c. 單詞的種別編碼和自身值 d. 單詞自身值
3、正規式M1和M2等價是指 。
a. M1和M2的狀態數相等 b. M1和M2的有向弧條數相等
c. M1和M2所識別的語言集相等 d. M1和M2狀態數和有向弧條數相等
4、狀態轉換圖（見圖3-6-1）接受的字集為 。

a. 以 0開頭的二進制數組成的集合 b. 以0結尾的二進制數組成的集合
c. 含奇數個0的二進制數組成的集合 d. 含偶數個0的二進制數組成的集合
5、詞法分析器作為獨立的階段使整個編譯程序結構更加簡潔、明確，因此， 。
a. 詞法分析器應作為獨立的一遍 b. 詞法分析器作為子程序較好
c. 詞法分析器分解為多個過程，由語法分析器選擇使用 d. 詞法分析器並不作為一個獨立的階段
解答 1、b 2、c 3、c 4、d 5、b
二、多項選擇題
1、在詞法分析中，能識別出 。
a. 基本字 b. 四元式 c. 運算符
d. 逆波蘭式 e. 常數
2、令∑={a,b}，則∑上所有以b開頭，後跟若干個ab的字的全體對應的正規式為 。
a. b(ab)* b. b(ab)+ c.(ba)*b
d. (ba)+b e. b(a|b)
解答 1、a、c、e 2、a、b、d
三、填空題
1、確定有限自動機DFA是 的一個特例。
2、若二個正規式所表示的 相同，則認為二者是等價的。
3、一個字集是正規的，當且僅當它可由 所 。
解答 1、NFA 2、正規集 3、DFA（NFA）所識別
四、判斷題
1、一個有限狀態自動機中，有且僅有一個唯一終態。 （ ）
2、設r和s分別是正規式，則有L（r|s）=L(r)|L(s)。 （ ）
3、自動機M和M′的狀態數不同，則二者必不等價。 （ ）
4、確定的自動機以及不確定的自動機都能正確地識別正規集。 （ ）
5、對任意一個右線性文法G，都存在一個NFA M，滿足L(G)=L(M)。 （ ）
6、對任意一個右線性文法G，都存在一個DFA M，滿足L(G)=L(M)。 （ ）
7、對任何正規表達式e，都存在一個NFA M，滿足L(G)=L(e)。 （ ）
8、對任何正規表達式e，都存在一個DFA M，滿足L(G)=L(e)。 （ ）
解答 1 、2、3、錯 4、5、6、7、8、正確
五、基本題
1、設M＝（{x,y}, {a,b}, f,x,{y}）為一非確定的有限自動機，其中f定義如下：
f（x,a）＝{x,y} f（x,b）＝{y}
f（y,a）＝φ f（y,b）＝{x,y}
試構造相應的確定有限自動機M′。
解答：對照自動機的定義M=(S,Σ,f,S0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數，所以是一非確定有限自動機，先畫出NFA M相應的狀態圖，如圖3-6-2所示。

用子集法構造狀態轉換矩陣表3-6-3所示。
I Ia Ib
{x} {x,y} {y}
{y} — {x,y}
{x,y} {x,y} {x,y}
將轉換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態轉換矩陣。
表3-6-4 狀態轉換矩陣
a b
0 2 1
1 — 2
2 2 2
即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其狀態轉換圖如圖3-6-5所示。

將圖3-6-5的DFA M′最小化。首先，將M′的狀態分成終態組{1，2}與非終態組{0}；其次，考察{1,2}。由於{1,2}a={1,2}b={2}⊂{1,2}，所以不再將其劃分了，也即整個劃分只有兩組{0}，{1,2}：令狀態1代表{1,2}，即把原來到達2的弧都導向1，並刪除狀態2。最後，得到如圖3-6-6所示化簡DFA M′。

2、對給定正規式b*（d|ad）（b|ab）+，構造其NFA M；
解答：首先用A+=AA*改造正規式得：b*(d|ad)(b|ab)(b|ab)*；其次，構造該正規式的NFA M，如圖3-6-7所示。
求採納為滿意回答。
希望能解決您的問題。

『伍』 編譯原理

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
總結起來編譯過程就上面的四個過程：預編譯、編譯、匯編、鏈接。了解這四個過程中所做的工作，對我們理解頭文件、庫等的工作過程是有幫助的，而且清楚的了解編譯鏈接過程還對我們在編程時定位錯誤，以及編程時盡量調動編譯器的檢測錯誤會有很大的幫助的。

『陸』 編譯原理LR分析法中的SLR(1)分析表和LR分析過程、語法樹怎麼求

第二題和第三題拿去，剛做的：

由B->cAa|c就可知該文法不是LR(0)文法了

『柒』 如何求語法分析樹

如果給出短語等名詞的形式化的定義，便較難理解，不好求。我們通過構造語法樹來求解。首先你應該會根據文法將所給句型構造成語法樹的形式，即根據文法怎樣推導出句型E+T*F。如果你有數據結構二叉樹基礎的話這很簡單就構造出來了。構造出語法樹後，求短語看根節點，有T，和E。則短語為：E+T*F,T*F，而直接短語模枝是指能旦銀敏直接搏腔推出葉子節點的根所對應的短語，可知該節點為T，直接短語為：T*F。句柄是最左直接短語，可知為：T*F。

『捌』 編譯原理問題，高手進。

回答下列問題：(30分)
(6分)對於下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若參數傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請寫出程序執行的輸出結果。
答： (1) 3 (2) 16 (3) 16 (每個值2分)

(6分)計算文法G(M)的每個非終結符的FIRST和FOLLOW集合，並判斷該文法是否是LL(1)的，請說明理由。
G(M)：
M → TB
T → Ba |
B → Db | eT |
D → d |

解答：
計算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， }
FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#}
FOLLOW (B) = {a，# } FOLLOW (D) = { b}

檢查文法的所有產生式，我們可以得到：
1. 該文法不含左遞歸，
2. 該文法中每一個非終結符M，T，B，D的各個產生式的候選首符集兩兩不相交。
3. 該文法的非終結符T、B和D，它們都有候選式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以該文法不是LL(1)文法。(2分)

(4分)考慮下面的屬性文法
產 生 式 語 義 規 則
S→ABC

A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
畫出字元串abc的語法樹;
對於該語法樹，假設S.u的初始值為5，屬性計算完成後，S.v的值為多少。
答：(1) (2分)

(2) S.v的值為18 (2分)

(4分)運行時的DISPLAY表的內容是什麼？它的作用是什麼？
答：DISPLAY表是嵌套層次顯示表。每當進入一個過程後，在建立它的活動記錄區的同時建立一張嵌套層次顯示表diaplay.假定現在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現行層、直接外層、…、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變數。

(5分)對下列四元式序列生成目標代碼：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本塊出口之後是活躍變數， R0和R1是可用寄存器。
答: 目標代碼序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H

(5分)寫出表達式a+b*(c-d)對應的逆波蘭式、三元式序列和抽象語法樹。
答：
逆波蘭式：(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象語法樹：(2分)

(8分)構造一個DFA，它接受={a，b}上所有包含ab的字元串。
答：
(2分)構造相應的正規式：(a|b)*ab(a|b)*

(3分)
a a

a b
b b

(3分)確定化：
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a

a b b
b

最小化：
{0，1，2} {3，4，5}
{0， 2}，1， {3，4，5}

(6分)寫一個文法使其語言為L(G)={anbncm| m,n≥1，n為奇數，m為偶數}。
答：
文法G(S):

(8分)對於文法G(S):

1. 寫出句型b(Ma)b的最右推導並畫出語法樹。
2. 寫出上述句型的短語，直接短語和句柄。
答：
1. (4分)

2. (4分)
短語: Ma)， (Ma)， b(Ma)b
直接短語: Ma)
句柄: Ma)

(12分)對文法G(S)：
S → a | ^ | (T)
T → T，S | S
(1) 構造各非終結符的FIRSTVT和LASTVT集合;
(2) 構造算符優先表;
(3) 是算符優先文法嗎?
(4) 構造優先函數。
答：
(1) (4分)

(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >

(3) 是算符優先文法，因為任何兩個終結符之間至多隻有一種優先關系。 (1分)

(4) 優先函數(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3

(8分)設某語言的do-while語句的語法形式為
S do S(1) While E
其語義解釋為：

針對自下而上的語法分析器，按如下要求構造該語句的翻譯模式，將該語句翻譯成四元式：
(1) 寫出適合語法制導翻譯的產生式；
(2) 寫出每個產生式對應的語義動作。
答：(1). 適合語法制導翻譯的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }

UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }

SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }

答案二：
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}

(10分)將語句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻譯成四元式。
答：
100 (j>， C， 0， 102)
101 (j， -， -， 112)
102 (jnz， A， -， 106)
103 (j， -， -， 104)
104 (j=， B， 0， 106)
105 (j， -， -， 109)
106 (+， C， D， T1)
107 (:=， T1， -， C)
108 (j， -， -， 100)
109 (*， C， D， T2)
110 (:=， T2， -， C)
111 (j， -， -， 100)
112

(10分)設有基本塊如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
畫出DAG圖；
設L，M，N 是出基本塊後的活躍變數，請給出優化後的四元式序列。
答：

1. (6分)
L

*
T2,M T4 T2,N

* - +

T1 T3
3 A B 12 C D

2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D

(8分)文法G(S)及其LR分析表如下，請給出串baba#的分析過程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答：
步驟 狀態 符號 輸入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈，估計認識！！

『玖』 編譯原理有關語法的題

短語：E+F*（E+i），F*(E+i),(E+i),E+i,i

直接短語：i（能直接推出來的）

句柄：i（最左直接短語）

素短語：i（並且至少含有一個終結符並除自身之外不含任何更小的素短語)

這些你根據語法樹看，就比較好找了啊~

語法樹如圖：

『拾』 語法樹是在編譯過程什麼階段完成後形成的

語法樹是在編譯過程（語法分析）階段完成後形成的。

注意每個節點都有一個語法符號，根節點是開始符，每個節點的子節點從左到右連在一起都是符合某一個語法規則，滿足這樣的條件即為語法樹。

語法樹反映出推導過程，每一步節點的生長過程都可以對應到一步推導。語法樹反映出串的語法結構。

畫出語法樹，從起始符開始，觀察語法樹如何生長（即當前樹的向下生長使用哪條規則），然後畫出語法樹，如果最後所有葉子節點從左到右和給的串一致，則當前串是句型。每一棵子樹的葉子節點對應的都是短語，單層的就是簡單短語，最左層的就是句柄。

語法樹的作用：

在處理源程序的時候，通常要把源程序變換成一種便於處理的中間表示形式，然後再對其中間表示進行處理。

一般中間表示形式都是用一種類似於語法樹的形式來做的，因為實際用的時候可能加上一些變形，比方說加上節點的類型，刪去沒用的節點。

比如表示一個循環語句實際上需要的就是兩部分信息，一個是條件一個是循環體。所以在實際的應用中都是用一種所謂的類似於語法樹的結構然後再進行處理的。在需求工程中，面向特徵的需求分析技術也是構建了特徵樹模型，然後才進行一系列的分析工作的。

對需求的修改就反映在對樹的修改上，然後分析起來就明確了很多。所以說語法樹和語法樹的變形在實際的處理中起到重要的作用。