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

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