将正则表达式转换为 CFG

Question

如何将一些常规语言转换为其等效的上下文无关语法？ 是否有必要构建与该正则表达式相对应的DFA，或者这种转换是否有某种规则？

例如，考虑以下正则表达式

01+10(11)^*

我该如何描述上面RE对应的语法？

Answer 1

• 将A+B改为语法

  <前><代码>G ->一个
  G->乙

• 将 A* 更改为

  <前><代码>G -> （空的）
  G->股份公司

• 将 AB 更改为

  <前><代码>G -> AB

并对 A 和 B 进行递归处理。基本情况是空语言（无产生式）和单个符号。

在您的情况下

 A -> 01
 A -> 10B
 B -> (empty)
 B -> 11B

如果语言是由有限自动机描述的：

• 使用状态作为非终结符号
• 使用语言作为终结符号
• 集添加转换 p -> aq 对于任何转换 p ->原始自动机中字母 a 上的 q
• 使用初始状态作为语法中的初始符号

Answer 2

我猜你的意思是用 V->w 形式的规则将其转换为正式语法，其中 V 是非终结符，w 是终结符/非终结符字符串。首先，您可以简单地说（混合 CFG 和正则表达式语法）：

S -> 01+10(11)*

其中 S 是开始符号。现在让我们稍微分解一下（为了清晰起见，添加空格）：

S -> 0 A 1 0 B
A -> 1+
B -> (11)*

关键是将 * 和 + 转换为递归。首先，我们将通过插入接受空字符串的中间规则将 Kleene 星号转换为加号：

S -> 0 A 1 0 B
A -> 1+
B -> (empty)
B -> C
C -> (11)+

最后，我们将 + 表示法转换为递归：

S -> 0 A 1 0 B
A -> 1
A -> A 1
B -> (empty)
B -> C
C -> 11
C -> C 11

要处理 x?，只需将其拆分为生成空的规则和生成 x 的规则。

Answer 3

实际上，不同的CFG语法可以产生相同的语言。因此，给定一个正则表达式（正则语言），它映射回 CFG 不是唯一的。

当然，您可以构造一个产生给定正则表达式的 CFG。上面的答案展示了实现这一目标的一些方法。

希望这能给您一个高层次的想法。

Answer 4

对于示例，以下语法是等效的：

S -> 01|10A
A -> 11A|empty