AccessViolation Exception

仕事でもはんだづけ、家でもはんだづけ

c#でSpracheを使った構文解析(3)

c#でSpracheを使った構文解析(2) - AccessViolation Exception

の続きです。

構文解析できるならbrainf*ck、作りたくなりますよね(ならない

以前にも

"brainf*ck" - 記事一覧 - AccessViolation Exception

こんなものばかり書いてまるでbrainf*ckが好きに見えますけど手軽で適当に中身濁すのにお手頃なだけなんです...。

処理系を作る

大した労力もかからないので適当に処理を書いたクラスを作ります。

class BrainfuckProcessor {
    public const int BUFFER_SIZE = 300000;
    public int Pointer { get; private set; }
    public char[] Buffer { get; private set; }
    public string Result {
        get { return outputList.Aggregate("", (s, x) => s + x); }
    }
    private List<char> outputList;
    public BrainfuckProcessor() {
        Reset();
    }
    public void Reset() {
        Pointer = 0;
        Buffer = new char[BUFFER_SIZE];
        outputList = new List<char>();
    }
    public void IncrementPtr() { Pointer++; }
    public void DecrementPtr() { Pointer--; }
    public void Increment() { Buffer[Pointer]++; }
    public void Decrement() { Buffer[Pointer]--; }
    public void Print() {
        Console.Write(Buffer[Pointer]);
        outputList.Add(Buffer[Pointer]);
    }
    public void Read() { Buffer[Pointer] = (char)Console.Read(); }

    public bool IsLoop() { return Buffer[Pointer] != 0; }
}

ResultとかoutputListは出力をリストで持ってるだけです、特に気にしなくていいです。

動作については

Brainfuck - Wikipedia

を参照

パース後の型を定義

class BrainfuckToken {
    public enum TokenType {
        IncrementPtr,// >
        DecrementPtr,// <
        Increment,//    +
        Decrement,//    -
        Print,//        .
        Read,//         ,
        Loop,//     []
        Master,
    }
    public TokenType Token { get; private set; }
    public IEnumerable<BrainfuckToken> Children { get; private set; }
    public BrainfuckToken(TokenType t, IEnumerable<BrainfuckToken> children = null) {
        this.Token = t;
        this.Children = children != null ? children : Enumerable.Empty<BrainfuckToken>();
    }
}

最初はenumのリストでいいかと思ったのですが、[]でループしなきゃいけないことも考え、xmlと同じように[]もひとつの要素として持ってループさせるように定義。

最上位だけリストで持つのもキモいのでTokenTypeにMasterを追加。

再びBrainfuckProcessorに戻りRunメソッドを追加

class BrainfuckProcessor {
    public const int BUFFER_SIZE = 300000;
    public int Pointer { get; private set; }
    public char[] Buffer { get; private set; }
    public string Result {
        get { return outputList.Aggregate("", (s, x) => s + x); }
    }
    private List<char> outputList;
    public BrainfuckProcessor() {
        Reset();
    }
    public void Reset() {
        Pointer = 0;
        Buffer = new char[BUFFER_SIZE];
        outputList = new List<char>();
    }
    public void IncrementPtr() { Pointer++; }
    public void DecrementPtr() { Pointer--; }
    public void Increment() { Buffer[Pointer]++; }
    public void Decrement() { Buffer[Pointer]--; }
    public void Print() {
        Console.Write(Buffer[Pointer]);
        outputList.Add(Buffer[Pointer]);
    }
    public void Read() { Buffer[Pointer] = (char)Console.Read(); }

    public bool IsLoop() { return Buffer[Pointer] != 0; }

    public void Run(BrainfuckToken token) {
        switch (token.Token) {
            case BrainfuckToken.TokenType.IncrementPtr:
                IncrementPtr();
                break;
            case BrainfuckToken.TokenType.DecrementPtr:
                DecrementPtr();
                break;
            case BrainfuckToken.TokenType.Increment:
                Increment();
                break;
            case BrainfuckToken.TokenType.Decrement:
                Decrement();
                break;
            case BrainfuckToken.TokenType.Print:
                Print();
                break;
            case BrainfuckToken.TokenType.Read:
                Read();
                break;
            case BrainfuckToken.TokenType.Loop:
                while (IsLoop()) {
                    foreach (var c in token.Children) {
                        Run(c);
                    }
                }
                break;
            case BrainfuckToken.TokenType.Master:
                foreach (var c in token.Children) {
                    Run(c);
                }
                break;
        }

    }
}

パーサを定義

><+-.,[]からBrainfuckTokenを生成するパーサを書きます

static readonly Parse<BrainfuckToken> IncrementPtr = 
    Parse.Char('>').Token().Return(new BrainfuckToken(BrainfuckToken.TokenType.IncrementPtr));

これを量産するのは少し不格好なので

static readonly Func<char, BrainfuckToken.TokenType, Parser<BrainfuckToken>> CreateToken =
    (c, t) => Parse.Char(c).Token().Return(new BrainfuckToken(t));
static readonly Parser<BrainfuckToken> IncrementPtr = CreateToken('>', BrainfuckToken.TokenType.IncrementPtr);
static readonly Parser<BrainfuckToken> DecrementPtr = CreateToken('<', BrainfuckToken.TokenType.DecrementPtr);
static readonly Parser<BrainfuckToken> Increment = CreateToken('+', BrainfuckToken.TokenType.Increment);
static readonly Parser<BrainfuckToken> Decrement = CreateToken('-', BrainfuckToken.TokenType.Decrement);
static readonly Parser<BrainfuckToken> Print = CreateToken('.', BrainfuckToken.TokenType.Print);
static readonly Parser<BrainfuckToken> Read = CreateToken(',', BrainfuckToken.TokenType.Read);
static readonly Parser<BrainfuckToken> Loop;//TODO:Implement here

CreateTokenを作って全部に適用しました。Loopに関してはToken本体が定義できていないのでまだ保留で。

Tokenは至ってシンプルです。

static readonly Parser<BrainfuckToken> Token =
    IncrementPtr
    .Or(DecrementPtr)
    .Or(Increment)
    .Or(Decrement)
    .Or(Print)
    .Or(Read)
    .Or(Loop);

先ほど定義した中のどれかが必ず要素になるので、Orでつないでやれば終了。

Loopの定義は[]に囲ってあるTokenたちになるので

Parse.Char('[') Token.Many() Parse.Char(']')

こうですね。

static readonly Parser<BrainfuckToken> Loop =
    from open in Parse.Char('[')
    from children in Token.Many()
    from close in Parse.Char(']')
    select new BrainfuckToken(BrainfuckToken.TokenType.Loop, children);

最後にTokenType.Masterを定義する大元のパーサを定義して

public static readonly Parser<BrainfuckToken> BrainFuck =
    from children in Token.Many()
    select new BrainfuckToken(BrainfuckToken.TokenType.Master, children);

動かしてみる

public void HelloWorld() {
    var input = "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.";
    var token = BrainFuck.Parse(input);

    var process = new BrainfuckProcessor();
    process.Run(token);//"Hello, world!"
}

ここまでくればいろいろ作れそうな気がしてきますね。

c#でSpracheを使った構文解析(4) - AccessViolation Exception