如何使用Python生成AST（用XML表示）的控制流？

我有XML格式的WHILE語言（http://www.program-analysis.com/while.html）。目前，我不處理函數調用或遞歸。我需要爲這個程序生成控制流程。如何使用Python生成AST（用XML表示）的控制流？

的樣品程序（//後的數字表示標籤由分析器所產生）：

begin 

x:=1;  // 1 
z:= 2+x;  // 2 
x := x+z; // 3 
y:=z-x+z; // 4 
w:=x+y+z; // 5 

while(not (y<z)) { // 12 
    x:=x+1;   // 6 
    if (w <=x) {  // 9 
     w:= w-x; // 7 
    } 
    else { 
     w:=w+x; // 8 
    } 
    z:=z-1;   // 10 
    y:=y+1;   // 11 
} 

x:=z+y;    // 13 
w:=x;    // 14 

end

用於上述程序的AST被表示爲：

<?xml version="1.0" encoding="UTF-8" standalone="no"?> 
<program> 
    <assignment label="1" variable="x"> 
     <value> 
      <number value="1"/> 
     </value> 
    </assignment> 
    <assignment label="2" variable="z"> 
     <value> 
      <binary operator="+"> 
       <left> 
        <number value="2"/> 
       </left> 
       <right> 
        <variable name="x"/> 
       </right> 
      </binary> 
     </value> 
    </assignment> 
    <assignment label="3" variable="x"> 
     <value> 
      <binary operator="+"> 
       <left> 
        <variable name="x"/> 
       </left> 
       <right> 
        <variable name="z"/> 
       </right> 
      </binary> 
     </value> 
    </assignment> 
    <assignment label="4" variable="y"> 
     <value> 
      <binary operator="+"> 
       <left> 
        <binary operator="-"> 
         <left> 
          <variable name="z"/> 
         </left> 
         <right> 
          <variable name="x"/> 
         </right> 
        </binary> 
       </left> 
       <right> 
        <variable name="z"/> 
       </right> 
      </binary> 
     </value> 
    </assignment> 
    <assignment label="5" variable="w"> 
     <value> 
      <binary operator="+"> 
       <left> 
        <binary operator="+"> 
         <left> 
          <variable name="x"/> 
         </left> 
         <right> 
          <variable name="y"/> 
         </right> 
        </binary> 
       </left> 
       <right> 
        <variable name="z"/> 
       </right> 
      </binary> 
     </value> 
    </assignment> 
    <while condition-label="12"> 
     <condition> 
      <not> 
       <binary operator="&lt;"> 
        <left> 
         <variable name="y"/> 
        </left> 
        <right> 
         <variable name="z"/> 
        </right> 
       </binary> 
      </not> 
     </condition> 
     <body> 
      <assignment label="6" variable="x"> 
       <value> 
        <binary operator="+"> 
         <left> 
          <variable name="x"/> 
         </left> 
         <right> 
          <number value="1"/> 
         </right> 
        </binary> 
       </value> 
      </assignment> 
      <if condition-label="9"> 
       <condition> 
        <binary operator="&lt;="> 
         <left> 
          <variable name="w"/> 
         </left> 
         <right> 
          <variable name="x"/> 
         </right> 
        </binary> 
       </condition> 
       <true-branch> 
        <assignment label="7" variable="w"> 
         <value> 
          <binary operator="-"> 
           <left> 
            <variable name="w"/> 
           </left> 
           <right> 
            <variable name="x"/> 
           </right> 
          </binary> 
         </value> 
        </assignment> 
       </true-branch> 
       <false-branch> 
        <assignment label="8" variable="w"> 
         <value> 
          <binary operator="+"> 
           <left> 
            <variable name="w"/> 
           </left> 
           <right> 
            <variable name="x"/> 
           </right> 
          </binary> 
         </value> 
        </assignment> 
       </false-branch> 
      </if> 
      <assignment label="10" variable="z"> 
       <value> 
        <binary operator="-"> 
         <left> 
          <variable name="z"/> 
         </left> 
         <right> 
          <number value="1"/> 
         </right> 
        </binary> 
       </value> 
      </assignment> 
      <assignment label="11" variable="y"> 
       <value> 
        <binary operator="+"> 
         <left> 
          <variable name="y"/> 
         </left> 
         <right> 
          <number value="1"/> 
         </right> 
        </binary> 
       </value> 
      </assignment> 
     </body> 
    </while> 
    <assignment label="13" variable="x"> 
     <value> 
      <binary operator="+"> 
       <left> 
        <variable name="z"/> 
       </left> 
       <right> 
        <variable name="y"/> 
       </right> 
      </binary> 
     </value> 
    </assignment> 
    <assignment label="14" variable="w"> 
     <value> 
      <variable name="x"/> 
     </value> 
    </assignment> 
