あいまい性が強い文脈自由文法の枝刈りに基づく効率的な構文解析

• Item type: Trans(1)
• 公開日: 2006-10-15
• タイトル: あいまい性が強い文脈自由文法の枝刈りに基づく効率的な構文解析
• タイトル / 言語: en
• タイトル: An Efficient Parsing for Highly Ambiguous Context-free Grammars Based on Pruning
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 株式会社NEC航空宇宙システム
• 著者所属: 明治大学理工学部情報科学科
• 著者所属: 明治大学理工学部情報科学科
• 著者所属(英): en
• 著者所属(英): NEC Aerospace Systems, Ltd.
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Meiji University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Meiji University
• 著者名: 森本, 真一; 石畑, 清; 疋田, 輝雄
• 著者名(英): Shin-ichi, Morimoto; Kiyoshi, Ishihata; Teruo, Hikita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，強いあいまい性を持つ文脈自由文法に対しても効率的な構文解析アルゴリズムを示す．本アルゴリズムはデータ構造として，Tomitaら(1991)，Kipps (1991)，Nederhof (1993)と同様に，グラフ構造スタックを用いる．ここでのグラフ構造スタックは，項と入力列の組を頂点とし，各頂点から，解析木でいう親頂点に対応する頂点への辺（親ポインタ）を持つ有向グラフである．本アルゴリズムの特徴は，還元時に項の部分が同じ頂点への親ポインタを枝刈りすることである．枝刈りはすべての文脈自由文法に対して可能ではないが，あいまいさの強い文法の多くは枝刈り可能である．また枝刈りすることにより，すべての解析木を求めることはできなくなる．しかし同じ頂点からの親ポインタの指す頂点の項部分はすべて異なるので，各頂点からの親ポインタの個数は入力列の長さnに依存しない定数で抑えられる．これにより，枝刈りが可能な文脈自由文法に対する構文解析の時間計算量はO(n2)となる．本論文ではまず本アルゴリズムの定義を述べ，正当性すなわち入力列が文法の語であるかを正しく判定できることを示し，さらに時間計算量の解析を行う．本アルゴリズムの適用例として，Kippsによって与えられているあいまいさの強い典型的な文法（Kippsの構文解析法による時間計算量は O(n3)）に対して，本アルゴリズムではO(n2)であることを示す．最後に，本アルゴリズムで扱える枝刈り可能な文脈自由文法の範囲について，いくつかの文法例に基づく定性的な考察を行い，これらが十分に広い範囲を占めることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We introduce an efficient parsing algorithm even for highly ambiguous context-free grammars. It uses a graph-structured stack as those by Tomita (1991), Kipps (1991), and Nederhof (1993). Here, a graph-structured stack is a directed graph whose nodes are pairs of an item and an input string, and whose edges are pointers (parent pointers), each pointing to a parent node in the parse tree. Our new technique here is to prune the parent pointers pointing to the nodes having the same item part. By this pruning, we cannot obtain all parse trees, but we can reduce the size of the set of parent pointers to a constant, thus making the time complexity of this algorithm O(n2). In this paper we first define the algorithm and show its correctness, and then we analyze its time complexity. Then we show that by our parsing a class of typical highly ambiguous grammars given by Kipps (1991) that need O(n3) by his algorithm can be parsed in O(n2). Finally some study is made on the range of prunable grammars.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 47, 号 SIG16(PRO31), p. 66-85, 発行日 2006-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会