超基本的なコンパイラを作ってみる（1. 字句解析編）

コンパイラ

大学で言語処理系論というコンパイラを扱う講義を受講したので，その実践を兼ねて自分でコンパイラを作ろうと決意しました． いきなり"なんとか言語"のコンパイラを作るのは難しいので，本当に単純なものから始めたいと思います．

作る題材は何かと言うと，『よくある例 (The all-time favorite) 、卓上計算機です。』（引用元：http://ocaml.jp/archive/ocaml-manual-3.06-ja/manual026.html）

新規性のカケラもない企画ですが，自分で作るところに意味があると思っています． もちろんコピペではなく「参考にして」オリジナルの機能も導入しながら作っていきます．

コンパイラの構成

コンパイラを作るためにはまず構成を知らなくてはいけないので，調べました． 参考文献はこちらです． いわゆるタイガーブックというやつですね．

https://www.amazon.co.jp/%E6%9C%80%E6%96%B0%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E6%A7%8B%E6%88%90%E6%8A%80%E6%B3%95-Andrew-W-Appel/dp/4798114685

さて，コンパイラのフェーズには（上の本よりも）大雑把に分けて次のものがあります．

1. 字句解析
   • ソースファイルを個々のトークンへと分解する
2. 構文解析
   • プログラムの句構造を解析する
3. 意味解析
   • 変数や式の型を検査して各句の意味を決定する
4. 中間コード生成
   • 特定のプログラミング言語やマシンに依存しない中間コードを生成する
5. 最適化
   • 高速化を図る
6. 機械語コード生成
   • 最適化した中間コードを元に機械語コードを生成する

字句解析

まずは字句解析器から作ってみたいと思います． 字句解析の入出力は次のイメージです．

• 入力：x = 3.1 + y * 20
• 出力：ID("x") EQ Float(3.1) PLUS ID("y") TIMES INT(20)

入力された文字列の各単語について，対応するトークンを割り当てます．

字句解析器の仕組み

字句解析器をどのように作るかというと， “正規表現” を使います． 正規表現についての説明は割愛します．

正規表現のプログラムでの実装は，正規表現をオートマトンに変換することで行います．

しかしここでは簡単のため"字句解析器生成ツール"というものを使いたいと思います．

Lex

Lexは字句解析器生成ツールです． 正規表現やトークンの情報を書いたファイルを入力すると，字句解析器を生成してくれます．

今回はLexのOcaml版，Ocamllexを使います．（Ocamlをインストールすれば一緒についてきた気がします…）

Ocamllex

Ocamllexの使い方については，下のリンクに書いてあります（がかなり分かりづらかったです） Lexer and parser generators (ocamllex, ocamlyacc)

以下，上のサイトのまとめになっています．

Ocamllexの設定ファイル（拡張子は.mll）のフォーマットは次のようになっています．

%{
  header：あらかじめ設定しておきたい事項や読み込んでおきたいモジュールを書いておく
%}
  declarations：変数を宣言したりする．正規表現を変数にしておくときとか
%%
  rules：正規表現を用いてトークンの定義を記述する
%%
  trailer: 最後に実行したい処理や後に使いたいOCamlのコードを書いておける

以上を書いたファイルをlexer.mllとして保存します． ここで，今回記述する文法の仕様を決めたいと思います．拡張する可能性もあるのでかなりざっくりですが…

• 四則演算はそのまま記述できるように
• 後に変数が使えるように，1文字目が英字，2文字目以降が英数字もしくはアンダースコアなものをIDとして認識

例えば今回は次のように記述しました． なおこのファイルは上のサイトだけでなく以下の講義サイトも参考にしています（講義資料は受講者しか見れませんが…）

http://www-kb.is.s.u-tokyo.ac.jp/~koba/class/compiler/

{
(* トークンの型を宣言 *)
type token = PLUS | MINUS | TIMES | DIV | LPAREN | RPAREN | EOL | EOF | ID of string | INT of int
}

(* よく使う正規表現に名前をつける *)
let space = [' ''\t''\r']
let digit = ['0'-'9']
let lower = ['a'-'z']
let upper = ['A'-'Z']

(* トークンのルール *)
rule tokenize = parse
| space+ { tokenize lexbuf } (* そのままバッファを返す *)
| (lower|upper)(lower|digit|upper|"_")+ { ID(Lexing.lexeme lexbuf) } (* 上で述べたIDの定義に従って正規表現を書いた *)
| digit+ { INT(int_of_string(Lexing.lexeme lexbuf)) } (* 数字 今はint型のみ *)
| "+" { PLUS }
| "-" { MINUS }
| "*" { TIMES }
| "/" { DIV }
| "(" { LPAREN }
| ")" { RPAREN }
| "\n" { EOL }
| eof { EOF }
| _
    { Format.eprintf "unknown token %s" (* エラー *)
    (Lexing.lexeme lexbuf);
    failwith "lex error" }

