編譯原理終態為什麼還能有自循環

『壹』 這個在編譯原理中什麼意思啊

大學課程為什麼要開設編譯原理呢？這門課程關注的是編譯器方面的產生原理和技術問題，似乎和計算機的基礎領域不沾邊，可是編譯原理卻一直作為大學本科的必修課程，同時也成為了研究生入學考試的必考內容。編譯原理及技術從本質上來講就是一個演算法問題而已，當然由於這個問題十分復雜，其解決演算法也相對復雜。我們學的數據結構與演算法分析也是講演算法的，不過講的基礎演算法，換句話說講的是演算法導論，而編譯原理這門課程講的就是比較專註解決一種的演算法了。在20世紀50年代，編譯器的編寫一直被認為是十分困難的事情，第一Fortran的編譯器據說花了18年的時間才完成。在人們嘗試編寫編譯器的同時，誕生了許多跟編譯相關的理論和技術，而這些理論和技術比一個實際的編譯器本身價值更大。就猶如數學家們在解決著名的哥德巴赫猜想一樣，雖然沒有最終解決問題，但是其間誕生不少名著的相關數論。推薦參考書雖然編譯理論發展到今天，已經有了比較成熟的部分，但是作為一個大學生來說，要自己寫出一個像TurbocC,Java那樣的編譯器來說還是太難了。不僅寫編譯器困難，學習編譯原理這門課程也比較困難。第一本書的原名叫《CompilersPrinciples,Techniques,andTools》,另外一個響亮的名字就是龍書。原因是這本書的封面上有條紅色的龍，也因為獗臼樵詒嘁朐?砘?嘴域確實?忻?所以很多國外的學者都直接取名為龍書。最近機械工業出版社已經出版了此書的中文版，名字就叫《編譯原理》。該書出的比較早，大概是在85或86年編寫完成的，作者之一還是著名的貝爾實驗室的科學家。裡面講解的核心編譯原理至今都沒有變過，所以一直到今天，它的價值都非凡。這本書最大的特點就是一開始就通過一個實際的小例子，把編譯原理的大致內容羅列出來，讓很多編譯原理的初學者很快心裡有了個底,也知道為什麼會有這些理論，怎麼運用這些理論。而這一點是我感覺國內的教材缺乏的東西，所以國內的教材都不是寫給願意自學的讀者，總之讓人看了半天，卻不知道裡面的東西有什麼用。第二本書的原名叫《ModernCompilerDesign》,中文名字叫做《現代編譯程序設計》。該書由人民郵電出版社所出。此書比較關注的是編譯原理的實踐，書中給出了不少的實際程序代碼，還有很多實際的編譯技術問題等等。此書另外一個特點就是其現代而字。在傳統的編譯原理教材中，你是不可能看到如同Java中的垃圾回收等演算法的。因為Java這樣的解釋執行語言是在近幾年才流行起來的東西。如果你想深入學習編譯原理的理論知識，那麼你肯定得看前面那本龍書，如果你想自己動手做一個先進的編譯器，那麼你得看這本《現代編譯程序設計》。第三本書就是很多國內的編譯原理學者都推薦的那本《編譯原理及實踐》。或許是這本書引入國內比較早吧，我記得我是在高中就買了這本書，不過也是在前段時間才把整本書看完。此書作為入門教程也的確是個不錯的選擇。書中給出的編譯原理講解也相當細致，雖然不如前面的龍書那麼深入，但是很多地方都是點到為止，作為大學本科教學已經是十分深入了。該書的特點就是注重實踐，不過感覺還不如前面那本《現代編譯程序設計》的實踐味道更重。此書的重點還是在原理上的實踐，而非前面那本那樣的技術實踐。《編譯原理及實踐》在講解編譯原理的各個部分的同時，也在逐步實踐一個現代的編譯器TinyC.等你把整本書看完，差不多自己也可以寫一個TinyC了。作者還對Lex和Yacc這兩個常用的編譯相關的工具進行了很詳細的說明，這一點也是很難在國內的教材中看到的。推薦了這三本教材，都有英文版和中文版的。很多英文好的同學只喜歡看原版的書，不我的感覺是這三本書的翻譯都很不錯，沒有必要特別去買英文版的。理解理論的實質比理解表面的文字更為重要。編譯原理的實質幾乎每本編譯原理的教材都是分成詞法分析，語法分析（LL演算法，遞歸下降演算法，LR演算法），語義分析，運行時環境，中間代碼，代碼生成，代碼優化這些部分。其實現在很多編譯原理的教材都是按照85,86出版的那本龍書來安排教學內容的，所以那本龍書的內容格式幾乎成了現在編譯原理教材的定式，包括國內的教材也是如此。一般來說，大學裡面的本科教學是不可能把上面的所有部分都認真講完的，而是比較偏重於前面幾個部分。像代碼優化那部分東西，就像個無底洞一樣，如果要認真講，就是單獨開一個學期的課也不可能講得清楚。所以，一般對於本科生，對詞法分析和語法分析掌握要求就相對要高一點了。詞法分析相對來說比較簡單。可能是詞法分析程序本身實現起來很簡單吧，很多沒有學過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法分析的時候，重點把正則表達式和自動機原理加了進來，然後以一種十分標準的方式來講解詞法分析程序的產生。這樣的做法道理很明顯，就是要讓詞法分析從程序上升到理論的地步。語法分析部分就比較麻煩一點了。現在一般有兩種語法分析演算法，LL自頂向下演算法和LR自底向上演算法。LL演算法還好說，到了LR演算法的時候，困難就來了。很多自學編譯原理的都是遇到LR演算法的理解成問題後就放棄了自學。其實這些東西都是只要大家理解就可以了，又不是像詞法分析那樣非得自己寫出來才算真正的會。像LR演算法的語法分析器，一般都是用工具Yacc來生成，實踐中完全沒有比較自己來實現。對於LL演算法中特殊的遞歸下降演算法，因為其實踐十分簡單，那麼就應該要求每個學生都能自己寫。當然，現在也有不少好的LL演算法的語法分析器，不過要是換在非C平台，比如Java,Delphi,你不能運用YACC工具了，那麼你就只有自己來寫語法分析器。等學到詞法分析和語法分析時候，你可能會出現這樣的疑問：詞法分析和語法分析到底有什麼？就從編譯器的角度來講，編譯器需要把程序員寫的源程序轉換成一種方便處理的數據結構（抽象語法樹或語法樹）,那麼這個轉換的過程就是通過詞法分析和語法分析的。其實詞法分析並非一開始就被列入編譯器的必備部分，只是我們為了簡化語法分析的過程，就把詞法分析這種繁瑣的工作單獨提取出來，就成了現在的詞法分析部分。除了編譯器部分，在其它地方，詞法分析和語法分析也是有用的。比如我們在DOS,Unix,Linux下輸入命令的時候，程序如何分析你輸入的命令形式，這也是簡單的應用。總之，這兩部分的工作就是把不規則的文本信息轉換成一種比較好分析好處理的數據結構。那麼為什麼編譯原理的教程都最終把要分析的源分析轉換成樹這種數據結構呢？數據結構中有Stack,Line,List這么多數據結構，各自都有各自的特點。但是Tree這種結構有很強的遞歸性，也就是說我們可以把Tree的任何結點Node提取出來後，它依舊是一顆完整的Tree。這一點符合我們現在編譯原理分析的形式語言，比如我們在函數裡面使用函樹，循環中使用循環，條件中使用條件等等，那麼就可以很直觀地表示在Tree這種數據結構上。同樣，我們在執行形式語言的程序的時候也是如此的遞歸性。在編譯原理後面的代碼生成的部分，就會介紹一種堆棧式的中間代碼，我們可以根據分析出來的抽象語法樹，很容易，很機械地運用遞歸遍歷抽象語法樹就可以生成這種指令代碼。而這種代碼其實也被廣泛運用在其它的解釋型語言中。像現在流行的Java,.NET，其底層的位元組碼bytecode,可以說就是這中基於堆棧的指令代碼的。關於語義分析，語法制導翻譯，類型檢查等等部分，其實都是一種完善前面得到的抽象語法樹的過程。比如說，我們寫C語言程序的時候，都知道，如果把一個浮點數直接賦值給一個整數，就會出現類型不匹配，那麼C語言的編譯器是怎麼知道的呢？就是通過這一步的類型檢查。像C++語言這中支持多態函數的語言，這部分要處理的問題就更復雜了。大部編譯原理的教材在這部分都是講解一些比較好的處理策略而已。因為新的問題總是在發生，舊的法不見得足夠解決。本來說，作為一個編譯器，起作用的部分就是用戶輸入的源程序到最終的代碼生成。但是在講解最終代碼生成的時候，又不得不講解機器運行環境等內容。因為如果你不知道機器是怎麼執行最終代碼的，那麼你當然無法知道如何生成合適的最終代碼。這部分內容我自我感覺其意義甚至超過了編譯原理本身。因為它會把一個計算機的程序的運行過程都通通排在你面前，你將來可能不會從事編譯器的開發工作，但是只要是和計算機軟體開發相關的領域,都會涉及到程序的執行過程。運行時環境的講解會讓你更清楚一個計算機程序是怎麼存儲，怎麼裝載，怎麼執行的。關於部分的內容，我強烈建議大家看看龍書上的講解，作者從最基本的存儲組織，存儲分配策略，非局部名字的訪問，參數傳遞，符號表到動態存儲分配(malloc,new)都作了十分詳細的說明。這些東西都是我們編寫平常程序的時候經常要做的事情，但是我們卻少去探求其內部是如何完成。關於中間代碼生成，代碼生成,代碼優化部分的內容就實在不好說了。國內很多教材到了這部分都會很簡單地走馬觀花講過去，學生聽了也只是作為了解，不知道如何運用。不過這部分內容的東西如果要認真講，單獨開一學期的課程都講不完。在《編譯原理及實踐》的書上，對於這部分的講解就恰到好處。作者主要講解的還是一種以堆棧為基礎的指令代碼，十分通俗易懂，讓人看了後，很容易模仿，自己下來後就可以寫自己的代碼生成。當然，對於其它代碼生成技術，代碼優化技術的講解就十分簡單了。如果要仔細研究代碼生成技術，其實另外還有本叫做《》,那本書現在由機械工業出版社引進的，十分厚重，而且是英文原版。不過這本書我沒有把它列為推薦書給大家，畢竟能把龍書的內容搞清楚，在中國已經就算很不錯的高手了，到那個時候再看這本《》也不遲。代碼優化部分在大學本科教學中還是一個不太重要的部分，就是算是實踐過程中，相信大家也不太運用得到。畢竟，自己做的編譯器能正確生成執行代碼已經很不錯了，還談什麼優化呢？編譯原理的課程畢竟還只是講解原理的課程，不是專門的編譯技術課程。這兩門課程是有很大的區別的。編譯技術更關注實際的編寫編譯器過程中運用到的技術，而原理的課

