上昇型先読み計算による文脈自由言語の構文解析法
スポンサーリンク
概要
- 論文の詳細を見る
一般の文脈自由文法を比較的効率良く構文解析する方法にEarleyのアルゴリズムがある.このアルゴリズムは汎用的であり,あいまいな文法にも適用できるため,非常に多くの項目を数え上げてしまう.そのアルゴリズムに先読み情報を用いることで項目の数え上げの数を減らすことができる.しかし,各項目に先読みのためのフィールドを付加すると多くの記憶容量が必要になってしまう.そこで,本論文では,各項目に先読みのためのフィールドを用意せずに先読み情報を用いる文脈自由言語の構文解析法を提案する.この方法では,開始非終端記号の生成規則からトップダウン的に計算する従来の先読みの計算法を用いずに,必要なときのみ必要な項目から開始非終端記号の生成規則まで項目をたどりながらボトムアップ的に先読みを計算する.短い長さの先読み計算を導入するだけで,記憶容量を低減した構文解析が可能になる.
- 社団法人電子情報通信学会の論文
- 1995-11-25
著者
関連論文
- コンパイラ自動生成系によるAda構文検査系作成 (プログラミング言語 : PascalとAda)
- Webアプリケーションの静的意味検査法
- パイプ/フィルタアーキテクチャに基づくWebアプリケーション生成系PF-Webの設計と実装
- 属性値予測による1パス属性文法の評価法
- 入力列の上限付き個数情報を用いる構文解析法
- シリアルラインによるコンピュータ間通信
- 局所伝播法と方程式解法に基づく制約充足法
- 制約プログラミング言語Constraint Pascal
- 経路方式によるアルゴリズムアニメーション
- 高信頼マルチキャストのためのテーブル依存制御アルゴリズム
- 循環属性文法に基づく生成系Junについて
- 電子メイルを日本国内で容易に送受できる環境を実現し,研究者の意見交換を高速大量化する方法について
- PV 操作について
- 特集「日本のソフトウェアの草創期」の編集にあたって
- 大特集「アルゴリズムの最近の動向」の編集にあたって
- 83-3 日本の第5世代計算機プロジェクト
- 2. プログラミング言語に関する一般的参考文献 (プログラミング言語の最近の動向)
- 大特集「プログラミング言語の最近の動向」の編集にあたって
- Ada実現に関する問題点について : ACMコンパイラ作成会議より
- 新しいLL(k)パーサとその最小化問題の計算
- 77-20 プログラム言語の規格を形式的に定義する手法の現況
- 76-36 可変長命令方式による計算機デザイン
- 76-32 2レベルと3レベルの主記憶構成の比較
- 76-21 HOS : アポロ計画に部分的に用いられたソフトウェア仕様・検証システム
- Lewis-Stearnsアルゴリズムに基づくLL(k)パ-サの誤り検出の遅れについて(技術談話室)
- 75-35 階層構造システムの設計に透明性の概念を用いることについて
- セマンティックWebの悲観論と楽観論(セマンティックWebと計算機科学)
- 特集「セマンティックWebと計算機科学」の編集にあたって
- 変更容易なソフトウエア構成のためのアーキテクチャの選択法
- 通信型時間属性文法の形式的定義
- 上昇型先読み計算による文脈自由言語の構文解析法
- 構造エディタ生成系
- 属性文法を効率的な動作ルーチンへ変換する方法について (プログラム合成/変換)
- 言語処理系の構成法
- 25. 分散型アルゴリズムの基礎 (アルゴリズムの最近の動向)
- 東日本大震災 危機発生時の対応について考える:14.放射線量測定・放射性物質拡散シミュレーション(独,仏,日本)
- 東日本大震災 危機発生時の対応について考える:11.地方自治体の危機対応と情報技術
- 東日本大震災 危機発生時の対応について考える:0.編集にあたって
- ケアプラン実施支援のための介護サービス割当手法
- ケアプラン実施支援システムCS Communityの開発 (2001年情報学シンポジウム講演論文集--21世紀の情報化社会・ネットビジネスを支える情報学/情報技術) -- (セッション3:応用システムの視点から)
- 仕様記述変換に基づく対話型ユーザインタフェース設計システム
- 仕様記述変換に基づく対話型ユーザインタフェース設計システム
- ユーザインタフェース設計における概念仕様記述の変換 : 因子化
- FORル-プの属性文法から動作ル-チンへの変換