{
(* trailer *)
(* 字句解析を実行するコード *)
let rec readloop lexbuf =
    let t = tokenize lexbuf in
        if t=EOF then []
            else t::(readloop lexbuf)

(* main ファイル名 で実行 *)
let main filename =
    let lexbuf = Lexing.from_channel(open_in filename) in
        readloop lexbuf
}

以上を準備したら，次の手順で字句解析を実行できます．

1. 入力ファイルを用意
   • 例えばx1 - (2 + 3) / 5 *6と書いたファイルをin.mlとして用意
2. ocamllex lexer.mllを実行する．エラーが出たら直す
3. lexer.mlが生成されているので，シェル上でocamlと叩いてインタラクティブ環境を起動し，#use "lexer.ml"と入力してエンター．ここでエラーになること重ある（特にtrailer内でのエラーが多い）
4. 同じインタラクティブ環境で，trailerに書いたコードを読み出す．この場合ではmain "in.ml"と入力する
5. エラーがなければ，次のように出力されるはず

token list =
[ID "x1"; MINUS; LPAREN; INT 2; PLUS; INT 3; RPAREN; DIV; INT 5; TIMES;
 INT 6; EOL]

きちんとスペースなども考慮して字句解析が行われていることがわかります．

まとめ

Ocamllexを使うことで，オートマトンなどの記述の必要なく字句解析を実行することができました． 機会があればオートマトンからフルスクラッチで書いてみたいと思います．そこまで手間でないかもしれないので…

字句解析はただの文字列が解釈されるだけであまり面白くないので，次はこれを構文木の形に直す構文解析を行ってみたいと思います．

OpenAI Gymを動かしてみた（keras-rlを用いたDQN編）

前回OpenAI Gymのチュートリアルを使ってQ学習を試してみました． 今回はAlphaGoなどで話題のDQN（Deep Q Network）を試してみたいと思います．

1. Deep Q Network

Deep Q Networkとは，Q学習で用いられるQ関数（状態を入力にとり，各行動の価値を返す．行動価値関数）をDeep Neural Networkで表現したものです． Q学習においては，行動価値関数はテーブルを用いて表現されるのが一般的です． しかし，ゲームなどの多くの状態をもつ環境や，実世界などの連続値環境では，テーブルのサイズが大きくなりうまく学習ができません． このテーブルをニューラルネットワークで近似しようというのが基本的なアイデアです． （以上は私の定性的理解です）

DQNは学習が収束しにくいなどの欠点があり，それを回避するためにExperience Replayなどの様々な手法が取り入れられていますが，今回はkeras-rlという強化学習ライブラリを使って簡単に試してみたいと思います．

2. keras-rl

kerasは機械学習のライブラリの一つです．

https://keras.io/ja/

TheanoやTensorflowのラッパーであり，これらに比べて簡単にニューラルネットワークを記述することができます．

keras-rlはkeras向けの強化学習ライブラリで，

• Deep Q Learning (DQN)
• Double DQN
• Deep Deterministic Policy Gradient (DDPG)

など様々な強化学習手法を試すことができます．

github.com

ドキュメントはこちらです．

keras-rl.readthedocs.io

3. 試してみる

まずはkerasとkeras-rlのインストールを行います． なおこの部分は以下のリンクを参考にしました． qiita.com

• keras

pip install keras

• keras-rl

git clone https://github.com/matthiasplappert/keras-rl.git
pip install ./keras-rl

keras-rlを展開したディレクトリに，example/dqn_cartpole.pyというファイルがあると思うので，それを実行します．

するとLayer情報が出力された後，Cartpoleの描画が始まります． しばらくすると学習され，持続時間が伸びていくことが確認できます．

私の環境では200エピソード程度でほぼ最後まで続くようになりました． （Q学習では数千エピソード程度の学習が必要だったので，それより優れているかもしれません．パラメータチューニングを行なっていないのでなんとも言えませんが…）

4. その他

自分でアルゴリズムを作りたい，などの場合は，CartPole-v0環境についてのドキュメントを確認すると良いと思います．

github.com

また，env.render()で描画される画面は，ディスプレイに見えていない時（ウィンドウの後ろにあるなど）は描画がスキップされるらしく，必要な時だけ見えるようにしておくことで学習の高速化が図れます．

今回DQNの細かい理論，アルゴリズムには触れませんでしたが，下のリンクはPythonとKeras，Tensorflowを用いてDQNの実装例があるので，このような記事を参考にすると良いと思います．

