Loading…

题前

之前在有看到死月撸了一个BrainF**k的解释器,因为不甘寂寞所以这次也循例来撸个和BrainF**k差不多的解释器——Befunge,同样感谢下@Bolt_白衣苍狗,我也是看了他的专栏才知道有codewars这么好玩的地方。

什么是Befunge

依照惯例贴下codewars问题描述。原题在此

Your task is to write a method which will interpret Befunge-93 code! Befunge-93 is a language in which the code is presented not as a series of instructions, but as instructions scattered on a 2D plane; your pointer starts at the top-left corner and defaults to moving right through the code. Note that the instruction pointer wraps around the screen! There is a singular stack which we will assume is unbounded and only contain integers. While Befunge-93 code is supposed to be restricted to 80x25, you need not be concerned with code size. Befunge-93 supports the following instructions (from Wikipedia)

语言简介

Befunge由Chris Pressey在1993年创造的、基于二维控制的程序语言,它用 < > v ^ 这四个符号来控制一个指针在代码中移动,指针经过一个字符或数字则把它压入一个栈,四则运算符号的功能就是弹出栈顶两个元素进行计算后把结果压回去。用 _ 和 | 来表示有条件的方向选择:当栈顶元素为0时向右(上)走,否则向左(下)走。句号和逗号分别表示将栈顶元素作为整数或字符输出。最后以一个@符号表示程序结束。Befunge代码的注释不需要任何符号标明,你可以把注释写在程序的任何地方,只要运行时指针不会经过它就行了。

示例代码 -> return 3

>1+2.@ 

示例代码 ->return HelloWorld!

>              v
v  ,,,,,"Hello"<  
>48*,          v
v,,,,,,"World!"<  
>25*,@

