編譯過程 詞法分析：對源程式從前到後（從左至右）逐個字元地掃描，從而識別出一個個"單詞"符號。 語法分析：判斷語法是否出錯，如表達式、迴圈語句、程式等。 語義分析：檢查如賦值語句左右是否匹配，是否有零除數等。 文法 G={Vt*Vn*S*P} Vt是一個非空有限的符號集合，它的每個元素稱為終結符。 ... ...
編譯過程
詞法分析：對源程式從前到後（從左至右）逐個字元地掃描，從而識別出一個個"單詞"符號。
語法分析：判斷語法是否出錯，如表達式、迴圈語句、程式等。
語義分析：檢查如賦值語句左右是否匹配，是否有零除數等。
文法
G={Vt*Vn*S*P}
Vt是一個非空有限的符號集合，它的每個元素稱為終結符。
Vn是一個非空有限集合的符號，它的每個元素稱為非總結符。
S稱為文法G的開始符號。
P是一個非空有限集合，它的元素稱為產生式。
1型文法：又稱為上下文有關文法。
2型文法：又稱為上下文無關文法。
3型文法：又稱為正規文法，使用最多。
0型文法：短語文法。
有限自動機
電腦控制系統的控製程序具有有限狀態自動機（FA）的特征，可以用有限狀態機理論來描述。
確定有限自動機（DFA）
自動機的每個狀態都有對字母表中所有符號的轉移。
非確定有限自動機（NFA）
自動機的狀態對字母表中的每個符號可以有也可以沒有轉移，對一個符號甚至可以有多個轉移。
（1）確定的有限自動機DFA
S是一個有限狀態集合。
是一個字母表，輸入字元的集合。
f是從S*àS上的單值部分映像。f(A,a)=Q表示當前狀態為A，輸入為a時，將轉換到下一狀態Q，稱Q為A的一個後繼狀態。
S0S，是唯一的初態。
ZS，是一個終態集。
已知有DFA M1=({s0,s1,s2,s3},{a,b},f,S,{s3})
（2）不確定的有限自動機NFA
S是一個有限狀態集合。
是一個字母表，輸入字元的集合。
f是從S*àS上的單值部分映像。f(A,a)=Q表示當前狀態為A，輸入為a時，將轉換到下一狀態Q，稱Q為A的一個後繼狀態。
S0S，是一個非空初態集。
ZS，是一個終態集。
正規式
下麵文法G[S]它無法識別（D），次文法對應正規式為（C）。
G[S]:
SàaA|bB
AàbS|b
BàaS|a
（1）A．ababab B.bababa C.abbaab D.babba
（2）A．(a|b)* B.(ab)* C.(ab|ba)* D.(ab)*b*
解析：
SàaAàabSàabaAàababSà(ab)*
SàbBàbaSàbabBàbabaSà(ba)*
SàaAàabSàabbBàabbaSàabbaaAàabbaabà(ab|ba)*
下圖所示為一個有限自動機（其中，A是初態，C是終態），該自動機識別的語言可用正規式（C）表示。
A.0000 B.1111 C.0101 D.1010
對於以下編號為 j，k，l的正規式，正確的說法是（C）。
j(aa*|ab)*b k(a|b)*b l((a|b)*|aa)*b
A.正規式j，k等價 B.正規式j，l等價
C．正規式k，l等價 D.正規式j，k，l互不等價
語法樹
以圖示化形式把句子分解成各個組成部分，以分析句子的語法結構。語法樹表示法與文法規則完全一致。但更為直觀和完整。
滿足下列條件的數稱為文法G的語法樹：
（1）每個節點用G的一個終結符或非終結符標記。
（2）根結點用文法開始符號S標記。
（3）內部結點一定是非終結符。若某個內部結點A有n個分支，且其所有子節點從左至右依次標記為X1,X2,…,Xn，則AàX1,X2,…,Xn一定是G的一條產生式；
（4）若某一結點n至少有一個它自己除外的子孫，並且有標記A，則A一定在非終結符中。
文法G=({a,b},{S,A},S,P)，其中：SàaAS|a，AàSbA|SS|ba。請構造句型aabAa的推導樹。
解析：
SàaASàa(SbA)Sàa(abA)a
中間代碼表達式
首碼表達式（+ab）
中綴表達式（a+b）
尾碼表達式（ab+）
例如，表達式(a-b)*(c+5)的尾碼是（D）。
A.abc5+*- B.ab-c+5*
C.abc-*5+ D.ab-c5+*
解析：從左至右，從下至上。ab-c5+*
