题解 P4911 【河童重工的计算机】
囧仙
2020-10-24 22:00:43
## 题目大意
- 实现一个简单的汇编语言解释器。
## 题解
- 写了一个截止到当前为止 $(2020.10.24)$ 最短的代码 $\text{(4.70KB)}$ 。看看有没有人能打破吧。
- 代码经过了一些压行，压到了 $98$ 行，但尽量保持了可读性，每行大约 $80$ 个字符，也没有刻意压缩变量名。
说了一些闲话，让我们进入正题吧。
### 概况
这条大模拟题要求我们实现一个简单的**汇编语言解释器**。显然，我们首先需要阅读附件中的语言规范。经过阅读后，我们能获得以下信息：
- 每条汇编程序仅仅会对 $12$ 个寄存器、一块内存条、一个系统栈进行操作。我们可以直接开下这么大的空间。
- 实现的操作都较为简单，没有麻烦的中缀表达式求知等问题。每个指令参数都很简单。
- 直接暴力模拟不会超时。
出题人在文档中有些细节没有说明到位，这里补充一下：
- 注释中的方括号保证两两配对；形如 $\texttt{[[haha]wch(65);]}$ 的代码并不会执行 $\texttt{wch(65);}$ 。
- 形如 $\texttt{@\%ret}$ 的代码的含义是，内存条中第 $ret$ 个元素。
### 输入格式化
首先我们删除所有的注释和换行。这部分很容易实现，不再赘述。
观察到每条语句都以 $\texttt{;}$ 结尾，所以我们能用它分割每条独立的代码。对于每个代码，我们进行以下操作：
- $1.$ 将所有的逗号替换成空格。
- $2.$ 删除多余的空格。连续的空格只保留一个。删除前导空格和后缀空格。
- $3.$ 将处理完的语句放在字符数组里备用。
这部分操作相当简单，但为我们精准识别每条指令很有帮助。
### 框架
其实这条题目并不是很难，主要考查了选手对程序的设计能力以及编写能力。
#### 指令的存储
考虑将每条指令用一个结构体进行存储。具体而言，我们定义一个结构体 $\text{Opt}$ ，里面存储：这是什么指令、这个指令的参数。由于这题的指令都只和全局变量（寄存器之类）有关，因此实际设计的时候，参数只需要传入指针就行了。同时，我们也可以用函数指针指向当前指令所代表的含义。
```cpp
struct Opt{
void (*fun)(int,int**); int agc,**agv;
}O[MAXN];
```
我们将每条指令所对应的函数剥离出来：
```cpp
void add (int agc,int **agv){*agv[2]=(*agv[0])+(*agv[1]);}
void sub (int agc,int **agv){*agv[2]=(*agv[0])-(*agv[1]);}
...以下省略其他函数
```
那么，我们存储某个指令时，可以这么写：
```cpp
O[1].fun=add;
O[1].agc=2;
O[1].agv[0]=&r1;
O[1].agv[1]=&r2;
```
当我们执行这个操作时，只需要调用 $\texttt{O[1].fun(O[1].agc,O[1].agv);}$ 就行了。
#### 名称的识别
考虑写一个简单的哈希函数。
```cpp
unsigned int hsh(const char *s){
unsigned int h=0;
for(int p=0;s[p]!=' '&&s[p]&&s[p]!='\r'&&s[p]!='\n';++p)
h=h*13331+s[p];
return h;
}
```
它的含义是，将一个 $\text{C}$ 风格字符串映射到一个 $32$ 位无符号整型。这样子便于我们识别输入的函数名称、寄存器名称。
为了方便识别，可以考虑写一个注册函数，将我们会用到的指令名提前映射到相应的函数。
```cpp
void (*FN[MAXV])(int,int**);
void rgf(const char *s,void(*fn)(int,int**)){
unsigned int h=hsh(s)%MAXV;
FN[h]=fn;
}
```
当我们调用 $\texttt{rgf("add",add)}$ 时，我们就“注册”了一个名为 $\text{add}$ 的指令。
对于寄存器的映射，如法炮制即可。这种方法同样可以用来处理自定义的函数名称 $\texttt{function \text{\textdollar} xxx}$ 。
#### 函数参数处理
在这个汇编程序中，有种比较特殊的数据格式 $\texttt{@\%p}$ 。它的含义是内存条中第 $p$ 个数据。其中 $p$ 是一个寄存器（如 $e_1,e_2,val\cdots$）。也就是说，参数所对应的**地址不是固定的**。
当然，这个问题也很容易解决。我们设 $p'$ 为内存条中第 $p$ 个元素的值，然后让函数的参数指向 $p'$ 就行了。不过，每执行一次指令，都需要更新一遍 $p'$ ；执行完指令后，还要根据 $p'$ 是否被更改来更新内存条中第 $p$ 个元素。
这其中还有其他细节，诸如 $p$ 并不是一个合法的内存下标。同时，由于 $p$ 可能在指令中被更改，我们需要提前记录执行指令前的 $p$ 的值。当然，这些都是小问题，特判就行了。
#### 常量
这部分内容也很简单。由于我们的函数参数是指针，操作的是指针指向的值，所以我们另开一个数组 $C$ ，常量存储在 $C$ 中，然后指针指向对应的内存就行了。
### 其他细节
- $1.$ 尽管寄存器数量众多，但我们能够发现，每个寄存器实现的操作类似。于是，只要开一个数组 $L$ 统一存储总共 $12$ 个寄存器就行了。
- $2.$ 规范文件中出现了多次形如“没有 $\texttt{<2>}$ 参数就存入 $val$ 内”的语句。我们可以用宏定义简化这个过程，类似于 $\texttt{\#define a2 (agc>=2?(*agv[2]):val)}$ 。
- $3.$ 指令部分的总长度可能超过 $\text{500KB}$ ，注意开大数组，防止 $\texttt{RE}$ 。
- $4.$ 我太懒了没写哈希碰撞的处理，可能会导致哈希碰撞然后 $\text{WA}$ 。
- $5.$ 换行符这种东西， $\text{Windows}$ 下是 $\verb!\r\n!$ ， $\text{Linux}$ 下是 $\verb!\n!$ 。但只要提升程序的鲁棒性，这都不是问题。
## 其他
当我第一次写完这份代码时，一共写了 $\text{8KB}$ 左右，大约 $200$ 行。后来进行了一些优化压缩到了现在的状态。
我想吐槽一下 $\texttt{callfunc}$ 函数。语言规范中它转到的是对应的函数名的所在行，而并非对应的函数名所在的 $\texttt{function}$ 函数位置。这可能导致一行写多条代码出错，尽管测试数据中并不存在这样的数据。
另外，这个测试数据好水，基本上是随机生成的；似乎没有 $\text{jmp}$ 指令和 $\text{jif}$ 指令；每行只有一个代码，没有注释，~~每个代码过于规范以至于我写的格式化部分没啥卵用~~。
但无论如何，这是编写高级语言解释器的第一步。~~手刃未来程序改指日可待~~。
最后说一句，$\Large\text{我大河童科技世界第一！}$
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
typedef long long i64;
#define ag (int agc,int **agv)
using namespace std;
const int MAXN =5e4+3,MAXM=5e5+3,MAXT=11+3,MAXV=999997;
const int MAXR=1e6+3,MAXK=1024*1024*16+3,MAXS=1024*512+3;
int n,m,rp,op,mc,len,s,pp,ll,tp;
int LL[MAXT],RR[MAXT],WW[MAXT],VV[MAXT],L[MAXN],R[MAXN],S[MAXS],C[MAXN*5],M[MAXK];
char RD[MAXR],TP[MAXM],IN[MAXM],OT[MAXM];
int* put(int w){C[++mc]=w; return &C[mc];}
int rdi(){
int w=1,c,r;
while((c=IN[rp++])> '9'||c< '0') w=(c=='-'?-1:1); r=c-'0';
while((c=IN[rp++])>='0'&&c<='9') r=r*10+c-'0';
return r*w;
}
int rdc(){char c; while((c=IN[rp++])=='\n'||c=='\r'||c==' '); return c;}
void wti(int x){i64 xx=x;if(xx<0) OT[op++]='-',xx=-xx; if(xx>9) wti(xx/10); OT[op++]=xx%10+'0';}
#define a0 (*agv[0])
#define a1 (*agv[1])
#define av2 (agc>2?(*agv[2]):LL[8])
#define af2 (agc>2?(*agv[2]):LL[9])
#define av0 (agc>0?(*agv[0]):LL[8])
void fnc ag{return;} void udf ag{return;} void nop ag{return;} void hlt ag{return;}
void sst ag{a1=a0;} void jmp ag{pp=L[a0+LL[11]]-1;} void jif ag{if(a1) pp=L[a0+LL[11]]-1;}
void cal ag{S[s++]=pp,pp=L[a0]-1;} void ret ag{if(agc>0)LL[10]=a0;pp=S[--s];}
void add ag{av2=a0+ a1;} void sub ag{av2=a0- a1;} void mlt ag{av2=a0* a1;}
void div ag{av2=a0/ a1;} void mod ag{av2=a0% a1;} void lst ag{av2=a0<<a1;}
void rst ag{av2=a0>>a1;} void bnd ag{av2=a0& a1;} void bor ag{av2=a0| a1;}
void bxr ag{av2=a0^ a1;} void lgr ag{af2=a0> a1;} void lls ag{af2=a0< a1;}
void lge ag{af2=a0>=a1;} void lle ag{af2=a0<=a1;} void leq ag{af2=a0==a1;}
void lnd ag{af2=a0& a1;} void lor ag{af2=a0| a1;} void inv ag{(agc>1?a1:LL[8])=-a0;}
void rnt ag{av0=rdi();} void rch ag{av0=rdc();}
void wnt ag{wti(av0);} void wch ag{OT[op++]=a0;}
struct Opt{void (*fun)(int,int**);int agc,**agv;}O[MAXN];
unsigned int hsh(const char *s){
unsigned int h=0; for(int p=0;s[p]!=' '&&s[p]&&s[p]!='\r'&&s[p]!='\n';++p)
h=h*13331+s[p]; return h;
}
void (*FN[MAXV])(int,int**); int N[MAXV],V[MAXV];
void rgf(const char *s,void(*fn)(int,int**)){unsigned int h=hsh(s)%MAXV; FN[h]=fn;}
void rgv(const char *s,int vl){unsigned int h=hsh(s)%MAXV; N[h]=vl;}
int main(){
int c,t=0,w=0,f=0; LL[11]=1;
rgf("function",fnc),rgf("callfunc",cal);
rgf("udef",udf),rgf("hlt" ,hlt),rgf("nop" ,nop),rgf("set" ,sst);
rgf("jmp" ,jmp),rgf("jif" ,jif),rgf("call",cal),rgf("ret" ,ret);
rgf("inv" ,inv),rgf("add" ,add),rgf("sub" ,sub),rgf("mult",mlt);
rgf("idiv",div),rgf("mod" ,mod),rgf("lsft",lst),rgf("rsft",rst);
rgf("band",bnd),rgf("bor" ,bor),rgf("bxor",bxr),rgf("lgr" ,lgr);
rgf("lls" ,lls),rgf("lge" ,lge),rgf("lle" ,lle),rgf("leql",leq);
rgf("land",lnd),rgf("lor" ,lor),rgf("rint",rnt),rgf("rch" ,rch);
rgf("wint",wnt),rgf("wch" ,wch);
rgv("r1",0),rgv("r2",1),rgv("r3",2),rgv("r4",3);
rgv("e1",4),rgv("e2",5),rgv("e3",6),rgv("e4",7);
rgv("r1",0),rgv("r2",1),rgv("r3",2),rgv("r4",3);
rgv("val",8),rgv("flag",9),rgv("ret",10),rgv("line",11);
scanf("%d",&n); up(1,n,i){
while((c=getchar())=='\r'||c=='\n'); RD[len++]=c;
while((c=getchar())!='\r'&&c!='\n') RD[len++]=c;
RD[len++]='!';
}
up(0,len-1,i){
if(RD[i]==',') RD[i]=' '; else if(RD[i]=='!'){++ll,L[ll]=m+1;continue;}
if(RD[i]=='[') ++f; else if(RD[i]==']') {--f;continue;} if(f) continue;
if(RD[i]==';'){
if(TP[t-1]==' ') --t,TP[t]=0;
O[++m].fun=FN[hsh(TP)%MAXV],R[m]=ll;
up(0,t-1,j) if(TP[j]==' ') ++O[m].agc; O[m].agv=new int*[O[m].agc];
up(0,t-1,j){
if(TP[j]!=' ') continue;
if(TP[j+1]=='%') O[m].agv[w++]=LL+N[hsh(TP+j+2)%MAXV];
else if(TP[j+1]=='#') O[m].agv[w++]=put(ll);
else if(TP[j+1]=='@'){
if(TP[j+2]=='%') O[m].agv[w++]=RR+N[hsh(TP+j+2)%MAXV];
else sscanf(TP+j+3,"%d",&tp),O[m].agv[w++]=M+tp;
} else if(TP[j+1]=='$'){
unsigned int h=hsh(TP+j+2)%MAXV;
if(O[m].fun==fnc) V[h]=ll; O[m].agv[w++]=V+h;
} else sscanf(TP+j,"%d",&tp),O[m].agv[w++]=put(tp);
}
memset(TP,0,t+3),t=w=0;
} else if(RD[i]!=' '||(RD[i]==' '&&t>0&&TP[t-1]!=' ')) TP[t++]=RD[i];
}
pp=1,fread(IN,1,MAXM,stdin);
while(pp<=m&&O[pp].fun!=hlt){
LL[11]=R[pp],memcpy(WW,LL,sizeof(LL));
up(0,11,i) if(LL[i]>=0&&LL[i]<MAXM) RR[i]=M[LL[i]],VV[i]=RR[i];
O[pp].fun(O[pp].agc,O[pp].agv);
up(0,11,i) if(WW[i]>=0&&WW[i]<MAXM) if(RR[i]!=VV[i]) M[WW[i]]=RR[i];
++pp;
}
fwrite(OT,1,op,stdout);
return 0;
}
```