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

NGC_4889 · 2023-09-23 18:32:04 · 题解

题解

&emsp;&emsp;无可争议的大模拟题。~~写到吐。~~ 题目中附件定义了具体的汇编语言格式，如果不嫌麻烦，一个一个地实现它们，就可以了，具体的实现细节就不逐一介绍了。这里简要介绍一下我自己实现过程中简化代码的方法和遇到的坑点。

（1）语句参数的统一处理

&emsp;&emsp;汇编语言中可能涉及到几种不同类型的参数，如常量、编译器常量、寄存器、内存等等。如果每执行一个汇编语句，都要分多种情形处理参数，未免太过繁琐。为了统一对参数的处理，可以定义一个参数类 struct Arg ，定义如下：

struct Arg {
    int type;   // 参数类型, 0: 常量 1: 寄存器 2: 固定位置内存 3: 寄存器位置内存
    int v;      // 获取参数值的辅助信息

    // 获取参数的值
    int getV() {
        if (type == 0)  return v;
        else if (type == 1) return reg[v];
        else if (type == 2) return mem[v];
        return mem[reg[v]];
    } 

    // 设置参数的值
    void setV(int a) {
        if (type == 1) reg[v] = a;
        else if (type == 2) mem[v] = a;
        else mem[reg[v]] = a;
    }
};

通过两个成员函数 setV 和 getV 统一处理不同类型参数的赋值操作和取值操作。

（2）查表优化

&emsp;&emsp;题目中需要用到 12 个寄存器，我们开一个寄存器数组 reg[15] ，数组下标 1-12 的位置分别存储这些寄存器的值。读入指令时，从中提取出表示寄存器的字符串，通过查表法，迅速获取寄存器在 reg 中的下标。对应的表的定义如下：

unordered_map<string, int> regType{{"R1", 1}, {"R2", 2}, {"R3", 3}, {"R4", 4}, {"E1", 5}, {"E2", 6}, 
                                   {"E3", 7}, {"E4", 8}, {"FLAG", 9}, {"VAL", 10}, {"LINE", 11}, {"RET", 12}};

类似地，给出一条指令的名称，我们也可以通过查表法迅速获取一条指令的操作码（编号 0-31），表的定义如下：

unordered_map<string, int> insType{{"UDEF", 0}, {"HLT", 1}, {"NOP", 2}, {"SET", 3}, {"JMP", 4}, {"JIF", 5}, {"CALL", 6},
                                   {"RET", 7}, {"INV", 8}, {"ADD", 9}, {"SUB", 10}, {"MULT", 11}, {"IDIV", 12}, {"MOD", 13},
                                   {"LSFT", 14}, {"RSFT", 15}, {"BAND", 16}, {"BOR", 17}, {"BXOR", 18}, {"LGR", 19},
                                   {"LLS", 20}, {"LGE", 21}, {"LLE", 22}, {"LEQL", 23}, {"LAND", 24}, {"LOR", 25}, {"RINT", 26},
                                   {"RCH", 27}, {"WINT", 28}, {"WCH", 29}, {"FUNCTION", 30}, {"CALLFUNC", 31}};

此外，当汇编语句开始模拟执行时，我们可以通过指令的操作码，从对应的函数指针数组中快速找到对应的执行函数，函数指针数组的定义如下：

using pFunc = void (*)(vector<Arg>& );

pFunc exec[32] = {Ins_UDEF, Ins_HLT, Ins_NOP, Ins_SET, Ins_JMP, Ins_JIF, Ins_CALL, Ins_RET, Ins_INV, Ins_ADD,
                  Ins_SUB, Ins_MULT, Ins_IDIV, Ins_MOD, Ins_LSFT, Ins_RSFT, Ins_BAND, Ins_BOR, Ins_BXOR, Ins_LGR,
                  Ins_LLS, Ins_LGE, Ins_LLE, Ins_LEQL, Ins_LAND, Ins_LOR, Ins_RINT, Ins_RCH, Ins_WINT, Ins_WCH,
                  Ins_FUNCTION, Ins_CALLFUNC};

