編程語言用於評估AST的算法是什麼？

也就是說，假設我們有4個基本功能，/*+-。什麼是基本的算法，將正確EVAL任何AST的形式，例如：

(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))

我的疑問，實際上是如果一個節點的評估返回仍有待評估的事情會發生什麼。例如，在Scheme中，((lambda (a) (+ a 2)) 3)的評估將是(+ 3 2)。但是這可以再次評估爲5.那麼，語言如何確定何時停止評估表單呢？

2012-10-08 MaiaVictor

如果你給，執行將停在5，因爲它是一個字面值，並代表自己。這不難測試。你可能會問一個深入遍歷列表的函數如何知道如何停止（實際上，你應該，因爲在Scheme中這是同樣的事情）。

在Scheme中，任何複合表達式最終應解析爲7個基本數據類型之一或空列表，除非它陷入無限循環。如果你想提前知道如果表達式可以解決，好，這是一個有趣的問題：http://en.wikipedia.org/wiki/Halting_problem

2012-10-09 00:06:08 itsbruce

我想你可能會問錯了問題，但我會嘗試：

直到它得到一個結果它可以工作。在你的例子中，你問的是一個Interpeter什麼時候停止評估一個表達式......它的100％語言依賴性，如果你要問一個編譯器，它將是一個完全不同的答案。對於您的Scheme示例，您需要閱讀Scheme規範（R5RS）。

所以它由解釋者的作者定義。如果單個文字（甚至變量）是我的語言中表達式的預期結果，那麼它就會在那裏停下來。

2012-10-09 00:30:24

有許多不同的算法。

備選方案1：您可以將AST編譯爲更線性的中間表示形式。您的代碼可以編譯爲以下內容：

a <- 3 * 2 
b <- 5/2 
c <- a - b 
d <- 2 * 4 
e <- c + d 
return e

這很容易評估，因爲它只是一系列指令。大多數指令具有相同的格式：X <- Y OP Z，因此評估者將非常簡單。

備選方案2：您可以將備選＃1編譯爲機器碼或字節碼。

li  r3, 3 
muli r3, 2 
li  r4, 5 
divi r4, r5, 2 
subf r3, r3, r4 
li  r4, 2 
muli r4, r4, 4 
add  r3, r3, r4 
blr

方案3：您可以編譯替代＃1到名爲SSA，或「單靜態分配」的一種特殊形式，它類似於＃1，但每一項任務的LHS是獨一無二的，特殊的「 phi「節點用於組合來自不同分支的值。然後可以將SSA編譯爲機器碼或字節碼。

方案4：您可以通過遞歸下降來評估AST。大多數關於Scheme/Lisp的書籍都對此進行了全面的介紹。

備選5：您可以使用遞歸下降將代碼轉換爲堆棧機器代碼，然後對其進行評估。喜歡的東西：

push 3 
push 2 
mul 
push 5 
push 2 
div 
sub 
push 2 
push 4 
mul 
add 
ret

替代∞：有大量的其他技術。寫在這個問題上的書是厚。

2012-10-09 00:53:09

您完全誤解了Scheme/Lisp評估的工作原理。我會用你給的例子：

(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))

評價的列表，我們評估每一個元素。第一個應該返回一個過程（我忽略了語法操作符的特殊情況），其餘的可以返回任意值。我們把其餘的程序稱爲參數。

在頂層，這是3個元素的列表：

每個這些被評估。第一個是一個變量，其值是一個過程（Scheme的內置附加函數）。其他人，名單，需要遞歸到評估算法。由於其複雜性，我將跳過第二個描述，並轉到第三個：(* 2 4)。

這是3個元素的列表：*，2和4.如上所述，*是乘法函數。 2和4是文字，所以他們評價自己。因此，我們將參數2和4稱爲乘法函數，並返回8.

複雜的第二個參數經歷了相同的過程，只是具有多個遞歸級別。它最終返回4.所以我們然後調用帶參數4和8的乘法函數，它返回32.

你的第二個例子的處理過程相似。在頂部，你有兩個元素的列表：

每一種評估。 Lambda是解析其內容並返回一個過程的特殊語法，該過程在參數變量綁定到參數的上下文中評估其主體，因此第一個返回的過程將2加到其參數並返回該參數。 3是一個文字，所以它只是返回數字3.然後我們用參數3調用該過程，它將它加2並返回5.

2012-10-09 01:43:06 Barmar

回答