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

Question

我正在学习自动机理论，在将RE直接转换为DFA时遇到了一些困难。此方法需要从 RE 创建语法树。但我无法生成。
我被赋予了一个正则表达式，例如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

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