GoForIt回答 - 申告制エレベータ -

引き続きGoForItの回答です。最後まで到達していませんが、せっかくなのでポストしようと思います。
回答はshidasan · GitHubで公開しています。
i)
乗り降りした階、時間、入力データの識別番号をファイルから取得し、出力フォーマット通りに標準出力に出力しています。

ii)
KonohaScriptにはテストケースを作る際に利用するAssert文と呼ばれるものがあります。Assert文中にtrueと見込まれる条件式を書く事で、その時点でプログラムが満たすべき用件について定義します。Assert文がfalseになった場合は例外が発行されます。

using konoha.math.*;
MAXCAPACITY=5;
DELAY=5;
int capacity;
int numElevator;
@Public dynamic Array.last() {
    return this[|this|-1];
}
class Decl {
    int id;
    int requestTime;
    int onFloor;
    int offFloor;
    Decl(Array<String> data) {
        _id = (int)data[0];
        _requestTime = (int)data[1];
        _onFloor = (int)data[2];
        _offFloor = (int)data[3];
    }
}
class Event {
    int id;
    int time;
    int floor;
    String eventStr;
    int[] target;
    Event(String[] data) {
        this.id = (to Int)data[0];
        this.time = (to Int)data[1];
        this.floor = (to Int)data[2];
        this.eventStr = data[3];
        this.target = [];
        for (int i = 4; i < |data|; i++) {
            if (data[i] != "0") {
                target.add((to Int) data[i]);
            }
        }
    }
}
int changeFloor(int floor0, int floor1) {
    return Math.abs(floor0-floor1) * 2;
}
void confirm(Decl[] decls, Event[] events) {
    int[][] passenger = new Int[][numElevator+1];
    Event[][] chkevents = new Event[][numElevator+1];
    int declComfirmed = 0;
    int result = 0;
    for (int i = 0; i < numElevator+1; i++) {
        passenger[i] = [];
        chkevents[i] = [new Event((i + ",0,1,E,0,0,0,0,0").split(","))];
    }
    Event publicLast = new Event(("1,0,1,E,0,0,0,0,0").split(","));
    for (int i = 0; i < |events|; i++) {
        Event e = events[i];
        assert(publicLast.time <= e.time);
        assert(e.id <= numElevator);
        assert(e.eventStr == "E" || e.eventStr == "B");
        Event last = chkevents[e.id].last();
        if (e.eventStr == "B") {
            assert(last.eventStr == "E");
            assert(e.time >= last.time + changeFloor(e.floor, last.floor));
            if (|e.target| > 0) {
                foreach (int p in e.target) {
                    assert(passenger[e.id].indexOf(p) != -1);
                    passenger[e.id].remove(passenger[e.id].indexOf(p));
                    result += e.time - decls[p].requestTime;
                    declComfirmed++;
                }
            }
            chkevents[e.id].add(e);
        } else {
            assert(last.eventStr == "B");
            assert(e.time >= last.time + DELAY);
            assert(e.floor == last.floor);
            if (|e.target| > 0) {
                foreach (int p in e.target) {
                    assert(decls[p].requestTime <= e.time);
                    passenger[e.id].add(p);
                    assert(|passenger[e.id]| <= capacity);
                }
            }
            chkevents[e.id].add(e);
        }
        publicLast = e;
    }
    assert(declComfirmed == |decls|-1);
    OUT.println("Confirmed");
    OUT.println("Total Delay: " + result);
}
void main(String[] args) {
    if (|args| != 4) {
        print "Usage: [input] [output] [capacity] [elevator count]";
        return;
    }

    InputStream inputdata = new (args[0]);
    InputStream outputdata = new (args[1]);
    capacity = (to Int)args[2];
    assert(capacity <= MAXCAPACITY);
    numElevator = (to Int) args[3];
    Decl[] decls = [null];
    Event[] events = [];
    String s = "";
    while ((s = inputdata.readLine()) != null) {
        decls.add(new Decl(s.split(",")));
    }
    while ((s = outputdata.readLine()) != null) {
        events.add(new Event(s.split(",")));
    }
    confirm(decls, events);
}

GoForIt回答 - 暗号検索の高速化 -

sonyが開催しているGo For Itに参加しています。言語はKonohaScriptKonoha Projectを使用しています。

TopCoderなどのように実行環境を限定されていないコンテストなため、こういう時はKonohaScriptを使ってみます。

回答はshidasan · GitHubで公開している他、こちらのアカウントでKonohaScriptの開発も行っています。
KonohaScriptのインストールは、KonohaScript インストール手順（１）ソースからのビルド - Konoha日誌で詳しく解説されています。

i)
skip数と先頭文字列の位置で単純にイテレートしました。KonohaScriptは静的な型付けによるプログラムの高速な実行を特徴とするスクリプト言語ですが、C言語やJavaのようなコンパイル言語と比較すると実行速度は劣ります。
工夫の無いプログラムだった事もあり、回答は出そうにありませんでした。
ii)
まず2次元配列dataに、キーワードのi番目に当てはまるランダム文字列の位置を配列として記憶します。

    for (int i = 0; i < |data|; i++) {
        for (int j = 0; j < STR_MAX; j++) {
            if (rand_str[j] == keyword[i]) {
                data[i].add(j);
            }
        }
    }

data[0]の配列とdata[1]の配列に格納されている数値からスキップ数を求める事で、比較的高速な実行が行えました。42秒程度です。

