編譯原理線性構造

1. ！！編譯原理DFA和NFA

DFA或NFA是對計算機程序的行為的抽象模型。你編寫的程序其實就對應了一個自動機。簡單舉例來說，如果a,b可以取值0或1; 程序： if(a==1) b=1; 這個程序對應了一個自動機。
對應的自動機就有狀態 (0,0), (0,1), (1,1), (1, 0)
比如你自動機的初始狀態是 (1,0)即a=1,b=0時，運行程序的下一個狀態就是(1,1)。

畫圖出來就是 這4個狀態作為頂點，並且有下面幾條邊
(0,0) --> (0,0)（自環）, (1,0)-->(1,1), (1,1)-->(1,1)（自環）, (0,1)-->(0,1)自環

存在的意義就是一種理論模型，也可以認為是一種編程思想。 詞法分析系也離不開 if else， 這一系列的if else和條件也就組成自動機。。。

最經典體現自動機思想的演算法就是KMP演算法，你肯定學過，字元串子串匹配的演算法。 回憶這個演算法的過程：演算法第一步構造的next表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機！ 演算法第二步將原串作為自動機輸入，自動機的輸出就是匹配到的子串位置或者無匹配。

2. 編譯原理全部的名詞解釋

書上有別那麼懶!.
編譯過程的六個階段：詞法分析,語法分析,語義分析,中間代碼生成,代碼優化,目標代碼生成
解釋程序：把某種語言的源程序轉換成等價的另一種語言程序——目標語言程序,然後再執行目標程序.解釋方式是接受某高級語言的一個語句輸入,進行解釋並控制計算機執行,馬上得到這句的執行結果,然後再接受下一句.
編譯程序：就是指這樣一種程序,通過它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序(機器語言程序或匯編語言程序).
解釋程序和編譯程序的根本區別：是否生成目標代碼
句子的二義性（這里的二義性是指語法結構上的.）:文法G[S]的一個句子如果能找到兩種不同的最左推導(或最右推導),或者存在兩棵不同的語法樹,則稱這個句子是二義性的.
文法的二義性:一個文法如果包含二義性的句子,則這個文法是二義文法,否則是無二義文法.
LL(1)的含義：(LL(1)文法是無二義的； LL(1)文法不含左遞歸)
第1個L：從左到右掃描輸入串 第2個L：生成的是最左推導
1 ：向右看1個輸入符號便可決定選擇哪個產生式
某些非LL(1)文法到LL(1)文法的等價變換: 1. 提取公因子 2. 消除左遞歸
文法符號的屬性:單詞的含義,即與文法符號相關的一些信息.如,類型、值、存儲地址等.
一個屬性文法(attribute grammar)是一個三元組A=(G, V, F)
G：上下文無關文法.
V：屬性的有窮集.每個屬性與文法的一個終結符或非終結符相連.屬性與變數一樣,可以進行計算和傳遞.
F：關於屬性的斷言或謂詞(一組屬性的計算規則)的有窮集.斷言或語義規則與一個產生式相聯,只引用該產生式左端或右端的終結符或非終結符相聯的屬性.
綜合屬性:若產生式左部的單非終結符A的屬性值由右部各非終結符的屬性值決定,則A的屬性稱為綜合屬
繼承屬性:若產生式右部符號B的屬性值是根據左部非終結符的屬性值或者右部其它符號的屬性值決定的,則B的屬性為繼承屬性.
(1)非終結符既可有綜合屬性也可有繼承屬性,但文法開始符號沒有繼承屬性.
(2) 終結符只有綜合屬性,沒有繼承屬性,它們由詞法程序提供.
在計算時： 綜合屬性沿屬性語法樹向上傳遞；繼承屬性沿屬性語法樹向下傳遞.
語法制導翻譯：是指在語法分析過程中,完成附加在所使用的產生式上的語義規則描述的動作.
語法制導翻譯實現：對單詞符號串進行語法分析,構造語法分析樹,然後根據需要構造屬性依賴圖,遍歷語法樹並在語法樹的各結點處按語義規則進行計算.
中間代碼（中間語言）
1、是復雜性介於源程序語言和機器語言的一種表示形式.
2、一般,快速編譯程序直接生成目標代碼.
3、為了使編譯程序結構在邏輯上更為簡單明確,常採用中間代碼,這樣可以將與機器相關的某些實現細節置於代碼生成階段仔細處理,並且可以在中間代碼一級進行優化工作,使得代碼優化比較容易實現.
何謂中間代碼：源程序的一種內部表示,不依賴目標機的結構,易於代碼的機械生成.
為何要轉換成中間代碼:(1)邏輯結構清楚；利於不同目標機上實現同一種語言.
(2)便於移植,便於修改,便於進行與機器無關的優化.
中間代碼的幾種形式：逆波蘭記號 ,三元式和樹形表示 ,四元式
符號表的一般形式：一張符號表的的組成包括兩項,即名字欄和信息欄.
信息欄包含許多子欄和標志位,用來記錄相應名字和種種不同屬性,名字欄也稱主欄.主欄的內容稱為關鍵字（key word）.
符號表的功能：（1）收集符號屬性 (2) 上下文語義的合法性檢查的依據： 檢查標識符屬性在上下文中的一致性和合法性.(3)作為目標代碼生成階段地址分配的依據
符號的主要屬性及作用：
1. 符號名 2. 符號的類型 （整型、實型、字元串型等））3. 符號的存儲類別（公共、私有）
4. 符號的作用域及可視性 （全局、局部） 5. 符號變數的存儲分配信息 （靜態存儲區、動態存儲區）
存儲分配方案策略：靜態存儲分配；動態存儲分配：棧式、 堆式.
靜態存儲分配
1、基本策略
在編譯時就安排好目標程序運行時的全部數據空間,並能確定每個數據項的單元地址.
2、適用的分配對象：子程序的目標代碼段；全局數據目標（全局變數）
3、靜態存儲分配的要求：不允許遞歸調用,不含有可變數組.
FORTRAN程序是段結構,不允許遞歸,數據名大小、性質固定. 是典型的靜態分配
動態存儲分配
1、如果一個程序設計語言允許遞歸過程、可變數組或允許用戶自由申請和釋放空間,那麼,就需要採用動態存儲管理技術.
2、兩種動態存儲分配方式：棧式,堆式
棧式動態存儲分配
分配策略：將整個程序的數據空間設計為一個棧.
【例】在具有遞歸結構的語言程序中,每當調用一個過程時,它所需的數據空間就分配在棧頂,每當過程工作結束時就釋放這部分空間.
過程所需的數據空間包括兩部分
一部分是生存期在本過程這次活動中的數據對象.如局部變數、參數單元、臨時變數等；
另一部分則是用以管理過程活動的記錄信息(連接數據).
活動記錄（AR）
一個過程的一次執行所需要的信息使用一個連續的存儲區來管理,這個區 (塊)叫做一個活動記錄.
構成
1、臨時工作單元；2、局部變數；3、機器狀態信息；4、存取鏈；
5、控制鏈；6、實參；7、返回地址
什麼是代碼優化
所謂優化,就是對代碼進行等價變換,使得變換後的代碼運行結果與變換前代碼運行結果相同,而運行速度加快或佔用存儲空間減少.
優化原則：等價原則：經過優化後不應改變程序運行的結果.
有效原則：使優化後所產生的目標代碼運行時間較短,佔用的存儲空間較小.
合算原則：以盡可能低的代價取得較好的優化效果.
常見的優化技術
(1) 刪除多餘運算(刪除公共子表達式) (2) 代碼外提 +刪除歸納變數+ (3)強度削弱; (4)變換循環控制條件 (5)合並已知量與復寫傳播 (6)刪除無用賦值
基本塊定義
程序中只有一個入口和一個出口的一段順序執行的語句序列,稱為程序的一個基本塊.
給我分數啊.

