解释无用符号的去除

并非所有语法都是最佳的，这意味着语法可能包含一些额外的符号（非终结符），这些符号会增加语法的长度。

因此，我们必须通过去除这些无用符号来简化语法。

属性

下面解释了简化语法的属性：

• 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+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习