トップダウン構文解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』
トップダウン構文解析（英: Top-down parsing）とは、関係の不明なデータを解析するにあたって、仮説的な汎用構文木構造を使い、既知の基本構造がその仮説に適合するかどうかを調べる戦略である。自然言語とコンピュータ言語の解析に使われる。
[編集] プログラミング言語の場合
コンパイラは、入力された文字列をあるプログラミング言語からアセンブリ言語や内部的な表現に変換する。その際にバッカス・ナウア記法の生成規則と入力文字列のマッチングを行う。このときの構文解析としてトップダウン戦略を用いる手法としてLL法などがある。これは、入力文字列に生成規則を適用していく際に、左端の記号からマッチングさせていき、非終端記号が出てくるたびにさらに生成規則を適用していく。このようにすると構文解析は生成規則の右辺の左端から開始され、左端から非終端記号を評価していくことになる。つまり、ある生成規則を適用してもその右辺の左端から順に評価していくため、途中で非終端記号が出てくるとさらに別の生成規則を適用する、という入れ子的動作をする。
例えば、次のような生成規則があるとする。
A から開始するとした場合、最初に 
にマッチし、次に（その右辺を左から評価していく過程で）
にマッチする。その後、
が適用される。言語の曖昧さは様々である。曖昧さのない言語とは、ある非終端記号に関する生成規則の右辺がそれぞれ異なる文字列となっている（特に同じ記号で始まることがない）場合である。曖昧さのない言語は LL(1) 文法で構文解析できる。ここで、(1) とは構文解析器が一度に先読みするトークンの数を表している。曖昧な言語では、LL法を使って構文解析するには、1つ以上の先読みが必要となる。