3. 編譯原理的數據結構

編譯原理一直是計算機學習的必修課.
當然，由編譯器的階段使用的演算法與支持這些階段的數據結構之間的交互是非常強大的。編譯器的編寫者盡可能有效實施這些方法且不引起復雜性。理想的情況是：與程序大小成線性比例的時間內編譯器，換言之就是，在0 （ n ）時間內，n是程序大小的度量（通常是字元數）。本節將講述一些主要的數據結構，它們是其操作部分階段所需要的，並用來在階段中交流信息。 臨時文件（temporary file）：計算機過去一直未能在編譯器時將整個程序保留在存儲器中。這一問題已經通過使用臨時文件來保存翻譯時中間步驟的結果或通過「匆忙地」編譯（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。存儲器的限制現在也只是一個小問題了，現在可以將整個編譯單元放在存儲器之中，特別是在可以分別編譯的語言中時。但是偶爾還是會發現需要在某些運行步驟中生成中間文件。其中典型的是代碼生成時需要反填（backpatch）地址。例如，當翻譯如下的條件語句時 if x = 0 then ... else ... 在知道else部分代碼的位置之前必須由文本跳到else部分：
CMP X,0 JNE NEXT ;;
location of NEXT not yet known < code for then-part > NEXT : < code for else-part >
通常，必須為NEXT的值留出一個空格，一旦知道該值後就會將該空格填上，利用臨時文件可以很容易地做到這一點。
如果想利用上面的編譯原理開發一套屬於自己的編程語言，或者想在一個產品中嵌入編程語言，可以參考zengl開源網開發的zengl編程語言，該編程語言為國人使用C語言開發，裡麵包含兩個部分，一個是編譯器，一個是解釋執行中間代碼的虛擬機。編譯器包含了詞法掃描，語法分析，中間代碼輸出等，虛擬機則類似JAVA一樣解釋執行中間代碼。作者將所有的版本都公布出來，好讓讀者可以由淺入深的做研究，並且為了證明該編程語言的實用性，還結合SDL游戲開發庫開發了一款圖形界面和命令行界面的21點撲克小游戲 。
zengl編程語言目前適用平台為windows和linux (最開始在Linux下使用gcc開發，後來移植到windows平台)

