CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:小型代码分析系统的实现方式 [2020/08/06 11:57]
great_designer
+++ 2020-2021:teams:namespace:小型代码分析系统的实现方式 [2020/08/06 12:32] (当前版本)
great_designer [代码]
@@ 行 19: / 行 19: @@
 上下文无关指针分析假设程序的语句将以任何顺序执行足够的次数。例如，在下面两个程序中，A和B都可以指向对象x和对象o，原因是在现实世界中，语句的确切执行顺序和执行时间很难预测。
+<code C>
+A = o
+A = x
+B = A
+B = A
+A = x
+A = o
+</code>
 现在，您需要对由N个语句组成的给定程序执行上下文无关指针分析，对于每个指针，输出它可以指向的对象。
@@ 行 29: / 行 41: @@
 在第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>
 =====题解=====
@@ 行 65: / 行 196: @@
 所有的 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

用户工具

站点工具

页面工具