3

将任何给定的正则表达式(RE)转换为左(或右)线性语法的标准算法是什么?

我知道我可以这样做(从 RE 编写线性语法):

RegEx -> NFA -> DFA -> Right Linear grammar.

对于直接方法,我可以处理简单的正则表达式(0 + 10)*并创建线性语法。
但是,当存在嵌套的 kleene 星时,如果没有任何明确定义的方法,就很难生成线性的 CFG。

我在这里这里看到了类似问题的一些答案。但它们不提供通用算法或不将正则表达式转换为线性语法。

特别是,如何(((01+10)*00)*11)*使用某种算法直接将其转换为线性语法?

任何帮助表示赞赏。

编辑

做了一些更多的搜索。并得到了这个。
从正则表达式构造等价的正则文法

4

1 回答 1

1

从正则表达式构造等价的正则文法

于 2013-06-21T07:05:52.810 回答