當前位置:首頁 » 編程軟體 » 什麼是有沖突項目編譯原理

什麼是有沖突項目編譯原理

發布時間: 2023-05-29 03:37:39

1. 編譯原理 LR(0) 項目集規范族怎麼構建。 書上的實在是看不懂那些I0、I1、I2的步驟。求一個

LR分析法是一種自下而上進行規范歸約的語法分析法,L指從左到右掃描輸入符號串,R是指構造最右推導的逆過程。對大多數無二義性上下文無關文法描述的語言都可用它進行有效的分析。主要分析器有LR(0),SLR(1),LR(1),LALR(1):
LR(0):在分析的每一步,只需根據當前棧頂狀態而不必向前查看輸入符號就能確定應採取的分析動作。所能分析的LR(0)文法要求文法的每一個LR(0)項目集中都不含沖突項目。
示例文法:
0 S』 -> S
1 S -> A
2 S -> B
3 A -> aAb
4 A -> c
5 B -> aBb
6 B -> d

2. 有關編譯原理

⑴拓廣文法 1 分
G[S ′ ]: S ′→ S ⑴
S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA :

⑵ 該文法的 LR(0) 分析表:
狀態 ACTION GOTO
a b # S A
0 S 2 1
1 S 3 acc
2 r 3 r 3 r 3
3 S 5 4
4 r 2 r 2 /S 6 r 2
5 r 5 r 5 r 5
6 S 2 7
7 r 4 /S 3 r 4 r 4
⑶ LR(0) 文法:該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中沒有沖突狀態。
該文法不是 LR(0) 文法
因為存在沖突狀態: I 4 和 I 7
⑷ SLR(1) 文法:該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中有沖突狀態,沖突可用 FOLLOW 集解決。
該文法不是 SLR(1) 文法。
因為 FOLLOW(S)={a,b,#} ,所以無法解決沖突

3. 計算機科學與技術中編譯原理簡答題

時間有點久記得不太真切,用通俗語言說,希望題主盡量查閱書籍參考資料自行驗證理解。

1、什麼是移進項目,什麼是規約項目

這個是自頂向下和自下向上分析時候用到的。所謂移進就是不處理,所謂規約就是處理,合並,替換。比如當前符合某個正規式左部,就用這個正規式右部替換左部,稱為規約。兩種操作的目的都是為了分析整體是否符合語法樹。

2、請給出生成C語言語句序列的文法(假定s表示任意一個語句,它為終結符)

關於這個,我感覺你描述的不是很清楚,因為C語言文法包含的正規式還是挺多的,如果單指statement的話,
statement_listà
statement
| statement_list statement

Statementà
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
再配合上相應的終結符。

3、能用上下文無關文法生成正規集嗎?為什麼?

可以。不過無法保證不含沖突。

4、計算first集和follow集對於構造自頂向下的語法分析器有什麼作用?

可以用來排除沖突。例如移進-移進沖突,移進-規約沖突。

5、是否可能存在這樣一個DFA,它的所有狀態都是接受狀態,包括其實狀態,為什麼?

這個愛莫能助,據我的構想是可以的,但是這樣的DFA最終都會成為單一狀態DFA。

4. 編譯原理 A產生空和B的規約在一個項目集里是規約沖突嗎

如果我們把同心的項目集合合並為一,就可能導致沖突,但是這種沖突不會是移進-規約沖突.因為如果存在這種沖突,則意味著對當前輸入符號a,有一個項目[A→α.,a]要求以A→α進行規約,同時又有另一個項目[B→β.aγ,b]要求把a移進.這兩個項目既然同處於合並之後的項目集中,則意味著在合並前,必有某個c使得[A→α.,a]和[B→β.aγ,c]同處於合並前的某一集合中.然而,這又意味著原來的LR(1)項目集就已經存在移進-規約沖突.從而文法不是LR(1)的,這與假設不符.事實上移進-規約沖突不依賴於搜索符號而只依賴於其心,因此,同心集合的合並不會引起新的移進-規約沖突

5. 編譯原理筆記17:自下而上語法分析(4)LR(0)、SLR(1) 分析表的構造

(移進項目就是指圓點右邊是終結符的項目,規約項目指的就是圓點在右部最右端的項目)

LR(0) 文法可以直接通過識別活前綴的 DFA 來構造 LR 分析表

假定 C = {I 0 , I 1 , ... , I n } (aka. LR(0) 項目規范族、DFA 狀態集)

首先為文法產生式進行編號,拓廣文法的產生式要標記為 0(這里就是後面分析表中 rj 的產生式編號 j 的由來)

然後令每個項目集 I k 的下標 k 作為分析器的狀態(行首),包含 S' → .S 的集合下標為分析器的初態(也就是 DFA 的初態,一般都是 0 )。

下面用一個例子來說明 ACTION、GOTO 子表的構造:

SLR(1) 為解決沖突提出了一個簡單的方法:通過識別活前綴的 DFA 和【簡單向前看一個終結符】構造 SLR(1) 分析表。

如果我們的識別活前綴的 DFA 中存在移進-規約沖突、規約-規約沖突,都可以嘗試使用這個方法來解決沖突。(這里說【嘗試】,當然是因為 SLR 也只能解決一部分問題,並不是萬能的靈丹妙葯。。)

這里,我們拿前面那個 LR(0) 解決不了的文法來舉例

該文法不是 LR(0) 文法,但是是 SLR(1) 文法。

觀察上圖 DFA 中的狀態2,想像當我們的自動機正處於這個狀態:次棧頂已經規約為 T 了,棧頂也是當前的狀態 2 ,而當前剩餘輸入為 *。

如果這個自動機不會【往前多看一步】的話,那麼對處於這個狀態的自動機來說,看起來狀態 2 中的移進項目和規約項目都是可選的。這就是移進-規約沖突。

想要解決這個沖突,就輪到【往前多看一步】上場了——把當前剩餘輸入考慮進來,輔助進行項目的選擇:

對其他的沖突也使用同樣的方法進行判斷。

這種沖突性動作的解決辦法叫做 SLR(1) 解決辦法

准備工作部分,與 LR(0) 分析表的構造差不多:同樣使用每個項目集的狀態編號作為分析器的狀態編號,也就同樣用作行下標;同樣使用拓廣文法產生式作為 0 號產生式。

填表也和 LR(0) 類似,唯一的不同體現在對規約項的處理方法上:如果當前狀態有項目 A → α.aβ 和 A → α. ,而次棧頂此時是 α 且讀寫頭讀到的是 a,那麼當且僅當 a∈FOLLOW(A) 時,我們才會用 A → α 對 α 進行規約。

如果構造出來的表的每個入口都不含多重定義(也就是如上圖中表格那樣的,每個格子裡面最多隻有一個動作),那麼該表就是該文法的 SLR(1) 表,這個文法就是 SLR(1) 文法。使用 SLR(1) 表的分析器叫做一個 SLR(1) 分析器。

任意的二義文法都不能構造出 SLR(1) 分析表

例:懸空 else

例:

這里的 L 可以理解為左值,R 可以理解為右值

經過計算可以確定其 DFA 如下圖所示。

在 狀態4 中,由於 "=" 同時存在於 FOLLOW(L) 與 FOLLOW(R) 中,因此該狀態內存在移進-規約沖突,故該文法不是 SLR(1) 文法。

這樣的非二義文法可以通過增加向前看終結符的個數來解決沖突(比如LL(2)、LR(2))但這會讓問題更加復雜,故一般不採用。而二義文法無論向前看多少個終結符都無法解決二義性。

6. 編譯原理 文法題目

首先擴展文法為:
1) S1->S
2) S->aS
3) S->bS
4) S->a
則:
I0 = Closure({S1->.S})={S1->.S,S->.aS,S->.bS,S->.a}
go(I0,S) = Closure({S1->S.})={S1->S.} = I1
go(I0,a) = Closure({S->a.S,S->a.})={S->a.S,S->.aS,S->.bS,S->.a,S->a.} = I2
go(I0,b) = Closure({S->b.S})={S->b.S,S->.aS,S->.bS,S->.a}=I3
go(I2,S) = closure({S->aS.})={S->aS.}=I4
go(I2,a) = Closure({S->a.S,S->a.}) = I2
go(I2,b) = Closure({S->b.S}) =I3
go(I3,S) = Closure({S->bS.}) = {S->bS.} = I5
go(I3,a) = Closure({S->a.S,S->a.}) = I2
go(I3,b) = Closure({S->b.S}) = I3

