抽象翻譯器如何工作？

Question

我正在嘗試爲C構建一個抽象解釋器。可能不是整個語法，而只是它的一個子集。我以前曾問過要使用哪種語言。在我進一步討論之前，我想知道這個抽象解釋是如何工作的？

我已經通過維基鏈接和講義註釋鏈接。我已經理解了它的理論基礎和理論。我已經分析了我的分析結果。我完全無法理解的部分是如何解釋代碼。也就是說，我有最初的代碼。我現在已經預處理了。我還對我的分析所需的代碼進行了一些標準化。現在，當我繼續執行代碼時，如何逐行執行代碼並提取數據？ （請告訴我，如果這是不可能的，或者有一些方法來正確執行程序，這將實現我的目標）。我正在收集信息，如動態分配空間的內存地址，函數調用的返回地址。

我之前被推薦過CIL，CIL主要是一個轉換工具，將代碼轉換爲一些規範化的形式來處理許多異常，但我無法獲得任何有關我的問題的信息。

我的問題是如何逐行提取信息，哪種語言更適合？命令式語言還是功能性語言？關於這方面的信息，我一直在谷歌搜索了幾天，但沒用。任何鏈接也非常感謝。謝謝。

編輯：我仍然有一些疑惑。我得到了我們嘗試構建虛擬環境的部分。讓我解釋一下我正在嘗試做什麼，以便它有助​​於討論。我基本上試圖做指針分析，主要集中在指針算術上。現在假設我有一個整數指針，我做了一個指針算術，然後我不能確定指針是否仍然指向一個有效的數據。

從你的意思，我知道我們需要爲變量分配空間，但值是什麼。如果我有類似下面

int a=10;
int *p = &a;
p = p+4;

這裏的值和常量「4」是已知的。如果我從用戶或文件中獲得價值，該怎麼辦？在這種情況下，我需要執行實際的程序。同時，我需要捕獲像地址這樣的數據。下面，

int *p =(int *) malloc (sizeof(int));
*p= 15;
cout<<*p;
p = p+ino//some user input value;
cout<<*p;


所以基本上代碼必須被執行，但該溶液的後面部分就更像解析C文件。如果我錯了，請糾正我。

Answer 1

假設你真的在談論抽象解釋，而不是僅僅解釋ç...

抽象解釋依賴於兩件事情 - 一個抽象的領域，有限的高度格和抽象的語義，其中的所述應用語義行到行之前的行中的值必須在高度相同或更高的域中產生新值。

即如果您的域是{1,2,3,4}的冪且輸入是{1,2,3}唯一有效的輸出是{1,2,3}或{1,2,3,4}（假設通常的集合排序）

然後，通過在每行上進行定點遞歸和存儲進行語義與行的輸出以及每個函數結尾處的語義與函數定義。你如何選擇域名並解釋你最終得到的設置取決於你正在嘗試做的分析，但這是我理解的概要...

我必須說我是而不是專家與此同時，但我的一些研究同事過去曾與我討論過這個問題，這就是我所瞭解的...

此外，您可以輕鬆地向後運行分析 - 從功能的結束和前進，這將更適合於某些分析...

Answer 2

從你提出問題的方式來看，似乎你是什麼e講的是的解釋，而不是抽象解釋。解釋僅僅意味着採用C代碼並自己運行它，以便從運行時發生的情況中提取一些信息。抽象解釋是指一種靜態分析過程，您可以在其中嘗試理解程序能夠做什麼，可能用於優化目的，或者可能試圖證明正確性或缺少錯誤。當然，我可能完全錯了，在這種情況下，你可以忽略這個答案。

如果您正在嘗試編寫解釋器，那麼您可能需要設置一個虛擬執行環境，程序將在其中運行。也就是說，你可能想要設置一個巨大的字節數組作爲程序的內存，並且需要維護自己的堆棧指針和堆分配器。然後，您可以逐行執行程序，並根據您正在執行的特定代碼行修改此環境的狀態。例如，執行像

int a; 

會由四個字節增加堆棧指針工作的聲明，在運行像

a = 137; 

東西看起來了一下全局存儲器陣列的一部分是由a引用然後用137的四字節值覆蓋字節。從這一點來看，跟蹤執行過程中發生的情況應該相對簡單 - 在解釋器執行任何特定語句或評估表達式之前，可以記錄任何相關詳細信息。

請注意，這並不容易。你將不得不手動分配和清除堆棧幀，維護一個程序計數器等。但是，這聽起來很有趣，並且我祝你好運！

Answer 3

CIL有能力做SSA-transform。 SSA格式的程序出奇地容易到reason about並部分評估 - 您只需替換命名值，忽略或合併值來自phi -nodes。所以，爲了把CIL變成一個合適的抽象解釋器，你只需要在SSA（已經存在）之後添加一些變換。或者，您可以在Clang生成的LLVM IR之上進行這種轉換。