編譯原理lr0狀態轉換圖

1. 編譯原理中，LR(0)文法的項目集規范族的I0,I1,I2,I3…………是怎麼求的～

先舉個例子：

}

將其命名為I1。

其他可類似推出。

2. LR分析法的LR(0)分析表的構造

顧名思義，LR(0)分析就是LR(K)分析當K=0的情況，亦即在分析的每一步，只要根據當前的棧頂狀態 (或者說根據當前分析棧中已移進或歸約出的全部文法符號)就能確定應採取何種分析動作，而無須向前查看輸入符號。
為了給出構造LR分析表的演算法，我們首先需要引入一些非常重要的概念和術語。 由例4?6對輸入串「a,b,a」的分析過程容易看出，如果所分析的輸入串沒有語法錯誤，則在分析的每一步，若將分析棧中已移進和歸約出的全部文法符號與余留的輸入符號串拼接起來，就形成了所給文法的一個規范句型。換言之，也就是在分析的每一步，如輸入串已被掃視的部分無語法錯誤，則當前分析棧中的全部文法符號應當是某一規范句型的前綴。而且還不難看出，此種規范句型的前綴決不會含有句柄右邊的任何符號，這是因為一旦句型的句柄在棧的頂部形成，將會立即被歸約之故。以後，我們將把規范句型具有上述性質 (即不含句柄之右的任何符號)的前綴稱為它的活前綴。例如，對於文法G[L]的規范句型「E,b,a」 (見表412分析過程第5步)，其句柄為「b」，棧中的符號串為「E，b」，此句型的活前綴為ε，「E」，「E，」，「E,b」等。
由此可見，一個LR分析器的工作過程，實質上也就是一個逐步產生 (或識別)所給文法的規范句型之活前綴的過程。同時，在分析的每一步，分析棧中的全部文法符號 (如果輸入串無語法錯誤)應是當前規范句型的活前綴，並且與此時的棧頂狀態相關聯。因此，我們自然會想到，如果能構造一個識別所給文法的所有活前綴的有限自動機，那麼就能很方便地構造出相應的LR分析表來。稍後我們將討論這一問題。 上面我們已經說過，在一個規范句型的活前綴中決不含有句柄右邊的任何符號。因此，活前綴與句柄的關系不外下述三種情況：
(1) 其中已含有句柄的全部符號 (句柄的最右符號即為活前綴的最右符號)；
(2) 其中只含句柄的一部分符號 (句柄開頭的若干符號與活前綴最右的若干個符號一致)；
(3) 其中全然不含有句柄的任何符號。
第一種情況表明，此時某一產生式A→β的右部符號串β已出現在棧頂，因此相應的分析動作應是用此產生式進行歸約。第二種情況意味著形如A→β1β2的產生式的右部子串β1已出現於棧頂，正期待著從余留輸入串中看到能由β2推出的符號串。而第三種情況則意味著期望從余留輸入串中能看到由某一產生式A→α的右部，即α所推出的符號串。為了刻畫在分析過程中，文法的一個產生式右部符號串已有多大一部分被識別，我們可在該產生式的右部的某處加上一個圓點「·」來指示位置。例如，對於上述三種情況，標有圓點的產生式分別為A→β·，A→β1·β2以及A→·α。我們把右部某位置上標有圓點的產生式稱為相應文法的一個LR(0)項目。特別，對形如A→ε的產生式，相應的LR(0)項目為A→·。顯然，不同的LR(0)項目反映了分析過程中棧頂的不同情況。下面我們就會看到，文法的全部LR(0)項目，將是構造識別其全部活前綴的有限自動機的基礎。 在作出文法的全部LR(0)項目之後，現在用它們來構造識別全部活前綴的DFA。這種DFA的每一個狀態由若干個LK(0)項目所組成的集合 (稱為項目集)來表示。下面以例4?7所給出的文法為例來說明構造此種DFA的方法。
首先，我們用I0表示這個DFA的初態，它預示著分析過程的開始，並且期待著將給定的輸入符號串逐步歸約為文法的開始符號S′。或者反過來說，我們所期待的是，從使用產生式S′→S開始，能夠逐步推導出所給的輸入符號串。因此，我們應將項目S′→·S列入狀態I0中。換言之，也就是我們期待著將要掃視的輸入串正好就是能由S推出的任何終結符號串。然而，由於不能從輸入串中直接讀出非終結符號S，因此我們也應當把項目S→·A以及S→·B列入到I0中。由於A和B同樣是非終結符號，所以又應當將A→·aAb，A→·c和B→·aBb，B→·d列入I0中。由於最後列入I0的項目中，圓點之後都是終結符號，故I0已經「封閉」，構造項目集I0宣告結束。這樣，表示初態的項目集I0由如下的項目組成：
I0: S′→·SS→·AA→·aAb
S→·BB→·aBbB→·d
A→·c
我們將項目S′→·S稱為項目集I0的基本項目。上述從項目S′→·S出發構造項目集I0的過程，可用一個對其基本項目集{S′→·S}的閉包運算，即CLOSURE({S′→·S})來表示。一般地，設I為一項目集，則構造I的閉包CLOSURE(I)的演算法如下：
(1) I中每一項目都屬於CLOSURE(I)；
(2) 若形如A→α·Xβ的項目屬於CLOSURE(I)，且X為非終結符號，則文法中任何X產生式的一切圓點在最左邊的項目X→·γ也都屬於CLOSURE(I)；
(3) 重復上述過程，直至不再有新的項目加入CLOSURE(I)為止。
有了初態I0之後，我們來說明如何確定從I0可能轉移到的下一個狀態。設X為一個文法符號 (終結符號或非終結符號)，若I0中有圓點位於X左邊的項目A→α·Xβ (其中α可以為ε)，則當分析器從輸入串識別出 (即移進或歸約出)文法符號X後，分析器將進入它的下一個狀態。設此狀態為Ii，顯然Ii中必含有全部形如A→αX·β的項目，我們將這樣的項目稱為A→α·Xβ的後繼項目。對於每一文法符號X，如果存在這樣的後繼項目，則可能不止一個，設其組成的集合為J,J中的每個項目也就是項目集Ii的基本項目。因此，按照與上面構造項目集I0相類似的討論，我們就有
Ii=CLOSURE(J)
為了指明Ii是「I0關於文法符號X的後繼狀態」這一事實，我們可定義一個狀態轉移函數
GO(I,X)=CLOSURE(J)
其中，I為當前狀態，X為文法符號，J為I中所有形如A→α·Xβ的項目的後繼項目所組成的集合，而CLOSURE(J)就是項目集I (即狀態I)關於X的後繼項目集 (即後繼狀態)。例如，對於上例，我們有：
I1=GO(I0,S)=CLOSURE({S′→S·})={S′→S·}
I2=GO(I0,A)=CLOSURE({S→A·})={S→A·}
I3=GO(I0,B)=CLOSURE({S→B·})={S→B·}
I4=GO(I0,a)=CLOSURE({A→a·Ab,B→a·Bb})=
{A→a·Ab, B→a·Bb, A→·aAb, B→·aBb, A→·c, B→·d}
I5=GO(I0,c)=CLOSURE({A→c·})={A→c·}
I6=GO(I0,d)=CLOSURE({B→d·})={B→d·}
請注意，由於I0中無圓點在b之前的項目，故GO(I0,b)無定義。這樣，我們求出了I0的全部後繼項目集I1,I2,I3,I4,I5,I6。容易看出，由於I1,I2,I3,I5,I6諸項目集中的項目均無後繼項目，因此它們都沒有後繼狀態。對於項目集I4，我們再仿此求出它的後繼狀態，這些後繼狀態是：
I7=GO(I4,A)=CLOSURE({A→aA·b})={A→aA·b}
I9=GO(I4,B)=CLOSURE({B→aB·b})={B→aB·b}
此外，由於
GO(I4,a)=I4GO(I4,c)=I5GO(I4,d)=I6
故它們均不產生新的項目集。最後，再求出I7,I9的後繼項目集。它們分別是
I8=GO(I7,b)=CLOSURE({A→aAb·})={A→aAb·}
I10=GO(I9,b)=CLOSURE({B→aBb·})={B→aBb·}
由於I8和I10已無後繼項目集，所以至此我們已求出所給文法G[S]的全部項目集I0~I10，通常，我們將這些項目集的全體稱為文法G[S]的LR(0)項目集規范族，並記為
C={I0,I1,I2,I3,…,I10}
於是，我們所要構造的識別文法G[S]全部活前綴的DFA為
M=(C,V,GO,I0,C)
其中： M的狀態集也就是文法的LR(0)項目集規范族C={I0,I1,…,I10}；
M的字母表也就是文法的字匯表V={S′，S，A，B，a,b,c,d}；
M的映像也就是如上定義的狀態轉換函數GO；
M的終態集也是C，這表明M的每一狀態都是它的終態。
對於上述文法G[S]，如上構造的識別其全部活前綴的DFA的狀態轉換圖如圖416所示。
由於狀態轉換圖416中的每一個狀態都是終態，因此在上述DFA工作的過程中，從初態I0出發，沿著有向邊所指示的方向前進，可以使DFA在所經歷的任何狀態上中止它的工作。當DFA到達某一狀態時，我們把從初態I0出發，到達該狀態所經過的全部有向邊上的標記符號依次連接起來，就得到了DFA在到達該狀態時，所識別出的某規范句型的一個活前綴。例如：當上述DFA處於初態I0時，它所識別的活前綴為ε；當M處於狀態I3時，它所識別的活前綴為B；當M處於I4時，它所識別的活前綴為aa*；而達到I9時，它所識別的活前綴為aa*B等等。需要注意的是，對那些只含有歸約項目的項目集，即M的I1,I2,I3,I5,I6,I8和I10，當M到達這些狀態時，表明活前綴中已含有相應句柄的全部符號 (即句柄已在棧頂形成)，因此，我們將這些狀態稱為句柄識別狀態。特別是當M處於狀態I1時，M所識別的活前綴為S，這意味著已將所給的輸入串歸約為S，如果再按產生式S′→S歸約一步，就得到了拓廣文法G′的開始符號S′。因此，我們將狀態I1稱為「接受狀態」，它預示著對輸入串的分析已成功地完成。
對於一個給定文法G的拓廣文法G′，當識別它的全部活前綴的DFA作出之後，我們就可據此構造相應的LR(0)分析表了。然而，應當首先注意的是，用前述方法所構造的每一個LR(0)項目集，實質上表徵了在分析過程中可能出現的一種分析狀態；再根據前面對LR(0)項目的分類，項目集中的每一個項目又與某一種分析動作相關聯，因此，我們自然會提出這樣的要求，即每一項目集中的諸項目應當是相容的。所謂相容，是指在一個項目集中，不出現這樣的情況：
(1) 移進項目和歸約項目並存；
(2) 多個歸約項目並存。
如果一個文法G滿足上述條件，也就是它的每個LR(0)項目集中都不含沖突項目，則稱G為LR(0)文法。顯然，只有當一個文法是LR(0)文法時，才能構造出不含沖突動作的LR(0)分析表來。
從前面的討論和分析，我們將不難得出構造LR(0)分析表的演算法。為方便起見，我們用整數0，1，2，…表示狀態I0,I1,…，而且如表411那樣，也將GOTO子表中有關終結符號的各列並入ACTION子表相應的各列中去，此外，演算法中形如sj和rj等記號的含義同前，此演算法如下：
(1) 對於每個項目集Ii中形如A→α·Xβ的項目，若GO(Ii,X)=Ij，且X為一終結符號a時，置ACTION[i,a]=sj。但若X為非終結符號時，則僅置GOTO[i,X]=j。
(2) 若歸約項目A→α·屬於Ii，設A→α為文法的第j個產生式，則對文法的任何終結符號或句子的右界符# (將它們統一地記為a)，置ACTION[i,a]=rj。
(3) 若接受項目S′→S·屬於Ii，則置ACTION[i,#]=acc。
(4) 在分析表中，凡不能按上述規則填入信息的元素，均置為「出錯」。

3. 編譯原理偶數個0和偶數個1轉換圖

嘛，差不多就是這樣了。思路是分析所有0和1的組合畫出存在的狀態，然後判斷轉移條件，找出可接受的狀態。

4. 編譯原理lr0和slr1的區別

語法分析有自上而下和自下而上兩種分析方法其中自上而下：遞歸下降，LL(1)自下而上：LR(0),SLR(1),LR(1),LALR(1)

LR需要構造一張LR分析表，此表用於當面臨輸入字元時，將它移進，規約（即自下而上分析思想），接受還是出錯。
LR(0)找出句柄前綴，構造分析表，然後根據輸入符號進行規約。 SLR(1)使用LR(0)時若有沖突，不知道規約，移進，活移進哪一個，所以需要向前搜索，則只把有問題的地方向前搜索一次。 LR(1)1.在每個項目中增加搜索符。2.舉個列子如有A->α.Bβ，則還需將B的規則也加入。 LALR(1)就是假如兩個產生式集相同則將它們合並為一個，幾合並同心集。

5. 編譯原理 語法

編譯原理不同教材用的表示不太一樣，翻譯也五花八門，我不是很確定你這個活前綴是什麼意思。我按我知道的告訴你，我用「。」表示狀態的位置，你的書上可能通常是一個黑點表示，先要建立文法的狀態集合：
S1：S->。a
S2：S->a。
S3：S->。^
S4：S->^。
S5：S->。(T)
S6：S->(。T)
S7：S->(T。)
S8：S->(T)。
S9：T->。T,S
S10：T->T。,S
S11：T->T,。S
S12：T->T,S。
S13：T->。S
S14：T->S。
歸集狀態，和狀態轉換關系（這應該是要畫成圖的，這里沒法畫。。。）用I表示
I0：S1 S3 S5 S9 S13
輸入a，I0->I1
I1：S2
輸入^，I0->I2
I2：S4
輸入(，I0->I3
I3：S6 S9 S13 S1 S3 S5
歸約S，I0->I4
I4：S14
歸約T，I0->I5
I5：S10
歸約T，I3->I6
I6：S7
輸入)，I6->I7
I7：S8
輸入,，I5->I8
I8：S11 S1 S3 S5
歸約S，I8->I9
I9：S12
輸入a，I8->I1
輸入^，I8->I2
輸入(，I8->I3
輸入a，I3->I1
輸入^，I3->I2
輸入(，I3->I3
然後你要建立狀態轉換表，網路不能畫表格。。。，你將就看看( $是結束符啊.還有你的文法沒有開始，即S')
先把題目中的規則編個號：
(1) S->a
(2) S->^
(3) S->(T)
(4) T->T,S
(5) T->S
action goto
狀態集 a ^ ( ) , $ S T
0 s1 s2 s3 14 10
1 acc
2 acc
3 s1
因為沒有S'不知道最終怎麼規約

6. 程序設計語言編譯原理試題，有會做的嗎

要求1、寫一個順序控製程序，要求輸出一個控制字，就必須查詢相應的一種輸入最好又每一步驟的說明，十分感謝！ DLX語言?

7. 編譯原理 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

8. 編譯原理——LR分析表

自底向上的語法分析

LR分析表的結構如上，其分為兩個部分 Action Goto

兩個參數狀態i，終結符號a（s(i)代表第i個狀態，r(i)代表第i條表達式）

Goto[i,A]=j

文法

容易得知這個文法可以推出 0 1 00 01 等的字元串。因為它是 左遞歸 。不適用於 LL 文法分析，只能使用 LR 分析。

因為本題入口有兩個—— S → L·L S → L ，所以需要構造額外的產生式 S'->S

2.1 第一次遍歷

我們從 [S -> . L·L] 開始，構造這個狀態的閉包，也就是加上所有能從這個產生式推出的表項。

首先，判斷 . 後面是否為 非終結符號A 。如果是，那我們就得找所有由 A-> 推出的產生式，並將它們添加進入 閉包 里(也就是State包里)。循環做即可。

因此我們可以得到 State 0 有

下一步，就是我的 . 往下一位移動。對每個符號X後有個 . 的項，都可以從 State 0 過渡到其他狀態。

由以上6條式子可以得知下一位符號可以是 S L B 0 1 。所以自然可以得到5個狀態。

State 1 是由 State 0 通過 S 轉移到這里的，所以我們找出所有 State 0 中在 S 前有 . 的項。

此狀態作為結束狀態 Accept ，不需要繼續狀態轉移了。

State 2 是由 State 0 通過 L 轉移到這里的，所以我們找出所有 State 0 中在 L 前有 . 的項。

S -> . L·L S -> . L L -> . LB

有3條式子，現在我們將 . 向後推一格，就得到 State 1 的項了。

但是 . 之後的符號分別是 · $ B ， B 為非終結符號，我們得包含 B -> 的項

State 3 是由 State 0 通過 B 轉移到這里的，所以我們找出所有 State 0 中在 B 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

State 4 是由 State 0 通過 0 轉移到這里的，所以我們找出所有 State 0 中在 0 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

很簡單，同樣的道理找 State 5

State 5 是由 State 0 通過 1 轉移到這里的，所以我們找出所有 State 0 中在 1 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

好的，現在我們第一次遍歷完成。

2.2 第二次遍歷

第二次遍歷自然從 State 2 開始。

我們回到 State2 ，可以看出 . 之後的符號有 · B 0 1 。

State 6 是由 State 2 通過 · 轉移到這里的，所以我們找出所有 State 2 中在 · 前有 . 的項。

S -> L. ·L 只有1條，我們往後移發現 L 又為非終結符號，參考 State 0 做的操作，我們得找出所有的式子。

共有5條式子，共同組成 State 6 ，由上面的式子可以看出我們還得繼續下一次遍歷。先不管著，我們進行下一次狀態查找。

State 7 是由 State 2 通過 B 轉移到這里的，所以我們找出所有 State 2 中在 B 前有 . 的項。

L -> L. B 也是只有1條，我們往後移發現沒有非終結符號了，那就不需要再繼續添加其他式子了。

這個狀態也不需要繼續進行轉移了。

接下來很關鍵，因為我們通過 State2 的 . 後的符號找出了 State 6 State 7 ，接下來還差符號 0 1 ，那麼是否像之前一樣按例添加狀態呢， 答案是不是的 ，因為我們發現通過 0 1 找到的閉包集分別是 B -> 0 B -> 1 ，這與我們的之前的 State 4 State 5 相同。所以我們得將其整合起來，相當於 State 2 通過 0 1 符號找到了 State 4 State 5 狀態。

2.3 第三次遍歷

回頭看第二次遍歷，可以看出只有 State 6 可以進行狀態轉移了。

那麼就將 State 6 作為第三次遍歷的源頭，可以看出 . 之後的符號有 L B 0 1 。

State 8 是由 State 6 通過 L 轉移到這里的，所以我們找出所有 State 6 在 L 前有 . 的項。

S -> L· .L L -> . LB 有兩條式子，往後移發現有非終結符號 B ，所以經過整合可以得到

可以看出 . 的後面還有一個符號，所以這里我們還得再進行一次遍歷。

接下來，又是遇到重復的包的情況，可以看出我們由 State 6 通過 B 0 1 得到的閉包分別是 L->B B->0 B->1 ，很明顯，這分別對應於 State 3 State 4 State 5 。

第三次遍歷也就結束了。

2.4 第四次遍歷

回看第三次遍歷，可以看出只有 State 8 可以進行狀態轉移，其 . 之後的符號分別是 B 0 1 。

誒，感覺很熟悉，就是上面幾行剛說的情況，也就是說通過這三個符號找到的閉包是我們之前遇到的狀態，分別是 State 3 State 4 State 5 。

做到這里，我們發現我們已經全部遍歷完畢！

總共有8個狀態，通過以上流程做成個圖是什麼樣子的？來看看！

這么一看就很清晰明了了，我們就可以通過這個圖做出我們的 LR分析表

其實就是我們之前呈現的表

在狀態 I2 和 I8 中，既有 移入 項目，也有 規約 項目，存在 移入 - 規約的沖突 ，所以不是 LR(0) 文法，但是因為 FOLLOW(S) ∩ {0, 1} = ∅，所以可以用 FOLLOW 集解決沖突，所以該文法是 SLR(1) 文法。

上表我們發現還有 r1，r2，r3 等。這個其實就是代表狀態停止轉移時為 第幾條表達式 ，r3代表第三條表達式 L -> LB 。

當我們構建了表之後，我們如何運用起來呢？

下面我們通過一個例子來說明

以上字元串是如何被SLR分析器識別的呢？

9. 求大神指導編譯原理的狀態轉換圖怎麼畫

這里你要弄清子集法中，每一行，指的是變遷。比如第一行，代表狀態0，畫一根線到狀態1，因此第1個0是指這個變遷的起點狀態0，第3個1是指變遷的終點狀態1。

同理，第2行是指從狀態1出發，有2個變遷，即第一個是狀態1指向狀態1（自己），第2個變遷是從狀態1到狀態1和2。

這樣第3行就表示如果從狀態{1，2}開始，輸入是0和1時的變遷分別是什麼，依此類推。
你紅的圈出來的就是NFA所有可能的狀態和狀態組合。