當前位置:首頁 » 編程軟體 » 編譯原理lr項目集

編譯原理lr項目集

發布時間: 2024-06-06 22:53:59

A. 編譯原理中語法分析的一道問題

LALR我做著做著覺得不對,但SLR還是沒問題的,這道題工程量非常龐大,想必以後也一定有人問,我就簡要的帶過吧,我歸納的解題步驟是:

  1. 構造LR(0)項目集規范族

  2. 求出FOLLOW集

  3. 根據規則圈出sj和rj對應的產生式

  4. 算出goto數

  5. 構造分析表

B. 編譯原理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)就是假如兩個產生式集相同則將它們合並為一個,幾合並同心集。

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

先舉個例子:

}

將其命名為I1。

其他可類似推出。

D. 有關編譯原理

⑴拓廣文法 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,#} ,所以無法解決沖突

E. 編譯原理——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分析器識別的呢?

F. 編譯原理中LR(1) 那個向前搜索符怎麼求的 跪求高手解答 復制粘貼或者答非所問的別來

1、首先第一步就是項目[S』-> . S,],自動生成搜索符],自動生成搜索符],自動生成搜索符,從項目[A->α.Bβ,?]生成項目[B->…,first(β)]。


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

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

H. 編譯原理簡單文法歸約計算

編譯原理中的語法和文法是不一樣的,但卻融會貫通。
在計算機科學中,文法是編譯原理的基礎,是描述一門程序設計語言和實現其編譯器的方法。
文法分成四種類型,即0型、1型、2型和3型。這幾類文法的差別在於對產生式施加不同的限制。
形式語言,這種理論對計算機科學有著深刻的影響,特別是對程序設計語言的設計、編譯方法和計算復雜性等方面更有重大的作用。
多數程序設計語言的單詞的語法都能用正規文法或3型文法(3型文法G=(VN,VT,P,S)的P中的規則有兩種形式:一種是前面定義的形式,即:A→aB或A→a其中A,B∈VN ,a∈VT*,另一種形式是:A→Ba或A→a,前者稱為右線性文法,後者稱為左線性文法。正規文法所描述的是VT*上的正規集)來描述。
四個文法類的定義是逐漸增加限制的,因此每一種正規文法都是上下文無關的,每一種上下文無關文法都是上下文有關的,而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。

熱點內容
android混淆代碼 發布:2024-11-08 05:54:18 瀏覽:947
用什麼做資料庫 發布:2024-11-08 05:54:18 瀏覽:239
rds雲資料庫 發布:2024-11-08 05:54:09 瀏覽:75
加密和黎曼猜想 發布:2024-11-08 05:33:08 瀏覽:419
中央編譯出版社一年的銷售額 發布:2024-11-08 05:32:15 瀏覽:562
c語言結構體位域 發布:2024-11-08 05:31:00 瀏覽:553
androidv7包 發布:2024-11-08 05:26:41 瀏覽:540
停止共享文件夾腳本 發布:2024-11-08 05:20:54 瀏覽:40
查看資料庫的sid 發布:2024-11-08 05:16:47 瀏覽:830
菲斯塔dlxdct是哪個配置 發布:2024-11-08 05:06:09 瀏覽:213