</program>

我需要生成程序的控制流。

用於上述程序的控制流程是這樣的：

1->2, 
2->3, 
3->4, 
4->5, 
5->12, 
12->6, 
12->13, 
11->12, 
6->9 , 
9->7, 
9->8, 
7->10, 
8->10, 
10->11, 
13->14.

注意：當可以在其中有嵌套if語句和while語句，反之亦然。我最好在Python/Java/C中尋找一個通用的解決方案。

由於提前，羅伊

來源

2012-02-16 user916315

只是一個觀察：我不知道，你可以在一個更多樣化的語言都要求幫助...的Python：解釋和動態強類型，Java的編譯和靜態強類型，C編譯靜態但相對較弱的類型......完全不是批評;事實上這很好，因爲這意味着更多人可以提供幫助，但它確實讓我好奇你想要做什麼。 :) – Crisfole 2012-02-16 15:49:31

嗯... 的Java：因爲很多的開發商我知道被它的Python發誓：因爲我覺得它很有趣，而且我敢肯定，那裏面寫丹相同片段會轉化爲大約100 +線的Java，包括對象和類。 C：因爲這是我很久以前學過的東西，而且比較容易閱讀。您可以指出的其他語言，如計劃，Lisp語言，C＃，但我認爲所有這些下跌的其中一個類別下。 – user916315 2012-02-16 16:36:18

這裏是一個可能的解決方案。它以與您的示例略有不同的順序返回弧線，但這不應該成爲問題。

from xml.dom import minidom 
dom = minidom.parse('test1.wl.xml') 


def print_arcs(from_list, to_list): 
    ''' 
    Print arcs from every member of the from list, to every member of 
    the to list 
    ''' 
    for source in from_list: 
     for target in to_list: 
      print "%s -> %s" % (source, target) 

def parse(node, came_from): 
    ''' 
    Descend an XML structure representing an AST 
    ''' 
    if not node: 
     return came_from 

    if node.nodeName=="#text": 
     return parse(node.nextSibling, came_from) 

    if node.nodeName=="program": 
     return parse(node.firstChild, came_from) 

    if node.nodeName=="assignment": 
     this = node.getAttribute('label') 
     print_arcs(came_from, [this]) 
     return parse(node.nextSibling, [this]) 

    if node.nodeName=="while": 
     loop_start = node.getAttribute('condition-label') 
     print_arcs(came_from, [loop_start]) 
     next = [loop_start] 
     for s in node.childNodes: 
      if s.nodeName=="body": 
       loop_end = parse(s, [loop_start]) 
       print_arcs(loop_end, [loop_start]) 
     return parse(node.nextSibling, next) 

    if node.nodeName=="if": 
     if_start = node.getAttribute('condition-label') 
     print_arcs(came_from, [if_start]) 
     next = [] 
     for s in node.childNodes: 
      if s.nodeName=="#text": 
       continue 
      item = parse(s, [if_start]) 
      if item: 
       next.extend(item) 
     return parse(node.nextSibling, next) 

    if node.nodeName=="condition": 
     return None 

    if node.nodeName=="true-branch": 
     return parse(node.firstChild, came_from) 

    if node.nodeName=="false-branch": 
     return parse(node.firstChild, came_from) 

    if node.nodeName=="body": 
     return parse(node.firstChild, came_from) 


parse(dom.firstChild, [])

