MENU

没事找事:WTFPL解释器的C++实现

July 21, 2014 • 程序

写在前面:本文中所提到的源代码及由其编译得到的二进制可执行文件(Windows)可以在这里下载到。本代码已在GNU/Linux GCC、MinGW GCC及Microsoft Visual C++环境下编译通过且正常运行测试样例。压缩包中的二进制文件是使用Microsoft Visual Studio 2013生成的。

简介:这是一个使用C++实现的What The Fuck Programming Language解析器。本来打算写的是GrassMudHorse Programming Language的解析器,最终由于编码问题放弃了。如果读者您能够完美解决这个问题并保持额外开销在一个很低的水平,请与我取得联系,不胜感激。

WTFPL和GMHPL均是由Whitespace编程语言改编而来。Whitespace这个东西我倒是知道挺久了,GMHPL是去年才偶然发现的。这种语言构造很简单,是基于堆栈实现的,最理想情况下仅需3种字符便能完成。它共有5种类型的指令:栈操作、堆操作、数学运算、流程控制、输入输出。解析器依据GMHPL简易指南编写。

抱歉我太啰嗦了,在文章正式开始之前,这里还是插入一个小小的常见问题解答。
问:我可以随意使用这个开源软件吗?它是否随着某许可协议发布?
答:WTFPL当然要使用WTFPL(Do What The Fuck You Want To Public License)发布!如WTF公共许可协议所言,你想干嘛就干嘛!
问:这份代码是否安全?我运行它不会造成电脑中毒或者崩溃死机等情况吧?
答:代码作者发誓未植入任何病毒或恶意代码,二进制文件完全由附带的源代码编译生成。因时间原因,除使用STL的代码有自动边界检查外,其它代码可能造成内存非法访问。如果您使用的操作系统还算主流,这仅仅只会导致解析器停止工作而不会对计算机造成损害。为了保障正常使用,请确认它运行的WTF代码没有错误。
问:不是说WTFPL是基于堆栈的语言吗?我怎么看到你的代码中堆用的是数组栈用的是vector容器实现的呢?这不是很不科学吗?
答:代码的实现是依据GMHPL的简易说明进行的,它对堆栈的定义就很不科学。为了完全支持WTFPL的各个指令,必须使用vector模拟栈,用数组实现堆。
问:类WS语言的解释器、虚拟机网上有一大把了,我为啥要用你的这个?
答:如果您愿意使用,作者当然是很高兴的。本解释器由作者花了几个小时使用效率极高的C++实现,性能是最大的亮点。自吹自擂的说,不用想也是比GMHPL的Just Out of Time虚拟机要快的。
问:WTFPL好难学也好难写呀!我怎么编写自己的测试用例来感受感受你的解释器运行是否正确呢?
答:如您所言,确实如此。建议您阅读GMHPL项目组编写的指南来举一反三。若您有耐心的话,请等到我的下一篇博文发布。

零、操作数转换

WTFPL中,对于操作数的定义如下:操作数是二进制的整数,对于流程控制指令来说是无符号的,否则是有符号的,第一位为符号位。定义方法是:W为0,T为1,F代表定义结束。对于符号位,W为正,T为负。
对此,我们将一个操作数读入字符数组,并进行一些处理。先回忆一下如何将X进制转换为十进制吧:结果计为0;从右向左计算,将结果加上第N位的值乘以X的N次方。这就很好办了。由上述定义可得,操作数最大可是一个无符号整数(设其为4字节),那么其范围为$[0,2^{32-1}]$。为了快速计算,咱们先打一个“2的0至31次方数值”表,然后按照基本计算方法计算就行啦。

unsigned int BinaryMap[] = {1,2,4,8,16,32,64,128,\
    256,512,1024,2048,4096,8192,16384,32768,\
    65536,131072,262144,524288,1048576,2097152,4194304,8388608,\
    16777216,33554432,67108864,134217728,268435456,536870912,1073741824\
};
int UnsignedOperandTransform(char *param)
{
    int len = strlen(param) - 1;//There's a character 'F' which is used to indicate the end of a binary number.
    int ret = 0;
    for(int i = len - 1; i >= 0; i--)
        if('T' == param[i])//'T' refers to 1
            ret += BinaryMap[len - i - 1];
    return ret;
}

对于有符号操作数,判断一下符号位然后接着调用这个函数即可。

一、栈操作