4. 編譯原理

編譯原理)：利用編譯程序從源語言編寫的源程序產生目標程序的過程； 用編譯程序產生目標程序的動作。 編譯就是把高級語言變成計算機可以識別的2進制語言，計算機只認識1和0，編譯程序把人們熟悉的語言換成2進制的。

編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段：詞法分析；語法分析；語義檢查和中間代碼生成

(4)編譯原理線性構造擴展閱讀：

編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。

編譯程序的語法規則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。

而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。

5. 編譯原理pdf

編譯原理pdf是計算機專業的一門重要專業課。

學習編譯原理pdf的方法：

1、端正認識：編譯原理在靜態文本處理上有廣泛應用，把HTML文件轉化為純文本，利用編譯原理來實現非常簡單。理解編譯原掘灶理的實用性，可以提高學習興趣。

2、反復看書：是基本的方法，看書可以讀懂很多內容。

3、結合源碼學習：看懂代碼，才能說真正理解理論。要完全看懂yacc的代碼，工作量很大，同樣要先理解理論。

4、刪繁就簡，避重就輕。對於詞法分析，可避免自動機理論和集合論推演的介紹，直接搬出源碼，跡散扒降低理解難度姿昌，對於語法分析遞歸下降和LL文法及相應的源碼可簡單介紹，而對LR文法理解即可，這樣可短時間內編寫出一個能夠運行的詞法分析器和語法分析器，可以提高學習積極性。

6. 編譯原理：構造產生此語言的上下文無關文法G

