CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:小型代码分析系统的实现方式 [2020/08/06 11:52]
great_designer 创建
+++ 2020-2021:teams:namespace:小型代码分析系统的实现方式 [2020/08/06 12:32] (当前版本)
great_designer [代码]
@@ 行 1: / 行 1: @@
 ======小型代码分析系统的实现方式======
+=====题目=====
+一个程序中有 26 个对象，每个对象有 26 个成员指针变量。同时还有 26 个普通的指针变量。给定 n 条赋值语句，询问在以任意顺序执行每条语句无限多次的过程中，每个指针变量可能指向的对象集合。
 指针分析（Pointer analysis）是静态程序分析的基本组成部分之一，它的目的是找出在程序执行过程中通过特定指针变量访问哪些对象。现在我们希望您对测试数据执行上下文无关指针分析。
 一个程序包含26个用小写字母表示的对象，每个对象也有26个用小写字母表示的成员变量（又称字段，可能指向某些对象的指针）。同时，程序中有26个用大写字母指定的全局指针。
 程序中有四种语句。我们使用[Variable]表示指针的名称，[Field]表示成员变量的名称，[Object]表示对象。
 A = x分配：指针A可以指向对象x（即可以通过A访问x）
 A = B转让：指针A可以指向通过B访问的每个对象
 A.f = B贮存：对于通过A访问的每个对象o，o的成员变量f可以指向通过B访问的每个对象
 A = B.f装载：对于通过B访问的每个对象o，A可以指向通过o的成员变量f访问的每个对象
 上下文无关指针分析假设程序的语句将以任何顺序执行足够的次数。例如，在下面两个程序中，A和B都可以指向对象x和对象o，原因是在现实世界中，语句的确切执行顺序和执行时间很难预测。
+<code C>
+A = o
+A = x
+B = A
+B = A
+A = x
+A = o
+</code>
 现在，您需要对由N个语句组成的给定程序执行上下文无关指针分析，对于每个指针，输出它可以指向的对象。
 输入的第一行包含一个整数N（1≤N≤200），表示程序中的语句数。等号“=”前后只有一个空格。
 以下N行中的每一行都包含一个语句。
 输出应该包含26行。
 在第i行中，输出第i个指针的名称（第i个大写字母），后跟冒号“：”和空格，然后按字母顺序列出可通过该指针访问的对象。