DQNをKerasとTensorFlowとOpenAI Gymで実装する

OpenAI Gym を動かしてみた

OpenAI Gym

OpenAI Gymとは，公式サイトにも"A toolkit for developing and comparing reinforcement learning algorithms.“とあるように，主に強化学習を開発，比較検討するのに使える環境が集まったサイトです．

gym.openai.com

まずは，チュートリアルを進めてみます．以下のサイトが公式のドキュメントになっています．

https://gym.openai.com/docs

上のサイトに従っていけばできますが，一応作業履歴ということでここに書いておきます． こちらのバージョンはPython3.5，anaconda3-4.0.0環境を使っています．

1. OpenGym AIのインストール

pip install gym が一番簡単でした．

2. 環境を動かしてみる

import gym

env = gym.make('CartPole-v0')

for episode in range(20):
    observation = env.reset()
    for t in range(100):
        env.render()
        print(observation)
        action = env.action_space.sample()
        observation, reward, done, info = env.step(action)
        if done:
            print("finished after {} timestamps".format(t+1))
            break

を実行すると，倒立振子が出てきて，20エピソード分実行され，描画されます．

3. Q学習で強化学習してみる

ここからは上のページにない内容ですが，せっかくなので強化学習を試してみます．

https://gym.openai.com/algorithms/alg_0eUHoAktRVWWM7ZoDBWQ9w

上に，どなたかが実装してくださったQ学習のコードが載っています． これをコピペして，Python3用に一部修正し（xrangeやprint）実行します． （私の環境ではenv.monitorがうまく動かなかったので（きちんと調査してはいませんが）env.monitor周りはコメントアウトして，その代わりに毎ループでenv.render()を実行しました．これにより倒立振子が学習されている様子を知ることができます）

うまく動くと，徐々にうまくなっていくことが確認できます．

4. 少し変更

先ほどコピペしたコードを，次を目標に一部変更します．

• 毎回の学習の様子をみる必要はないので，何回かに1回のみにする
• 学習の結果をみるテストメソッドを追加する（学習は行われず，greedyに行われる）

これを追加したコードが次になります．

gist.github.com

まとめ

気づいた点をまとめておきます．

• CartPole-v0は200フレームで強制的にdoneになる（うまくいっても行かなくても）
  • それ以上経ってからはactionの指示が効かない
• 連続空間でもQ学習は有効であることがわかった
  • 連続空間では状態数が多くなりがちなので，離散化が粗すぎても細かすぎても適していないイメージだったが，すんなりと学習できた（学習タスクにもよると考えられる）

今回はせっかくQ学習までやったので，次回は流行りのDQNを試してみたいと思います（と書いていますが実はもう試してあるのでそれをまとめる時間があれば…）

それと

今後，自身がどんなことをやっているきたかの日記としての活用を考えていて，新規性のないやってみたレポートが増えそうな気がしています． 新規性がありそうなものはQiitaにもアップしたいと思っています（がそんなに新規性のある記事がポンポン浮かぶわけでもない）

AnalogDiscovery2を使ってみた

はじめに

PC接続の全部入り計測器，AnalogDiscovery2を使ってみました．

購入はDigilentから行いました．学生だと学割でだいぶ安くなります．送料が5000円近くするのが難点ですが，2万5000円程度でした．

秋月よりかは安くなった．

store.digilentinc.com

akizukidenshi.com

中身はこちら。
学割+送料で
\17000 + \5000 = \22000くらい。 pic.twitter.com/mVSlUdnEUW

— tellusium (@tellusium) 2016年7月20日

ツイート見ればわかりますが，買ったのが2016/7なので，半年以上眠らせてたことになります（電子回路を扱う機会がなかったのだ…）

I2C信号を観測する

I2C通信を扱う機会があり，久しぶりの電子回路なのとAnalogDiscoveryの存在を思い出し，信号を観測してみることにしました．

細かい回路は省略で．

実際に通信がうまく行かない現象に遭遇し，その原因究明にも使えました．

（原因はArduino内部でのプルアップと外付けプルアップの両方使ってしまっていたことでした）

以下はアドレス0x04に0を送った後，4バイトのデータを受け取った時の信号です．はじめに0x04すなわち0b00001000が送られていることが確認できます．　

I2Cの波形を観測してみた
これでAddr=0x04に"0"を送った後，[73, 73, 173, 129]の4byteが通信されている pic.twitter.com/3KXBuLOgMP

— tellusium (@tellusium) 2017年2月27日

と書いたのですが，3つ目の173が怪しいですね…173 = 0x10101101なので，0が一つ足りないような．SCLも観測しておくべきだった…