第8回で計算式の平坦化を行いましたが、それは全て Int 型を想定して行っていました。拡張として、複数の型を導入して、型検査を実行してみようと思います。例えば、プラスの記号の両側には同じ型の値が与えられ、それらと同じ型の値を返すというように決め…

そういえばドラゴン本を買いました。これを参考にしてコンパイラ制作を加速させます。第5回で字句解析と構文解析を行いました。四則演算や関数適用などの簡易的な入力に対し、それを構文解析して抽象構文木を出力しましたが、今度はそれを変換します。例えば…

LLVM を用いて FizzBuzz を書きました。色々と躓いた点があったので、それを記述しておきます。まずはプログラム本体から @s1 = constant [10 x i8] c"FizzBuzz\0A\00" @s2 = constant [6 x i8] c"Buzz\0A\00" @s3 = constant [6 x i8] c"Fizz\0A\00" @s4 = …

引き続いて LLVM を勉強します。今回は、 FizzBuzz のC言語プログラムを LLVM に変換して、その内容を確認してみようと思います。C言語の FizzBuzz プログラムです。 #include <stdio.h> int main(void){ int i; for(i = 1; i <= 100; i++){ if(i % 15 == 0){ printf(</stdio.h>…

LLVM の勉強と平行して、コンパイラについて勉強します。コンパイラは、プログラムの入力から中間コード生成までの間に、字句解析と構文解析の作業を行います。ただの文字列からトークン列、構文木というように変換していきます。字句解析と構文解析はプログ…

ある場において出発地点、目的地点、通過可能な場所が与えられた時、出発地点から目的地点までたどり着くことが可能かどうかを判定する到達可能問題を解こうと思います。問題を想定します。幅 width 高さ height の場が与えられ、出発地点と目的地点が与えら…

第2,3回で x_86-64 のアセンブリに手を出してみましたが、プログラムをいきなりアセンブリに変換するのは困難です。普通は中間コードを経てアセンブリ、機械語に変換されます。色々調べてみると LLVM というものがあってそれ用の中間コードを作ると、あとの…

C++ と OCaml でダイクストラ法の実装を行いました。 ダイクストラ法では、夫々の辺に負でない長さが与えられたグラフ上で、二つの頂点間の最短距離とそれを与える経路を求められます。まずグラフを用意します。 インターネット上でいい感じのグラフを見つけ…

自作言語を作っている途中ですが、様々な手法を学習するため、 MinCaml という言語のコンパイラを作りながら関数型プログラミング言語のコンパイラ作成の概形と内容について学びます。MinCaml というのは OCaml のサブセットのような言語で、検索するとわか…

Homebrew で LLVM をインストールしたのですが、 llc と入力しても command not found となり実行できなかったので解決策を書きます。Homebrew のインストール時に keg-only という出力がされているものは、普段使っている /usr/local/bin にインストールさ…

前回は Hello, world! を出力させる x86-64 アセンブリを書いたので、一段階レベルを上げて、数字を出力させてみます。 アセンブリでは、C言語みたく printf("%d", n) のような一発で数値を出力する機構は存在しません。数値を文字列に変換しなければ出力で…

コンパイラを作るには、手順としては最初にする必要は無いでしょうが、アセンブリの事を分かっていないとあまりイメージが湧きにくい気がします。 そのようなわけで、まずはアセンブリプログラミングをしてみようと思います。 私が使っている多くのパソコン…

新しいプログラミング言語のコンパイラを作りたいと思ってなかなか行動に移していなかったのですが、社会人になることですし、そろそろ開発をしていきたいと思います。 最初から道筋が決まっていてそれを解説するのではなく、作りながら試行錯誤を繰り返して…

CentOS で Python3.5 をインストールして pip3.5 をしようと次のコマンドを実行しました。 sudo pip3.5 search nltkすると、コマンドが無いということで実行できませんでした。普通に pip3.5 をコマンドとして入力すると実行できるので、sudo にした際にパス…

自然言語処理のために文字列のアノテーションを行うためのブラウザインターフェースを、 PHP, MySQL, JavaScript で作っていたのですが、コーパスの文字コードが統一されていなくて、それを UTF-8 に変換して使うために苦戦したので記しておきます。 PHP の…