通过上述这些查表优化，我们就省去了许多条件判断，降低了程序复杂度。

（3）个别指令的延迟处理

&emsp;&emsp;在我实现的程序中，对于指令的解析、注释的删除是边输入边处理的，每读入一行，就立即删除注释，把指令解析好，然后再读取下一行。然而，个别指令无法在线处理，比如， CALLFUNC 指令，该指令需要调用一个函数，处理该指令时，需要用到函数所在的行的信息。而调用的函数可能在 CALLFUNC 指令的后面才有定义，需要全部读取完输入数据才能确定该函数所在的行数。因此，该指令需要进行延迟处理。具体地，每读到一条 CALLFUNC 指令，将其加入一队列中，待 N 行程序全部读完，再逐一处理它们。

（4）遇到的坑

输入数据时，使用 scanf 读取 N 后，正式读取汇编程序前，要额外加一句 fgets，吃掉行尾的换行符。
注意常量有可能是负数，所以解析参数遇到负号 '-' 要特判一下。
寄存器的名称中可能含有数字，如 R1，E4 等，解析参数时不能遇到非字母字符就中止了。
打表时，不要把表中的指令的字母拼错。
注意区分左移 << 和右移 >> ······（谁能想到这是我debug过程中花费时间最长才发现的错误呢？T_T）

（5）代码实现

&emsp;&emsp;附上（不太会有人看的）代码实现如下：

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <unordered_map>

using std::vector;
using std::string;
using std::unordered_map;

unordered_map<string, int> regType{{"R1", 1}, {"R2", 2}, {"R3", 3}, {"R4", 4}, {"E1", 5}, {"E2", 6}, 
                                   {"E3", 7}, {"E4", 8}, {"FLAG", 9}, {"VAL", 10}, {"LINE", 11}, {"RET", 12}};

unordered_map<string, int> insType{{"UDEF", 0}, {"HLT", 1}, {"NOP", 2}, {"SET", 3}, {"JMP", 4}, {"JIF", 5}, {"CALL", 6},
                                   {"RET", 7}, {"INV", 8}, {"ADD", 9}, {"SUB", 10}, {"MULT", 11}, {"IDIV", 12}, {"MOD", 13},
                                   {"LSFT", 14}, {"RSFT", 15}, {"BAND", 16}, {"BOR", 17}, {"BXOR", 18}, {"LGR", 19},
                                   {"LLS", 20}, {"LGE", 21}, {"LLE", 22}, {"LEQL", 23}, {"LAND", 24}, {"LOR", 25}, {"RINT", 26},
                                   {"RCH", 27}, {"WINT", 28}, {"WCH", 29}, {"FUNCTION", 30}, {"CALLFUNC", 31}};

unordered_map<string, int> funcLoc;

int sp, stk[1 << 22], mem[1 << 24], reg[15];
int N, pc, rp, rcnt, rList[500005], lineStart[100005];
char buf[10005];
bool notefg = 0;    // 标识当前内容是否在注释中 

// 参数 
struct Arg {
    int type;   // 0: constant 1: % 2: @ 3: @%
    int v;

    int getV() {
        if (type == 0)  return v;
        else if (type == 1) return reg[v];
        else if (type == 2) return mem[v];
        return mem[reg[v]];
    } 

    void setV(int a) {
        if (type == 1) reg[v] = a;
        else if (type == 2) mem[v] = a;
        else mem[reg[v]] = a;
    }
}; 

void Ins_UDEF(vector<Arg>& arg) { exit(0); }

void Ins_HLT(vector<Arg>& arg) { exit(0); }

void Ins_NOP(vector<Arg>& arg) { ++pc; }

void Ins_SET(vector<Arg>& arg) { ++pc; arg[1].setV(arg[0].getV()); }

void Ins_JMP(vector<Arg>& arg) {
    pc = lineStart[reg[11] + arg[0].getV()];
}

void Ins_JIF(vector<Arg>& arg) {
    ++pc;
    if (arg[1].getV()) pc = lineStart[reg[11] + arg[0].getV()];
}

