Loading article…
コンピュータサイエンスでは、構文解析は線形入力テキストの文法構造を明らかにし、その意味を解明する第一歩となります。 ボトムアップ構文解析では、まずテキストの最下位レベルの細かい部分を認識し、次に中間レベルの構造を認識し、最後に最上位レベルの全体構造を認識します。[ 1 ]
ボトムアップという名前は、構文解析ツリーの概念に由来します。構文解析ツリーでは、最も詳細な部分が逆さまのツリーの一番下にあり、それらから構成されるより大きな構造が、ツリーの最上部または「ルート」で単一のユニットが入力ストリーム全体を記述するまで、順次高い階層に配置されます。ボトムアップ構文解析は、左下の端から開始してそのツリーを発見して処理し、段階的に上方向と右方向に進んでいきます。[ 2 ]パーサーは、実際のデータツリーを作成することなく、構造階層の低レベル、中間レベル、および最高レベルに作用することができます。この場合、ツリーはパーサーの動作に暗黙的に含まれているだけです。ボトムアップ構文解析は、結合された構造が何であるかを確定する前に、何らかの構造のすべての部分をスキャンして解析するまで辛抱強く待ちます。
これとは反対に、トップダウン構文解析では、まず入力の全体構造が決定（または推測）され、中間レベルの部分が処理され、最下層の詳細の完了は最後に行われます。トップダウン構文解析器は、階層ツリーを上から発見して処理し、まず下へ、次に右へと段階的に処理を進めます。トップダウン構文解析では、構成要素の左端のシンボルをスキャンしただけで、まだ構成要素を解析していない段階で、構成要素が何であるかを早急に決定します。 左隅構文解析は、各サブツリーの左端に沿って下から上へ、残りの構文解析ツリーでは上から下へと処理するハイブリッド方式です。
言語文法に、同じ左端の記号で始まるものの末尾が異なる複数の規則がある場合、その文法は決定論的なボトムアップ構文解析によって効率的に処理できますが、トップダウン構文解析では推測やバックトラッキングなしには処理できません。そのため、実際にはボトムアップ構文解析器は、決定論的なトップダウン構文解析器よりも、やや幅広い種類のコンピュータ言語文法を処理できます。
ボトムアップ構文解析は、バックトラッキングによって行われる場合もあります。しかし、より一般的には、LALRパーサーなどのシフトリデュースパーサーによって行われます。
ボトムアップ構文解析を使用するパーサーには、以下のようなものがあります。