netail.net

_ [論文] 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 などがあるようです．使ったことありませんが……．

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

_ [読書] The Annotated Turing ▲

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

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

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

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

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

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

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

_ [近況] ICSE出張は禁止 ▲

うちの大学では，豚インフルエンザ感染者が発見された国，感染した疑いがある人がいる国への渡航は原則禁止になりました．渡航した場合は帰国後一週間は自宅待機となり，授業とかで大幅に支障が出るので，ちょっとICSEへの参加は無理そうです．今回の duty は ICPC のツールデモだけなので，渡航できなくても，私はそれほど被害はありませんが……．

他の大学でも似たような状況なんでしょうか．

_ [近況] 研究室移転 ▲

今日から３日間かけて，新しい建物へ移転します．メールサーバもネットワーク機器も電話も取り外すので，外部との連絡はほとんどできなくなります．

何か重要な連絡が必要なイベントが入ってるわけではないので（SIGSEとは日程が重なっていますが），あまり影響はないと信じています．

_ [近況] 締め切りはいつも Apia Time ▲

国際会議の締め切りは，日本から見ると-20時間の Apia Time で設定されることが多いのですが，３月２日締め切りの Proposal を，なぜか３日締め切りと自分のスケジュールに書いてたことが発覚しました．

とうとう脳内で Apia Time に自動変換されはじめたようです．日本国内での締め切りにも変換が働きそうなところが怖いです．

_ [近況] しめきり x4 ▲

修士論文x2の締切とSIGSE原稿x2の締切が同時だったので，暇なしの土日でした．月曜は修論発表会で１日かかりきりになってしまうので，学会関連のことは火曜から進み始めます．たぶん．

今回の知見: どんなに良い内容があっても，体裁や構成が崩れただけで文章が読めなくなる（頭が読むことを拒否する）．PDFとかでもらったテキストを切り貼りして構成を直しながら読むほうが，そのまま無理して読むよりも圧倒的に早い．

某先生曰く「論理展開は循環なしの有向グラフであり，論文はそれを直列化しただけのもの」なので，今回みたいに内容には問題がないのに構成が悪い場合は，グラフ構造で編集しつつ，いろいろな順序でセクションに並べて試し読みができるエディタとかあると便利だろうなーと思います．アウトラインエディタとかアイディアプロセッサとか，そういう分類になっているソフトウェアのカバー範囲だと思うのですが，まだ，これというものが見つかりません．