void Ins_CALL(vector<Arg>& arg) {
    ++pc;
    stk[++sp] = pc;
    stk[++sp] = reg[11];
    pc = lineStart[arg[0].getV()];
}

void Ins_RET(vector<Arg>& arg) {
    if (arg.size() > 0) reg[12] = arg[0].getV();
    reg[11] = stk[sp--];
    pc = stk[sp--];
}

void Ins_INV(vector<Arg>& arg) { ++pc; arg[1].setV(-arg[0].getV());}

void Ins_ADD(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() + arg[1].getV());}

void Ins_SUB(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() - arg[1].getV());}

void Ins_MULT(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() * arg[1].getV());}

void Ins_IDIV(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() / arg[1].getV());}

void Ins_MOD(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() % arg[1].getV());}

void Ins_LSFT(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() << arg[1].getV());}

void Ins_RSFT(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() >> arg[1].getV());}

void Ins_BAND(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() & arg[1].getV());}

void Ins_BOR(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() | arg[1].getV());}

void Ins_BXOR(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() ^ arg[1].getV());}

void Ins_LGR(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() > arg[1].getV());}

void Ins_LLS(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() < arg[1].getV());}

void Ins_LGE(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() >= arg[1].getV());}

void Ins_LLE(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() <= arg[1].getV());}

void Ins_LEQL(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() == arg[1].getV());}

void Ins_LAND(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() && arg[1].getV());}

void Ins_LOR(vector<Arg>& arg) { ++pc; arg[2].setV(arg[0].getV() || arg[1].getV());}

void Ins_RINT(vector<Arg>& arg) { ++pc; arg[0].setV(rList[rp++]);}

void Ins_RCH(vector<Arg>& arg) { ++pc; arg[0].setV(rList[rp++]);}

void Ins_WINT(vector<Arg>& arg) { ++pc; printf("%d", arg[0].getV());}

void Ins_WCH(vector<Arg>& arg) { ++pc; putchar(arg[0].getV()); }

void Ins_FUNCTION(vector<Arg>& arg) { ++pc; arg[1].setV(arg[0].getV()); }

void Ins_CALLFUNC(vector<Arg>& arg) { 
    ++pc; 
    stk[++sp] = pc;
    stk[++sp] = reg[11];
    pc = arg[0].getV();
}

using pFunc = void (*)(vector<Arg>& );

pFunc exec[32] = {Ins_UDEF, Ins_HLT, Ins_NOP, Ins_SET, Ins_JMP, Ins_JIF, Ins_CALL, Ins_RET, Ins_INV, Ins_ADD,
                  Ins_SUB, Ins_MULT, Ins_IDIV, Ins_MOD, Ins_LSFT, Ins_RSFT, Ins_BAND, Ins_BOR, Ins_BXOR, Ins_LGR,
                  Ins_LLS, Ins_LGE, Ins_LLE, Ins_LEQL, Ins_LAND, Ins_LOR, Ins_RINT, Ins_RCH, Ins_WINT, Ins_WCH,
                  Ins_FUNCTION, Ins_CALLFUNC};

struct Instruction {
    int type;
    vector<Arg> arg;

    void run() { exec[type](arg); }

} ins[55005];

int insp;

void passSpace(char*& p) {
    while (*p && isspace(*p)) ++p;
}

void passNote(char*& p) {
    if (!notefg) return;
    while (*p && *p != ']') ++p;
    if (*p == ']') notefg = 0, ++p;
}

int findEffCon(char*& p) {
    int fg = 0;     // 跳过的非注释内容中, 不包括逗号和分号(0)，包括逗号(1)，包括分号(2); 
    passNote(p);
    while (*p) {
        if (isspace(*p)) passSpace(p);
        if (*p == '[') {
            notefg = 1;
            ++p;
            passNote(p);
        }
        if (*p == ']') ++p;
        if (*p == ',') ++p, fg = 1;
        if (*p == ';') ++p, fg = 2;
        if (isalpha(*p) || isdigit(*p) || *p == '%' || *p == '@' || *p == '#' || *p == '$') break;
    }
    return fg;
}


