computer-science - 如何将正则表达式转换为 CFG？

Question

如何将正则表达式转换(ab*)*b为上下文无关语法？

当我查找示例时，我一直在表达式中看到加号，但我没有。这只是一种不同的写作方式吗？

标签： computer-sciencecontext-free-grammarcomputation-theory

Answer 1

您可以递归地应用以下规则，每个规则将单个正则表达式运算符更改为非终结符。（为每个运算符使用不同的非终结符名称。）在下面，R和S是正则表达式运算符的操作数的翻译；N是这个运算符被翻译成的非终结符。终端简单地通过不变。

1. 级联：

   R S ⇒   N → R

2. 交替：

   R | S ⇒ N → R
           N → S

3. 克莱恩明星：

   R* ⇒    N → ε
           N → N R

4. 克莱恩加：

   R+ ⇒    N → R
           N → N R

5. 可选的：

   R? ⇒    N → ε
           N → R

例如，

Regex               Transform          Productions
(a b* )*b           3. b* ⇒ N1          N1 → ε
                                       N1 → N1 b
( aN1 )*b           1. aN1 ⇒ N2         N2 → a N1
N2* b               3. N2* ⇒ N3         N3 → ε
                                       N3 → N3 N2
N3b                 1. N3b ⇒ N4         N4 → N3 b