あいまい性が強い文脈自由文法の枝刈りに基づく効率的な構文解析
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,強いあいまい性を持つ文脈自由文法に対しても効率的な構文解析アルゴリズムを示す.本アルゴリズムはデータ構造として,Tomitaら(1991),Kipps (1991),Nederhof(1993)と同様に,グラフ構造スタックを用いる.ここでのグラフ構造スタックは,項と入力列の組を頂点とし,各頂点から,解析木でいう親頂点に対応する頂点への辺(親ポインタ)を持つ有向グラフである.本アルゴリズムの特徴は,還元時に項の部分が同じ頂点への親ポインタを枝刈りすることである.枝刈りはすべての文脈自由文法に対して可能ではないが,あいまいさの強い文法の多くは枝刈り可能であ.また枝刈りすることにより,すべての解析木を求めることはできなくなる.しかし同じ頂点からの親ポインタの指す頂点の項部分はすべて異なるので,各頂点からの親ポインタの個数は入力列の長さnに依存しない定数で抑えられる.これにより,枝刈りが可能な文脈自由文法に対する構文解析の時間計算量はO(n^2)となる.本論文ではまず本アルゴリズムの定義を述べ,正当性すなわち入力列が文法の語であるかを正しく判定できることを示し,さらに時間計算量の解析を行う.本アルゴリズムの適用例として,Kippsによって与えられているあいまいさの強い典型的な文法(Kippsの構文解析法による時間計算量はO(n^3))に対して,本アルゴリズムではO(n^2)であることを示す.最後に,本アルゴリズムで扱える枝刈り可能な文脈自由文法の範囲について,いくつかの文法例に基づく定性的な考察を行い,これらが十分に広い範囲を占めることを示す.
- 一般社団法人情報処理学会の論文
- 2006-10-15
著者
関連論文
- 2. コンピュータ科学領域(J07-CS)(情報専門学科カリキュラム標準J07)
- IIOSSにおけるUMLモデルの振舞い解析
- トランプの1人遊び(プログラム・プロムナード)
- A Mapping System from Object-Z to C++
- データ列に関するアルゴリズムの逆変換に基づく導出
- メッセージ交換における優先度逆転とその対策
- 5.Ada-9X : 大規模ソフトウェア向きの手続き型言語 (<特集>プログラミング言語最新情報-II)
- M-096 実際的なページ操作の共有を実現したウェブブラウジング協調システム(ユビキタス・モバイルコンピューティング,一般論文)
- 3C-5 Webアプリケーションの汎用化のための中間表現の提案と実装(Web検索支援,一般セッション,データベースとメディア,情報処理学会創立50周年記念)
- 1C-2 OpenLaszloによるXHTMLからの柔軟なFlash生成システム(コンテンツ作成支援,一般セッション,データベースとメディア)
- デジタルデータ放送コンテンツのHTMLへの変換
- IIOSSにおけるUMLモデルのインタラクティブな動的検証
- Smalltalkにおけるリソースプログラミング
- データ列に対する各種アルゴリズムの逆変換に基づく統一的導出
- データ列に関するアルゴリズムの属性文法の逆変換に基づく導出
- データ列に関するアルゴリズムの属性文法の逆変換に基づく導出
- 枝刈り式構文解析法の効率化と自然言語解析への応用
- ぺた語義 : シラバスに基づく理工系情報学科のカリキュラム調査
- 中間表現とフレームワークを用いたWebアプリケーションのメンテナンス法の提案と評価
- あいまい性が強い文脈自由文法の枝刈りに基づく効率的な構文解析
- カリキュラムCC2001について(情報技術と教育)
- 4G-10 CORBA環境におけるミーティングスケジューリングシステムFlexMeet
- CORBA分散処理による会合日決定アルゴリズムと評価
- Program transformation of Ada tasks to Standard forms
- カテゴリー理論とプログラミング : カルテシアン閉カテゴリー (関数型プログラミングと計算の基礎)
- Variable SharingとMessage Sendingとの間のプログラム変換 (数理情報科学の研究)
- ICPC世界大会2007の問題(ACM国際大学対抗プログラミングコンテスト世界大会報告)
- 点の密集区域(プログラム・プロムナード)
- 多角形の面積の近似(プログラム・プロムナード)
- 円の集まりをロープで囲む(プログラム・プロムナード )
- プログラム・プロムナード : 嘘つき島の問題
- 倍数の和による整数の表現(プログラム・プロムナード)
- 点の集合を包含する球(プログラム・プロムナード)
- 複数の文字を含む区間の検索(プログラム・プロムナード)
- 問題の解決をさがす : 計算機による問題解決(さがす)
- 2.各界からみたDTP : ニーズの把握のために 2.5 著作者のためのDTPの一実例 (デスクトップパブリシング)
- カテゴリ理論による構文解析アルゴリズムの導出
- カテゴリ理論による構文解析アルゴリズムの導出
- 中間表現とフレームワークを用いたWebアプリケーションのメンテナンス法の提案と評価
- 一様遅れ演算の完全性 (クローン理論と離散数学・計算機科学をめぐる代数と論理)
- M-048 FlexアプリケーションのiOS環境でのHTML5変換による実行(作業支援ほか,M分野:ビキタス・モバイルコンピューティング)