編譯原理中空串是短語嗎

1. 求解編譯原理的一道題:設有文法如下

首先要做這題你要知道判別文法類型
包括四個層次：

0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。
1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這里的A 是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
2-型文法生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這里的A 是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程序設計語言的語法提供了理論基礎。
3-型文法（正規文法）生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個非終結符號後隨一個終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程序設計語言中的詞法結構。
正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這里的包含都是集合的真包含關系，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在上下文無關語言不屬於正規語言類。

1）本題應該是--上下文無關文法

句子是產生式在推導時「僅僅有終結符」的任何一步
2）%mm%nn 是一個句子

由於下面一題的圖我等級不夠 不能貼圖 發你郵箱

2. 編譯原理有關語法的題

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

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

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

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

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

語法樹如圖：

3. 提問 編譯原理問題（高分）

詞法分析 的作用是把輸入的源語句轉化成單詞形式
第五個最右推導沒給要推出的句子 如果是 cbb 那過程也不對
E->CB

C->c

B->b

最右推導的分析為

1 CB

2 Cb

3 cb
你給的文法有問題吧，最右推導通俗的說 就是只按照最右邊的非終結符推導

你這些都是要干什麼的題，如果要考試，後面那幾道的類型幾乎必考！！！

4. 編譯原理什麼是素短語

編譯原理中，素短語是至少含義一個終結符，並且自身不包含任何更小素短語的一種短語。

素短語是一種特殊的短語，它是一個遞歸的定義，至少含有一個終結符，並且除它自身之外不再含任何更小的素短語，所謂最左素短語就是處於句型最左邊的素短語的短語。

一個算符優先文法G的任何句型的最左素短語是滿足以下條件的最左子串NaNb…NcNdN(N是非終結符，a,b,c,d是終結符)。例如：句型T+T*F+id，T*F是最左素短語，id是素短語。

(4)編譯原理中空串是短語嗎擴展閱讀：

通過語法樹可以得知素短語：

1、每個句型對應一棵語法樹

2、每棵語法樹的葉子結點從左到右排列構成一個句型

3、每棵語法樹的子樹的葉子結點從左到右排列構成一個短語

4、每棵語法樹的簡單子樹（只有父子兩層結點）的葉子結點從左到右排列構成一個簡單(直接)短語。

5、素短語是至少包含一個終結符的短語，但它不能包含其它素短語。

5. 編譯原理：空字元串可以是短語嗎

ε可以是短語

6. 編譯原理中的短語、直接短語、句柄

就是說，對一棵分析樹從上到下，從左到右把所有的直接短語寫出來，在所有的直接短語的最前面(也就是最左邊)的那個就是句柄啦。
希望幫到你理解這個意思。

7. 編譯原理中，形式語言里怎麼區分2型文法與3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文無關文法，表現在產生式上就是產生式的左部只有一個非終結符；3型文法從廣義上講包括左線形文法、右線形文法和正規文法 。
B、左線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最左端。
C、右線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最右端 。
D、正規文法是右線形文法的一個子集，其產生式右部只有三種情況：
1）空串
2）只有一個終結符
3）只有一個終結符後接一個非終結符
E、所有的3型文法都是2型文法。

8. 編譯原理的疑問

設文法G的開始符號為S，abc是G的一個句型。
如果有句型S *=>aAc，且A +=>b，則稱b是句型abc相對於非終結符A的短語。
假如A =>b，則稱b是句型abc相對於規則A=>b的直接短語。
句柄就是句型的最左直接短語。
假如一個短語，有且只含有一個非終結符，則稱之為素短語；（語法樹）最左邊的素短語為最左素短語。

形式語言里，規范推導是最右開始，則歸約是最左開始。
短語的特點是由非終結符而來。在算符優先分析里，短語是進行歸約的方向。它和常見的中文、英文里所說的短語概念有相似，也有不同。

9. 編譯原理 空串為什麼可以區分終態和非終態

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）中...

10. 編譯原理空字元ε與空集區別

不知你說的空集是為何指？據我所猜應該是指某個文法所能推導的語句的集合為空，這里的空集意思是不存在匹配該文法的句子。而ε則是指某個包含非終結符號的文法符號串的推導為空，例如A->ε。咋看上去好像差不多，其實它們卻有本質的區別，空集是面向結果的，即一個文法所有可能推導的最終語句；而ε則是面向定義的，即某個非終結符號可以推導為空，這樣的定義可以在推導過程重復使用。
最後給你來點哲學的。為什麼會存在ε？古代有句話叫，其大無外，其小無內，大小之間轉化的奧秘在編譯原理中真實的被呈現了出來，就看你有沒有發現。可以肯定的說，ε的存在正是應了無窮的需要。例如：A->aA|ε，這里ε既可以A可以表達任意多的a串，又可以動態的將其終止，不至無休止的無限下去。
你終會明白，理解了ε，就是理解了形式語言的整個靈魂。