从正则表达式创建正则语法

Question

任何人都可以指导我完成从正则表达式获取正则语法的过程吗？我发现很少'tutorials'，但我仍然无法将更复杂的正则表达式转换为语法。

你会如何应对 ((a+b)*(c|d))+a?？

我想到了

A -> aB
A -> aA
B -> bA
A -> cC
A -> dC
C -> cA
C -> dA
C -> a
C -> epsilon

但这显然是不正确的。

Answer 1

从内到外工作。各运营商介绍一个新的非终端

 Operator  Grammar     Operator  Grammar
 --------  -------     --------  -------
    R|S     A->R          R*      A->
            A->S                  A->AR

    R?      A->           R+      A->R
            A->R                  A->AR

（大多数说明也会引入新的非终结符用于连接；在这里，我没有打扰。希望不会造成混淆。）

示例：

((a+b)*(c|d))+a?

Sub-          Rewritten with   Rules for
expression    new nonterminal  new nonterminal
----------    ---------------  -----------
a+            A                A->a    A->Aa
a+b           Ab
(a+b)*        (Ab)*            B->     B->BAb
c|d           C                C->c    C->d
(a+b)*(c|d)   BC
(a+b)*(c|d)+  (BC)+            D->BC   D->DBC
a?            E                E->     E->a
(a+b)*(c|d)+  DE               S->DE

从正则表达式创建正则语法

Creating a regular grammar out of a regular expression

regex

grammar

regular-language