简化上下文无关语法
原文:https://www . geesforgeks . org/simplified-context-free-grammars/
上下文无关语法(CFGs)的定义允许我们开发各种各样的语法。很多时候，一些氯氟化碳的生产是无用的和多余的。出现这种情况是因为氟氯化碳的定义并没有限制我们进行这些多余的生产。
通过简化 CFG，我们从一个语法中移除了所有这些冗余产物，同时保持转换后的语法与原始语法等价。如果两种语法产生相同的语言，它们被称为等价语法。简化 CFG 是必要的，以便以后将它们转换为普通形式。
冗余产品的类型和删除它们的过程如下。 1。无用的作品-永远不能参与任何弦的推导的作品，被称为无用的作品。类似地，永远不能参与任何字符串推导的变量称为无用变量。例如
S -> abS | abA | abB
A -> cd
B -> aB
C -> dc
在上面的例子中，生产“C -> dc”是无用的，因为变量“C”永远不会出现在任何字符串的派生中。其他产品的编写方式使得变量“C”永远无法从起始变量“S”到达。
生产“B ->aB”也是无用的，因为它永远不会终止。如果它永远不会终止，那么它永远不会产生一个字符串。因此，产品永远不能参与任何推导。
为了删除无用的产品，我们首先找到所有的变量，这些变量永远不会导致一个终端字符串，如变量“B”。然后，我们移除变量“B”出现的所有产品。 所以修改后的语法变成–
S -> abS | abA
A -> cd
C -> dc
然后，我们尝试识别从起始变量(如变量‘C’)永远无法到达的所有变量。然后，我们移除变量“C”出现的所有产品。 下面的语法现在没有无用的产物了–
S -> abS | abA
A -> cd
2。λ生产–类型‘A->λ’的生产称为λ生产(也称为λ生产和零生产)。这些产品只能从那些不生成λ(空字符串)的语法中移除。语法可能包含空结果，但不会产生空字符串。
要删除空生产，我们首先必须找到所有可为空的变量。如果λ可以从“A”中导出，则变量“A”称为可空的。对于类型为“A -> λ”的所有产品，“A”是一个可空变量。对于类型“B -> A1A2…An”的所有产品，其中所有“Ai”都是可空变量，“B”也是可空变量。
找到所有可空变量后，我们现在可以开始构建空生产自由语法。对于原始语法中的所有生成，我们添加原始生成以及通过用λ替换生成中的可空变量而形成的所有生成组合。如果产品的 RHS 上的所有变量都可以为空，那么我们不会在新语法中添加“A -> λ”。举个例子就能说明问题。考虑语法–
S -> ABCd (1)
A -> BC (2)
B -> bB | λ (3)
C -> cC | λ (4)
让我们首先找到所有可空变量。变量“B”和“C”显然是可空的，因为它们在其产品的 RHS 中包含“λ”。变量“A”也是可空的，因为在(2)中，RHS 上的两个变量也是可空的。同样，变量“S”也是可空的。所以变量‘S’、‘A’、‘B’和‘C’都是可空变量。
让我们创建新的语法。我们从第一部作品开始。按原样添加第一个产品。然后我们创建所有可能的组合，这些组合可以通过用λ替换可空变量来形成。因此，第(1)行现在变成了' S -> ABCd | ABd | ACd | BCd | Ad | Bd |Cd | d '。我们对第(2)行应用了相同的规则，但是我们没有添加“A -> λ”，即使它是一个可能的组合。我们删除所有类型为“V -> λ”的产品。新语法现在变成–
S -> ABCd | ABd | ACd | BCd | Ad | Bd |Cd | d
A -> BC | B | C
B -> bB | b
C -> cC | c
3。单元生产–类型为“A - > B”的产品称为单元生产。 要从原始语法“G”创建单位生产自由语法“Guf”，我们遵循下面提到的程序。
先把《高夫》中的“G”的所有非单元作品加起来。然后对于语法“G”中的每个变量“A”，找出所有变量“B”，使得“A *=> B”。现在，对于像“A”和“B”这样的所有变量，将“A -> x1 | x2 | …xn”添加到“Guf”中，其中“B -> x1 | x2 | …xn”在“Guf”中。x1，x2 … xn 都不是单变量，因为我们在‘Guf’中只增加了非单位产量。因此，生成的语法是无单位生产的。例如
S -> Aa | B
A -> b | B
B -> A | a
让我们把《孤》中所有的非单元作品加起来。“Guf”现在变成–
S -> Aa
A -> b
B -> a
现在我们找到所有满足‘X * = > Z’的变量。这些是‘S * = > B’、‘A * = > B’和‘B * = > A’。对于‘A * = > B’，我们添加‘A-> A’，因为‘B-> A’存在于‘Guf’中。“孤”现在变成了
S -> Aa
A -> b | a
B -> a
对于‘B * = > A’，我们添加‘B-> B’，因为‘A-> B’存在于‘Guf’中。新语法现在变成
S -> Aa
A -> b | a
B -> a | b
我们对“S*=>B”执行相同的步骤，最终得到以下语法–
S -> Aa | b | a
A -> b | a
B -> a | b
现在去掉 B -> a|b，因为它没有出现在生产‘S’中，那么下面的语法就变成了，
S->Aa|b|a
A->b|a
注意:要删除上述各种生产，先删除空生产，再删除单位生产，最后删除无用生产。遵循这个顺序对于获得正确的结果非常重要。
本文由 Nitish Joshi 供稿。如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
