プログラミング言語の場合
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/11/30 09:29 UTC 版)
「ボトムアップ構文解析」の記事における「プログラミング言語の場合」の解説
プログラミング言語のコンパイラにおけるボトムアップ構文解析は、最初に終端記号を識別し、それらを徐々に組み合わせていって非終端記号を生成する。この過程で人間の読めるソースコードで書かれたプログラムの構文木が構築され、そこからアセンブリ言語や擬似コードにコンパイルされる。 言語が異なれば構文解析技法も異なるが、実際に必要とされるより強力な構文解析技法を適用することも珍しくない。 ボトムアップ構文解析器による汎用構文解析器もあり、特定のプログラミング言語向けの構文解析器を生成するのに使われる(パーサジェネレータ)。例えば、yaccなどがある。
※この「プログラミング言語の場合」の解説は、「ボトムアップ構文解析」の解説の一部です。
「プログラミング言語の場合」を含む「ボトムアップ構文解析」の記事については、「ボトムアップ構文解析」の概要を参照ください。
プログラミング言語の場合
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/03/05 02:09 UTC 版)
「トップダウン構文解析」の記事における「プログラミング言語の場合」の解説
一般に、コンパイラやインタプリタは、入力である、あるプログラミング言語で書かれたソースコードの文字列を、構文解析器を通して内部的な表現に変換する。以上はその文法を問わず、またトップダウン構文解析に限らない話である。 以下では対象のソース言語の文法が文脈自由文法であるとする。 トップダウン構文解析では、入力全体が、文脈自由文法の最上位の生成規則の左辺の非終端記号にマッチするはず、とまず仮定して構文解析を始める。そして、入力文字列に生成規則を適用していく際に、左端の記号からマッチングさせていき、非終端記号が出てくるたびにさらに生成規則を適用していく。このようにすると構文解析は生成規則の右辺の左端から開始され、左端から非終端記号を評価していくことになる。つまり、ある生成規則を適用してもその右辺の左端から順に評価していくため、途中で非終端記号が出てくるとさらに別の生成規則を適用する、という入れ子的動作をする。 例えば、次のような生成規則があるとする。 A → a B C {\displaystyle A\rightarrow aBC} B → c | c d {\displaystyle B\rightarrow c|cd} C → d f | e g {\displaystyle C\rightarrow df|eg} A から開始するとした場合、最初に A → a B C {\displaystyle A\rightarrow aBC} にマッチし、次に(その右辺を左から評価していく過程で) B → c | c d {\displaystyle B\rightarrow c|cd} にマッチする。その後、 C → d f | e g {\displaystyle C\rightarrow df|eg} が適用される。ある非終端記号に関する生成規則の右辺の記号列群において、記号列の先頭に現れる終端記号により、唯一の記号列が決定可能であれば、LL(1) 文法で構文解析できる。ここで、(1) とは構文解析器が先読みする必要があるトークンの数を表している。終端記号ひとつで決定できない言語では、LL法を使って構文解析するには、1つ以上の先読みが必要となる。
※この「プログラミング言語の場合」の解説は、「トップダウン構文解析」の解説の一部です。
「プログラミング言語の場合」を含む「トップダウン構文解析」の記事については、「トップダウン構文解析」の概要を参照ください。
- プログラミング言語の場合のページへのリンク