小型代码分析系统的实现方式
题目
一个程序中有 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，原因是在现实世界中，语句的确切执行顺序和执行时间很难预测。
A = o
A = x
B = A
B = A
A = x
A = o
现在，您需要对由N个语句组成的给定程序执行上下文无关指针分析，对于每个指针，输出它可以指向的对象。
输入的第一行包含一个整数N（1≤N≤200），表示程序中的语句数。等号“=”前后只有一个空格。
以下N行中的每一行都包含一个语句。
输出应该包含26行。
在第i行中，输出第i个指针的名称（第i个大写字母），后跟冒号“：”和空格，然后按字母顺序列出可通过该指针访问的对象。
样例
样例一：
5
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:
样例二：
4
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:
样例三：
3
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:
题解
直接暴力求解即可。本题难点可能只在于处理读入。
这里给出一个简单的暴力框架：令 pt(x) 为指针 x 可能指向的对象集合。
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
样例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 这些是指针。
代码
#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;
}
