ボトムアップ構文解析

From Wikipedia, the free encyclopedia

ボトムアップ構文解析(ボトムアップこうぶんかいせき、: Bottom-up parsing)は、構文解析において、構文木を、木の葉に相当する終端記号の列から始めて、それを順次左辺の非終端記号へ書き換え、最終的に最上位の非終端記号(たとえば「文」)を得る、というような手順によって導出する構文解析の戦略である。逆はトップダウン構文解析

プログラミング言語コンパイラにおけるボトムアップ構文解析は、最初に終端記号を識別し、それらを徐々に組み合わせていって非終端記号を生成する。この過程で人間の読めるソースコードで書かれたプログラムの構文木が構築され、そこからアセンブリ言語擬似コードにコンパイルされる。

言語が異なれば構文解析技法も異なるが、実際に必要とされるより強力な構文解析技法を適用することも珍しくない。

ボトムアップ構文解析器による汎用構文解析器もあり、特定のプログラミング言語向けの構文解析器を生成するのに使われる(パーサジェネレータ)。例えば、yaccなどがある。

構文解析器を使った例

ボトムアップ構文解析器の種類

外部リンク

Related Articles

Wikiwand AI