从给定的正则表达式创建语法树（对于RE到DFA）

Question

我正在学习自动机理论，并且面临将RE直接转换为DFA时遇到的一些困难。此方法需要从RE创建语法树。但我无法生成。
我给出一个正则表达式e.ga*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 

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