從給定的正則表達式創建語法樹（對於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 

請注意，上面的樹使用左關聯連接運算符。