對於文法G=(V, T, S, P)，如果產生式的形式如下：
A -> xB
A -> x
其中A, B屬於V，x屬於T*，則稱為右線性文法；相似的，如果產生式的形式如下：
A -> Bx
A -> x
則稱為左線性文法。右線性文法和左線性文法統稱為正則文法。
正則表達式的表達能力等價於正則文法，正則表達式的定義如下：
字母表中的任意字母是正則表達式，空串和空集也是正則表達式；
如果r, s是正則表達式，那麼r|s, rs, r*, (r)也是正則表達式。
正則表達式的擴展：
r+：一個或多個重復
. ：任意字元
[a-z]：字元范圍
[^abc]：不在給定集合中的任意字元
r?：可選
正則表達式只能使用終結符（字母表中的字元），因而很容易變得復雜又難懂，實際中，經常使用正則描述，正則描述允許使用非終結符定義表達式，很像EBNF，但是它限制在未完全定義之前，不能使用非終結符，也就是說不允許遞歸或自嵌套。
像正則表達式的表達能力等價於正則文法一樣，BNF範式的表達能力等價於上下文無關文法。BNF是「Backus Naur Form」的縮寫。John Backus和Peter Naur首次引入一種形式化符號來描述給定語言的語法。
BNF的元符號：
::= 表示「定義為 」，有的書上用-->
| 表示「或者」
< > 尖括弧用於括起非終結符。
BNF的擴展EBNF：
可選項被括在元符號「[」和「]」中
重復項（零個或者多個）被括在元符號「{」和「}」中
僅一個字元的終結符用引號（"）引起來，以和元符號區別開來
上述操作符不是嚴格限定的，有的人喜歡直接使用擴展正則表達式的操作符描述EBNF。除了方便表達以外，引入EBNF的另一個主要原因是為了更緊密地把文法映射到遞歸下降分析程序的真實代碼。當需要手動構造歸下降分析程序的時候，通常把上下文無關文法改寫為EBNF是必需的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
BNF的擴展EBNF：
可選項被括在元符號「[」和「]」中
重復項（零個或者多個）被括在元符號「{」和「}」中
僅一個字元的終結符用引號（"）引起來，以和元符號區別開來
上述操作符不是嚴格限定的，有的人喜歡直接使用擴展正則表達式的操作符描述EBNF。除了方便表達以外，引入EBNF的另一個主要原因是為了更緊密地把文法映射到遞歸下降分析程序的真實代碼。當需要手動構造歸下降分析程序的時候，通常把上下文無關文法改寫為EBNF是必需的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
如上所述，上下文無關文法的遞歸性，對其分析方法也有很大影響。首先，用作識別這些結構的演算法必須使用遞歸調用或顯式管理的分析棧。其次，用作表示語言語義結構的數據結構現在也必須是遞歸的（通常是一顆分析樹），而不再是線性的（如同用於詞法和記號中的一樣）了。
在程序設計語言中，通常用正則表達式描述詞法規則。但是正則表示式的表達能力有限，她無法表達括弧配對等語法形式，因而，需要引入表達能力更強的上下文無關文法。編譯程序中常用正則文法表示詞法，用上下文無關文法表示語法。那麼程序語言中那些屬於詞法哪些屬於語法呢？一個簡單的辦法，把所有能用正則文法表示的規則成為詞法，即我們用盡可能的使用正則文法表示更多的東西，那些無法用正則表示式表示的成為句法，如C語言中的{ statement; }語法形式。語言中有些規則使用上下文無關文法仍然無法描述，例如變數的定義在使用之前，類型匹配等等，這些通常稱為（靜態）語義，它們在編譯程序的靜態語義檢查階段進行檢測。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。

7. 什麼是編譯原理

問題一：什麼是編譯原理 編譯：就是將程序語言進行翻譯，生成可供用戶直接執行的二進制代碼，即可執行文件。
任務是個比較模糊的概念，指的是操作系統中正在進行的工作，既可以指進程，也可以指程序春坦灶。
程序指的是可以連續執行，並能夠完成一定任務的一條條指令的 *** 。
進程是程序在一個數據 *** 上運行的過程,它是傳統操作系統進行資源分配和調度的一個獨立單位。
線程是一個指令執行序列，是操作系統調度的最小單位。一個或多個線程構成進程，構成一個進激的線程之間共享資源。進程和線程之間的最大區別就是線程不能獨立擁有資源，進程擁有自己的資源。

問題二：編譯原理中V*是什麼意思 V是一個符號 *** ，假設V指的是三個符號a, b, c的 *** ，記為 V = {a, b, c }
V* 讀作「V的閉包」，它的數學定義是V自身的任意多次自身連接（乘法）運算的積，也是一個 *** 。
也就是說，用V中的任意符號進行意多次（包括0次）連接，得到的符號串，都是V*這個 *** 中的元素。
0次連接的結果是不含任何符號的空串，記為 ε
1次連接就是只有一個符號的符號串，比如，a，b， c
2次連接是兩個符號構成的符號串，比如，aa, ab, ac, ba, bb, bc,等等
……
n次連接是一個長度為n、由a、b、c三個符號構成的符號串，比如abaacbbac……
因此，V*包含一切由a,b,c三個符號連接而成的、任意長度的符號串（以及空串ε）

問題三：編譯原理 V+什麼意思，例如下面的例子。。。 v表示終結符和非終結符 *** 。
+表示 *** 中的一個或多個元素構成的串的 *** 。
所以v+表示由一個或多個終結符或非終結符構成的串的 *** 。比如如果a∈VT，A∈VN，那麼a，A，aA，Aa，aAA，AaA等都是v+中的元素。

