在消除左遞歸的過(guò)程中，我們需要將一個(gè)左遞歸的非終結(jié)符A的產(chǎn)生式改寫(xiě)為一系列不含A的產(chǎn)生式。這個(gè)過(guò)程中，我們需要將形如A -> Aα的產(chǎn)生式改寫(xiě)為A -> β1A | β2A | ... | βkA | γ1 | γ2 | ... | γm，其中β1, β2, ..., βk均為不以A開(kāi)頭的產(chǎn)生式，而γ1, γ2, ..., γm均為不含A的產(chǎn)生式。

對(duì)于每個(gè)βi，我們需要將其改寫(xiě)為不含A的形式。這時(shí)候，我們會(huì)引入一個(gè)新的非終結(jié)符B，然后將βi改寫(xiě)為Bα'的形式，其中α'是βi中A后面的部分。這樣，我們就得到了一個(gè)新的產(chǎn)生式A -> Bα' A'，其中A'表示A的其他產(chǎn)生式。接下來(lái)，我們將B的產(chǎn)生式中所有以A開(kāi)頭的產(chǎn)生式用A -> Bα' A'代替，這樣就消除了A的左遞歸。

在這個(gè)過(guò)程中，β是不斷縮小的，因?yàn)槊看挝覀兌际菍ⅵ耰改寫(xiě)為Bα'的形式，并將B的產(chǎn)生式代入到原來(lái)的產(chǎn)生式中，直到βi不再以A開(kāi)頭為止。因此，β最終會(huì)縮小到一個(gè)不以A開(kāi)頭的產(chǎn)生式，也就是1。因此，在消除左遞歸的推導(dǎo)過(guò)程中，β始終是1。

以上是由福州網(wǎng)站建設(shè)的小編為你分享了"編譯原理中消去左遞歸的推導(dǎo)中β應(yīng)該是冪越來(lái)越大，為什么始終是1呢"文章，如果你在這方面有什么問(wèn)題，隨時(shí)聯(lián)系我們