LLVMの最適化パス

LLVMの最適化パスはlib/Transforms以下にあるようです。
lib/Transforms/InstCombine以下は全てピープホール最適化（覗き穴最適化）に関するパスが集まっていて、

-A + B  -->  B - A
-A + -B  -->  -(A + B)

のような局所的な最適化が行われています。
パッと見で理解できるものが大量にあるはずなので、見ていると結構楽しいです。

オリジナル言語のLLVMフロントエンドをKonohaScriptで実装する その4

前回までで作成したASTから、LLVMの中間表現（IR）を作成していきます。
http://llvm.org/docs/tutorial/こちらのページの5章までの内容になります。
具体的にはASTのクラス毎に定義されているcodegen関数を定義していきます。
四則演算、比較などのオペレータを表すBinaryExprASTクラスを例とすると、

class BinaryExprAST extends ExprAST {
    int op; 
    ExprAST lhs, rhs;
    BinaryExprAST (int op, lhs, rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
        this.op = op; 
    }   
}

lhs op rhsとa + bが対応する表現になります。
lhsとrhsの中間表現を得るためにはそれぞれlhs.codegen(), rhs.codegen()とすれば良いので、
この二つの中間表現に対してオペレータを作用させるだけです。
現状ではデータ型は64ビット整数型のみなので、比較命令では返り値を1ビットから64ビットにキャストする命令が必要になります。

class BinaryExprAST extends ExprAST {
    int op; 
    ExprAST lhs, rhs;
    BinaryExprAST (int op, lhs, rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
        this.op = op; 
    }   
    Value codeGen (Generator gen) {
        Value l = lhs.codeGen (gen);
        Value r = rhs.codeGen (gen);
        if (l == null || r == null) return null;

        switch (op) {
            case '+': return gen.builder.CreateAdd (l, r); 
            case '-': return gen.builder.CreateSub (l, r); 
            case '*': return gen.builder.CreateMul (l, r); 
            case '<': { 
                          Value v = gen.builder.CreateICmpSLT (l, r); 
                          v = gen.builder.CreateZExt (v, intTy);
                          return v;
                      }   
            case '>': { 
                          Value v = gen.builder.CreateICmpSGT (l, r); 
                          v = gen.builder.CreateZExt (v, intTy);
                          return v;
                      }   
            default : return errorV ("invalid binary operator");
        }   
    }   
}

LLVMの中間表現はSSA形式となっているため、for文やif文などで分岐した制御フローの合流地点にPHI関数と呼ばれるものを挿入する必要が出てきます。

実際にFibonacchi関数についてLLVM IRの内容をダンプし、実行した結果が以下です。
実行時間は、C言語で記述した同等のコードとほぼ同じ程度になります。#gccの最適化オプション無しの状態です。

[shida@adm hatena]$ konoha kaleidoscope.k
ready>def fib(n)
ready>if n < 3 then 1
ready>else fib(n-1) + fib(n-2);
(handleDefinition:658) Read function definition

define i64 @fib(i64 %n) {
%1 = icmp slt i64 %n, 3
%2 = zext i1 %1 to i64
%3 = icmp eq i64 %2, 1
br i1 %3, label %4, label %5

; <label>:4 ; preds = %0
br label %11

; <label>:5 ; preds = %0
%6 = sub i64 %n, 1
%7 = call i64 @fib(i64 %6)
%8 = sub i64 %n, 2
%9 = call i64 @fib(i64 %8)
%10 = add i64 %7, %9
br label %11

; <label>:11 ; preds = %5, %4
%12 = phi i64 [ 1, %4 ], [ %10, %5 ]
ret i64 %12
}

ready>fib(36);
(handleTopLevelExpression:673) Parsed a top-level expr

define void @Script1(i64*, i64*, i64) {
%4 = call i64 @fib(i64 36)
%5 = call i64 @printf(i8* getelementptr inbounds ([4 x i8]* @0, i32 0, i32 0), i64 %4)
ret void
}

14930352

コードは大分長くなってしまいましたが、ここまで作っておけばif文の追加やローカル変数/グローバル変数の追加なども楽に作れるのではないでしょうか。

using konoha.llvm.*;
using konoha.lang.*;

int f ();
Value persentD;
static Map<String, int> binopPrecedence = {};

class Generator
{
    Type intTy, intPtrTy;
    Type int8Ty, int8PtrTy;
    Module m;
    Function func;
    IRBuilder builder;

    Method mtd;
    Map<String, Value> namedValues;
    int scriptId;
    Generator (Module m, Method mtd) {
        this.m = m;
        this.mtd = mtd;
        namedValues = {};
        scriptId = 0;
    }


    void emit() {
        ee = m.createExecutionEngine();
        mtd.setFunction(ee.getPointerToFunction(m, func));
        return;
    }
}


static void createScript (Generator gen)
{
    gen.scriptId += 1;
    gen.intTy = Type.getInt64ty;
    gen.intPtrTy = PointerType.get(gen.intTy);
    Type[] argsTy = [gen.intPtrTy,
        gen.intPtrTy,
        gen.intTy];
    FunctionType fTy = FunctionType.get(Type.getVoidTy(), argsTy, false);
    func = gen.m.getOrInsertFunction("Script" + gen.scriptId,fTy);
    BasicBlock bb = BasicBlock.create(func);
    IRBuilder builder = new IRBuilder (bb);
    gen.builder = builder;
    gen.builder.setInsertPoint (bb);

    gen.func = func;
}

