BE-Lang を C で構築する試み 2

BE-Lang を C で構築する試み

　今回の記事は、こちらの BE-Lang を C で構築する試み という私の記事の続きとなっております。こちらの内容を前提として話しますので、まだ読んでいない方はぜひ読んでください。

　みなさんこんにちは。tukinyanJP こと つきにゃんじぇーぴーです。今回も前回に続き、 C 言語で構築していこうかなと思います。

実は記事を書く前にできてた新しい機能

　この記事を書く前にすでに実装していた新しい機能が実はあって、それは for 文です。このように定義しています。

parser.y

for_stmt: FOR '(' NAME ARROW assignment ',' exp ')' THEN '{' program '}'

解説しますと、

• FOR は lex [^1] で定義しているトークンの識別子です。小文字の for にマッチします
• NAME は FOR と同じく lex [^1] で定義しているトークンの識別子です。変数の識別子にも使われています小文字大文字にマッチします
• ARROW FOR , NAME と同じく識別子です -> にマッチします
• assignment 代入式の定義です。 NAME += exp などにマッチします
• exp は数式などです 1 == 1 , 1 + 1 比較式、数式マッチします
• THEN は NAME などと同じくトークンの識別子で、小文字の then にマッチします
• program は、 for_stmt や、 assignment などの集まりを示します

　つまり、文法的には以下のような式が当てはまります。

for.be

for (i -> i += 1, i <= 10) then {
  puts(i)
}

　で、結局文法に当てはまったらどういうアクションをするのかと言うと、

• i -> i += 1, ここで、一ステップ(一回の処理)で比較対象の変数をどのように値を変更するか指定する
• i <= 10 変数 i が 10以下の場合 { } の間のプログラムを実行するフラグを立てる。
• 以下、 AST などを生成し実行。 前回の記事を参照

これだけでは分からないと思うのでこのような 5 から 100 万までの素数を求めるプログラムを示します。

sosuu.be

def sosuu(n) {
    if (n == 1) then { return 0 }
    if (n == 2) then { return 1 }
    if (n % 2 == 0) then { return 0 }
    if (n % 3 == 0) then { return 0 }

    i = 5
    for (i -> i += 6, i * i <= n) then {
        if (n % i == 0) then {
            return 0
        }
    }
    return 1
}

for (t -> t += 1, t <= 1000000) then {
    if (sosuu.(t) == 1) then {
        puts(t)
    }
}

出力はこんな感じです。

output.txt

2
5
7
11
13
17
...略

これ、結構すごいんじゃないか...? 素数を求められるってことは チューリング完全性 できるんじゃないか?

終わりに

　結構 C で実装するのが難しいと思っていたこの私ですが、案外簡単なものですね。これが簡単に速く動くなんて感動です!
それではまた次の記事で。さようなら!