CFG 简化
在 CFG 中，可能会出现不需要所有产生式规则和符号来导出字符串的情况。此外，还可能存在一些空产生式和单元产生式。消除这些产生式和符号称为CFG 的简化。简化主要包括以下步骤 -
- 减少CFG
- 移除单位产品
- 删除空产生式
减少CFG
CFG 分两个阶段减少 -
第 1 阶段-从 CFG G派生等效语法G'，以便每个变量派生一些终端字符串。
推导过程-
步骤 1 - 包括导出某个终端并初始化i=1的所有符号W 1。
步骤 2 - 包括导出Wi 的所有符号Wi +1。
步骤 3 - 增加i并重复步骤 2，直到Wi +1 = Wi。
步骤 4 - 包括所有包含W i的产生式规则。
第 2 阶段-从 CFG G'推导等效语法G”，使得每个符号都以句子形式出现。
推导过程-
步骤 1 - 将起始符号包含在Y 1中并初始化i = 1。
步骤 2 - 包括可以从Y i导出的所有符号Y i+1并包括已应用的所有产生规则。
步骤 3 - 增加i并重复步骤 2，直到Y i+1 = Y i。
问题
找到与语法 G 等价的简化语法，具有产生式规则 P：S → AC | B、A → a、C → c | BC、E → aA | e
解决方案
第一阶段-
T = { a, c, e }
W 1 = { A, C, E } 根据规则 A → a, C → c 和 E → aA
W 2 = { A, C, E } U { S } 根据规则 S → AC
W 3 = { A, C, E, S } U ∅
由于 W 2 = W 3，我们可以将 G' 推导为 -
G' = { { A, C, E, S }, { a, c, e }, P, {S}}
其中 P：S → AC，A → a，C → c，E → aA | e
第 2 阶段-
Y 1 = { S }
Y 2 = { S, A, C } 根据规则 S → AC
Y 3 = { S, A, C, a, c } 根据规则 A → a 和 C → c
Y 4 = { S, A, C, a, c }
由于 Y 3 = Y 4，我们可以推导出 G” 为 -
G” = { { A, C, S }, { a, c }, P, {S}}
其中 P：S → AC，A → a，C → c
移除单位产品
任何形式为 A → B 的生产规则，其中 A, B ∈ 非终结符称为单位生产。。
移除程序 -
步骤 1 - 要删除A → B，每当语法中出现B → x 时，将产生式 A → x添加到语法规则中。[x ∈ Terminal, x 可以为 Null]
步骤 2 -从语法中删除A → B。
步骤 3 - 重复步骤 1，直到删除所有单位产品。
问题
从以下内容中删除单位生产 -
S → XY，X → a，Y → Z | b，Z → M，M → N，N → a
解决方案-
语法中有 3 个单元产生式 -
Y→Z、Z→M、M→N
首先，我们将删除 M → N。
当 N → a 时，我们添加 M → a，并删除 M → N。
生产集变为
S → XY，X → a，Y → Z | b，Z→M，M→a，N→a
现在我们将删除 Z → M。
当 M → a 时，我们添加 Z→ a，并删除 Z → M。
生产集变为
S → XY，X → a，Y → Z | b、Z → a、M → a、N → a
现在我们将删除 Y → Z。
当 Z → a 时，我们添加 Y→ a，并删除 Y → Z。
生产集变为
S → XY，X → a，Y → a | b、Z → a、M → a、N → a
现在 Z、M 和 N 无法访问，因此我们可以删除它们。
最终的 CFG 是免费的单位生产 -
S → XY，X → a，Y → a | 乙
删除空产生式
在 CFG 中，如果存在产生式A → ε或存在从A开始并最终以
ε: A → .... → ε
移除程序
步骤 1 - 找出导出 ε 的可空非终结变量。
步骤 2 - 对于每个产生式A → a，构造所有产生式A → x，其中x是通过从步骤 1 中删除一个或多个非终结符从'a'获得的。
步骤 3 - 将原始产生式与步骤 2 的结果相结合并删除ε-产生式。
问题
从以下内容中删除空产生式 -
S → ASA | 乙 | b，A → B，B → b | ε
解决方案-
有两个可为 null 的变量 - A和B
首先，我们将删除 B → ε。
移除B → ε后，产生式集变为 -
S→ASA | 乙 | 乙| a, A ε B | 乙| ε, B → b
现在我们将删除 A → ε。
移除A → ε后，产生式集变为 -
S→ASA | 乙 | 乙| 一个 | 南澳 | 作为| S，A→B| b, B → b
这是没有空转换的最终生产集。