囧仙 的博客

囧仙 的博客

题解 P4911 【河童重工的计算机】

posted on 2020-10-24 22:00:43 | under 题解 |

题目大意

  • 实现一个简单的汇编语言解释器。

题解

  • 写了一个截止到当前为止 $(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}$ ,里面存储:这是什么指令、这个指令的参数。由于这题的指令都只和全局变量(寄存器之类)有关,因此实际设计的时候,参数只需要传入指针就行了。同时,我们也可以用函数指针指向当前指令所代表的含义。

struct Opt{
    void (*fun)(int,int**); int agc,**agv;
}O[MAXN];

我们将每条指令所对应的函数剥离出来:

void add (int agc,int **agv){*agv[2]=(*agv[0])+(*agv[1]);}
void sub (int agc,int **agv){*agv[2]=(*agv[0])-(*agv[1]);}
...以下省略其他函数

那么,我们存储某个指令时,可以这么写:

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);}$ 就行了。

名称的识别

考虑写一个简单的哈希函数。

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$ 位无符号整型。这样子便于我们识别输入的函数名称、寄存器名称。

为了方便识别,可以考虑写一个注册函数,将我们会用到的指令名提前映射到相应的函数。

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{我大河童科技世界第一!}$

参考代码

#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;
}