『貳』 編譯原理 題目

習題一、單項選擇題
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所示。
求採納為滿意回答。
希望能解決您的問題。

『叄』 編譯原理DFA子集法怎麼分割

NFA確定化的時候，包含NFA初態的那個DFA狀態就是確定後的DFA的初態

DFA的終態就是所有包含了NFA終態的DFA的狀態

就如下邊的例子，是一個初態為1，終態為6，7，9的NFA經過確定化得到的轉換矩陣，右側是將左側的轉換矩陣改名之後的DFA，也就是最後得到的DFA

對於DFA來說，他的初態就是包含了NFA唯一初態1的那個狀態，就是左邊的1，2右邊的1了

終態則是左邊的2，4，5，6，7和3，8，9和9對應的就是右邊的2，4，5

『肆』 編譯原理 構造正規式的dfa時怎麼確定是否為終態

NFA確定化的時候，包含NFA初態的那個DFA狀態就是確定後的DFA的初態
DFA的終態就是所有包含了NFA終態的DFA的狀態
就如下邊的例子，是一個初態為1，終態為6，7，9的NFA經過確定化得到的轉換矩陣，右側是將左側的轉換矩陣改名之後的DFA，也就是最後得到的DFA
對於DFA來說，他的初態就是包含了NFA唯一初態1的那個狀態，就是左邊的1，2右邊的1了
終態則是左邊的2，4，5，6，7和3，8，9和9對應的就是右邊的2，4，5

