P4911 河童重工的计算机题解

AzusaShirasu · 2021-06-30 20:21:19 · 题解

Update at June 30th

这道题目最重要的就是实现指令的操作

然后实现操作离不开变量与内存系统。

所以我们必须先实现内存系统，然后才能够进行下一步的工作。

=====正文分割线=====

1.内存系统

内存系统中包含寄存器，这个相对好模拟，直接使用变量保存即可

还包含许多内存单元，而且有地址，这时我们用一个数组来充当就行了

具体来说，在访问变量时我们要判断是什么类型的变量：

如果是常量就直接返回；
如果是内存地址就去数组里找对应的值；
如果是寄存器就去取对应的变量，这里我用了 12 个 if 语句去逐一判断；
如果是 @% 开头的，就分步计算：先找寄存器，再找内存。

有一些细节（比如编译期常量 #line）需要注意去实现，可参见代码。

2.指令系统

指令还行，按照题目意思去模拟即可，算术指令代码量大，好在思维难度不高

判断第一个字符串就可以知道是什么类型的指令了，然后按照上面所说的方式去获取操作数

另外：

注意判断操作数个数

注意判断操作数个数！

注意判断操作数个数！！！

很容易在这里卡住（事实上我就是这样），因为如果操作数不够要把运行结果放到 %val 寄存器当中。

然后比较难的就是调用 call 和跳转 jmp 指令

怎么办呢？

其实可以使用一个额外的变量 line 来代表“当前运行到程序的哪一行”，这样就顺手解决了 #line 常量的问题。

call 指令还需要实现一个调用栈

什么？不知道什么是调用栈？？？

。。。。。。看过来，下面是简单的解释：

在一个线程中（可能不是很严谨，望包涵），同一时刻只能有一个函数在运行

也就是 CPU 控制权是在这个函数的栈帧上的，

然后呢，这个函数运行完之后，CPU 控制权会回到这个函数的调用者身上

所以说，每调用一层函数，控制权就会到这个函数身上；

然后调用完，回到调用者身上

这不就是一个先进后出的栈吗？

在本道题中就是使用栈保存当前 line 的值

每次返回都弹出栈顶

总之，调用 call 时调用栈 push；返回时调用栈 pop，解决。

3. 读取系统

读取时我们可以直接忽略注释

当检测到没有闭合的中括号 [] 时就只读入字符不送进指令流

在专业的代码编译 / 解释器中（比如浏览器的 HTML 解析），运行方式如下：

先把代码词法分析（tokenize）成许多的 token
然后送进一个 token 流（token stream）
然后建立语法树，叫做语法分析
最后送给编译器编译 / 虚拟机执行

本道题我们实现的就是一个虚拟机，执行字节码（bytecode）

我们忽略所有的空白，包括注释在内，运行时就不用去特判了

其实如果开发过语言解释器或者编译器的话，相对比较容易理解。

（但是开发解释器真的很不容易……亲身经历）

=====分割线=====

关键代码如下，想找完整源代码可以戳剪贴板传送门

//这是一个运行指令的函数
...
    String type = tokens[0];
    if(type == "set") {
        setval(tokens[1], expression(tokens[2]));
        line++;
    }
    else if(type == "rint") {
        int x;
        cin >> x;
        if(opcnt == 1) setval("%val", x);
        else setval(tokens[1], x);
        line++;
    }
    else if(type == "rch") {
        char x;
        cin >> x;
        if(opcnt == 1) setval("%val", x);
        else setval(tokens[1], x);
        line++;
    }
    else if(type == "wint") {
        if(opcnt == 1) cout << expression("%val");
        else cout << expression(tokens[1]);
        line++;
    }
    else if(type == "wch") {
        if(opcnt == 1) cout << (char)expression("%val");
        else cout << (char)expression(tokens[1]);
        line++;
    }
    else if(type == "Warfarin") {
        cout << "っ！おい！何をしている……" << endl;
        line++;
    }
    else if(type == "Ptilopsis") {
        cout << "エラー発生。" << endl;
        line++;
    }
    else if(type == "inv") {
        int ans = !expression(tokens[1]); 
        if(opcnt == 2) setval("%val", ans);
        else setval(tokens[2], ans);
        line++;
    }
    else if(type == "add") {
        int ans = expression(tokens[1]) + expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "sub") {
        int ans = expression(tokens[1]) - expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "mult") {
        int ans = expression(tokens[1]) * expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "idiv") {
        int ans = expression(tokens[1]) / expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "mod") {
        int ans = expression(tokens[1]) % expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "lsft") {
        int ans = expression(tokens[1]) << expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "rsft") {
        int ans = expression(tokens[1]) >> expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "band") {
        int ans = expression(tokens[1]) & expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "bor") {
        int ans = expression(tokens[1]) | expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "bxor") {
        int ans = expression(tokens[1]) xor expression(tokens[2]); 
        if(opcnt == 3) setval("%val", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "lgr") {
        int ans = expression(tokens[1]) > expression(tokens[2]); 
        if(opcnt == 3) setval("%flag", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "lls") {
        int ans = expression(tokens[1]) < expression(tokens[2]); 
        if(opcnt == 3) setval("%flag", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "lge") {
        int ans = expression(tokens[1]) >= expression(tokens[2]); 
        if(opcnt == 3) setval("%flag", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "lle") {
        int ans = expression(tokens[1]) <= expression(tokens[2]); 
        if(opcnt == 3) setval("%flag", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "leql") {
        int ans = expression(tokens[1]) == expression(tokens[2]); 
        if(opcnt == 3) setval("%flag", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "land") {
        int ans = expression(tokens[1]) && expression(tokens[2]); 
        if(opcnt == 3) setval("%flag", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "lor") {
        int ans = expression(tokens[1]) || expression(tokens[2]); 
        if(opcnt == 3) setval("%flag", ans);
        else setval(tokens[3], ans);
        line++;
    }
    else if(type == "callfunc") {
        String func = CUT(tokens[1]);
        callFunc(func);
    }
    else if(type == "jmp") {
        line = funcline[callstack.top()];
        line = line + expression(tokens[1]);
    }
    else if(type == "jif") {
        bool condition;
        if(opcnt == 2) condition = getval("%flag");
        else condition = expression(tokens[2]);
        if(condition) {
            line = funcline[callstack.top()];
            line = line + expression(tokens[1]);
        }
        else line++;
    }
    else if(type == "ret") {
        if(opcnt == 2) setval("%ret", expression(tokens[1]));
        return false;
    } 
    else if(type == "hlt") {
        exit(0);
        line++;
    }
    else line++;
...

最后，给那些想了解解释器、编译器、虚拟机等的oier们安利一下WarfarinBloodanger 博客哦

求通过~

P4911 河童重工的计算机 题解

1.内存系统

2.指令系统

3. 读取系统

P4911 河童重工的计算机题解