由圖所示,狀態I2,既有歸約項目(S->a.)又有移近項目(S->.aS,S->.bS,S->.a),產生沖突。當用SRL分析法時,需向前看一步,即求出:
Follow(S) = Follow(S1) = {#}
則,Follow(S)∩{a,b} =∮
故而Action(I2,a) = s2
Action(I2,b) = s3
Action(I2,#) = r4

則構造出srl分析表如下所示:
Action Goto
a b # S
I0 s2 s3 1
I1 acc
I2 s2 s3 r4 4
I3 s2 s3 5
I4 r2 r2 r2
I5 r3 r3 r3

請採納。

熱點內容
javaice 發布:2024-03-29 21:56:37 瀏覽:354
編譯圖書 發布:2024-03-29 21:56:36 瀏覽:331
linux全選vi 發布:2024-03-29 21:55:11 瀏覽:773
艾譜保險箱初始密碼一般是什麼 發布:2024-03-29 21:48:11 瀏覽:824
商家粉腳本 發布:2024-03-29 21:34:57 瀏覽:150
我的世界ec伺服器怎麼獲得 發布:2024-03-29 21:21:44 瀏覽:708
小米4設置限制的訪問 發布:2024-03-29 21:21:10 瀏覽:405
linux向伺服器上傳文件 發布:2024-03-29 21:17:20 瀏覽:928
腳本健康cpu佔用率報警 發布:2024-03-29 21:16:42 瀏覽:254
vivox9什麼配置參數 發布:2024-03-29 21:08:09 瀏覽:936