『伍』 編譯原理:能被5整除的10進制數的集合

這數是無窮個。編譯的話也是死循環
n=0;
a=5*n;n=n+1;

『陸』 編譯原理里怎麼區分終態集和非終態集

終態集就是狀態圖中畫兩層圈的狀態的集合。非終態集就是狀態圖中畫一個圈的狀態的集合。

『柒』 誰知道編譯原理中的有窮自動機是怎麼回事

即是有限自動機．在一個有限的狀態集中，當前狀態根據有窮字母表的輸入符號，確定下一個狀態．有限自動機只有一個初態，可以有幾個終態

『捌』 編譯原理中DFA的終態和非終態怎麼區分啊，誰說的通俗點啊

編譯原理中DFA的終態和非終態區別為：包含不同、空集不同、狀態不同。

一、包含不同

1、DFA的終態：DFA的終態包含了NFA終點結點的狀態集合。

2、DFA的非終態：DFA的非終態不包含NFA終點結點的狀態集合。

二、空集不同

1、DFA的終態：DFA的終態不可能為空集，因為NFA的終點一定會包含在某個DFA的狀態集合中。

2、DFA的非終態：DFA有可能得到的非終態是空集，意味著所有的DFA的狀態集合都包含了NFA的終點。

三、狀態不同

1、DFA的終態：DFA的終態每個狀態之間屬於同一個狀態。

2、DFA的非終態：DFA的非終態每個狀態之間不一定屬於同一個狀態。

『玖』 編譯原理 空串為什麼可以區分終態和非終態

follow集合是針對非終結符而言的；follow（U）所表達的是句型中非終結符U的所有可能的後隨終結符號的集合，特別注意一點：「#」是識別符號的後隨附。
直接收取：形如「……Ua」的組合，直接把啊收入到follow（U）中
直接收取：形如「……UP……」的組合，（P是非終態符）；把firth（P）除去ε直接收入到follow（U）中。
反復傳遞：形如「P-……U」的產生式，
follow（P）的全部內容傳遞到follow（U）中，或者說是P-……UB且first（B）包含ε，則把first（B）除去ε直接收入到follow（U）中，同時吧follow（P）的全部內容傳送到follow（U）中...

『拾』 編譯原理課程的習題··

罵人自然是不好的,但是我建議你翻翻書,其中大部分答案在書上都能找到.
雖然不能說大學沒學好出來就混不好,但大學也不能白上了啊,看看書吧.
這些題目換兩年前我上學的時候還會做,現在就不行了,誰還記得這些概念啊.