将任何给定的正则表达式(RE)转换为左(或右)线性语法的标准算法是什么?
我知道我可以这样做(从 RE 编写线性语法):
RegEx -> NFA -> DFA -> Right Linear grammar
.
对于直接方法,我可以处理简单的正则表达式(0 + 10)*
并创建线性语法。
但是,当存在嵌套的 kleene 星时,如果没有任何明确定义的方法,就很难生成线性的 CFG。
我在这里和这里看到了类似问题的一些答案。但它们不提供通用算法或不将正则表达式转换为线性语法。
特别是,如何(((01+10)*00)*11)*
使用某种算法直接将其转换为线性语法?
任何帮助表示赞赏。
编辑
做了一些更多的搜索。并得到了这个。
从正则表达式构造等价的正则文法