解釋無用符號的去除

並非所有語法都是最佳的，這意味著語法可能包含一些額外的符號（非終結符），這些符號會增加語法的長度。

因此，我們必須透過去除這些無用符號來簡化語法。

屬性

下面解釋了簡化語法的屬性：

• G的每個非終結符和終結符都出現在L中某個單詞的推導中。
• 不應該有任何形如X→Y的產生式，其中X和Y是非終結符。
• 如果ε不在語言L中，則在產生式X→ε中不需要ε。

簡化語法的用途如下：

定義

如果存在形如以下的推導，則符號X是有用的：

S =>* aXb =>* w

否則，符號X是無用的。請注意，在推導中，最終我們應該得到一個終結符字串，並且所有這些符號都必須可以從起始符號S到達。

在推導中根本沒有使用的符號和產生式是無用的。

示例

考慮以下去除符號的示例：

S->aAa|bBb| ε
A->C|a
B->C|b
C->CDE| ε
D->A|B|ab

給定語法中無用的符號是E。因為E不在右端(RHS)出現。

去除無用符號後，產生式如下：

S->aDa|bDb
D->a|b|ab

Bhanu Priya

更新於：2021年6月12日

6K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習