regex - 将任何正则表达式转换为右线性正则语法的算法

Question

是否有一种算法可以将任何正则表达式转换为正确的线性语法？我熟悉将简单正则表达式转换为 CFG 的算法。右线性语法有更严格的规则。A -> a B 或 A -> a 。这使得构建算法变得困难。

score 3 · Accepted Answer

有一种算法方法可以将正则表达式 (RE) 转换为非确定性有限自动机 (NFA) [1] [2] [3]
还有一种算法可以将 DFA 转换为 Right-Linner-Grammar (RLG)。[1] [2]

因此，当然，它们是将 RE 转换为 RLG 的算法方式。

1 回答 1