用C++实现一个Brainfuck解释器

阅读量：6609 次

发布时间：2019-06-24

本文共 3296 字，大约阅读时间需要 10 分钟。

Brainfuck是一种极小化的计算机语言，只含有8种运算符，由于fuck在英语中是脏话，这种语言有时被称为brainfck或brainf**，甚至被简称为BF。正如它的名字所暗示，brainfuck程序很难读懂,尽管如此，brainfuck却是图灵完备的，也就是说它能够完成所有可计算的任务。
- - -

简介

以下摘自。

Müller的目标是创建一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。这种语言由八种运算符构成，为Amiga机器编写的编译器（第二版）只有240个字节大小。

这种语言基于一个简单的机器模型，除了指令，这个机器还包括：一个以字节为单位、被初始化为零的数组、一个指向该数组的指针（初始时指向数组的第一个字节）、以及用于输入输出的两个字节流。

下面是这八种状态的描述，其中每个状态由一个字符标识：(博客园的markdown居然不支持表格，我实在是...)

如果把这些指令翻译成C语言就是下面这样的：

示例程序

所以，Brainfuck的程序就是长这样的:

,. 这段代码的意思是，从键盘读取一个字符并输出到屏幕

,>++++++++[<-->-]<-. 这也是我自己写的第一个BrainFuck程序啊哈哈，功能是，从键盘读取一个大写字母，然后转化成对应的数字，#比如A就输出0，B输出1。

代码解释

解释下,>++++++++[<-->-]<-.

首先，读取一个大写字母放到[0]里，然后把指针指向[1]，接下来把[1]里的值增加8次，也就是变成8。

然后进入循环，指针左移一位，指向[0]，把[0]的值减两次，又右移一位回到[1]，把[1]的值减少1。因为一开始[1]被赋值为8，所以循环一共能执行8次，因此[0]里的值会被减少8 * 2 = 16，最后[1]变成了0，循环不再执行，这时候指针指向的是[1]，将其左移一位指向[0]，然后将[0]的值减1，所以[0]的值一共减少了16 + 1 = 17此，这刚好是‘A’的ACSII码与'0'的ACSII码的差值

是不是很好玩？

不如写个解释器更好玩。

解释器

#include 
    
     #include 
     
      #include 
      
       #include 
       using   namespace   std;const   int SIZE = 300000;bool    is_instruction(char);int main(void){    while(1)    {        char    instruction[SIZE];        char    ch;        int count = 0;        while((ch = getchar()) != EOF)          //读取指令，忽略空格回车等非命令字符            if(is_instruction(ch))                instruction[count ++] = ch;        instruction[count] = '\0';        stack
        
           left_bracket_stack;        map
         
           another_bracket_at; bool instruction_ok = true; for(int i = 0;instruction[i] != '\0';i ++) //检查代码是否有误，同时匹配括号 { if(instruction[i] == '[') left_bracket_stack.push(i); else if(instruction[i] == ']') { if(left_bracket_stack.empty()) { instruction_ok = false; break; } int left_barcket_index = left_bracket_stack.top();; left_bracket_stack.pop(); another_bracket_at[i] = left_barcket_index; another_bracket_at[left_barcket_index] = i; } } if(!left_bracket_stack.empty()) instruction_ok = false; if(!instruction_ok) //如果括号不匹配则输出错误 { puts("代码有误"); continue; } cout << endl << "***** BEGIN *****" << endl << endl; int i = 0; char box[SIZE] = {0}; char * cur = box; while(instruction[i] != '\0') { if(instruction[i] == '>') cur ++; else if(instruction[i] == '<') { cur --; if(cur < box) //如果操作会导致数组越界就报错 { puts("代码有误"); break; } } else if(instruction[i] == '+') ++ (*cur); else if(instruction[i] == '-') -- (*cur); else if(instruction[i] == '.') putchar(*cur); else if(instruction[i] == ',') *cur = getchar(); else if(instruction[i] == '[') { if(*cur == 0) i = another_bracket_at[i]; } else if(instruction[i] == ']') if(*cur) i = another_bracket_at[i]; i ++; } cout << endl << endl << "***** DONE *****" << endl << endl; } return 0;}bool is_instruction(char ch){ if(ch == '>' || ch == '<' || ch == '+' || ch == '-' || ch == '.' || ch == ',' || ch == '[' || ch == ']') return true; return false;}

代码应该很好懂，逐个字符读入，同时忽略非命令的字符，处理到文件末尾为止。稍微复杂点的就是用到了map和stack来记录每一个括号对应的另外一半的位置。首先每遇到一个[就压进栈里，然后遇到]就从栈顶取出一个[来和它配对，这时候用map来记录他们的位置。

测试程序

输出"Hello World!" :

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

输出字符'A' :

++++++ [ > ++++++++++ < - ] > +++++ .

把小写字母转换成大写，按回车结束：

,----------[----------------------.,----------]

提示：在控制台输入完指令后按回车，然后按ctrl+z可以模拟EOF

效果

如有BUG欢迎指出~

转载于:https://www.cnblogs.com/xz816111/p/5341379.html

你可能感兴趣的文章