Brainfuck 파서를 만들면 루프 연산자를 구문 분석하는 가장 좋은 방법은 무엇입니까?
https://stackoverflow.com/questions/1055758
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 Brainfuck 파서 (기본 방언으로)를 만들어 궁극적으로 통역사를 만들고 있지만 처음 생각했던 것만 큼 간단하지 않다는 것을 알고 있습니다. 내 문제는 Brainfuck 프로그램 내에서 일치하는 루프 연산자를 정확하게 구문 분석하는 방법이 필요하다는 것입니다. 이것은 예제 프로그램입니다.
,>,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-],<.>.
'['= 루프의 시작
']'= 루프 끝
필요에 따라 소스를 뛰어 넘을 수 있도록 각 일치 루프 연산자의 시작점과 끝점을 기록해야합니다. 일부 루프는 혼자이고 일부는 중첩되어 있습니다.
이것을 구문 분석하는 가장 좋은 방법은 무엇입니까? 나는 각 일치하는 연산자의 시작 및 끝 위치를 녹화하는 2D 배열 (또는 같은)을 생성하는 소스 파일을 통해 움직일 것이라고 생각했지만 소스를 통해 많은 'to'ing and fro'ing'처럼 보입니다. 이것이 가장 좋은 방법입니까?
더 많은 정보: Brainfuck 홈페이지
편집 : 모든 언어의 샘플 코드는 크게 감사합니다.
해결책
스택 데이터 구조를 사용하여 "점프 포인트"(즉, 명령어 포인터의 위치)를 기록하는 것을 고려 했습니까?
따라서 기본적으로, ["당신은이 스택에서 명령 포인터의 현재 위치를 푸시합니다. A "] "가을 수있을 때마다 명령 포인터를 현재 스택 상단에있는 값에 대해 재설정합니다. 루프가 완료되면 스택에서 튀어 나옵니다.
다음은 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((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와 같은 파서 생성기를 사용하고 싶을 수도 있습니다.
며칠 전, 나는 Java에서 Brainf*CK 통역사를 쓰고있었습니다.
내가 가진 문제 중 하나는 공식 페이지 불충분했고 중첩 루프에 대한 부분을 언급하지 않았습니다. 그만큼 Brainf*CK의 Wikipedia 페이지 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- 전류 루프의 중첩 레벨.nesting의0현재 위치가 중첩 루프에 있지 않음을 의미합니다.
기본적으로 루프가 열릴 때 [ 발생하면 현재 메모리 위치가 확인되어 값이 0. 이 경우, a while 루프가 입력되어 해당 지역으로 점프됩니다 ].
중첩이 처리되는 방식은 다음과 같습니다.
만약
[해당 루프 닫기를 찾는 동안 발생합니다], 그런 다음nesting변수가 증가합니다1중첩 루프를 입력했음을 나타 내기 위해.만약
]발생하고 :ㅏ. 만약
nesting변수는보다 큽니다0, 그런 다음nesting변수는 감소합니다1중첩 루프를 남겼 음을 나타냅니다.비. 만약
nesting변수입니다0, 우리는 루프의 끝이 발생했다는 것을 알고 있으므로 루프의 끝을 찾습니다.while루프는 abreak성명.
이제 다음 부분은 루프 폐쇄를 처리하는 것입니다. ]. 루프의 개구부와 유사하게 사용합니다. nesting 루프의 현재 중첩 레벨을 결정하고 해당 루프 개구부를 찾으려면 카운터 [.
이 방법은 일을하는 가장 우아한 방법은 아니지만 현재 중첩 레벨의 카운터로 사용하려면 하나의 추가 변수 만 있으면 자원 친화적 인 것 같습니다.
(물론, "자원 친화적"은이 통역사가 Java로 작성되었다는 사실을 무시하고 있습니다. 나는 단지 빠른 코드를 작성하고 싶었고 Java는 내가 쓴 것입니다.)
'[' '를 찾을 때마다 현재 위치 (또는 다른 "마커"토큰 또는 "컨텍스트")를 스택에 푸시하십시오. 당신이 a ']' '에 올 때, 당신은 루프의 끝에 있고, 스택에서 마커 토큰을 터뜨릴 수 있습니다.
BF에서 '['는 이미 조건을 확인하고 '' '를 지나가야 할 수도 있기 때문에, 현재 루프 컨텍스트에서 지침이 건너 뛰어야한다는 플래그가있을 수 있습니다.
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를 모른다. 그래서 다음에 무엇을 해야할지, 나는 모른다.)
그리고 여기 C ++의 이전 예제와 동일한 코드가 있지만 vb.net으로 포팅되었습니다. Gary가 기본 방언으로 파서를 쓰려고했다고 언급 한 이후로 여기에 게시하기로 결정했습니다.
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
샘플 코드는 없지만.
나는 다음과 같은 알고리즘과 함께 스택을 사용해 볼 수 있습니다.
- (교육 스트림 실행)
- 만남 [
- 포인터 == 0이면 ']'를 만나기 전까지 계속 읽고, 도달 할 때까지 지침을 실행하지 마십시오. GOTO 단계 1.
- 포인터! = 0이면 해당 위치를 스택으로 밀어 넣으십시오.
- 계속 지침을 실행하십시오
- 당신이 만나면 a
- 포인터 == 0 인 경우 [스택의 오프를 팝업하고 (Goto 1 단계)
- 포인터! = 0이면 스택 상단을 엿보고 해당 위치로 이동하십시오. (Goto 5 단계)
이 질문은 조금 오래되었지만 여기서 답이 내 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;
}
제휴하지 않습니다 StackOverflow