問題四：誰能夠解釋下編譯原理中什麼是FIRSTVT,和LASTVT，盡量淺顯易懂點謝謝 Firstvt和Lastvt是為了畫算符優先關系表的（就是表裡面填優先大於小於等於的那個）。
然後要注意他們可都是終結符的 *** 。
Firstvt
找Firstvt的三條規則：如果要找A的Firstvt，A的候選式中出現：
A->a.......，即以終結符開頭，該終結符入Firstvt
A->B.......，即以非終結符開頭，該非終結符的Firstvt入A的Firstvt
攻 A->Ba.....，即先以非終結符開頭，緊跟終結符，則終結符入Firstvt
Lastvt
找Lastvt的三條規則：如果要找A的Lastvt，A的候選式中出現：
A->.......a，即以終結符結尾，該終結符入Lastvt
A->.......B，即以非終結符結尾，該非終結符的Lastvt入A的Lastvt
A->.....aB，即先以非終結符結尾，前面是終結符，則終結符入Firstvt

問題五：編譯原理 什麼是語義分析 在編譯原理中，語法規則和詞法規則不同之處在於：規則主要識別單詞,而語法主要識別多個單片語成的句子。詞法分析信孝和詞法分析程序：詞法分析階段是編譯過程的第一個階段。這個階段的任務是從左到右一個字元一個字元地讀入源程序，即對構成源程序的字元流進行掃描然後根據構詞規則識別單詞(也稱單詞符號或符號)。詞法分析程序實現這個任務。詞法分析程序可以使用lex等工具自動生成。語法分析（Syntax *** ysis或Parsing）和語法分析程序（Parser） 語法分析是編譯過程的一個邏輯階段。語法分析的任務是在詞法分析的基礎上將單詞序列組合成各類語法短語，如「程序」，「語句」，「表達式」等等.語法分扒扮析程序判斷源程序在結構上是否正確.源程序的結構由上下文無關文法描述.語義分析（Syntax *** ysis） 語義分析是編譯過程的一個邏輯階段. 語義分析的任務是對結構上正確的源程序進行上下文有關性質的審查, 進行類型審查.語義分析將審查類型並報告錯誤:不能在表達式中使用一個數組變數,賦值語句的右端和左端的類型不匹配.

問題六：編譯原理中，（E）是什麼意思？ E→(E)? 10分 就是 字元本身 意思是F產生（ E ） 或者 i 比如If語句的開頭 就是 帶括弧的 必須是 if(表達式)這樣的形式 丟了任何即括弧就是其 終結符 「(」 和 「)」.

