形式文法によるプログラム複雑度の特徴づけ
スポンサーリンク
概要
- 論文の詳細を見る
プログラムの複雑度の尺度として, Halstead尺度やMcCabe尺度があるが, ここではMcCabeのような制御の流れに関する尺度を考察する. McCabe尺度は, プログラムを制御フローグラフに抽象化したものを基礎にした尺度であるが, この抽象化の段階で失われる情報のために限界がある. 本稿で提案する方法では, プログラムを形式文法の形に抽象化し, その文法のChomsky階層の水準や, 非終端記号の数, 生成規則の数などによって, プログラムの複雑度を特徴づける. とくに, 再帰的な生成規則の数は, プログラム実行回数を制御するパラメータの数に相当し, プログラムの実行回数頻度統計(プロフィール)のパラメータ数にあたる複雑度の一つの指標である. 本稿では, ソーティング, パックトラッキング, およびリストのマーキングの例について, 流れ図の形のプログラム(アルゴリズム)から制御フローグラフを作り, 流れ図のフロー解析結果を反映させた形式文法を対応させるようすを示し, 提案している方法を具体的に設明する. またこれらの例を通して, この方法の現時点での限界を述べ, それらを克服するための見通しについて触れる.
- 一般社団法人情報処理学会の論文
- 1985-03-15
著者
関連論文
- ソフトウェア科学会第4回大会
- 自動改札機収集データによる旅客行動パターンの解明
- GUIを用いたL-systemエディタの開発
- GUIを用いたL-systemエディタの開発
- 翻訳検証テストのためのストリングリソースID(機械翻訳)
- いろいろな変種Quicksortアルゴリズムの比較について
- 構造的な抽象化機能を持つオブジェクト指向言語 : Ondineの概要
- ディジタル・ドキュメント作成支援環境の提案 : Collaborative Framing for Digital Journalism
- 情報処理専門教育について コンピュータリテラシー教育の一事例
- 実時間システム仕様記述法について
- パズルなどの組合せ問題を解く効率のよいプログラムを書くには
- Pascalプログラムに対する呼出数最小のモジュール宣言方法について
- 実時間並行プロセス仕様記述の一考察
- 特性多項式によるプログラム複雑度の特徴づけ
- 形式文法によるプログラム複雑度の特徴づけ
- ソフトウェア生産過程の評価実験に関する考察
- ARMの報告 (実験整数論)
- プログラミング言語とソフトウェア工学
- 長時間連続移動環境下でのバリアフリー施策の社会経済性評価と評価性能向上に資する新しいコミュニケイション手法の研究
- 全国規模の社会調査に基づく各種障碍者の長時間移動特性の研究
- 大都市圏在住の障碍者全般を対象にした長時間移動特性の研究
- 都市政府水準での対知的障碍者社会調査の展開状況と今後の方向性にかんする研究
- 東京圏在住下肢障碍者の地域内移動特性の研究
- HyperCampus: 物理的環境と連動した情報システムの個人化とその応用
- インホォスケープの世界-"知の風景"をめぐって-
- 三次元動画をもちいた電子新聞 (情報メディアの構造とサーチ)
- 20. 再帰呼出しの索表計算法 (アルゴリズムの最近の動向)
- 構造化プログラムにおける非決定性構文と新しいループ構造
- データベースを利用した列車情報案内システムの作成
- 自律分散型鉄道制御シミュレータの設計
- 四次元空間の可視化を支援するシステム : Julia-Mandelbrot空間の可視化
- パズルゲイム
- C++による仕様記述について
- オブジェクト指向言語Smalltalkによる仕様記述
- 京都賞受賞で来日されたD. E. Knuth先生について
- 輪送情報(乗車人員)の視覚化について
- マルチメディアを応用した経営情報システムのユーザ・インターフェースの改善について
- D.E.クヌース先生のコンピュータライフ
- 階層状体系をもつプログラミング言語の考察
- 組合せ論の証明とプログラミング : パリティ検査の一般化 (組合せ構造とグラフ理論)
- 都市間交通における交通機関選択要因の研究
- 日本の叙情歌
- 慶應義塾大学湘南藤沢キャンパスの授業評価
- リアルタイム制御の記述