バックトラックのないマッチングオートマトンを用いたXML変換のためのアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
XML文書をヘッジとして扱い,ヘッジを対象とした書き換え系に基づく,XML変換のためのアルゴリズムの設計を行った.このアルゴリズムは,1)ヘッジ書き換え規則間の優先順位を考慮したヘッジ書き換え系をマッチングオートマトンに変換するアルゴリズム,2)オートマトンを効率良く運用するための書き換えアルゴリズムの2種類のアルゴリズムから成り立っている.1)のアルゴリズムは,Nedjaらによる項書き換え系からバックトラックを排除したマッチングオートマトンを生成する方法を拡張してヘッジ書き換え系のための,決定性マッチングオートマトンを生成するアルゴリズムである.ヘッジのパターン照合では,変数に代入できる列の長さがあらかじめ分からないため,バックトラックを排除するための新たな手法が必要となる.本発表では変数を含むパターンとヘッジとのパターンマッチングでバックトラックを排除するための手法について述べる.2)のアルゴリズムは,1)のアルゴリズムによって生成されるマッチングオートマトンを効率良く運用するための,適用戦略を基にした書き換えアルゴリズムである.適用戦略とは,Haskellらの関数型言語に用いられるのと同様な遅延評価型の戦略である.適用戦略を採用することで,遅延評価に基づいたXML変換が可能になる.
- 2010-09-22