私は最終的にインタプリタを作成するためにBrainfuckパーサーを（BASIC方言で）作成していますが、最初に思ったほど簡単ではないことに気づきました。私の問題は、Brainfuckプログラム内で一致するループ演算子を正確に解析する方法が必要なことです。これはサンプルプログラムです：
,>,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-],<.>.
'['=ループの開始
']'=ループの終わり
必要に応じてソースをジャンプできるように、一致する各ループ演算子の開始点と終了点を記録する必要があります。一部のループは単独で、一部はネストされています。
これを解析するための最良の方法は何でしょうか？ソースファイルを移動して、一致する各演算子の開始位置と終了位置を記録する2D配列（など）を作成することを考えていましたが、これはソースを「行き来する」ことが多いようです。これはそれを行うための最良の方法ですか？
編集：どの言語のサンプルコードでも大歓迎です。
スタックデータ構造を使用して「ジャンプポイント」（つまり、命令ポインターの位置）を記録することを検討しましたか。
したがって、基本的に、「[」に遭遇するたびに、このスタック上の命令ポインタの現在の場所をプッシュします。「]」に遭遇するたびに、命令ポインタを現在スタックの最上位にある値にリセットします。ループが完了したら、スタックからポップします。
これは、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インタープリターを書いていました。
私が抱えていた問題の1つは、公式ページでのコマンドの説明が不十分であり、ネストされたループに関する部分について言及していなかったことです。Brainf * ckのWikipediaページには、正しい動作を説明するコマンドサブセクションがあります。
基本的に問題を要約すると、公式ページには、命令がa[で、現在のメモリ位置が0である場合、次のにジャンプすると記載されてい]ます。正しい動作は、次のものではなく、対応するにジャンプすることです。 ]
この動作を実現する1つの方法は、ネストのレベルを追跡することです。入れ子のレベルを追跡するカウンターを用意することで、これを実装することになりました。
以下は、通訳者のメインループの一部です。
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対応するにジャンプするためにループに入り]ます。
ネストの処理方法は次のとおりです。
[対応するループの終了を探しているときにが検出された場合、ネストされたループに入ったことを示すために]、nesting変数が増分されます。1
]に遭遇した場合、および：
a。nesting変数がより大きい場合、0変数はnestingによってデクリメントされ1、ネストされたループを残したことを示します。
b。nesting変数が、の場合0、ループの終わりに遭遇したことがわかります。したがって、ループ内のループの終わりを探すことは、ステートメントwhileを実行することによって終了します。break
次に、ループの終了を。で処理します]。ループの開始と同様に、ループnestingの現在のネストレベルを決定するためにカウンターを使用し、対応するループの開始を見つけようとします[。
この方法は、物事を行うための最も洗練された方法ではないかもしれませんが、現在のネストレベルのカウンターとして使用するために必要な追加の変数が1つだけなので、リソースに優しいようです。
（もちろん、「リソースに優しい」というのは、このインタープリターがJavaで書かれているという事実を無視しています。簡単なコードを書きたかったのですが、たまたまJavaが書いたものでした。）
文脈自由文法を解析するための標準的な方法は、スタックを使用することです。他の何かとあなたはあまりにも一生懸命働いており、正確さを危険にさらしています。
汚い作業の多くはあなたのために行われるので、cupやyaccのようなパーサジェネレータを使用したいかもしれませんが、BFのような単純な言語では、やり過ぎかもしれません。
'['を見つけるたびに、スタック上の現在の位置（または別の「マーカー」トークンまたは「コンテキスト」）をプッシュします。']'に出くわすと、ループの終わりになり、スタックからマーカートークンをポップできます。
BFでは、「[」はすでに条件をチェックしており、「]」を飛び越える必要がある場合があるため、現在のループコンテキストで命令がスキップされることを示すフラグが必要になる場合があります。
他の投稿者によって説明されているスタックアルゴリズムのPython3.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に移植されています。ゲイリーがパーサーを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
サンプルコードはありませんが。
次のようなアルゴリズムとともに、スタックを使用してみることができます。
この質問は少し古いですが、ここでの回答は、自分の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;
}