+=====样例=====
+样例一：
+<code C>
+B.f = A
+C = B.f
+C = x
+A = o
+B = o
+A: o
+B: o
+C: ox
+D:
+E:
+F:
+G:
+H:
+I:
+J:
+K:
+L:
+M:
+N:
+O:
+P:
+Q:
+R:
+S:
+T:
+U:
+V:
+W:
+X:
+Y:
+Z:
+</code>
+样例二：
+<code C>
+A = o
+B.f = A
+C = B.f
+C = g
+A: o
+B:
+C: g
+D:
+E:
+F:
+G:
+H:
+I:
+J:
+K:
+L:
+M:
+N:
+O:
+P:
+Q:
+R:
+S:
+T:
+U:
+V:
+W:
+X:
+Y:
+Z:
+</code>
+样例三：
+<code C>
+A = o
+B = A
+A = x
+A: ox
+B: ox
+C:
+D:
+E:
+F:
+G:
+H:
+I:
+J:
+K:
+L:
+M:
+N:
+O:
+P:
+Q:
+R:
+S:
+T:
+U:
+V:
+W:
+X:
+Y:
+Z:
+</code>
+=====题解=====
+直接暴力求解即可。本题难点可能只在于处理读入。
+这里给出一个简单的暴力框架：令 pt(x) 为指针 x 可能指向的对象集合。
+<code python>
+Let worklist be a set
+For every allocation statement A = x:
+    insert x into pt(A)
+    If pt(A) has been changed, add A into worklist
+While worklist is not empty:
+    While worklist is not empty:
+        select one element X from worklist
+        delete X from worklist
+        For every assignment statement like Y = X:
+            merge pt(X) into pt(Y)
+            If pt(Y) has been changed, add Y into worklist
+    For every store statement Y.f = X:
+        For every object o in pt(Y):
+            merge pt(X) into pt(o.f)
+    For every load statement Y = X.f:
+        For every object o in pt(X):
+            merge pt(o.f) into pt(Y)
+            If pt(Y) has been changed, add Y into worklist
+</code>
+样例2是说，B没法指向任何对象，是空指针。
+这题的重点是，要分清对象和指针：
+所有的 a, b, c, d, e, f... z 都是对象，A, B, C, ..., Z 和 A.a, A.b, ..., A.z 和 o.a, o.b, o.c, ...o.z 这些是指针。
+=====代码=====
+<hidden>
+<code C++>
+#include<stdio.h>
+#include<string.h>
+#include<vector>
+#include<set>
+using namespace std;
+vector<pair<int,int> > storeEdge, loadEdge, allocEdge;
+vector<int> assignEdge[2 * 27];
+int pt[(27 + 27) * 27];
+int ObjectIndex(char ch)
+{
+    return ch - 'a';
+}
+int PointerIndex(char ch)
+{
+    return ch - 'A' + 26;
+}
+int FieldIndex(char ch)
+{
+    return ch - 'a' + 1;
+}
+int makeField(int v, int f)
+{
+    return f * 52 + v;
+}
+int makeField(char v, char f)
+{
+    if ('a' <= v && v <= 'z')
+	{
+		return makeField(ObjectIndex(v), FieldIndex(f));
+	}
+    return makeField(PointerIndex(v), FieldIndex(f));
+}
+int makeField(int v, char f)
+{
+    return makeField(v, FieldIndex(f));
+}
+int getBase(int v)
+{
+    int base = v % 52, field = v / 52;
+    return base;
+}
+int getField(int v)
+{
+    int base = v % 52, field = v / 52;
+    return field;
+}
+int checkFieldNode(const char *s)
+{
+    int n = strlen(s);
+    if (n == 1)
+	{
+        return -1;
+    }
+    return makeField(s[0], s[2]);
+}
+void propagate()
+{
+    set<int> worklist;
+    vector<pair<int,int> >::iterator e;
+    for(e=allocEdge.begin();e!=allocEdge.end();e++)
+	{
+        pt[e->first] |= (1 << e->second);
+        worklist.insert(e->first);
+    }
+    while (!worklist.empty())
+	{
+        while (!worklist.empty())
+		{
+            int u = *worklist.begin();
+            worklist.erase(worklist.begin());
+            vector<int>::iterator v;
+            for(v=assignEdge[u].begin();v!=assignEdge[u].end();v++)
+			{
+                if ((pt[*v] & pt[u]) != pt[u])
+				{
+                    pt[*v] |= pt[u];
+                    worklist.insert(*v);
+                }
+            }
+        }
+        for(e=storeEdge.begin();e!=storeEdge.end();e++)
+		{
+            int p = e->second;
+            int q = getBase(e->first);
+            int f = getField(e->first);
+            int i;
+            for(i = 0; i < 26; i++)
+            {
+            	if ((pt[q] >> i) & 1)
+				{
+                    pt[makeField(i, f)] |= pt[p];
+                }
+			}
+        }
+        for(e=loadEdge.begin();e!=loadEdge.end();e++)
+		{
+            int p = getBase(e->second);
+            int f = getField(e->second);
+            int q = e->first;
+            int i;
+            for(i = 0; i < 26; i++)
+            {
+            	if ((pt[p] >> i) & 1)
+				{
+                    int value = pt[makeField(i, f)];
+                    if ((pt[q] & value) != value)
+					{
+                        pt[q] |= value;
+                        worklist.insert(q);
+                    }
+                }
+			}
+        }
+    }
+}
+void output(int x)
+{
+	int i;
+    for(i = 0; i < 26; i++)
+	{
+        if ((x >> i) & 1)
+		{
+			printf("%c",(char)('a' + i));
+		}
+    }
+    printf("\n");
+}
+int main()
+{
+    char receiver[10], sender[10];
+    int n;
+    scanf("%d", &n);
+    int ii;
+    for(ii= 1;ii<= n;ii++)
+	{
+        scanf("%s = %s", receiver, sender);
+        int R = checkFieldNode(receiver);
+        int G = checkFieldNode(sender);
+        if (R != -1 && G == -1)
+		{
+            storeEdge.push_back(pair<int,int>(R, PointerIndex(sender[0])));
+        }
+        if (R == -1 && G != -1)
+		{
+            loadEdge.push_back(pair<int,int>(PointerIndex(receiver[0]), G));
+        }
+        if (R == -1 && G == -1)
+		{
+            if (sender[0] >= 'a' && sender[0] <= 'z')
+            {
+            	allocEdge.push_back(pair<int,int>(PointerIndex(receiver[0]), ObjectIndex(sender[0])));
+			}
+            else
+			{
+                assignEdge[PointerIndex(sender[0])].push_back(PointerIndex(receiver[0]));
+            }
+        }
+    }
+    propagate();
+    char i;
+    for(i = 'A'; i <= 'Z'; i++)
+	{
+		printf("%c: ",i);
+		int j;
+        for(j = 0; j < 26; j++)
+        {
+        	if ((pt[PointerIndex(i)] >> j) & 1)
+			{
+				printf("%c",(char)(j + 'a'));
+			}
+		}
+        printf("\n");
+    }
+    return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具