int getInsType(char*& p) {
    string s = "";
    while (isalpha(*p)) 
        s += (char)toupper(*p), ++p;
    return insType[s];
}

Arg getInsArg(char*& p, int L) {
    int type, v;
    string s = "";
    if (isdigit(*p) || *p == '-') {
        int fg = (*p == '-' ? -1 : 1);
        type = v = 0; 
        while (isdigit(*p))
            v = v * 10 + *p - '0', ++p;
        v *= fg;
    } else if (*p == '#') {
        type = 0;
        v = L;
        ++p;
        while (isalpha(*p)) ++p;
    } else if (*p == '%') {
        type = 1;
        ++p;
        while (isalpha(*p) || isdigit(*p)) 
            s += (char)toupper(*p), ++p;
        v = regType[s];
    } else if (*p == '@') {
        ++p;    
        if (*p == '%') {
            type = 3; ++p;
            while (isalpha(*p) || isdigit(*p)) 
            s += (char)toupper(*p), ++p;
            v = regType[s];
        } else {
            type = 2;
            v = 0;
            while (isdigit(*p))
                v = v * 10 + *p - '0', ++p;
        }
    }
    return (Arg){type, v};
} 

string getFunName(char*& p) {
    string s = "";
    if (*p != '$') return s;
    s += *p;
    ++p;
    while (isalpha(*p) || isdigit(*p)) 
        s += *p, ++p;
    return s;
}

void input() {
    notefg = 0;
    scanf("%d", &N);
    fgets(buf, 10002, stdin);

    vector<std::pair<int, string>> q;
    for (int i = 1; i <= N; ++i) {
        fgets(buf, 10002, stdin);

        char* p = buf;
        findEffCon(p);
        while (*p) {
            int type = getInsType(p);
            ++insp;
            ins[insp].type = type;
            if (lineStart[i] == 0) lineStart[i] = insp;

            if (type == 7) ins[insp].arg.emplace_back((Arg){1, 12});
            if (type >= 26 && type <= 29) ins[insp].arg.emplace_back((Arg){1, 10});

            while (!findEffCon(p)) {
                if (type == 3) {
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                    findEffCon(p);
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type == 4 || type == 6) {
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type == 5) {
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                    if (findEffCon(p) == 2) {
                        ins[insp].arg.emplace_back((Arg){1, 9});
                        break;
                    }
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type == 7) {
                    ins[insp].arg.pop_back();
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type == 8) {
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                    if (findEffCon(p) == 2) {
                        ins[insp].arg.emplace_back((Arg){1, 10});
                        break;
                    }
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type >= 9 && type <= 18) {
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                    findEffCon(p);
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                    if (findEffCon(p) == 2) {
                        ins[insp].arg.emplace_back((Arg){1, 10});
                        break;
                    }
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type >= 19 && type <= 25) {
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                    findEffCon(p);
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                    if (findEffCon(p) == 2) {
                        ins[insp].arg.emplace_back((Arg){1, 9});
                        break;
                    }
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type >= 26 && type <= 29) {
                    ins[insp].arg.pop_back();
                    ins[insp].arg.emplace_back(getInsArg(p, i));
                } else if (type == 30) {
                    funcLoc[getFunName(p)] = insp;
                    ins[insp].arg.emplace_back((Arg){0, i});
                    ins[insp].arg.emplace_back((Arg){1, 11});
                } else if (type == 31) {
                    q.emplace_back(make_pair(insp, getFunName(p)));
                }
            }
        }
    }
    for (auto& [pos, s] : q) {
        ins[pos].arg.emplace_back((Arg){0, funcLoc[s]});
    }

    while (scanf("%d", rList + rcnt) == 1) ++rcnt;
}

int main() {
    pc = 1; 
    rp = rcnt = insp = 0;

    input();

    while (1) ins[pc].run();

    return 0;
}

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

题解