栈操作共有6种,如下:①将操作数压栈;②复制栈顶;③复制栈的第N个元素到栈顶;④交换栈顶两元素位置;⑤栈顶元素出栈;⑥保持栈顶不变,后面N个元素出栈。
在上面的FAQ中已经提到了,由于第③个栈操作非常的奇葩,必须使用vector(或其他容器)模拟来这个栈,就是用不了stack容器。功能使用STL的std::vector实现,非常简单,不再赘述。

二、数学运算

操作规则定义:操作时先弹出一个栈元素为运算的右值,再弹出一个为左值,计算后将结果压栈。
操作数类型:整型。
支持的运算:加、减、乘、除、模。此处除法是整数除法。
实现思路:从栈中弹出两个操作数ab,使用switch判断操作类型,将结果存入result。最后,将result压栈。

三、堆操作

堆的定义:与栈一样,堆也只能存储整数,默认情况下堆最多支持65536个堆元素(地址0-65535)。堆的大小可通过改变const int HEAP_SIZE来改变(当然需要重新编译)。
堆操作的规则:如果要存储,要先将要操作的堆地址压栈,再把要存储的数压栈,操作时弹出栈顶两元素,将栈顶元素存储到次栈顶指示的堆空间中;如果要取出,要先将地址压栈,操作时弹出栈顶元素,根据其指示的地址取出堆中元素压栈。
实现思路:继续使用STL即可,非常简单。如果要避免非法内存访问,需结合HEAP_SIZE做边界检查。

四、流程控制

流程控制是实现中最难的地方。共有七种指令:①定义一个标记;②调用标记处的函数;③无条件跳转到标记处;④如果栈顶元素等于0则跳转到标记指示处并弹出栈顶元素;⑤如果栈顶元素小于0则跳转到标记指示处并弹出栈顶元素;⑥函数结束,返回调用处;⑦无条件结束程序运行。
凭感觉来说,指令①像是写一个语句标号,指令③像是goto,而指令②竟然还引入了函数的概念,这就有些小麻烦了。看了代码就会知道,解释器使用的是FILE指针读取源代码,那如果要实现跳转就相当于fseek到某个位置。
既然引入了标签和函数的概念,我们需要一个表来保存标签的位置,这里采用std::map容器(map是使用红黑树组织的,据说采用散列表的unordered_map可以达到$O(1)$级别的效率)实现;我们还需要在调用函数时保存当前位置,那么再用std::vector容器模拟一个函数调用栈。函数调用栈是可以使用std::stack的,出于对解析器大小的考虑,没有引入新的头文件了。
为了确保程序执行时能够正确跳转到任意一个标签,在正式开始解释程序前,解释器需要先把程序遍历一遍,找出所有的标签并放入map容器。map容器的声明是这样的:std::map<int,int> Labels;。键是标签,值是相对文件头部的偏移字节数。遍历程序并找出标签的功能是由函数Parse实现的。定义如下。

void Parse(void)
{
    char Ins[64];
    while(fscanf(fp,"%s",Ins) != EOF)
        if('F' == Ins[0] && 'W' == Ins[1] && 'W' == Ins[2])
            Labels.insert(std::make_pair(UnsignedOperandTransform(Ins + 3), ftell(fp)));
    fseek(fp, 0, SEEK_SET);
}

从这个函数也可以看出,流程控制只需善用ftellfseek函数就能很好地完成。

五、输入输出

输入输出仅有四种情况:①弹出栈顶以字符形式输出;②弹出栈顶以整数形式输出;③从标准输入读入一个字符,放入栈顶对应的堆空间并将栈顶弹出;④从标准输入读入一个整数,放入栈顶对应的堆空间并将栈顶弹出。
实现思路:STL+stdio即可咯。

测试用例

WWWTF
FWWWTWWWWTTF
WFW
TFWT
WWWTWTWF
TFWW
WWWTF
TWWW
WFW
WWWTWTTF
TWWT
FTWWTWWWTWTF
FWFWTWWWWTTF
FWWWTWWWTWTF
WFF
SHIT

请将上面的代码保存为onetoten.wtf并与解释器置于同一目录。对于Windows系统:执行wtf onetoten.wtf;对于*nix系统:执行./wtf onetoten.wtf。若终端中出现了逐行输出的数字1至10,则程序运行正常。

Tags: c/cpp
Archives Tip
QR Code for this page
Tipping QR Code