再帰的降下構文解析と予測構文解析の違いとは？分かりやすく解説!

再帰的降下構文解析と予測構文解析の主な違いは、再帰的降下構文解析はバックトラックを必要とする場合としない場合がありますが、予測構文解析はバックトラックを必要としない点です。

コンパイルプロセスにはいくつかの段階があります。

最初のフェーズは字句解析です。

これはソースコードを文字の流れとしてスキャンし、意味のある字句に変換するものです。

さらに、トークンの表現です。

次の段階は構文解析です。

トークンを入力とし、パースツリーを生成する。

構文解析とは、このプロセスのことを指す。

構文解析では、文脈自由文法で定義された生成規則を確認する。

より重要なのは、構文解析は生成規則に依存していることである。

パーシングの1つのタイプは、トップダウンパーシングです。

そして、この構文解析法は、ルートノードから構文木を作成し、リーフノードに漸次降りていく。

再帰的降下法とは？

再帰的降下構文解析は先頭から順に構文木を作成し、左から右へと入力を読み込んでいきます。

各終端エンティティ、非終端エンティティに対して手続きを使用します。

さらに、入力を再帰的に解析して解析木を作成する。

さらに、バックトラックが必要な場合と不要な場合があるが、関連する文法はバックトラックを避けることができない。

バックトラックとは、与えられた計算問題に対して、一部または全部の解を捕らえるアルゴリズムです。

構文解析や他の種類の論理型言語で使用される。

予測構文解析は、入力文字列を置き換えるためにどのようなプロダクションを使用するかを特定します。

バックトラックは行いません。

述語解析は先読みポインタを使用します。

このポインターは次の入力記号を指します。

バックトラックのないパーサーを実現するために、文法にいくつかの制約を設けています。

そのため、LL(k)文法と呼ばれる文法しか受け付けない。

再帰的降下構文解析は、相互に再帰的な手続きのセットから構築されるトップダウン構文解析の一種で、各手続きは文法の非終端の1つを実装しています。

一方、予測構文解析は、再帰的降下構文解析の一種であり、バックトラックを伴わないトップダウン構文解析アプローチの一種である。

このように、再帰的降下構文解析と予測構文解析の根本的な違いを説明している。

ここで、バックトラックの有無が再帰的降下構文解析と予測構文解析の主な違いです。

つまり、再帰的降下構文解析はバックトラックを必要とするかしないか、予測構文解析はバックトラックを必要としないかである。

また、再帰的降下構文解析では、すべての終端および非終端のエンティティに対して手続きを使用しますが、予測構文解析では、入力文字列を置き換えることによって使用するプロダクションを見つけます。

したがって、この点も再帰的降下構文解析と予測構文解析の違いと言える。

結論から言うと、トップダウン構文解析とは、構文木の最上位レベルで作業し、形式文法の書き換えルールを使って構文木を下降させていく構文解析の一種である。

再帰的降下構文解析と予測構文解析は、このような構文解析手法の一つです。