トップダウン設計とボトムアップ設計
構文解析におけるトップダウンとボトムアップという用語、ないしはトップダウン構文解析とボトムアップ構文解析は、設計戦略でもなければ、情報や知識の順序付け戦略でもない。そもそもソフトウェア工学での用語や用法とは全く関係なく、また「組織における意見流通の用語が原義で、行政学や経営学、特に経営学での意思決定論で、日米企業比較の主要な焦点という非常に重要な事項」など(当記事のノートを参照)とも無関係な、単に普通の英語の表現である「トップダウン」と「ボトムアップ」からの用語・用法である。すなわちこの記事の冒頭の定義がまともなものとするならば、この節はこの記事に書かれるべきではない。
句構造文法(生成文法)以外にも形式言語の文法の捉え方にはいくつかあるが、ここではそれらに議論を限定し、そのうちでも特にBNFで定義されている文脈自由文法のことを考える。BNFにおいて各ルールの左側の非終端記号を以下では「左辺の非終端記号」、右側の記号列を「右辺の記号列」と呼ぶ。
トップレベルの左辺の非終端記号(プログラミング言語の場合は〈プログラム〉、一般の言語では〈文〉などといった名前の非終端記号であることが多い)から右辺の記号列への展開の操作を繰り返し、最終的に入力と一致する終端記号の列が得られるならば解析成功とするのがトップダウン構文解析であり、入力の終端記号の列から始めて右辺の記号列から左辺の非終端記号への還元の操作を繰り返し、最終的にトップレベルの左辺の非終端記号が得られるならば解析成功とするのがボトムアップ構文解析である。
ソフトウェア開発工程では、トップダウン設計とボトムアップ設計は重要な意味をもつ。
トップダウン設計では、計画とシステムについての理解の完全性が重要となる。システムのある程度の部分の設計が十分な詳細さのレベルになるまでコーディングを開始することはできない。したがって、設計の大部分が完了するまで主要な機能のテストはできない。ボトムアップ設計では、モジュール単位の設計が完了した時点でコーディングとそのテストが開始できる。しかし、ボトムアップではモジュール間の関連が明確化されていないと後から設計変更が発生してしまう危険性があり、実際問題としてモジュール間の関連を最初から全て完璧に見通すことは困難である。ボトムアップ設計の利点の一つとして、コードの再利用性の高さが挙げられる。
トップダウン設計は、1970年代にIBMの研究者ハーラン・ミルズとニクラウス・ヴィルトが提案した。ミルズは構造化プログラミングを実用化し、1969年にニューヨーク・タイムズ紙の資料検索の自動化プロジェクトで実践して成果を上げた。