抽象翻译器如何工作？

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之上进行这种转换。