创建一个>,[.>,]通过移动指针的分析器，什么是最好的方法分析环经营者?

StackOverflow https://stackoverflow.com/questions/1055758

  •  20-08-2019
  •  | 
  •  

题

我创建一个>,[.>,]通过移动指针的分析器(在一个基本的话)，最终创建一个解释的但我已经意识到它不是直线前进，因为我首先想到的。我的问题是，我需要一种方法来精确分析的匹配循环的运营商在一个>,[.>,]通过移动指针的程序。这是一个例子程序：

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

'['=开始的循环

']'=结束循环

我需要记录的起点和终点的每个匹配的循环操作，所以我可以跳的来源需要。一些循环是单独一人，有些是嵌套。

什么是最好的方式来分析这个吗？我在想，也许通过移动的源文件创造一个2D阵列(或者等)的记录的开始和结束的位置的每个匹配的操作者，但这似乎是一个很大的'到'ing回'ing'通过的来源。这是最好的方式来做到这一点？

更多信息： >,[.>,]通过移动指针的网页

编辑：代码样本的任何语言的极大的赞赏。

有帮助吗？

解决方案

有您使用堆栈数据结构来记录“跳跃点”（即，指令指针的位置）考虑。

因此，基本上，每次遇到一个“[”您这堆栈上推指令指针的当前位置。每当你遇到一个“]”你重置指令指针到这是目前在堆栈的顶部的值。当一个循环完成时，你的流行堆栈。

下面是C中的例子与++ 100的存储器单元。的代码处理嵌套循环递归并且尽管它不精应该说明这些概念.. 

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;
}

修改 我只是对代码又去，我意识到有while循环，将“跳过”解析环路中的错误，如果指针的值是0。这就是我所做的更改：

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;
}

其他提示

用于解析的上下文无关文法的规范的方法是使用一个堆栈。还有什么和你的工作太辛苦，并冒着正确性。

您可能需要使用一个解析器生成像杯或YACC，因为有很多肮脏的工作是为你做，但作为BF一样简单的语言，它可能是矫枉过正。

足够有趣的，只是几天前，我正在写一brainf*ck的解释。

其中一个问题我是解释命令 官方网页 是不够的，没有提到部分关于嵌套的循环。的 维基百科的网页上Brainf*ck 有一个 命令 分节描述了正确的行为。

基本上总结的问题，官方的网页说时指令是 [ 而目前存在的位置是 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 --水平的筑巢的当前循环。 nesting 的 0 意味着，目前的位置不是在一套循环。

基本上，当一个循环开口 [ 遇到目前存储位置进行检查，看如果价值是 0.如果是这种情况下， while 循环是进入了跳到相应的 ].

路上筑巢是处理如下：

  1. 如果一个 [ 是时遇到寻找的对应环闭 ], ，然后 nesting 变量增加 1 为了表明，我们已经进入了一套循环。

  2. 如果一个 ] 遇到，并且：

    a.如果的 nesting 变量大于 0, ，然后 nesting 变量减 1 要表明，我们已经离开了一套循环。

    b.如果的 nesting 变量 0, 然后我们知道，结束循环已经遇到的，所以寻求结束循环在 while 回路是终止通过执行 break 发言。

现在，下一部分是要处理封闭的循环 ].类似于开放的循环，它将使用 nesting 反，以便确定目前的嵌套级别的循环，并试图找到相应的循环开口 [.

这种方法可能不是最优雅的方式来做事，但是现在看来似乎是资源友好型的，因为它仅需要一个额外变量使用作为反对当前嵌套的水平。

(当然，"资源"是忽略了一个事实，这种解释是写在Java-我只是想写些代码快速和Java刚刚发生了什么我写的。)

每次找到一个“[”，按当前位置（或另一种“标记”令牌或“上下文”）的堆叠上。当你翻过一个“]”，你在循环结束时，可以从弹出堆栈标记令牌。

由于BF的“[”已经检查的条件，并且可能需要跳过去的“]”，可能需要具有指示指令应当在电流回路上下文被跳过的标志。

3.0的Python由其他海报中描述的堆栈算法的示例：

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，所以下一步要做什么，我不知道。）

和这里是我在C ++，得到作为例子前面相同的代码，但移植到VB.NET。我决定把它张贴在这里，因为加里提到他试图写他的解析器，基础方言。

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

我没有代码样本，但.

我可以尝试使用一堆，以及一个算法是这样的：

  1. (执行指令的流)
  2. 收到一个[
  3. 如果指针==0,然后继续读书直到你遇到的']',并不执行任何指令直到你达到它..转到第1步。
  4. 如果指针!=0，则推动这一位置向一个堆栈。
  5. 继续执行指令
  6. 如果你遇到一个]
  7. 如果指针==0,出的[关的堆，并且继续进行(goto步骤1)
  8. 如果指针!= 0,看看顶叠，并走到那个位置。(goto步骤5)

这个问题是有点老了，但我想说的是，这里的答案帮助我决定写我自己的Brainf **亩解释时采取的路线。这里的最终产物：

#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;
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top