2018年4月30日月曜日

操車場アルゴリズムの実装例[Python]

1. 概要

コンパイラを書いてみたいと思いつつも,構文解析すらわからない.
その手の本を開くと操車場アルゴリズムというものが書いてあったのでWikipediaをもとに実装してみた.
ついでに逆ポーランド記法の処理系と変数及び代入を実装し,対話形式で計算ができるようにした.


一応確認した限りではちゃんと動作しているのが,クリティカルなミスはない(と信じたい).

2. ソースコード

200行ちょいと,ブログに貼るのは少し長くなったのでGitHub Gistにあげた.


3. 感想とか

動作したところはこんなかんじ.
操車場アルゴリズムのWikipediaが割と詳しく書いてあったので良かった.実装時にそれ以外のリファレンスは特に見ていない.
このサイトにあるコードを写経したときはこんなに面倒なのかと思ったけど,これなら僕にも実装できそうだ(というかできた)のでよかった.

そういえば今年に入ってPython3に移行した.
WindowsでのPython2の開発環境の構築が無限に面倒だったので,またインストールするの嫌だなぁと渋っていたのですが,やってみたらすぐ終わってしまった.
とくにpipでnumpyとかが入るのはすごい.Python2だとまだ入らないのでは.
mapの返り値がイテレータなのはビビったけどなんとか使えそう.