static void init (Generator gen)
{
    gen.intTy = Type.getInt64ty;
    gen.int8Ty = Type.getInt8ty;
    gen.intPtrTy = PointerType.get(gen.intTy);
    gen.int8PtrTy = PointerType.get(gen.int8Ty);
    persentD = null;

    return;
}



static void printi (Generator gen, Value v)
{
    if (persentD == null) {
        persentD = gen.builder.CreateGlobalString("%d\n");
        persentD = gen.builder.CreateBitCast(persentD, gen.int8PtrTy); 
    }
    Type[] argsTy = [gen.int8PtrTy,
        gen.intTy];
    FunctionType fTy = FunctionType.get(gen.intTy, argsTy, false);
    Function func = gen.m.getOrInsertFunction("printf", fTy); 
    gen.builder.createCall2(func, persentD, v);
    return;
}

static void generate (Generator gen)
{
    builder = gen.builder;
    printi(gen, ConstantInt.get(gen.intTy, 10));
    builder.CreateRetVoid();
    gen.m.dump();
    return;
}

int tok_eof = -1; int tok_def = -2; int tok_extern = -3;
int tok_identifier = -4; int tok_number = -5;
int tok_if = -6; int tok_then = -7; int tok_else = -8;
int tok_for = -9; int tok_in = -10;


static boolean isspace (String s)
{
    int c = ((Bytes)s[0])[0];
    return (c == ' ');
}