問題七：大家覺得對編譯器及編譯原理需要掌握到一個什麼程度 我跟你說，編譯原理太有用了。
我是做手機游戲的，現在做一個游戲引擎。既然是引擎，就需要提供抽象的東西給上層使用。這里，我引入了腳本系統。
這個腳本系統包括一堆我根據實際需求自行設計的指令集，包括基本的輸入輸出，四則運算，系統功能調用，函數聲明，調用等等（其實你要是用過lua或者其他游戲腳本你就知道了。）整個結構包括指令集、編譯器、虛擬機等部分。這樣，引擎提供一些基礎服務，比如繪圖，計算位置等，腳本就可以非常簡單控制游戲。甚至快速構建新游戲。你應該知道QUAKE引擎吧？
這里提供給你一個計算器的小程序，應用了EBNF理論，支持表達式，比如(2+3*6)*4+4，你自己體驗一下它的簡潔和強大。
/*
simple integer arithmetic calculator according to the EBNF
-> {}
->+|-
->{}
-> *
-> ( )| Number
Input a line of text from stdin
Outputs Error or the result.
*/
#include
#include
#include
char token;/*global token variable*/
/*function prototypes for recursive calls*/
int exp(void);
int term(void);
int factor(void);
void error(void)
{
fprintf(stderr,Error\n);
exit(1);
}
void match(char expectedToken)
{
if(token==expectedToken)token=getchar();
else error();
}
main()
{
int result;
token = getchar();/*load token with first character for lookahead*/
result = exp();
if(token=='\n')/*check for end of line */
printf(Result = %d\n,result);
else error();/*extraneous cahrs on line*/
return 0;
}
int exp(void)
{
int temp = term();
while((token=='+')||(token=='-'))
switch(token)
{
case '+':
match('+');
temp+=term......>>

問題八：編譯原理中,自動機究竟是什麼. 形式語言
形式語言 是一個字母表上的某些有限長字串的 *** 。一個形式語言可以包含無限多個字串。
語言的形式定義
字母表 ∑ 為任意有限 *** ，ε 表示空串， 記 ∑ 0 為{ε}，全體長度為 n 的字串為 ∑ n ， ∑ * 為 ∑ 0 ∪∑ 1 ∪…∪∑ n ∪…， 語言 L 定義為 ∑ * 的任意子集。
注記：∑ * 的空子集 Φ 與 {ε} 是兩個不同的語言。
語言間的運算
語言間的運算就是 ∑ * 冪集上的運算。
字串 *** 的交並補等運算。
連接運算：L 1 L 2 = { xy | x 屬於L 1 並且 y 屬於L 2 }。
冪運算：L n = L … L （共 n 個 L 連接在一起），L 0 = {ε}。
閉包運算：L * = L 0 ∪L 1 ∪…∪L n ∪…。
（右）商運算：L 1 /L 2 = {x | 存在 y 屬於L 2 使得 xy 屬於L 1 }。
語言的表示方法
一個形式語言可以通過多種方法來限定自身，比如：
枚舉出各個字串（只適用於有限字串 *** ）。
通過 形式文法 來產生（參見 喬姆斯基譜系 ）。
通過正則表達式來產生。
通過某種自動機來識別，比如 圖靈機 、 有限狀態自動機 。
自動機
automata
對信號序列進行邏輯處理的裝置。在自動控制領域內，是指離散數字系統的動態數學模型，可定義為一種邏輯結構，一種演算法或一種符號串變換。自動機這一術語也廣泛出現在許多其他相關的學科中，分別有不同的內容和研究目標。在計算機科學中自動機用作計算機和計算過程的動態數學模型，用來研究計算機的體系結構、邏輯操作、程序設計乃至計算復雜性理論。在語言學中則把自動機作為語言識別器，用來研究各種形式語言。在神經生理學中把自動機定義為神經網路的動態模型，用來研究神經生理活動和思維規律，探索人腦的機制。在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函數，研究各種演算法。現代自動機的一個重要特點是能與外界交換信息，並根據交換得來的信息改變自己的動作，即改變自己的功能，甚至改變自己的結構，以適應外界的變化。也就是說在一定程度上具有類似於生命有機體那樣的適應環境變化的能力。
自動機與一般機器的重要區別在於自動機具有固定的內在狀態，即具有記憶能力和識別判斷能力或決策能力，這正是現代信息處理系統的共同特點。因此，自動機適宜於作為信息處理系統乃至一切信息系統的數學模型。自動機可按其變數集和函數的特性分類，也可按其抽象結構和聯結方式分類。主要有：有限自動機和無限自動機、線性自動機和非線性自動機、確定型自動機和不確定型自動機、同步自動機和非同步自動機、級聯自動機和細胞自動機等。
這可能有你想要的答案
./question/7218281?fr=qrl3

問題九：編譯原理中"(E)"表示什麼 字元( 表達式 字元)

8. 編譯原理中的一概念：什麼是左線性正規文法

正規文法是左線性文法和右線性文法的統稱.它們都是Chomsky分類下的3型文法.由正規文法產生的語言稱為正規集.下面我們將會看到,這里之所以用「正規」二字為一種語言命名,是因為這種語言的結構可以用所謂正規式來描述.
1．右線性文法
設G[S]=(VN,VT,P,S)為CFG,若P中的產生或均有如下的形式：
A→aB或A→a（A∈VN,a∈VT）
則稱G為右線性文法.例如,文法
G1[S]=({S,A,B},{a,b},P1,S)
其中
P1={S→aA,A→aA,A→bB,A→b,B→bB,B→b}
為一右線性文法,G1所產生的正規集為
L(G1)={aibj |i,j≥1}
2．左線性文法
若一個文法G[S]=(VN,VT,P,S)中的產生式均有如下的形式：
A→Ba或A→a（A,B∈VN,a∈VT）
則稱G為左線性文法.例如,文法
G2[S]=({S,A},{a,b},P2,S)
其中
P2={S→Sb,S→Ab,A→Aa,A→a}
為一左線性文法,且有
L(G2)=L(G1)={aibj |i,j≥1}
請注意,雖然文法
G3[S]=({S,A,B},{a,b},P3,S)
其中
P3={S→aA,A→aA,A→Bb,A→b,B→Bb,B→b}
也同樣產生語言{aibj |i,j≥1},但由於G3中同時含有左線性產生式和右線性產生式,故G3不是正規文法.
另外
P4={S-->aA,A-->ab},
也不是正規文法