トップダウン構文解析
トップダウン構文解析(トップダウンこうぶんかいせき、英: Top-down parsing)は、構文解析において、構文木を、最上位の非終端記号から始めて、それを順次右辺の記号列へと書き換えていくような手順によって導出する構文解析の戦略である。逆はボトムアップ構文解析。
一般に、コンパイラやインタプリタは、入力である、あるプログラミング言語で書かれたソースコードの文字列を、構文解析器を通して内部的な表現に変換する。以上はその文法を問わず、またトップダウン構文解析に限らない話である。
以下では対象のソース言語の文法が文脈自由文法であるとする。
トップダウン構文解析では、入力全体が、文脈自由文法の最上位の生成規則の左辺の非終端記号にマッチするはず、とまず仮定して構文解析を始める。そして、入力文字列に生成規則を適用していく際に、左端の記号からマッチングさせていき、非終端記号が出てくるたびにさらに生成規則を適用していく。このようにすると構文解析は生成規則の右辺の左端から開始され、左端から非終端記号を評価していくことになる。つまり、ある生成規則を適用してもその右辺の左端から順に評価していくため、途中で非終端記号が出てくるとさらに別の生成規則を適用する、という入れ子的動作をする。
例えば、次のような生成規則があるとする。
A → a B C {\displaystyle A\rightarrow aBC}