入力列の上限付き個数情報を用いる構文解析法
スポンサーリンク
概要
- 論文の詳細を見る
通常の構文解析は順序をもった入力終端記号列に対して行われる.これに対し図形の構文解析, 例えばパラメータ付き文脈自由文法を用いて導出した図形が与えられて, その構成要素を列挙した列を構文解析する場合を考える.この場合, 列挙した列は必ずしも導出列の順番とは一致せず, 導出列の置換列となる.このため, 例えば右辺の各記号を置換した構文規則を追加した文法を用いても, 順序情報を利用する従来の方法では一般にはうまく構文解析できない.本論文では, 文脈自由文法の導出列の終端符号について順序情報が利用できない場合に, 個数ベクトルと呼ぶ, 残りの入力列の各終端記号の上限付き個数情報を用いて決定的に構文解析する方法を上昇型, 下降型の2種類について示す.上昇型では, 通常の構文解析と異なり, 還元動作のみならず, シフト動作も一意に決まる必要がある.また下降型では, 終端記号の照合位置を左端に限定する必要がないため, 通常の構文解析では扱えない左再帰型構文規則を扱える場合がある.以上、一定の条件下で, 個数ベクトルを用いて導出列の順番とは必ずしも一致しない入力列を一意に構文解析して, 対応する導出列に対する解析結果を得る方法を示す.
- 社団法人電子情報通信学会の論文
- 2001-04-01
著者
関連論文
- コンパイラ自動生成系によるAda構文検査系作成 (プログラミング言語 : PascalとAda)
- Webアプリケーションの静的意味検査法
- パイプ/フィルタアーキテクチャに基づくWebアプリケーション生成系PF-Webの設計と実装
- 属性値予測による1パス属性文法の評価法
- オブジェクト指向2002シンポジウム
- 入力列の上限付き個数情報を用いる構文解析法
- シリアルラインによるコンピュータ間通信
- 局所伝播法と方程式解法に基づく制約充足法
- 制約プログラミング言語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.編集にあたって