インクリメンタルな解析による空間解析器の高速化

概要

論文の詳細を見る
図式はある規則の基に描かれており,これを文法として定義することができる.この文法を,プログラミング言語の文法に対して図形文法と呼び,矩形や線などの基本図形要素がトークンとして扱われる.また,プログラミング言語と同様に,図形文法に基づいて図式を解析する空間解析器を作ることができる.これをインタラクテイブな図形処理システムに適用した場合,ユーザの入力に応じて,トークンが動的に追加・削除されることになる.空間解析器は,これに応じて解析をリアルタイムにやり直す必要が生じる.我々は,すでに提案されている,図形文法を与えることで空間解析器を利用できるシステムを改良し,この解析を高速に行うインクリメンタルな解析器を実現した.高速化のポイントは,解析時に探索するトークンの組合せ数を減少させることにある.我々は,組合せを求める際に,ルールの適用条件に間するグラフを利用した.これにより,ルールが適用できる組合せを効率的に求めることができる.また,前処理を行うことで効率的なグラフの探索を行うことができる.さらに,属性値に関するテーブルを用意することでさらなる高速化が可能であることを述べる.
一般社団法人情報処理学会の論文
2003-10-15