在AST

背景執行轉到：由於過寒假短的項目，我想實現使用Python和PLY稱爲斧一種編程語言（專爲圖形計算器）。簡要說明：該語言只允許全局變量並大量使用指針。在AST

我試圖實現這種語言跳轉，但不知道該怎麼做。

我的一般方法，是先用簾布層的代碼解析成一個AST，然後通過它執行，我去散步。

例如，聲明

If 3 
    Disp 4 
    Disp 6 
End

...會變成...

['PROGRAM', 
    ['BLOCK', 
    ['IF', 
     ['CONDITION', 3], 
     ['BLOCK', 
     ['DISP', 4], 
     ['DISP', 6] 
     ] 
    ] 
    ] 
]

...我會遞歸執行（我加了縮進了可讀性）。

因爲ast是一棵樹，所以我不確定如何在不同節點之間跳轉。我考慮過可能將樹轉換爲平坦的數組['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]]，這樣我就可以使用flat-ish數組的索引去代碼中的特定行，但這似乎缺少某種優雅，幾乎感覺像是退後一步（儘管我可能是錯的）。

我已經看了this，但無法瞭解它是如何工作的。

任何幫助或暗示，將不勝感激。

來源

2011-12-27 Michael0x2a

「跳」？你覺得你的意思是「跳躍」？爲什麼你會在節點之間「跳躍」？請提供一個特定的例子，您可以跳轉到任意節點。在基於樹的語言中很難找到跳躍的明智需求。 – 2011-12-27 12:12:08

我選擇實施的語言有goto語句。我想匹配規範，這就是爲什麼我需要轉到。我製作了這種基於樹的版本，因爲當時這似乎是明智的做法。我猜這是一個錯誤：還有什麼其他形式的語言？ – Michael0x2a 2011-12-27 17:38:09

AX真的*需要*一個GOTO？似乎很奇怪。有無數種語言的「形式」：過程式，功能性等等。在程序語言中，Python和Java（除其他外）都沒有GOTO。這是一件非常罕見的事情。 – 2011-12-27 17:41:14

「執行遞歸」不goto合身。要使goto正常工作，您需要一臺PC，一個「程序計數器」，並且程序中的每個語句都必須有一個明確的地址。執行時，每個語句的地址都分配給PC。當遇到goto時，goto（它的參數）的目標地址被放入PC並且執行從那裏開始。

這幾乎不可能通過基於堆棧的遞歸方法來實現。你有兩個選擇：

拼合您的AST成一個序列，在那裏你可以指定一個不同的地址，每個語句
添加「跳過」模式，你的解釋。遇到goto時，拋出一個GotoException，它跳出所有堆棧幀並返回根目錄。進程語句（跳過它們而不執行）直到到達目標地址。

我想你能想象這個實現的goto不是很高性能，可能脆實現。

來源

2011-12-27 08:40:42

好的，謝謝你的建議！我想我要去平整樹。 – Michael0x2a 2011-12-29 16:47:21

我曾考慮也許將樹轉換爲平面陣列...但這似乎缺乏某種優雅，幾乎感覺像一個倒退（雖然我可能是錯的）。

你錯了。機器代碼始終是平坦的。像C這樣的語言被壓扁以創建機器碼。

一個計算器（像其他簡單的機器）是平坦的。

但是，展平你的AX語法樹並不完全是必需的。

您只需將編程源標籤應用於樹中的每個節點即可。

然後，一個「GOTO」只是搜索樹的標籤，然後繼續執行該標籤。

來源

2011-12-27 17:49:18

啊，關於機器碼的好點。我想我錯了那麼:) – Michael0x2a 2011-12-29 16:48:35

因爲機器代碼是平坦的，我們現在不用它來編程。我們更喜歡結構化的語言，並使用工具將一個漂亮的結構化語言平鋪到機器執行的平坦世界中。 – 2011-12-29 16:50:09

您還可以將AST平面化爲有向圖（控制流圖）。如何做到這一點可以產生一個networkx圖可以通過解釋器遍歷的例子可以找到here。請注意，您必須爲此編寫一些AST類。

來源

2015-03-27 09:47:41

回答

相關問題