属性文法の高速循環性検査アルゴリズム

• Item type: Journal(1)
• 公開日: 1987-02-15
• タイトル: 属性文法の高速循環性検査アルゴリズム
• タイトル / 言語: en
• タイトル: Some Fast Algorithms for Testing Circularity of Attribute Grammars
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 基礎理論
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Engineering, Gunma University
• 著者名: 小池, 博; 五十嵐, 善英; 佐渡, 一広
• 著者名(英): Hiroshi, Koike; Yoshihide, Igarashi; Kazuhiro, Sado
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 属性文法の循環性検査の時間計算量は 本質的に文法の大きさの指数時間であることが知られている.この換査アルゴリズムは 最初Knuthによって与えられたが その後 Chebotar Raiha Deransartらによって効率の改善が行われた.本論文では 属性文法の構文解析木に対する依存グラフの性質を調べ 計算時間をさらに短縮した循環性検査アルゴリズムについて述べる.我々のアルゴリズムでは 生成規則に意味規則から得られる情報を付加し 循環性検査に不必要な情報を取り除く前処理を行っている.このことにより主検査の実行時間はかなり短縮される.幾つかの属性文法の記述例について 我々のアルゴリズムとすでに知られている循環性検査アルゴリズムの効率の比較を計算機によって行った.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 28, 号 2, p. 131-138, 発行日 1987-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764