static boolean isalpha (String s)
{
    int c = ((Bytes)s[0])[0];
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

static boolean isdigit (String s)
{
    int c = ((Bytes)s[0])[0];
    return (c >= '0' && c <= '9');
}

static boolean isalnum (String s)
{
    return (isalpha(s) || isdigit(s));
}

int curTok;

class Reader {
    String str;
    String lastChar = " ";
    String identifierStr;
    int numVal;
    int cur;
    Reader () {
        this.str = "def fib(n) if n < 3 then 1 else fib(n-1) + fib(n-2); fib(40);";
        this.cur = 0;
        this.lastChar = " ";
        this.identifierStr = " ";
        this.numVal = 0;
    }

    String getchar ()
    {
        String res = "";
        while (str == null || cur == |str| + 1) {
        System.out.print("ready>");
        OUT.flush();
            str = readLine();
            cur = 0;
        }
        if (cur == |str|) {
            res = " ";
        } else {
            res = str[cur];
        }
        cur++;
        return res;

    }
    int gettok ()
    {
        while (isspace(lastChar)) {
            lastChar = getchar();
        }

        if (isalpha(lastChar)) {
            identifierStr = "";
            identifierStr = lastChar;
            while (isalnum((lastChar = getchar()))) {
                identifierStr += lastChar;
            }
            if (identifierStr == "def") return tok_def;
            if (identifierStr == "extern") return tok_extern;
            if (identifierStr == "if") return tok_if;
            if (identifierStr == "then") return tok_then;
            if (identifierStr == "else") return tok_else;
            if (identifierStr == "for") return tok_for;
            if (identifierStr == "in") return tok_in;
            if (identifierStr == "exit" ||
                    identifierStr == "quit" ||
                    identifierStr == "bye"  ||
                    identifierStr == "q") {
                print "bye";
                return tok_eof;
            }
            return tok_identifier;
        }

        if (isdigit(lastChar) || lastChar == ".") {
            String numStr = "";
            do {
                numStr += lastChar;
                lastChar = getchar();
            } while (isdigit(lastChar) || lastChar == ".");
            numVal = (int)numStr;
            return tok_number;
        }

        if (lastChar == "#") {
            do {
                lastChar = getchar();
            } while (lastChar != "\n");
            return gettok();
        }

        String thisChar = lastChar;
        lastChar = getchar();
        return ((Bytes)thisChar[0])[0];
    }
    int getNextToken () {
        curTok = gettok ();
        return curTok;
    }


}



class ExprAST {
    ExprAST () {}
    @virtual Value codeGen (Generator gen) {return null;};
}

class NumberExprAST extends ExprAST {
    int val;
    NumberExprAST (int val) {
        this.val = val;
    }
    Value codeGen (Generator gen) {
        return ConstantInt.get (gen.intTy, val);
    }
}

ExprAST error (String str) {
    print "Error: ", str;
    ExprAST res = null;
    return res;
}

PrototypeAST errorP (String str) { 
    error (str); 
    PrototypeAST res = null;
    return res;
}
FunctionAST errorF (String str) {
    error (str);
    FunctionAST res = null;
    return res;
}

Value errorV (String str) {
    error(str);
    Value res = null;
    return res;
}

class VariableExprAST extends ExprAST {
    String name;
    VariableExprAST (String name) {
        this.name = name;
    }
    Value codeGen (Generator gen) {
        Value v = gen.namedValues[name];
        return (v != null) ? v : errorV ("Unknown variable name");
    }
}

class BinaryExprAST extends ExprAST {
    int op;
    ExprAST lhs, rhs;
    BinaryExprAST (int op, lhs, rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
        this.op = op;
    }
    Value codeGen (Generator gen) {
        Value l = lhs.codeGen (gen);
        Value r = rhs.codeGen (gen);
        if (l == null || r == null) return null;

        switch (op) {
            case '+': return gen.builder.CreateAdd (l, r);
            case '-': return gen.builder.CreateSub (l, r);
            case '*': return gen.builder.CreateMul (l, r);
            case '<': { 
                          Value v = gen.builder.CreateICmpSLT (l, r);
                          v = gen.builder.CreateZExt (v, gen.intTy);
                          return v;
                      }
            case '>': { 
                          Value v = gen.builder.CreateICmpSGT (l, r);
                          v = gen.builder.CreateZExt (v, gen.intTy);
                          return v;
                      }
            default : return errorV ("invalid binary operator");
        }
    }
}

class CallExprAST extends ExprAST {
    String callee;
    ExprAST[] args;
    FunctionType ft;
    CallExprAST (String callee, ExprAST[] args) {
        this.callee = callee;
        this.args = args;
    }
    Value codeGen (Generator gen) {
        Type[] argsTy = [];
        for (int i = 0; i < args.getSize(); i++) argsTy.add(gen.intTy);
        ft = FunctionType.get (gen.intTy, argsTy, false);
        Function calleeF = gen.m.getOrInsertFunction(callee, ft);
        if (calleeF == null) return errorV ("Unknown function referenced");
        if (calleeF.getArguments().getSize() != args.getSize()) return errorV ("Incorrect # arguments passed");
        Value[] argsV = [];
        int e;
        for (int i = 0; i != args.getSize (); i++) {
            Value v = args[i].codeGen (gen);
            argsV.add (v);
            if (argsV[argsV.getSize() - 1] == null) return null;
        }
        return gen.builder.CreateCall (calleeF, argsV);
    }
}

class IfExprAST extends ExprAST {
    ExprAST cond, thenAST, elseAST;
    IfExprAST (ExprAST cond, ExprAST thenAST, ExprAST elseAST) {
        this.cond = cond;
        this.thenAST = thenAST;
        this.elseAST = elseAST;
    }
    Value codeGen (Generator gen) {
        Value condV = cond.codeGen (gen);
        if (condV == null) return null;
        condV = gen.builder.CreateICmpEQ (condV, ConstantInt.get(gen.intTy, 1));
        BasicBlock thenBB = BasicBlock.create (gen.func);
        BasicBlock elseBB = BasicBlock.create (gen.func);
        BasicBlock mergeBB = BasicBlock.create (gen.func);

        gen.builder.CreateCondBr(condV, thenBB, elseBB);

        gen.builder.setInsertPoint (thenBB);
        Value thenV = thenAST.codeGen (gen);
        if (thenV == null) return null;
        gen.builder.createBr (mergeBB);
        //thenBB = gen.builder.getInsertBlock ();

        gen.builder.setInsertPoint(elseBB);
        Value elseV = elseAST.codeGen (gen);
        if (elseV == null) null;
        gen.builder.createBr (mergeBB);
        //elseBB = gen.builder.getInsertBlock ();

        gen.builder.setInsertPoint (mergeBB);
        PHINode pn = gen.builder.createPHI (gen.intTy, 2);
        pn.addIncoming (thenV, thenBB);
        pn.addIncoming (elseV, elseBB);
        return pn;
    }
}

class ForExprAST extends ExprAST {
    String varName;
    ExprAST start, end, step, body;
    ForExprAST (String varName, ExprAST start, ExprAST end, ExprAST step, ExprAST body) {
        this.varName = varName;
        this.start = start;
        this.end = end;
        this.step = step;
        this.body = body;
    }
    Value codeGen (Generator gen) {
        IRBuilder builder = gen.builder;
        Value startVal = start.codeGen ();
        if (startVal == null) return null;
        Function func = gen.func;
        BasicBlock preheaderBB = builder.getInsertBlock ();
        BasicBlock loopBB = BasicBlock.create (gen.func);
        builder.createBr (loopBB);
        builder.setInsertPoint (loopBB);

        PHINode variable = builder.createPHI (gen.intTy, 2);
        variable.addIncoming (startVal, preheaderBB);
        Value oldVal = gen.namedValues[varName];
        gen.namedValues[varName] = variable;

        if (body.codeGen (gen) == null) return null;
        Value stepVal;
        if (step != null) {
            stepVal = step.codeGen (gen);
            if (stepVal == null) return null;
        } else {
            stepVal = ConstantInt.get(gen.intTy, 1);
        }
        Value nextVar = builder.createAdd (variable, stepVal);
        Value endCond = end.codeGen (gen);
        if (endCond == null) return endCond;
        endCond = builder.createIcmpEQ (endCond, ConstantInt.get(gen.intTy, 1));

        BasicBlock loopEndBB = builder.getInsertBlock ();
        BasicBlock afterBB = BasicBlock.create (gen.func);
        builder.createCondBr (endCond, loopBB, afterBB);
        builder.setinsertPoint (afterBB);
        variable.addIncoming (nextVar, loopEndBB);
        if (oldVal != null) {
            gen.namedValues[varName] = oldVal;
        } else {
            gen.namedValues.remove (varName);
        }
        return ConstantInt.get (gen.intTy, 0);
    }
}

class PrototypeAST {
    String name;
    String[] args;
    PrototypeAST (String name, String[] args) {
        this.name = name;
        this.args = args;
    }
    Function codeGen (Generator gen) {
        Type[] argsTy;
        argsTy = new Type[args.getSize()];
        for (int i = 0; i < args.getSize(); i++) {
            argsTy[i] = gen.intTy;
        }
        FunctionType ft = FunctionType.get (gen.intTy, argsTy, false);
        Function f = gen.m.getOrInsertFunction (name, ft);

        argsF = f.getArguments ();
        for (int i = 0; i < args.getSize (); i++) {
            argsF[i].setName (args[i]);
            gen.namedValues[args[i]] = argsF[i];
        }
        return f;
    }
}

class FunctionAST {
    PrototypeAST proto;
    ExprAST body;
    FunctionAST (PrototypeAST proto, ExprAST body) {
        this.proto = proto;
        this.body = body;
    }
    Function codeGen (Generator gen) {
        gen.namedValues = {};
        Function theFunction = proto.codeGen (gen);
        gen.func = theFunction;
        if (theFunction == null) return null;
        BasicBlock bb = BasicBlock.create (theFunction);
        IRBuilder builder = new IRBuilder (bb);
        gen.builder = builder;
        gen.builder.setInsertPoint (bb);
        Value retVal = body.codeGen (gen);
        if (retVal != null) {
            gen.builder.createRet (retVal);
            return theFunction;
        }
        //theFunction.eraseFromParent ();
        return null;
    }
}


static ExprAST parsePrimary (Reader reader);
static ExprAST parseBinOpRHS (Reader reader, int exprPrec, ExprAST lhs);

static ExprAST parseExpression (Reader reader) {
    ExprAST lhs = parsePrimary (reader);
    if (lhs == null) return null;
    return parseBinOpRHS (reader, 0, lhs);
}

static ExprAST parseParenExpr (Reader reader) {
    reader.getNextToken();
    ExprAST res = ParseExpression(reader);
    if (res == null) return null;
    if (curTok != ')') return error ("expected ')'");
    reader.getNextToken();
    return res;
}

static ExprAST parseIfExpr (Reader reader) {
    reader.getNextToken ();
    ExprAST cond = parseExpression (reader);
    if (cond == null) return null;
    if (curTok != tok_then) {
        return error ("expected then");
    }
    reader.getNextToken ();
    ExprAST thenAST = parseExpression (reader);
    if (thenAST == null) return null;
    if (curTok != tok_else) {
        return error ("expected else");
    }
    reader.getNextToken ();
    ExprAST elseAST = parseExpression (reader);
    if (elseAST == null) return null;

    return new IfExprAST (cond, thenAST, elseAST);
}

static ExprAST parseForExpr (Reader reader) {
    reader.getNextToken ();
    if (curTok != tok_identifier)
        return error ("expected identifier after for");
    String idname = reader.identifierStr;
    reader.getNextToken ();
    if (curTok != '=')
        return error ("exprcted '=' after for");

    reader.getNextToken ();

    ExprAST start = parseExpression (reader);
    if (start == null) return null;
    if (curTok != ',')
        return error ("expected ',' after for start value");
    reader.getnextToken ();

    ExprAST end = parseExpression (reader);
    if (end == null) return null;

    ExprAST step = null;
    if (curTok == ',') {
        reader.getNextToken ();
        step = parseExpression (reader);
        if (step == null) return null;
    }

    if (curTok != tok_in)
        return error ("expected 'in' after for");
    reader.getNextToken ();

    ExprAST body = parseExpression (reader);
    if (body == null) return null;

    return new ForExprAST (idName, start, end, step, body);
} 
static ExprAST parseNumberExpr (Reader reader) {
    reader.getNextToken ();
    ExprAST res = new NumberExprAST (reader.numVal);
    return res;
}

static ExprAST parseIdentifierExpr (Reader reader) {
    String idName = reader.identifierStr;
    reader.getNextToken ();
    if (curTok != '(') {
        return new VariableExprAST (idName);
    }
    reader.getNextToken ();
    ExprAST[] args = [];
    if (curTok != ')') {
        while (true) {
            ExprAST arg = ParseExpression (reader);
            if (arg == null) return null;
            args.add (arg);
            if (curTok == ')') break;
            if (curTok != ',') {
                return error("Expected ')' or ',' in argument list");
            }
            reader.getNextToken ();
        }
    }
    reader.getNextToken ();
    return new CallExprAST (idName, args);
}

static ExprAST parsePrimary (Reader reader) {
    if (curTok == tok_identifier) {
        return parseIdentifierExpr (reader);
    } else if (curTok == tok_number) {
        return parseNumberExpr (reader);
    } else if (curTok == tok_if) {
        return parseIfExpr (reader);
    } else if (curTok == tok_for) {
        return parseForExpr (reader);
    } else if (curTok == '(') {
        return parseParenExpr (reader);
    } else {
        return error ("unknown token when expecting an expression");
    }
}

static int getTokPrecedence () {
    int tokPrec = binopPrecedence[(String)curTok];
    if (tokPrec <= 0) return -1;
    return tokPrec;
}

static ExprAST parseBinOpRHS (Reader reader, int exprPrec, ExprAST lhs) {
    while (true) {
        int tokPrec = getTokPrecedence ();
        if (tokPrec < exprPrec) {
            return lhs;
        }
        int binOp = curTok;
        reader.getNextToken ();
        ExprAST rhs = parsePrimary (reader);
        if (rhs == null) return null;
        int nextPrec = getTokPrecedence ();
        if (tokPrec < nextPrec) {
            rhs = parseBinOpRHS (reader, tokPrec + 1, rhs);
            if (rhs == null) return null;
        }
        lhs = new BinaryExprAST (binOp, lhs, rhs);
    }
    print "error";
    return null;
}

static PrototypeAST parsePrototype (Reader reader) {
    if (curTok != tok_identifier) {
        return errorP ("Expected function name in prototype");
    }
    String fnName = reader.identifierStr;
    reader.getNextToken ();
    if (curTok != 40) {
        return errorP("Expected '(' in prototype");
    }
    String[] argNames = [];
    while (reader.getnextToken () == tok_identifier) {
        argNames.add (reader.identifierStr);
    }
    if (curTok != 41) {
        return errorP ("Expected ')' in prototype");
    }
    reader.getNextToken ();
    return new PrototypeAST (fnName, argNames);
}

static FunctionAST parseDefinition (Reader reader) {
    reader.getNextToken ();
    PrototypeAST proto = parsePrototype (reader);
    if (proto == null) return null;
    ExprAST e = ParseExpression (reader);
    if (e != null) {
        return new FuctionAST (proto, e);
    }
    return null;
}

static PrototypeAST parseExtern (Reader reader) {
    reader.getNextToken ();
    return parsePrototype (reader);
}

static ExprAST parseTopLevelExpr (Reader reader) {
    ExprAST e = ParseExpression (reader);
    if (e != null) {
        //PrototypeAST proto = new PrototypeAST ("Script", new String[]());
        //return new FunctionAST (proto, e);
        return e;
    }
    return null;
}

static void handleDefinition (Generator gen, Reader reader) {
    FunctionAST f = parseDefinition (reader);
    if (f != null) {
        Function lf = f.codeGen (gen);
        if (f != null) {
            print "Read function definition";
            lf.dump ();
        }
    } else {
        print "definition error";
        reader.getNextToken ();
    }
}

static void handleTopLevelExpression (Generator gen, Reader reader) {
    ExprAST f = parseTopLevelExpr (reader);
    if (f != null) {
        createScript (gen);
        Value lf = f.codeGen (gen);
        if (lf != null) {
            print "Parsed a top-level expr";
            printi(gen, lf);
            gen.builder.CreateRetVoid();
            gen.func.dump();
            gen.emit();
            f();
            exit();
        }
    } else {
        print "top-level error";
        reader.getNextToken ();
    }
}

static void handleExtern (Generator gen, Reader reader) {
    PrototypeAST p = parseExtern (reader);
    if (p != null) {
        Function f = p.codeGen (gen);
        if (f != null) {
            print "Parsed an extern";
            f.dump ();
        }
    } else {
        print "extern error";
        reader.getNextToken ();
    }
}


static void mainLoop (Generator gen, Reader reader) {
    while (true) {
        OUT.flush ();
        switch (curTok) {
            case ';': { reader.getNextToken (); break;}
            case -2:  { handleDefinition (gen, reader); break;}
            case -3:  { handleExtern (gen, reader); break;}
            case -1:  return;
            default:  { handleTopLevelExpression (gen, reader); break;}
        }
    }
}

void main (String[] args)
{
    binopPrecedence["60"] = 10; // <
    binopPrecedence["62"] = 10; // >
    binopPrecedence["43"] = 20; // +
    binopPrecedence["45"] = 20; // -
    binopPrecedence["42"] = 40; // *
    Module m = new Module("konoha");
    Method mtd = method:Script.f;
    Reader reader = new Reader ();
    gen = new Generator(m, mtd);

    init(gen);
    reader.getNextToken ();
    MainLoop (gen, reader);
    return;
}

オリジナル言語のLLVMフロントエンドをKonohaScriptで実装する その3

　LLVMのチュートリアルページ(http://llvm.org/docs/tutorial/LangImpl1.html)の2章まで追っていきます。ここまではチュートリアルで記述されているものとほぼ一緒です。LLVM IRを作成し、KonohaScriptの関数として実行する際には若干手を加えている部分があります。
　今回は文字列を受け取る所から、ASTを作成する所までです。

• Lexer

　文字列を標準入力から受け取って、トークンへと分解していきます。
KonohaScriptではSystem.readLine()関数で行単位での文字列の入力を受けとることが出来ます。

• Parser

　Lexerから受け取ったトークン列を元に、Abstract Syntax Tree (AST, 抽象構文木) を作ります。

ここまでで以下のような動作が確認出来ます。

$ konoha kaleidoscope.k
ready>def foo(x y) x+foo(y, 4.0);
ready>(handleDefinition:330) Parsed a function definition
ready>def foo(x y) x+y;
ready>(handleDefinition:330) Parsed a function definition
ready>y;
ready>(handleTopLevelExpression:339) Parsed a top-level expr

ソースコード

　370行程です。5章まで実装している段階で700行を超えているのですが、こちらに直接書き込むのは既に限界のようです。
GitHubの利用を検討してみます。

　コピペしても動くはずです。

using konoha.lang.*;

static Map<String, int> binopPrecedence = {};

int tok_eof = -1; int tok_def = -2; int tok_extern = -3;
int tok_identifier = -4; int tok_number = -5;

static int numVal = 0;
static String identifierStr = "";

static boolean isspace (String s)
{
    int c = ((Bytes)s[0])[0];
    return (c == ' ');
}

static boolean isalpha (String s)
{
    int c = ((Bytes)s[0])[0];
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

static boolean isdigit (String s)
{
    int c = ((Bytes)s[0])[0];
    return (c >= '0' && c <= '9');
}

static boolean isalnum (String s)
{
    return (isalpha(s) || isdigit(s));
}

static String str = null;
static int cur = 0;

String getchar ()
{
    String res;
    while (str == null || cur == |str| + 1) {
        str = readLine();
        cur = 0;
    }
    if (cur == |str|) {
        res = " ";
    } else {
        res = str[cur];
    }
    cur++;
    return res;

}
String lastChar = " ";
static int gettok ()
{
    while (isspace(lastChar)) {
        lastChar = getchar();
    }

    if (isalpha(lastChar)) {
        identifierStr = "";
        identifierStr = lastChar;
        while (isalnum((lastChar = getchar()))) {
            identifierStr += lastChar;
        }
        if (identifierStr == "def") return tok_def;
        if (identifierStr == "extern") return tok_extern;
        if (identifierStr == "exit" ||
            identifierStr == "quit" ||
            identifierStr == "bye"  ||
            identifierStr == "q") {
            print "bye";
            return tok_eof;
        }
        return tok_identifier;
    }

    if (isdigit(lastChar) || lastChar == ".") {
        String numStr = "";
        do {
            numStr += lastChar;
            lastChar = getchar();
        } while (isdigit(lastChar) || lastChar == ".");
        numVal = (int)numStr;
        return tok_number;
    }

    if (lastChar == "#") {
        do {
            lastChar = getchar();
        } while (lastChar != "\n");
        return gettok();
    }

    String thisChar = lastChar;
    lastChar = getchar();
    return ((Bytes)thisChar[0])[0];
}

int curTok;

static int getNextToken () {
    curTok = gettok ();
    return curTok;
}


class ExprAST {
    ExprAST () {}
}

class NumberExprAST extends ExprAST {
    int val;
    NumberExprAST (int val) {
        this.val = val;
    }
}

ExprAST error (String str) {
    print "Error: ", str;
    ExprAST res = null;
    return res;
}

PrototypeAST errorP (String str) { 
    error (str); 
    PrototypeAST res = null;
    return res;
}
FunctionAST errorF (String str) {
    error (str);
    FunctionAST res = null;
    return res;
}

class VariableExprAST extends ExprAST {
    String name;
    VariableExprAST (String name) {
        this.name = name;
    }
}

class BinaryExprAST extends ExprAST {
    int op;
    ExprAST lhs, rhs;
    BinaryExprAST (int op, lhs, rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
        this.op = op;
    }
}

class CallExprAST extends ExprAST {
    String callee;
    ExprAST[] args;
    CallExprAST (String callee, ExprAST[] args) {
        this.callee = callee;
        this.args = args;
    }
}

class PrototypeAST {
    String name;
    String[] args;
    PrototypeAST (String name, String[] args) {
        this.name = name;
        this.args = args;
    }
    Function codeGen (LLVMGenerator gen) {
    }
}

class FunctionAST {
    PrototypeAST proto;
    ExprAST body;
    FunctionAST (PrototypeAST proto, ExprAST body) {
        this.proto = proto;
        this.body = body;
    }
    Function codeGen (LLVMGenerator gen) {
    }
}


static ExprAST parsePrimary ();
static ExprAST parseBinOpRHS (int exprPrec, ExprAST lhs);

static ExprAST parseExpression () {
    ExprAST lhs = parsePrimary ();
    if (lhs == null) return null;
    return parseBinOpRHS (0, lhs);
}

static ExprAST parseParenExpr () {
    getNextToken();
    ExprAST res = ParseExpression();
    if (res == null) return null;
    if (curTok != ')') return error ("expected ')'");
    getNextToken();
    return res;
}

static ExprAST parseNumberExpr () {
    getNextToken ();
    ExprAST res = new NumberExprAST (numVal);
    return res;
}

static ExprAST parseIdentifierExpr () {
    String idName = identifierStr;
    getNextToken ();
    if (curTok != '(') {
        return new VariableExprAST (idName);
    }
    getNextToken ();
    ExprAST[] args = [];
    if (curTok != ')') {
        while (true) {
            ExprAST arg = ParseExpression ();
            if (arg == null) return null;
            args.add (arg);
            if (curTok == ')') break;
            if (curTok != ',') {
                print (char)curTok;
                return error("Expected ')' or ',' in argument list");
            }
            getNextToken ();
        }
    }
    getNextToken ();
    return new CallExprAST (idName, args);
}

static ExprAST parsePrimary () {
    if (curTok == tok_identifier) {
        return parseIdentifierExpr ();
    } else if (curTok == tok_number) {
        return parseNumberExpr ();
    } else if (curTok == '(') {
        return parseParenExpr ();
    } else {
        return error ("unknown token when expecting an expression");
    }
}

static int getTokPrecedence () {
    int tokPrec = binopPrecedence[(String)curTok];
    if (tokPrec <= 0) return -1;
    return tokPrec;
}

static ExprAST parseBinOpRHS (int exprPrec, ExprAST lhs) {
    while (true) {
        int tokPrec = getTokPrecedence ();
        if (tokPrec < exprPrec) {
            return lhs;
        }
        int binOp = curTok;
        getNextToken ();
        ExprAST rhs = parsePrimary ();
        if (rhs == null) return null;
        int nextPrec = getTokPrecedence ();
        if (tokPrec < nextPrec) {
            rhs = parseBinOpRHS (tokPrec + 1, rhs);
            if (rhs == null) return null;
        }
        lhs = new BinaryExprAST (binOp, lhs, rhs);
    }
    print "error";
    return null;
}

static PrototypeAST parsePrototype () {
    if (curTok != tok_identifier) {
        return errorP ("Expected function name in prototype");
    }
    String fnName = identifierStr;
    getNextToken ();
    if (curTok != 40) {
        return errorP("Expected '(' in prototype");
    }
    String[] argNames = [];
    while (getnextToken () == tok_identifier) {
        argNames.add (identifierStr);
    }
    if (curTok != 41) {
        return errorP ("Expected ')' in prototype");
    }
    getNextToken ();
    return new PrototypeAST (fnName, argNames);
}

static FunctionAST parseDefinition () {
    getNextToken ();
    PrototypeAST proto = parsePrototype ();
    if (proto == null) return null;
    ExprAST e = ParseExpression ();
    if (e != null) {
        return new FuctionAST (proto, e);
    }
    return null;
}

static PrototypeAST parseExtern () {
    getNextToken ();
    return parsePrototype ();
}

static ExprAST parseTopLevelExpr () {
    ExprAST e = ParseExpression ();
    if (e != null) {
        return e;
    }
    return null;
}

static void handleDefinition () {
    FunctionAST f = parseDefinition ();
    if (f != null) {
            print "Parsed a function definition";
    } else {
        getNextToken ();
    }
}

static void handleTopLevelExpression () {
    ExprAST f = parseTopLevelExpr ();
    if (f != null) {
        print "Parsed a top-level expr";
    } else {
        getNextToken ();
    }
}

static void handleExtern () {
    PrototypeAST p = parseExtern ();
    if (p != null) {
        print "Parsed an extern";
    } else {
        getNextToken ();
    }
}


static void mainLoop () {
    while (true) {
        System.out.print("ready>");
        OUT.flush ();
        switch (curTok) {
            case ';': { getNextToken (); break;}
            case -2:  { handleDefinition (); break;}
            case -3:  { handleExtern (); break;}
            case -1:  return;
            default:  { handleTopLevelExpression (); break;}
        }
    }
}

void main (String[] args)
{
    binopPrecedence["60"] = 10; // <
    binopPrecedence["62"] = 10; // >
    binopPrecedence["43"] = 20; // +
    binopPrecedence["45"] = 20; // -
    binopPrecedence["42"] = 40; // *
    OUT << "ready>";
    OUT.flush ();
    getNextToken ();
    MainLoop ();
    return;
}

オリジナル言語のLLVMフロントエンドをKonohaScriptで実装する その2

　前回の補足です。KonohaScriptのインストールはKonohaScript インストール手順（１）ソースからのビルド - Konoha日誌 で確認する事が出来ます。LLVMパッケージの利用には、LLVM(http://llvm.org/)のインストールも必要です。
　KonohaScriptのLLVMパッケージではC++で記述されているLLVMをバインドしています。コード自体はLLVMのチュートリアル(http://llvm.org/docs/tutorial/)にあるオリジナルのKaleidoscopeのサンプルコードが基本になります。このため実装の大部分については終了しているといえます。今回はコードを簡潔に記述するために省略していますが、KonohaScriptからJITコンパイルされた関数を呼び出す際、引数や返り値はKonohaScriptのスタックにロード/ストアする必要があります。

JITコンパイルされたプログラムの実行

JITコンパイルされた関数addを、KonohaScriptから呼び出してみます。

int x = 10, y = 20;
print add(x, y)

関数addへの引数は、KonohaScriptのスタック上にストアされています。このため、addが引数x、yを利用するためには、KonohaScriptのスタック上から値をロードする必要があります。同様に返り値もKonohaScriptのスタックにストアしなければいけません。このためにはLLVMのモジュールにKonohaScriptのスタックや、KonohaScript内部で利用されている構造体の型情報を登録する必要があります。KonohaScript内部で利用されている構造体の中には、メンバが非常に多い構造体がいくつか存在します。冗長なコードなので、今回はKonohaScriptとの引数と返り値のやりとりは省略します。JITコンパイルされた関数の結果の表示は、関数内で直接printfを呼ぶなどしようかと思います。

オリジナル言語(Kaleidoscope)のLLVMフロントエンドをKonohaScriptで実装する

　題名の通り、ごく単純な数値演算を行えるプログラミング言語(Kaleidoscope)のフロントエンドをKonohaScriptで実装しようと考えています。
現在KonohaScriptにはLLVMパッケージが用意されており、KonohaScript上からLLVMのAPI(一部)を利用することが出来ます。LLVMパッケージは、KonohaScriptのバイトコードをJITコンパイルするために利用されていますが、KonohaScriptでオリジナル言語のLLVMフロントエンドを実装する事も当然可能です。

　LLVMのチュートリアル(http://llvm.org/docs/tutorial/)にて、Kaleidoscopeと呼ばれている言語をC++で実装しているので、これとほぼ同じ物をKonohaScriptで実装してみようと思います。今回の目標として、こちらにある以下のコード

def fib(x)
if x < 3 then
1
else
fib(x-1)+fib(x-2)

fib(40)

が動作する事としたいと思います。