netail.net

_ [hyCalendar] Vista 用スケジュール表示ガジェット試作品 ▲

hyCalendar の「今日と翌日」スケジュールを表示するVista用のガジェットを試作してみました．２時間で作ったものなので，作りは粗いかもしれませんが，hyCalendar-gadget.zipとして公開しておきます．

このガジェットは，内部で hyCalendar のエクスポート機能を呼び出し，出てきたファイルを読み込んで表示するだけです．hyCalendar.exe のパスや表示したいファイルのパス情報だけでなく，Shell.Execute 実行が終了するまで500ミリ秒待つとかいった条件まで，色々とハードコーディングされてます．似たようなものを作ろうとしてる人には，コードも参考になるかもしれません．

_ [読書] The Annotated Turing ▲

電車通勤になって本を読むぐらいにしか使えない時間が増えたので，Charles Petzold のThe Annotated Turingという本を読んでました．面白かったので，紹介しときます．

文章はチューリング機械について述べられた Alan Turing の論文の文章に注釈や図を追加した形で構成されていて，さらに時代背景や様々な数学の成果との関連まで丁寧に説明しています．論文の展開に合わせて，ドキュメンタリーのように読める文章になってます．

チューリング機械が最初に登場した論文を扱っている都合上，数値などが計算可能（Computable）かどうか，Enumerableかどうかという話が中心です．授業でチューリング機械が登場する場面ではNP完全とかの概念も出てきそうですが，そのあたりについては取り扱っていません．

計算機におけるプログラミングとの関連などにも言及しているので，情報系の授業をある程度受けている人が，数学とのつながりなどの知識を楽しみつつ補強できる読み物という感じでした．

_ [論文] Island Grammar の作り方とか例とか ▲

ときどき論文の構文解析に関する記述で目にしていた Island Grammar の解説を探してたんですが，１本だけそれらしいのを見つけました： Leon Moonen: Generating Robust Parsers using Island Grammars. WCRE 2001, pp.13-22. [DOI]

Island Grammar の作り方とかが明示的に与えられているわけではなく，興味ある構文要素だけを取りだすように簡略化した文法の総称だったようです．Island Grammar の非形式的な定義としては，元となった文法で受理できる言語よりも広い言語を受理することがあるが，文法が単純化されたもの，となっているようです．興味のある場所を Island，そうでない場所を Water と呼びます．

構文エラーやヘッダファイルの不足，処理系の方言などの問題によって「正しくASTが作れない」状況や，そもそも特定の構文要素にしか興味がない状況において，ソースコードから情報を取り出したい場合に使うものらしいです．

文法の作り方としては，興味のある最小限の言語要素の並び順だけを処理する単純な Lexer ＆ Parser を作成する方法と，通常の文法をもとに興味のない場所をすべて Waterに置き換えていく方法があります．結局，どういう構文要素が，どんな順序で登場すべきか，というのを厳密に書き下す必要があります．

論文では，COBOL の Call Graph を抽出するために CALL 命令だけ取りだすという状況を最初の例に挙げていて，「CALL Id」「MOVE Id TO CALLEE（CALL HANDLER による呼び出し先を動的に決める命令）」は取り出すが「CALL HANDLER」やそれ以外の空白以外の記号などを Water とする，という文法を作ってます．Island Grammar の定義自体には文法をどのクラスで構成するかは制限なしのようですが，この著者はGeneralized LR (GLR) 文法の世界で定義を作っています．GLR 文法を処理できる parser generator には，Elkhound，DMS Software Reengineering Tools や Bison などがあるようです．使ったことありませんが……．

まじめな構文解析をさぼる分，興味のない部分の構文エラーを無視するようになります．ただし，本当は受理しないはずのソースを受理するので，目的に合致した範囲に収まってるかどうかは注意する必要もあるようです．