此遞歸通過AST的結構，並且其輸出依賴於節點的所遇到的類型。分配只是將前一個節點的弧線輸出到當前節點;一個if需求電弧以這兩種可能性，和一個while需要表示所述環和可能落空弧。給出的代碼保存了執行可能來自哪裏以便在當前位置結束的列表。 parse函數返回結束當前塊的位置。

請注意，在這裏執行while和if這有點不好意思，它會在某些類型的語法錯誤上崩潰。

來源

2012-02-16 15:46:20 Dan

丹！你真棒！它非常完美！：D 如何將其標記爲有用的答案，請幫助！注意：你不認爲標籤：11-13是不正確的？ – user916315 2012-02-16 16:17:40

好點！ while循環的終止爲11-> 12-> 13，所以不應該有直接的弧。我將修復代碼。 – Dan 2012-02-16 17:21:37

如果你在不需要的標籤列表中寫了['binary'，'number'，'variable']，然後解析它，你認爲不是寫#text，它會更好嗎？ – user916315 2012-02-16 17:56:15

您將需要實現虛擬機執行該代碼。幸運的是，你必須在這段代碼中處理的是if和while語句。您還需要虛擬機來保存變量名稱的註冊表，這可以通過Python字典完成。從第一條語句開始，分配只是執行並繼續下一個。如果語句必須評估條件並相應地進行分支。雖然與if類似，但當條件評估爲false（使用堆棧處理嵌套while）時，需要一堆地址才能退出。並隨時跟蹤標籤號碼。

來源

2012-02-16 11:22:40 PaulMcG

嗨，我已經完成小髒程序，它生成程序代碼，而如果/當。 from xml.dom import minidom dom = minidom.parse（'test1.wl.xml'） assignments = dom.getElementsByTagName（'assignment'） numbers = [statement.getAttribute（'label'）for assignments] #this適用於x，y in zip（數字[： - 1]，數字[1：]），而沒有/如果的程序： \t打印「％s - >％s」％（x，y ）＃尋找父母在分配節點： \t打印node.parentNode.nodeName，node.getAttribute（「標籤」）你能告訴我一個小片斷它處理，而條件是什麼？ – user916315 2012-02-16 11:37:13

我也無法理解字典的需要。我不需要檢查變量。 – user916315 2012-02-16 13:38:23

如果您要映射控制流程，那麼您需要評估是否需要採取哪條路徑。要評估if條件，您需要知道變量的值，因此您可以測試true/false的條件。除非我誤解了你所說的「控制流」。 – PaulMcG 2012-02-16 14:07:29

您不必執行完整的VM來執行控制流分析。你需要走過AST。事實上，您鏈接到的網站（Principles of Program Analysis）所提到的這本書解釋瞭如何做到這一點。想一想你的語言中的每一種語言是如何進入和退出的。在程序語言中，if/else if/else語句可以從其前面的語句中輸入，並且可能有幾個退出點（if/else if/else的每個分支一個）。 A while聲明中有一個來自其前面的聲明的入口點和兩個出口點 - 一個出口循環到while的頂部，另一個出口從while中跳出並轉到下一個語句。賦值語句在賦值之前的語句中有一個條目，並且有一個出口點導致後面的語句。

這是需要繪製的有向圖。所以，你想迭代你在那裏「發射」CFG中的節點的XML。要做到這一點，最簡單的方法就是使用visitor pattern，因爲您使用的是OO語言。

例如，此程序：

begin 
    x := 10   // 1 
    if x < 100 {  // 2 
     print "foo" // 3 
    } 
    else { 
     print "bar" // 4 
    } 
end

將具有以下CFG：

CFG

來源

2012-02-16 15:40:22 snim2

謝謝你的exaplanation snim2！ – user916315 2012-02-16 16:44:29

不客氣。順便說一句，如果這是一個家庭作業問題，請標記它。 – snim2 2012-02-16 16:47:03

是的，沒有。我正在審覈這門課程！只是把它當做一個練習，但可怕地卡住了。這種類型的流量分析沒有以前的經驗可能是原因。 – user916315 2012-02-16 17:32:35

如何使用Python生成AST（用XML表示）的控制流？

回答

相關問題