コンパイラ設計-解析の種類

構文解析器は、文脈自由文法によって定義された生成規則に従います。プロダクションルールの実装方法（派生）は、解析を2つのタイプ（トップダウン解析とボトムアップ解析）に分割します。

トップダウン解析

パーサーが開始シンボルから解析ツリーの構築を開始し、開始シンボルを入力に変換しようとする場合、トップダウン解析と呼ばれます。

再帰下降解析：トップダウン解析の一般的な形式です。再帰的プロシージャを使用して入力を処理するため、再帰的と呼ばれます。再帰降下解析は、バックトラックの影響を受けます。
バックトラッキング：プロダクションの派生が失敗した場合、構文アナライザーは同じプロダクションの異なるルールを使用してプロセスを再起動します。この手法では、入力文字列を複数回処理して、適切な製品を決定できます。

名前が示すように、ボトムアップ解析は入力シンボルから開始し、開始シンボルまで解析ツリーを構築しようとします。

入力文字列：a + b* c

生産ルール：

S → E
E → E + T
E → E *T
E → T
T → id

ボトムアップ解析を開始しましょう

a + b* c

入力を読み取り、入力と一致する生産があるかどうかを確認します。

a + b *c
T + b* c
E + b *c
E + T* c
E *c
E* T
E
S