我正在创建一个 Brainfuck 解析器（在 BASIC 方言中）最终创建一个解释器，但我意识到它并不像我最初想象的那么简单。我的问题是我需要一种方法来准确解析 Brainfuck 程序中的匹配循环运算符。这是一个示例程序：
,>,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-],<.>.
'[' = 循环开始
']' = 循环结束
我需要记录每个匹配循环运算符的起点和终点，以便我可以根据需要跳过源。有些循环是单独的，有些是嵌套的。
解析这个的最佳方法是什么？我在想也许可以通过源文件创建一个 2D 数组（或类似的）来记录每个匹配运算符的开始和结束位置，但这似乎是通过源代码“来来回回”的。这是最好的方法吗？
更多信息：Brainfuck 主页
编辑：非常感谢任何语言的示例代码。
您是否考虑过使用堆栈数据结构来记录“跳转点”（即指令指针的位置）。
所以基本上，每次遇到“[”时，都会将指令指针的当前位置压入堆栈。每当遇到“]”时，都会将指令指针重置为当前位于堆栈顶部的值。当一个循环完成时，你将它从堆栈中弹出。
这是一个具有 100 个存储单元的 C++ 示例。代码递归地处理嵌套循环，虽然它没有细化，但它应该说明这些概念。
char cells[100] = {0}; // define 100 memory cells
char* cell = cells; // set memory pointer to first cell
char* ip = 0; // define variable used as "instruction pointer"
void interpret(static char* program, int* stack, int sp)
{
int tmp;
if(ip == 0) // if the instruction pointer hasn't been initialized
ip = program; // now would be a good time
while(*ip) // this runs for as long as there is valid brainF**k 'code'
{
if(*ip == ',')
*cell = getch();
else if(*ip == '.')
putch(*cell);
else if(*ip == '>')
cell++;
else if(*ip == '<')
cell--;
else if(*ip == '+')
*cell = *cell + 1;
else if(*ip == '-')
*cell = *cell - 1;
else if(*ip == '[')
{
stack[sp+1] = ip - program;
*ip++;
while(*cell != 0)
{
interpret(program, stack, sp + 1);
}
tmp = sp + 1;
while((tmp >= (sp + 1)) || *ip != ']')
{
*ip++;
if(*ip == '[')
stack[++tmp] = ip - program;
else if(*ip == ']')
tmp--;
}
}
else if(*ip == ']')
{
ip = program + stack[sp] + 1;
break;
}
*ip++; // advance instruction
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int stack[100] = {0}; // use a stack of 100 levels, modeled using a simple array
interpret(",>,>++++++++[<------<------>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>>>++++++[<++++++++>-],<.>.", stack, 0);
return 0;
}
编辑 我刚刚再次检查了代码，我意识到如果指针的值为 0，while 循环中有一个错误会“跳过”已解析的循环。这就是我进行更改的地方：
while((tmp >= (sp + 1)) || *ip != ']') // the bug was tmp > (sp + 1)
{
ip++;
if(*ip == '[')
stack[++tmp] = ip - program;
else if(*ip == ']')
tmp--;
}
下面是同一个解析器的一个实现，但没有使用递归：
char cells[100] = {0};
void interpret(static char* program)
{
int cnt; // cnt is a counter that is going to be used
// only when parsing 0-loops
int stack[100] = {0}; // create a stack, 100 levels deep - modeled
// using a simple array - and initialized to 0
int sp = 0; // sp is going to be used as a 'stack pointer'
char* ip = program; // ip is going to be used as instruction pointer
// and it is initialized at the beginning or program
char* cell = cells; // cell is the pointer to the 'current' memory cell
// and as such, it is initialized to the first
// memory cell
while(*ip) // as long as ip point to 'valid code' keep going
{
if(*ip == ',')
*cell = getch();
else if(*ip == '.')
putch(*cell);
else if(*ip == '>')
cell++;
else if(*ip == '<')
cell--;
else if(*ip == '+')
*cell = *cell + 1;
else if(*ip == '-')
*cell = *cell - 1;
else if(*ip == '[')
{
if(stack[sp] != ip - program)
stack[++sp] = ip - program;
*ip++;
if(*cell != 0)
continue;
else
{
cnt = 1;
while((cnt > 0) || *ip != ']')
{
*ip++;
if(*ip == '[')
cnt++;
else if(*ip == ']')
cnt--;
}
sp--;
}
}else if(*ip == ']')
{
ip = program + stack[sp];
continue;
}
*ip++;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
// define our program code here..
char *prg = ",>++++++[<-------->-],[<+>-]<.";
interpret(prg);
return 0;
}
有趣的是，就在几天前，我正在用 Java 编写一个brainf*ck 解释器。
我遇到的问题之一是官方页面上的命令解释不充分，并且没有提到嵌套循环的部分。Brainf*ck 上的Wikipedia 页面有一个Commands小节，它描述了正确的行为。
基本上总结问题，官方页面说当一条指令是a [，当前内存位置是0，然后跳转到下一条]。正确的行为是跳转到对应 ]的，而不是下一个。
实现此行为的一种方法是跟踪嵌套级别。我最终通过有一个跟踪嵌套级别的计数器来实现这一点。
以下是解释器主循环的一部分：
do {
if (inst[pc] == '>') { ... }
else if (inst[pc] == '<') { ... }
else if (inst[pc] == '+') { ... }
else if (inst[pc] == '-') { ... }
else if (inst[pc] == '.') { ... }
else if (inst[pc] == ',') { ... }
else if (inst[pc] == '[') {
if (memory[p] == 0) {
int nesting = 0;
while (true) {
++pc;
if (inst[pc] == '[') {
++nesting;
continue;
} else if (nesting > 0 && inst[pc] == ']') {
--nesting;
continue;
} else if (inst[pc] == ']' && nesting == 0) {
break;
}
}
}
}
else if (inst[pc] == ']') {
if (memory[p] != 0) {
int nesting = 0;
while (true) {
--pc;
if (inst[pc] == ']') {
++nesting;
continue;
} else if (nesting > 0 && inst[pc] == '[') {
--nesting;
continue;
} else if (inst[pc] == '[' && nesting == 0) {
break;
}
}
}
}
} while (++pc < inst.length);
这是变量名称的图例：
memory-- 数据的存储单元。p-- 指向当前内存单元位置的指针。inst-- 保存指令的数组。pc - 程序计数器; 指向当前指令。nesting-- 当前循环的嵌套级别。nestingof0表示当前位置不在嵌套循环中。基本上，当遇到循环打开[时，会检查当前内存位置以查看值是否为0. 如果是这种情况，while则进入一个循环以跳转到相应的].
嵌套的处理方式如下：
如果[在寻找相应的循环关闭时遇到an ]，则nesting变量递增1以表明我们已进入嵌套循环。
如果]遇到一个，并且：
一个。如果nesting变量大于0，则nesting变量减11 表示我们已经离开了一个嵌套循环。
湾。如果nesting变量是0，那么我们就知道已经遇到了循环的结尾，所以在循环中寻找循环的while结尾是通过执行一个break语句来终止的。
现在，下一部分是处理循环的关闭]。类似于循环的打开，它会使用nesting计数器来确定循环的当前嵌套级别，并尝试找到对应的循环打开[。
这种方法可能不是最优雅的处理方式，但它似乎是资源友好的，因为它只需要一个额外的变量来用作当前嵌套级别的计数器。
（当然，“资源友好”忽略了这个解释器是用 Java 编写的——我只是想写一些快速的代码，而 Java 恰好是我写的。）
解析上下文无关文法的规范方法是使用堆栈。其他任何事情，您都在努力工作并冒着正确性的风险。
您可能想要使用像 cup 或 yacc 这样的解析器生成器，因为很多繁琐的工作已经为您完成了，但是对于像 BF 这样简单的语言，这可能是矫枉过正。
每次找到'['时，将当前位置（或另一个“标记”标记或“上下文”）压入堆栈。当您遇到“]”时，您处于循环的末尾，您可以从堆栈中弹出标记标记。
由于在 BF 中，'[' 已经检查了一个条件并且可能需要跳过 ']'，因此您可能需要一个标志来指示应在当前循环上下文中跳过指令。
这是我之前在 C++ 中作为示例给出的相同代码，但移植到了 VB.NET。我决定在这里发布它，因为 Gary 提到他正试图用 BASIC 方言编写他的解析器。
Public cells(100) As Byte
Sub interpret(ByVal prog As String)
Dim program() As Char
program = prog.ToCharArray() ' convert the input program into a Char array
Dim cnt As Integer = 0 ' a counter to be used when skipping over 0-loops
Dim stack(100) As Integer ' a simple array to be used as stack
Dim sp As Integer = 0 ' stack pointer (current stack level)
Dim ip As Integer = 0 ' Instruction pointer (index of current instruction)
Dim cell As Integer = 0 ' index of current memory
While (ip < program.Length) ' loop over the program
If (program(ip) = ",") Then
cells(cell) = CByte(AscW(Console.ReadKey().KeyChar))
ElseIf (program(ip) = ".") Then
Console.Write("{0}", Chr(cells(cell)))
ElseIf (program(ip) = ">") Then
cell = cell + 1
ElseIf (program(ip) = "<") Then
cell = cell - 1
ElseIf (program(ip) = "+") Then
cells(cell) = cells(cell) + 1
ElseIf (program(ip) = "-") Then
cells(cell) = cells(cell) - 1
ElseIf (program(ip) = "[") Then
If (stack(sp) <> ip) Then
sp = sp + 1
stack(sp) = ip
End If
ip = ip + 1
If (cells(cell) <> 0) Then
Continue While
Else
cnt = 1
While ((cnt > 0) Or (program(ip) <> "]"))
ip = ip + 1
If (program(ip) = "[") Then
cnt = cnt + 1
ElseIf (program(ip) = "]") Then
cnt = cnt - 1
End If
End While
sp = sp - 1
End If
ElseIf (program(ip) = "]") Then
ip = stack(sp)
Continue While
End If
ip = ip + 1
End While
End Sub
Sub Main()
' invoke the interpreter
interpret(",>++++++[<-------->-],[<+>-]<.")
End Sub
其他海报描述的堆栈算法的 Python 3.0 示例：
program = """
,>,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-],<.>.
"""
def matching_brackets(program):
stack = []
for p, c in enumerate(program, start=1):
if c == '[':
stack.append(p)
elif c == ']':
yield (stack.pop(), p)
print(list(matching_brackets(''.join(program.split()))))
（好吧，老实说，这只会找到匹配的括号。我不知道brainf*ck，所以接下来要做什么，我不知道。）
我没有示例代码，但是。
我可能会尝试使用堆栈以及这样的算法：
这个问题有点老了，但我想说这里的答案帮助我决定了在编写自己的 Brainf**k 解释器时要走的路线。这是最终产品：
#include <stdio.h>
char *S[9999], P[9999], T[9999],
**s=S, *p=P, *t=T, c, x;
int main() {
fread(p, 1, 9999, stdin);
for (; c=*p; ++p) {
if (c == ']') {
if (!x)
if (*t) p = *(s-1);
else --s;
else --x;
} else if (!x) {
if (c == '[')
if (*t) *(s++) = p;
else ++x;
}
if (c == '<') t--;
if (c == '>') t++;
if (c == '+') ++*t;
if (c == '-') --*t;
if (c == ',') *t = getchar();
if (c == '.') putchar(*t);
}
}
}
package interpreter;
import java.awt.event.ActionListener;
import javax.swing.JTextPane;
public class Brainfuck {
final int tapeSize = 0xFFFF;
int tapePointer = 0;
int[] tape = new int[tapeSize];
int inputCounter = 0;
ActionListener onUpdateTape;
public Brainfuck(byte[] input, String code, boolean debugger,
JTextPane output, ActionListener onUpdate) {
onUpdateTape = onUpdate;
if (debugger) {
debuggerBF(input, code, output);
} else {
cleanBF(input, code, output);
}
}
private void debuggerBF(byte[] input, String code, JTextPane output) {
for (int i = 0; i < code.length(); i++) {
onUpdateTape.actionPerformed(null);
switch (code.charAt(i)) {
case '+': {
tape[tapePointer]++;
break;
}
case '-': {
tape[tapePointer]--;
break;
}
case '<': {
tapePointer--;
break;
}
case '>': {
tapePointer++;
break;
}
case '[': {
if (tape[tapePointer] == 0) {
int nesting = 0;
while (true) {
++i;
if (code.charAt(i) == '[') {
++nesting;
continue;
} else if (nesting > 0 && code.charAt(i) == ']') {
--nesting;
continue;
} else if (code.charAt(i) == ']' && nesting == 0) {
break;
}
}
}
break;
}
case ']': {
if (tape[tapePointer] != 0) {
int nesting = 0;
while (true) {
--i;
if (code.charAt(i) == ']') {
++nesting;
continue;
} else if (nesting > 0 && code.charAt(i) == '[') {
--nesting;
continue;
} else if (code.charAt(i) == '[' && nesting == 0) {
break;
}
}
}
break;
}
case '.': {
output.setText(output.getText() + (char) (tape[tapePointer]));
break;
}
case ',': {
tape[tapePointer] = input[inputCounter];
inputCounter++;
break;
}
}
}
}
private void cleanBF(byte[] input, String code, JTextPane output) {
for (int i = 0; i < code.length(); i++) {
onUpdateTape.actionPerformed(null);
switch (code.charAt(i)) {
case '+':{
tape[tapePointer]++;
break;
}
case '-':{
tape[tapePointer]--;
break;
}
case '<':{
tapePointer--;
break;
}
case '>':{
tapePointer++;
break;
}
case '[': {
if (tape[tapePointer] == 0) {
int nesting = 0;
while (true) {
++i;
if (code.charAt(i) == '[') {
++nesting;
continue;
} else if (nesting > 0 && code.charAt(i) == ']') {
--nesting;
continue;
} else if (code.charAt(i) == ']' && nesting == 0) {
break;
}
}
}
break;
}
case ']': {
if (tape[tapePointer] != 0) {
int nesting = 0;
while (true) {
--i;
if (code.charAt(i) == ']') {
++nesting;
continue;
} else if (nesting > 0 && code.charAt(i) == '[') {
--nesting;
continue;
} else if (code.charAt(i) == '[' && nesting == 0) {
break;
}
}
}
break;
}
case '.':{
output.setText(output.getText()+(char)(tape[tapePointer]));
break;
}
case ',':{
tape[tapePointer] = input[inputCounter];
inputCounter++;
break;
}
}
}
}
public int[] getTape() {
return tape;
}
public void setTape(int[] tape) {
this.tape = tape;
}
public void editTapeValue(int counter, int value) {
this.tape[counter] = value;
}
}
这应该有效。您需要对其进行一些修改。这实际上是brainfuck解释器如何工作的标准示例。我修改它以在我的应用程序中使用，括号在那里处理：
case '[': {
if (tape[tapePointer] == 0) {
int nesting = 0;
while (true) {
++i;
if (code.charAt(i) == '[') {
++nesting;
continue;
}
else if (nesting > 0 && code.charAt(i) == ']') {
--nesting;
continue;
}
else if (code.charAt(i) == ']' && nesting == 0) {
break;
}
}
}
break;
}
case ']': {
if (tape[tapePointer] != 0) {
int nesting = 0;
while (true) {
--i;
if (code.charAt(i) == ']') {
++nesting;
continue;
}
else if (nesting > 0 && code.charAt(i) == '[') {
--nesting;
continue;
}
else if (code.charAt(i) == '[' && nesting == 0) {
break;
}
}
}
break;
}
看起来这个问题已经成为“发布你的 bf 口译员”民意调查。
所以这是我刚开始工作的：
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
void error(char *msg) {
fprintf(stderr, "Error: %s\n", msg);
}
enum { MEMSIZE = 30000 };
char *mem;
char *ptr;
char *prog;
size_t progsize;
int init(char *progname) {
int f,r;
struct stat fs;
ptr = mem = calloc(MEMSIZE, 1);
f = open(progname, O_RDONLY);
assert(f != -1);
r = fstat(f, &fs);
assert(r == 0);
prog = mmap(NULL, progsize = fs.st_size, PROT_READ, MAP_PRIVATE, f, 0);
assert(prog != NULL);
return 0;
}
int findmatch(int ip, char src){
char *p="[]";
int dir[]= { 1, -1 };
int i;
int defer;
i = strchr(p,src)-p;
ip+=dir[i];
for (defer=dir[i]; defer!=0; ip+=dir[i]) {
if (ip<0||ip>=progsize) error("mismatch");
char *q = strchr(p,prog[ip]);
if (q) {
int j = q-p;
defer+=dir[j];
}
}
return ip;
}
int run() {
int ip;
for(ip = 0; ip>=0 && ip<progsize; ip++)
switch(prog[ip]){
case '>': ++ptr; break;
case '<': --ptr; break;
case '+': ++*ptr; break;
case '-': --*ptr; break;
case '.': putchar(*ptr); break;
case ',': *ptr=getchar(); break;
case '[': /*while(*ptr){*/
if (!*ptr) ip=findmatch(ip,'[');
break;
case ']': /*}*/
if (*ptr) ip=findmatch(ip,']');
break;
}
return 0;
}
int cleanup() {
free(mem);
ptr = NULL;
return 0;
}
int main(int argc, char *argv[]) {
init(argc > 1? argv[1]: NULL);
run();
cleanup();
return 0;
}