algoNote

プログラミング関連の記録

ターミナルエミュレータを自作してみた記録

以前からターミナルエミュレータを作ってみたいなと思っていたのですが、ついに手を着けました。

実際に作ってみると、それっぽく動く段階までの実装はそこまで大変ではないことが分かりました。 実用出来るレベルまで持っていくのはかなり大変だと思います……

今回作ったものは、クリップボードをサポートしていなかったり、画面サイズの動的な変更に対応していなかったりと実用上は不便ですが、 「ターミナルエミュレータを作ってみたい」という興味は満たすことができました。

github.com

続きを読む

正規表現に入門した

本を読んだ

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

以前から読みたかった「正規表現技術入門 最新エンジン実装と論理的背景」という本を読みました。 説明が分かりやすくとても良い本でした。自分の知らないことがたくさん書かれている本は読んでいて楽しいです。

正規表現を高度に使いこなすテクニックの本というより、正規表現エンジンの仕組みに興味がある人向けの本だと思います。 僕も正規表現エンジンの仕組みが知りたくてこの本を読みました。

この本には、

といったことが書かれています。

実際に正規表現エンジンの仕組みを知ってしまうと、(最適化などを無視すれば)基本的な動作原理はとてもシンプルなんだなと感じました。

逆に、実用的な正規表現エンジンは最適化をとんでもなく頑張っているということなんですよね。 あとマルチバイト文字の対応もかなり大変そうという気持になりました。

それから、Appendixで紹介されていた正規言語を代数的に扱うことの出来るsyntactic monoidの話がとても興味深かったです。 正規言語からsyntactic monoidを構成することができ、これによって正規言語の性質を判定したり、正規表現最適化問題を代数的な問題として扱うことが出来るようになるらしいです。 (例えば「ある正規表現*を含まない別の正規表現に書き換えることが出来るか」といったことが、syntactic monoid上のいくつかの等式が成り立つことを確認するだけで判定出来るらしい)

実装してみた

この本で2種類目のエンジンとして紹介されていたVM型のエンジンを実装してみました。

github.com

parser.rsでは再帰降下パーサによって正規表現構文解析し、compiler.rs構文木からVMの命令列に変換し、matcher.rsで文字列のマッチを実行するという形です。

とりあえず書いてみたという感じで、おそらくバグがありますし最適化は一切行っていません。

まとめ

かなりオススメの本です。正規表現に入門しましょう。


追記:おまけ

NFAを正規表現に変換するツールをC++で書きました

NFAを正規表現に変換するやつ · GitHub

ウィンドウシステム・ウィンドウマネージャを作った話

例によって大学の課題で作りました。

C言語である程度の規模のものを書くのは結構大変でしたが、 なんとか目標だったウィンドウマネージャの作成(とはいっても簡単なものですが)まで達成できました。

GitHubリポジトリ

github.com

続きを読む

Rustでシェルを作った

大学の課題でシェルを作ってみるというものがあり、言語は何でもよいということだったのでRustで実装しました。そのときの感想やら何やらを残しておこうと思います。

続きを読む

ブログに競プロのレーティングを表示するようにした(その2)

以前の記事でプログのサイドバーに競プロのレーティング(と色)を表示するjavascriptを紹介しました。 意外にも多くの方に使って頂けているようで嬉しいです。

algon-320.hatenablog.com

以前紹介したスクリプトではAtCoderのレーティング取得がYQLに依存していましたが、 残念ながらYQLは2019年1月でサービス終了してしまいました。 それに伴って、AtCoderのレーティング取得ができなくなっていました。

この問題に対応するために、簡易的なAPIサーバー的なもの(Kyopro-Ratingsと命名)を作成し、Heroku上で動かすことにしました。

デモ

続きを読む