Создание парсера Brainfuck, какой метод синтаксического анализа операторов цикла лучший? - PullRequest
Новая
       19

Создание парсера Brainfuck, какой метод синтаксического анализа операторов цикла лучший?

5 голосов
/ 29 июня 2009

Я в конечном итоге создаю парсер Brainfuck (на бейсовом диалекте), чтобы создать переводчика, но я понимаю, что это не так просто, как я думал в первый раз. Моя проблема в том, что мне нужен способ точного разбора соответствующих операторов цикла в программе Brainfuck. Это пример программы: 

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

'[' = начало цикла

']' = конец цикла

Мне нужно записать начальную и конечную точку каждого соответствующего оператора цикла, чтобы я мог прыгать вокруг источника по мере необходимости. Некоторые циклы одиночные, некоторые вложенные.

Каков наилучший способ разобрать это? Я подумал, может быть, перемещаться по исходному файлу, создавая двумерный массив (или что-то подобное), записывающий начальную и конечную позиции каждого оператора сопоставления, но это похоже на «смещение и смещение» источника. Это лучший способ сделать это?

Дополнительная информация: Домашняя страница Brainfuck

РЕДАКТИРОВАТЬ: Пример кода на любом языке очень ценится.

Ответы [ 10 ]

11 голосов
/ 29 июня 2009

Рассматривали ли вы использование структуры данных стека для записи «точек перехода» (т. Е. Расположения указателя инструкций).

Таким образом, в основном, каждый раз, когда вы сталкиваетесь с «[», вы помещаете текущее положение указателя инструкции в этот стек. Всякий раз, когда вы встречаете «]», вы сбрасываете указатель инструкции на значение, которое в данный момент находится на вершине стека. Когда цикл завершен, вы вытаскиваете его из стека.

Вот пример на 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;
}

EDIT Я просто снова просмотрел код и понял, что в цикле 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;
}
3 голосов
/ 16 августа 2010

Канонический метод синтаксического анализа грамматики без контекста - использование стека. Что-нибудь еще, и вы слишком усердно работаете и рискуете исправить.

Возможно, вы захотите использовать генератор синтаксического анализатора, такой как cup или yacc, поскольку большая часть грязной работы для вас сделана, но с таким простым языком, как BF, это может быть излишним.

2 голосов
/ 29 июня 2009

Интересно, всего пару дней назад я писал интерпретатор brainf * ck на Java.

Одна из проблем, с которыми я столкнулся, заключалась в том, что объяснение команд на официальной странице было недостаточным и не упоминало часть о вложенных циклах. Страница Википедии на 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. Если встречается ] и:

    а. Если переменная nesting больше 0, то переменная nesting уменьшается на 1, чтобы указать, что мы оставили вложенный цикл.

    б. Если переменная nesting равна 0, то мы знаем, что был обнаружен конец цикла, поэтому поиск конца цикла в цикле while завершается выполнением оператора break.

Теперь следующая часть должна обработать закрытие цикла на ]. Подобно открытию цикла, он будет использовать счетчик nesting, чтобы определить текущий уровень вложенности цикла, и попытаться найти соответствующее открытие цикла [.

Этот метод, возможно, не самый элегантный способ сделать что-то, но кажется, что он дружественный к ресурсам, потому что ему требуется только одна дополнительная переменная для использования в качестве счетчика для текущего уровня вложенности.

(Конечно, «дружественный к ресурсам» игнорирует тот факт, что этот интерпретатор был написан на Java - я просто хотел написать какой-то быстрый код, и Java оказалась именно тем, в котором я его написал.)

1 голос
/ 29 июня 2009

А вот тот же код, который я привел в качестве примера ранее в 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 голос
/ 29 июня 2009

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, так что делать дальше, я понятия не имею.)

1 голос
/ 29 июня 2009

Каждый раз, когда вы найдете '[', поместите текущую позицию (или другой маркер "маркера" или "контекст") в стек. Когда вы сталкиваетесь с ']', вы находитесь в конце цикла и можете вытолкнуть маркер маркера из стека.

Поскольку в BF '[' уже проверяет условие и может потребоваться перепрыгнуть через ']', вы можете захотеть иметь флаг, указывающий, что инструкции должны быть пропущены в контексте текущего цикла.

0 голосов
/ 25 сентября 2016 
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;
}
0 голосов
/ 12 августа 2011

Похоже, этот вопрос стал опросом "Post Your 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;
}
0 голосов
/ 11 августа 2010

Этот вопрос немного стар, но я хотел сказать, что ответы здесь помогли мне решить, какой путь выбрать при написании моего собственного переводчика 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);
        }
    }
}
0 голосов
/ 29 июня 2009

У меня нет примера кода, но.

Я мог бы попробовать использовать стек вместе с алгоритмом, подобным этому:

  1. (выполнение потока команд)
  2. Встреча с [
  3. Если указатель == 0, продолжайте чтение, пока не встретите ']', и не выполняйте никаких инструкций, пока не достигнете его. Перейти к шагу 1.
  4. Если указатель! = 0, поместите эту позицию в стек.
  5. Продолжить выполнение инструкций
  6. Если вы встретите]
  7. Если указатель == 0, вытолкните [из стека и продолжайте (переходите к шагу 1)
  8. Если указатель! = 0, заглянуть на вершину стека и перейти в эту позицию. (перейдите к шагу 5)
...