① 編譯原理-句型、句子、短語、直接短語、句柄、素短語、最左素短語
在進行語法分析的時候，有時候會對這些詞語的概念不清晰，這里我們就詳細歸納總結一下。
可以看出這個裡面，最需要理解的概念就是短語，其他大部分概念都是在短語基礎上延伸的，從概念上可以看出：
假設有一個文法
針對文法的一個特定句型 (Sd(T)db) , 其推導過程如下:
這個句型 (Sd(T)db) 對應的 CFG 分析樹如下：
那個這個句型 (Sd(T)db) 有多少個短語呢？
還記得短語的定義么， S ⇒* αβδ ， αβδ 代表句型就是這里的 (Sd(T)db) 。
因此這個句型 (Sd(T)db) :
演算法非常簡單，就是通過分析樹的後序遍歷，先將子樹的葉節點從左到右排合並成字元串(即一個短語)，然後用它代表子樹的根節點的值，再和與子樹根節點同一層節點值合並，得到新的短語。就這樣從分析樹的最底層，一路合並到分析樹的根節點，就能得到所有的短語了。
通過遞歸的方法，獲取短語列表 phraseList , 直接短語列表 directPhraseList 和 素短語列表 plainPhraseList 。
運行結果:
② 【編譯原理】第二章：語言和文法
上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。
約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：
產生式
可以簡寫為：
如上例中，
可以簡寫為：
給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。
如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。
推導的反過程稱為 歸約 。
如果 ，則稱 是 的一個 句型（sentential form ）。
由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：
例
文法
表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。
並、連接、冪、克林閉包、正閉包。
如上例表示為：
中必須包含一個 非終結符 。
產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。
上下文有關文法不包含空產生式（ ）。
產生式的一般形式：
即產生式左邊都是非終結符。
右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。
例：（右線性文法）
以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：
正則文法能描述程序設計語言中的多數單詞。
正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。
根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。
給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。
直接短語一定是某產生式的右部，但反之不一定。
如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。
二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。
③ 編譯原理中 「句子」的概念 LR（1）分析法中「L」 「 R」的含義分別是
字母表上符合某種規則構成的串稱作句子。
L：自左至右掃描，R：最右推倒的逆過程。
④ 編譯原理
編譯原理是計算機專業的一門重要專業課，旨在介紹編譯程序構造的一般原理和基本方法。內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。 編譯原理是計算機專業設置的一門重要的專業課程。編譯原理課程是計算機相關專業學生的必修課程和高等學校培養計算機專業人才的基礎及核心課程，同時也是計算機專業課程中最難及最挑戰學習能力的課程之一。編譯原理課程內容主要是原理性質，高度抽象[1]。
中文名
編譯原理[1]
外文名
Compilers: Principles, Techniques, and Tools[1]
領域
計算機專業的一門重要專業課[1]
快速
導航
編譯器
編譯原理課程
編譯技術的發展
編譯的基本流程
編譯過程概述
基本概念
編譯原理即是對高級程序語言進行翻譯的一門科學技術, 我們都知道計算機程序由程序語言編寫而成, 在早期計算機程序語言發展較為緩慢, 因為計算機存儲的數據和執行的程序都是由0、1代碼組合而成的, 那麼在早期程序員編寫計算機程序時必須十分了解計算機的底層指令代碼通過將這些微程序指令組合排列從而完成一個特定功能的程序, 這就對程序員的要求非常高了。人們一直在研究如何如何高效的開發計算機程序, 使編程的門檻降低。[2]
編譯器
C語言編譯器是一種現代化的設備, 其需要藉助計算機編譯程序, C語言編譯器的設計是一項專業性比較強的工作, 設計人員需要考慮計算機程序繁瑣的設計流程, 還要考慮計算機用戶的需求。計算機的種類在不斷增加, 所以, 在對C語言編譯器進行設計時, 一定要增加其適用性。C語言具有較強的處理能力, 其屬於結構化語言, 而且在計算機系統維護中應用比較多, C語言具有高效率的優點, 在其不同類型的計算機中應用比較多。[3]
C語言編譯器前端設計
編譯過程一般是在計算機系統中實現的, 是將源代碼轉化為計算機通用語言的過程。編譯器中包含入口點的地址、名稱以及機器代碼。編譯器是計算機程序中應用比較多的工具, 在對編譯器進行前端設計時, 一定要充分考慮影響因素, 還要對詞法、語法、語義進行分析。[3]
1 詞法分析[3]
詞法分析是編譯器前端設計的基礎階段, 在這一階段, 編譯器會根據設定的語法規則, 對源程序進行標記, 在標記的過程中, 每一處記號都代表著一類單詞, 在做記號的過程中, 主要有標識符、關鍵字、特殊符號等類型, 編譯器中包含詞法分析器、輸入源程序、輸出識別記號符, 利用這些功能可以將字型大小轉化為熟悉的單詞。[3]
2 語法分析[3]
語法分析是指利用設定的語法規則, 對記號中的結構進行標識, 這包括句子、短語等方式, 在標識的過程中, 可以形成特殊的結構語法樹。語法分析對編譯器功能的發揮有著重要影響, 在設計的過程中, 一定要保證標識的准確性。[3]
3 語義分析[3]
語義分析也需要藉助語法規則, 在對語法單元的靜態語義進行檢查時, 要保證語法規則設定的准確性。在對詞法或者語法進行轉化時, 一定要保證語法結構設置的合法性。在對語法、詞法進行檢查時, 語法結構設定不合理, 則會出現編譯錯誤的問題。前端設計對精確性要求比較好, 設計人員能夠要做好校對工作, 這會影響到編譯的准確性, 如果前端設計存在失誤, 則會影響C語言編譯的效果。[3]
⑤ 求解編譯原理的一道題:設有文法如下
首先要做這題你要知道判別文法類型
包括四個層次：
0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。
1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這里的A 是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
2-型文法生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這里的A 是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程序設計語言的語法提供了理論基礎。
3-型文法（正規文法）生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個非終結符號後隨一個終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程序設計語言中的詞法結構。
正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這里的包含都是集合的真包含關系，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在上下文無關語言不屬於正規語言類。
1）本題應該是--上下文無關文法
句子是產生式在推導時「僅僅有終結符」的任何一步
2）%mm%nn 是一個句子
由於下面一題的圖我等級不夠 不能貼圖 發你郵箱
⑥ 編譯器有哪幾部分構成.編譯原理
1. 詞法分析
詞法分析器根據詞法規則識別出源程序
中的各個記號（token）,每個記號代表一類單詞（lexeme）。源程序中常見的記號可以歸為幾大類：關鍵字、標識符、字面量和特殊符號。詞法分析器
的輸入是源程序,輸出是識別的記號流。詞法分析器的任務是把源文件的字元流轉換成記號流。本質上它查看連續的字元然後把它們識別為「單詞」。
2. 語法分析
語法分析器根據語法規則識別出記號流中的結構（短語、句子）,並構造一棵能夠正確反映該結構的語法樹。
3. 語義分析
語義分析器根據語義規則對語法樹中的語法單元進行靜態語義檢查,如果類型檢查和轉換等,其目的在於保證語法正確的結構在語義上也是合法的。
4. 中間代碼生成
中間代碼生成器根據語義分析器的輸出生成中間代碼。中間代碼可以有若干種形式,它們的共同特徵是與具體機器無關。最常用的一種中間代碼是三地址碼,它的一種實現方式是四元式。三地址碼的優點是便於閱讀、便於優化。
⑦ 編譯原理實現判斷是不是一個文法的句子
構造LL(1)語法分析程序，任意輸入一個文法符號串，並判斷它是否為文法的一個句子。程序要求為該文法構造預測分析表，並按照預測分析演算法對輸入串進行語法分析，判別程序是否符合已知的語法規則，如果不符合（編譯出錯），則輸出錯誤信息。
⑧ 編譯原理題目
習題一、單項選擇題
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所示。
求採納為滿意回答。