OCaml の処理系の実装を大学の課題で取り組んだことがあって、そのときは let多相の実装まで取り組めなかったので、改めてやってみることにしました。 let多相というのは、例えば引数を一つ受け取って同じ値を返す関数 id を定義すると、 # let id x = x;; v…

Mac で Homebrew によって D言語のコンパイラ dmd を導入していたのですが、 brew upgrade をするとなぜか import std.cstream; import conv: to; int main(){ dout.writeLine(to!(string)(3)); return 0; } だけの簡単なプログラムすら動かなくなってしまっ…

Scala で構文木出力のためのパーサーコンビネーターを書きました。多言語対応にするつもりで、現在はC言語のそれが大体動くようにはなったのですが、 何故か構文解析プログラムで勝手にトークン列が変更されてしまうという原因不明のバグにはまってしまった…

先日書いていた Node.js で動作させる JavaScript のプログラムを実行したところ、何故かエラーで動かなかったので色々と調べてみました。 原因は function 式にセミコロンを付与していなかったことなんですが、結構わかりづらいバグで苦戦しました。動作環…

手元で実行した Scala 2.11.1 のインタプリタで、 immutable の Array, Set などが何故か変更可能になっている。 scala> var s = scala.collection.immutable.Set[Int]() s: scala.collection.immutable.Set[Int] = Set() scala> s += 1 scala> s s: scala.c…

D 言語を扱ってみたくなったので Hello World! プログラムを探して DMD でコンパイルした。 import std.stream; int main(){ stdout.writeLine("Hello World!"); return 0; } しかしコンパイルエラーになってしまった。 D 言語は開発途上で仕様が頻繁に変わ…

再帰をスタックに直したことが無かったので、 factorial と fibonacci について実行してみた。（ factorial(0) が正しく動かないのは見逃してください。） #include <iostream> #include <stack> using namespace std; int factorial(int n){ int ans = 1; stack<int> s; s.push(n)</int></stack></iostream>…

動的計画法を用いる機会が無くてナップザック問題すら解いたことが無いのでナップザック問題を解きました。入力 n w w1 v1 ... wn vnn 種類の荷物から自由に選択し、重さ w 以下で価値が最大となる組み合わせを選択する。 i 番目の荷物の重さは wi で価値は …

動的計画法を学習してから数年、全然使っていないと思って DNA 配列の LCS を求めるプログラムを書きました。 長さ n の文字列 s と長さ m の文字列 t が与えられたとして、部分文字列がより長く一致する空白（ギャップ）の与え方を求めます。 s の i 番目ま…

Python3 で Wikipedia のデータを解析するために、 class Entry: def __init__(self, title, redirect_from=[], document=None, link_from=[], link_to=None): self.title = title self.redirect_from = redirect_from self.document = document self.link_f…

enchant.js を使ったゲームのソースコードを GitHub のリポジトリに追加する際、間違って enchant.js までアップしてしまったので、 git rm --cached js/enchant.jsで削除しました。これで、手元にファイルを残したままリポジトリから削除出来ました。

.gitignore に .DS_Store などを登録しておいたが、 git add . とコマンドを入力するとなぜか .DS_Store まで含まれてしまいました。 とりあえず git config --global core.excludesfile ~/.gitignoreを実行したんですが、 .gitconfig にただ内容を追加して…

今まで SSH はパスワードを使ってログインしていたのですが、先日、初めてさくら VPS に鍵認証の設定をしたので、それをメモしておきます。(OS:Ubuntu)なぜ鍵認証をしたかというと、ポート番号の変更がなぜか出来なかったからです。（他の PC では普通に出来…

ARC018 の C 問題「席替え」を（解説を見ながら）解きました。 i 行 j 列 (i,j) の人の成績 G(i, j) とするとき、 (a,b) まず、 x_i = (x_(i-1) + a) % p で、 a%p!=0, m*n 成績がすべて異なる値をとるとき、行は floor(G[i][j]/m) で確定し、列は交差しない…

N 個の数値のうち、好きなだけ選んで合計を X にできるパターンの個数を求めるという問題で、 N が小さい値ならばそのまま全探索(O(2^N))すれば良いんですが、 N が 32 だと時間切れになります。解説を読むと、N 個の数値を半分に分割し、片方の合計を p, も…