YAGLRアルゴリズムの実現と評価

• Item type: SIG Technical Reports(1)
• 公開日: 1991-11-15
• タイトル: YAGLRアルゴリズムの実現と評価
• タイトル / 言語: en
• タイトル: A Practical Realization of YAGLR Algorithm on Prolog Using Tree - Structure Stacks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学工学部
• 著者所属: 東京工業大学工学部
• 著者所属: 東京工業大学工学部
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Tokyo Institute of Technology
• 著者名: K.G.スレッシュ; 沼崎, 浩明; 田中, 穂積
• 著者名(英): K.G., Suresh; Hiroaki, Numazaki; Hozumi, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では，YAGLR法と呼ぶ新しい一般化LR法を提案する．YAGLR法に基づくパーザを計算機にインプリメントし，その性能を評価する．YAGLR法は，実際にグラフ構造化スタックを用いる．現在YAGLRアルゴリズムは，木構造化スタックを用いて重複計算を回避する．YAGLR法では，スタックのマージをトップ節点よりも深く進める．解析中に統語解析木は作らず，統語解析木を構成する部品（逆ドット項）を作成する．YAGLR法は，スタックのマージを深く進めることと，逆ドット項を作成することによって従来のパーサと比較して統語解析時間が高速になる．さらに，メモリ空間の圧縮も可能になる．YAGLRパーザは論理型言語Prologを用いて，計算機上に実現する．木構造化スタックが消費するメモリ空間は，Prologのshared?structureの機構によりスタックが消費するメモリ空間はグラフ構造化スタックと同じである．本論文では，YAGLR法のインプリメンデーションと実験による性能評価の結果を示す．また，実験結果に基づいて，YAGLRの解析時間がn^3のオーダであるという事実を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we describe an implementation and evaluation of our new generalized LR parsing algorithm called YAGLR. In our implementation we used tree-structure stack to realize YAGLR algorithm, whereas in its original version we use graph-structure stack. The merge operations of YAGLR proceeds deeper than top nodes effectively. Through reduce actions YAGLR creates items called drit which are symmetrically different from Earley's item. Through our implementation we show the advantages of creating drits instead of Barley's items. We also show through our implementation that, the parsing time of YAGLR is in the order of n^3, where n is the length of an input sentence. Because of our merge algorithm and due to the nature of shared-structure of Prolog, even though we use tree-structure stack, we retain the packed nature of GSS. This reduces the memory space used by YAGLR to a greater extent.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10115061
• 書誌情報: 情報処理学会研究報告自然言語処理（NL）; 巻 1991, 号 96(1991-NL-086), p. 1-8, 発行日 1991-11-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会