操作符

  • [0-9] 将数字压入栈
  • [+]    加法运算: 弹出a,b, 将运算结果压栈.
  • [-]     减法运算: 弹出 a,b, 将运算结果压栈.
  • [*]     乘法运算: 弹出 a,b, 将运算结果压栈.
  • [/]     除法运算(整数): 弹出 a,b, 将运算结果压栈, 四舍五入,如果a为0,直接压入0.
  • [%]   模运算: 弹出 a,b, 将运算结果压栈. 如果a为0,直接压入0.
  • [!]      逻辑非: 弹出一个值. 如果值为0,像栈内压入1,否则压入0.
  • [`]     比较: 弹出a,b, 如果b大于a向栈内压入1, 否则压入0.
  • [>]    右移.
  • [<]    左移.
  • [^]    上移.
  • [v]    下移.
  • [?]    随机上下左右移动.
  • [_]    弹出一个值,如果值为0则向右移动,否则向左移动.
  • [|]     弹出一个值,如果值为0则向下移动,否则向上移动.
  • ["]    开启字符串模式直到遇到下一个双引号为止,并且把每一个字符的Ascii码值压入栈。
  • [:]     复制栈顶元素. 如果栈为空,则压入0.
  • []      交换栈顶得两个元素. 如果只有一个元素, 则假设底部元素为0.
  • [$]    弹出一个值,丢弃.
  • [.]     弹出一个值且以整数输出.
  • [,]     弹出一个值输出其对应Ascii码表中的字符.
  • [#]    忽略下一个操作符
  • [p]   “放置” (一种存储值以便将来使用的方法).弹出 y,x,v 并且将代码位置(x,y)的值改变成v对应Ascii表中的字符.
  • [g]   "获取" (一种从贮存器读取数据的方法).弹出y,x ,然后将这个字符的ascii值压栈.
  • @     程序终了.
  • (i.e. 空格) 不进行任何操作.

相比Codewars问题描述中对操作符的解释,我更倾向于这版文档

相应工具函数

为了方便解释器的运行,首先需要建立一系列的工具函数。

var utils={}  

既然Befunge是一个基于二维的程序语言,而测试端的输入是通过\n换行符来表示换行的,我们第一个需要做的就是把字符串转换成一个二维矩阵来方便后续的使用。

tokenize:function(code){  
        var matrix=[[]],x=0,y=0;
        for(var i=0;i<code.length;i++){
            if(code[i]==='\n'){
                y++;x=0;
                matrix.push([])
            } else {
                matrix[y][x]=code[i];
                x++;
            }
        }
        return matrix;          
    }

其次对应的加减乘除运算。

    add:function(a,b){
        return parseInt(a)+parseInt(b);
    },
    minus:function(a,b){
        return parseInt(b)-parseInt(a);
    },
    multiply:function(a,b){
        return parseInt(a)*parseInt(b)
    },
    divide:function(a,b){
        return a===0 ? 0 : parseInt(b)/parseInt(a)
    },
    mod:function(a,b){
        return a===0 ? 0 : parseInt(b)%parseInt(a)
    },
    not:function(a){
        return a===0 ? 1 : 0
    },
    greater:function(a,b){
        return b>a ? 1 : 0
    }

使用LCG线性同余生成器来生成随机数

    rnd:function(seed){
        seed = ( seed * 9301 + 49297 ) % 233280; 
        return seed / ( 233280.0 );     
    },
    random:function(num){
        today = new Date(); 
        seed = today.getTime();
        return Math.ceil( this.rnd( seed ) * num );     
    }

Befunge的解释器之所以是Rank2,其中一部分原因就是这种代码太难调试,为了方便调试,实现sleep函数和行走路径记录。

sleep:function(n){  
        var ms=n*1000;
        var end=new Date().getTime()+ms
        while(new Date().getTime()<end){
            void 0
        }       
    },
    PathHistory:[]

解释器实现

function interpret(code,debug){}  

首先需要初始化一系列变量、参数.

    var  posX=0,posY=0,stringMode=false,output="",stack=[]
    var  matrix=utils.tokenize(code)

初始化我们的方向函数来实现指针在矩阵中的运动.

Go={  
            right:function(){
                posX++;
                utils.PathHistory.push('Right')
                Go.update=true;
                Previous.ready(Go.right)
            },
            left:function(){
                posX--;
                if(posX<0)
                    posX=0
                utils.PathHistory.push('Left')
                Go.update=true;
                Previous.ready(Go.left)
            },
            up:function(){
                posY--;
                if(posY<0)
                    posY=0;
                utils.PathHistory.push('Up')
                Go.update=true
                Previous.ready(Go.up)
            },
            down:function(){
                posY++;
                utils.PathHistory.push('Down')
                Previous.ready(Go.down)
                Go.update=true;
            },
            update:false
        }
        ,Previous={
            cb:Go.right,
            ready:function(cb){ this.cb=cb},
            go:function(){ this.cb(); Go.update=false }
        }

        Go.Dir=[Go.right,Go.left,Go.up,Go.down]

根据需要增强Array

Array.prototype.popUp=function(){ return this.length==0 ? 0 : this.pop() }  

而主体逻辑基本上就是如下的判断情况。

while (当前操作符不为@){  
    如果 (处于字符串模式且当前操作符不为双引号){
        将当前字符的Ascii码压栈
    } 否则 {
        switch(当前操作符){
            //case by case
            default:
                如果(数字){
                    压栈
                }
        }
        如果 (行走方向没有被更新过){
            按照上一次行动的方向继续运动
        } 否则 {
            将表示方向更新的开关置为False
        }
    }
}
如果(处于debug模式){
    输出行走路径
}
return 返回值  

接着挑几个操作符解释一下.

+ 加法运算

case "+":  
    stack.push(utils.add(stack.popUp(),stack.popUp()));
    break;

\ 反斜杠,由于JS的数组的压入压出是倒序模式,所以可以顺序压出组成数组然后和原先的栈连接就达到了交换的目的。

case "\\":  
    var tmp=[]
    if(stack.length==1)
        tmp=[0,stack.popUp()]
    else
        tmp=[stack.popUp(),stack.popUp()]
    stack=stack.concat(tmp);
    break;

# 井号 若为井号则忽略下一个操作符,按照上一次的运动方向直接行走。

case "#":  
    Previous.go();
    break;

? 问号,通过生成器生成随机数,获得方向函数,执行。

case "?":  
    Go.Dir[utils.random(4)-1]();
    break;

左移

case "<":  
    Go.left();
    break;

完整的代码实现

相比老外的惊才绝艳,我的实现可能比较传统而且显得冗长。

function interpret(code,debug){

    var  stack=[]
        ,matrix=utils.tokenize(code)
        ,Go={
            right:function(){
                posX++;
                utils.PathHistory.push('Right')
                Go.update=true;
                Previous.ready(Go.right)
            },
            left:function(){
                posX--;
                if(posX<0)
                    posX=0
                utils.PathHistory.push('Left')
                Go.update=true;
                Previous.ready(Go.left)
            },
            up:function(){
                posY--;
                if(posY<0)
                    posY=0;
                utils.PathHistory.push('Up')
                Go.update=true
                Previous.ready(Go.up)
            },
            down:function(){
                posY++;
                utils.PathHistory.push('Down')
                Previous.ready(Go.down)
                Go.update=true;
            },
            update:false
        }
        ,Previous={
            cb:Go.right,
            ready:function(cb){ this.cb=cb},
            go:function(){ this.cb(); Go.update=false }
        }

    Go.Dir=[Go.right,Go.left,Go.up,Go.down]
    Array.prototype.popUp=function(){ return this.length==0 ? 0 : this.pop() }
    var posX=0,posY=0,stringMode=false,storage=[],output="",isSkip=false;


    while( matrix[posY][posX]!=='@' ){

        if(debug)
            utils.sleep(2)

        var command=matrix[posY][posX]
        if(stringMode && command!=="\""){
            stack.push(command.charCodeAt(0));
            //strCount++;
        } else {
            switch(command){
                case "+":
                    stack.push(utils.add(stack.popUp(),stack.popUp()))
                    break;
                case "-":
                    stack.push(utils.minus(stack.popUp(),stack.popUp()))
                    break;
                case "*":
                    stack.push(utils.multiply(stack.popUp(),stack.popUp()))
                    break;
                case "/":
                    stack.push(utils.divide(stack.popUp(),stack.popUp()))
                    break;
                case "%":
                    stack.push(utils.mod(stack.popUp(),stack.popUp()))
                    break;
                case "!":
                    stack.push(utils.not(stack.popUp()))
                    break;
                case "`":
                    stack.push(utils.greater(stack.popUp(),stack.popUp()))
                    break;
                case ">":
                    Go.right()
                    break;
                case "<":
                    Go.left()
                    break;
                case "^":
                    Go.up()
                    break;
                case "v":
                    Go.down()
                    break;
                case "?":
                    Go.Dir[utils.random(4)-1]();
                    break;
                case "_":
                    var val=stack.popUp();
                    ( val==0 ? Go.right() : Go.left() );
                    break;
                case "|":
                    var val=stack.popUp();
                    ( val==0 ? Go.down() : Go.up() );
                    break;
                case "\"":
                    stringMode=!stringMode;
                    break;
                case ":":
                    if(stack.length==0)
                        stack.push(0)
                    else 
                        stack.push(stack.slice(stack.length-1)[0])
                    break;
                case "\\":
                    var tmp=[]
                    if(stack.length==1)
                        tmp=[0,stack.popUp()]
                    else
                        tmp=[stack.popUp(),stack.popUp()]
                    stack=stack.concat(tmp);
                    break;
                case "$":
                    stack.popUp();
                    break;
                case ".":
                    var val=stack.popUp()
                    output+= ( val!==undefined ? String(val): "" )
                    break;
                case ",":
                    output+=String.fromCharCode(stack.popUp())
                    break;
                case " ":
                    break;
                case "#":
                    Previous.go()
                    break;
                case "~":
                    //this symbol was not implemented
                    break;
                case "p":
                    var y=stack.popUp(),x=stack.popUp(),v=String.fromCharCode(stack.popUp());
                        matrix[y][x]=v              
                    break;
                case "g":
                    var y=stack.popUp(),x=stack.popUp();
                    stack.push(matrix[y][x].charCodeAt())
                    break;
                default:
                    if(/\d/.test(command)){
                        stack.push(command)
                    }
                    break;
            }           
        } 

        if(!Go.update)
            Previous.go()
        else 
            Go.update=false
    }
    if(debug)
        console.log(utils.PathHistory.join(" -> "))

    return output
}


