regex - 从给定的正则表达式创建语法树(对于 RE 到 DFA)

Question

我正在学习自动机理论，在将 RE 直接转换为 DFA 时遇到了一些困难。此方法需要从 RE 创建语法树。但是我无法生成。
我得到了一个正则表达式 e.g a*b*(a|b)abc

现在我想从中生成一个语法树。我不想要它的程序，但我想手动完成。谁能帮帮我？

Answer 1

你需要弄清楚这个表达式代表的操作是什么，它们应用的顺序是什么，它们的操作数是什么。

例如 a* 表示:“将 * 运算符应用于 a”。在表达式树中，您将获得星号运算符的节点，以及运算符所作用的符号的 a 节点。

同样，| 表示一个交替，因此它是树中的一个节点，子节点是交替的子表达式。

顶级操作只是一个串联，即您的根节点。

这是从这些规则派生的完整 AST:

a*b*(a|b)abc

--+ CONCAT
  |
  +-+ STAR
  | |
  | +-- a
  |
  +-+ STAR
  | |
  | +-- b
  |
  +-+ OR
  | |
  | +-- a
  | |
  | +-- b
  |
  +-- a
  |
  +-- b
  |
  +-- c

编辑:您要求二叉树，转换应该很简单。我会留下两棵树，这样你就可以弄明白了:

              .
             / \
            .   c
           / \
          .   b
         / \
        .   a
       / \
      /   \
     /     \
    .       |
   / \     / \
  *   *   a   b
 /     \
a       b

请注意，上面的树使用了左关联连接运算符。