utils={  
    rnd:function(seed){
        seed = ( seed * 9301 + 49297 ) % 233280; 
        return seed / ( 233280.0 );     
    },
    random:function(num){
        today = new Date(); 
        seed = today.getTime();
        return Math.ceil( this.rnd( seed ) * num );     
    },
    tokenize:function(code){
        var matrix=[[]],x=0,y=0;
        for(var i=0;i<code.length;i++){
            if(code[i]==='\n'){
                y++;x=0;
                matrix.push([])
            } else {
                matrix[y][x]=code[i];
                x++;
            }
        }
        return matrix;          
    },
    add:function(a,b){
        return parseInt(a)+parseInt(b);
    },
    minus:function(a,b){
        return parseInt(b)-parseInt(a);
    },
    multiply:function(a,b){
        return parseInt(a)*parseInt(b)
    },
    divide:function(a,b){
        return a===0 ? 0 : parseInt(b)/parseInt(a)
    },
    mod:function(a,b){
        return a===0 ? 0 : parseInt(b)%parseInt(a)
    },
    not:function(a){
        return a===0 ? 1 : 0
    },
    greater:function(a,b){
        return b>a ? 1 : 0
    },
    sleep:function(n){
        var ms=n*1000;
        var end=new Date().getTime()+ms
        while(new Date().getTime()<end){
            void 0
        }       
    },
    PathHistory:[]
}

最后

感谢您耐着性子阅读到最后,既然读完了通篇的Befunge解释器实现,那么问题来了.........

About the author
comments powered by Disqus