構文分析: コンパイラーのトップダウンおよびボトムアップの解析タイプ

コンパイラ設計プロセスにおける構文解析は、字句解析フェーズの後に行われます。これは、解析ツリーまたは構文ツリーとも呼ばれます。解析ツリーは、言語の事前定義された文法の助けを借りて開発されます。構文アナライザーは、指定されたプログラムが文脈自由文法によって暗示される規則を満たしているかどうかもチェックします。満たしている場合、パーサーはそのソース プログラムの解析ツリーを作成します。満たしていない場合は、エラー メッセージが表示されます。

なぜ構文アナライザーが必要なのでしょうか?

• コードが文法的に有効かどうかを確認する
• 構文アナライザーはコードにルールを適用するのに役立ちます
• 各開始中括弧に対応する終了中括弧があることを確認するのに役立ちます。
• 各宣言には型があり、その型が存在する必要があります。

構文アナライザーの重要な用語

構文解析プロセスで使用される重要な用語:

• 文： 文は、アルファベット上の文字のグループです。

• 語彙素: 語彙素は、言語の最低レベルの構文単位です (たとえば、total、start)。

• トークン： トークンは語彙素の単なるカテゴリです。

• キーワードと予約語 – ステートメントの構文の固定部分として使用される識別子です。 これは予約語であり、変数名または識別子として使用できません。

• ノイズワード – ノイズワードはオプションで、文の読みやすさを高めるためにステートメントに挿入されます。

• コメント – これはドキュメントの非常に重要な部分です。 ほとんどの場合、/* */、または//空白 (スペース) で表示されます。

• デリミタ – これは、何らかの構文単位の開始または終了をマークする構文要素です。 ステートメントや式、「開始」…「終了」、または {} と同様です。

• キャラクターセット – ASCII、Unicode

• 識別子 – 長さの制限により、文章の読みやすさが低下します。

• Operaトールシンボル – + と – は 2 つの基本的な算術演算を実行します。
• 言語の構文要素

なぜ解析が必要なのでしょうか?

解析では、入力文字列が整形式であるかどうかもチェックされ、整形式でない場合は拒否されます。

コンパイラ設計においてパーサーが実行する重要なタスクは次のとおりです。

• あらゆる種類の構文エラーの検出に役立ちます
• エラーが発生した位置を見つける
• エラーの明確かつ正確な説明。
• エラーから回復して続行し、コード内のさらなるエラーを見つけます。
• 「正しい」プログラムのコンパイルには影響しません。
• 解析では、構文エラーを報告することで無効なテキストを拒否する必要があります。

解析テクニック

解析手法は XNUMX つの異なるグループに分類されます。

• トップダウン解析、
• ボトムアップ解析

トップダウン解析

トップダウン解析では、解析ツリーの構築はルートから始まり、次に葉に向かって進みます。

トップダウン解析には次の XNUMX 種類があります。

1. 予測解析:

予測解析は、特定の入力文字列を置き換えるためにどのプロダクションを使用する必要があるかを予測できます。 予測パーサーは、次の入力シンボルを指す先読みポイントを使用します。 この解析手法では、バックトラッキングは問題になりません。 LL(1) パーサーとして知られています。

2. 再帰降下解析:

この解析手法では、入力を再帰的に解析して語句ツリーを作成します。 これは、文法の各非終端に XNUMX つずつ対応する、いくつかの小さな関数で構成されます。

ボトムアップ解析

コンパイラ設計におけるボトムアップ解析では、解析木の構築は葉から始まり、ルートに向かって処理されます。これはシフトリデュース解析とも呼ばれます。コンパイラ設計におけるこのタイプの解析は、いくつかの方法を使用して作成されます。 ソフトウェア·ツール.

エラー – 回復方法

システム ソフトウェアの解析時に発生する一般的なエラー

• 語彙: 間違って入力された識別子の名前
• 構文: アンバランスな括弧またはセミコロンの欠落
• 意味論的: 互換性のない値の割り当て
• 論理的: 無限ループでコードに到達できません

パーサーはプログラム内で見つかったエラーを検出して報告できなければなりません。したがって、エラーが発生するたびに、パーサーはそれを処理して残りの入力の解析を続行できる必要があります。プログラムは、さまざまなコンパイルプロセスの段階で次のタイプのエラーが発生する可能性があります。パーサーで実装できる一般的なエラー回復方法は5つあります。

ステートメントモードのリカバリ

• パーサーでエラーが発生した場合、修正手順を実行するのに役立ちます。 これにより、残りの入力と状態を先に解析できるようになります。
• たとえば、欠落しているセミコロンを追加することは、ステートメント モードの回復メソッドで行われます。 ただし、間違った修正を XNUMX つ行うと無限ループにつながる可能性があるため、解析設計者はこれらの変更を行う際に注意する必要があります。

パニックモードからの回復

• パーサーがエラーに遭遇した場合、このモードではステートメントの残りの部分は無視され、エラーのある入力からセミコロンなどの区切り文字までの入力は処理されません。これは単純なエラー回復方法です。
• このタイプの回復方法では、指定された同期トークンのグループが 1 つ見つかるまで、パーサーは入力シンボルを 1 つずつ拒否します。同期トークンは通常、またはなどの区切り文字を使用します。

フレーズレベルのリカバリ

• コンパイラはトークンを挿入または削除することでプログラムを修正します。 これにより、元の場所から解析を続行できるようになります。 残りの入力に対して補正を実行します。 残りの入力のプレフィックスを何らかの文字列に置き換えることができるため、パーサーがプロセスを続行するのに役立ちます。

エラープロダクション

• エラー生成回復は、エラーのある構造を生成する言語の文法を拡張します。次に、パーサーはその構造に関するエラー診断を実行します。

グローバル補正

• コンパイラは、不正な入力文字列を処理する際に、変更をできるだけ少なくする必要があります。不正な入力文字列 a と文法 c が与えられると、アルゴリズムは関連する文字列 b の解析ツリーを検索します。an を b に変換するために必要なトークンの挿入、削除、および変更は、できるだけ少なくする必要があります。

文法

文法は、言語を記述する一連の構造規則です。 文法はあらゆる文に構造を割り当てます。 この用語はこれらの規則の研究も指し、このファイルには形態論、音韻論、および構文が含まれます。 の構文の多くを記述することができます。 プログラミング言語.

形式文法の規則

• 非終端記号は、少なくとも XNUMX つのプロダクションの左側に表示される必要があります。
• ゴールシンボルは、いかなるプロダクションの::=の右側に表示されるべきではない。
• LHS が RHS に出現する場合、ルールは再帰的です。

表記規則

表記規則 シンボルは、要素を角括弧で囲むことで示されます。これは、要素を中括弧で囲み、その後にアスタリスク記号 { … }* を付けることで示すことができる、要素のインスタンスの任意のシーケンスです。

これは、単一のルール内でシンボルを使用できる代替手段の選択です。 必要に応じて括弧 ([,] ) で囲むこともできます。

終端記号と非終端記号の XNUMX 種類の表記規則領域

1.端末：

• a、b、c、などのアルファベットの小文字
• Opera+、-、* などの記号。
• 括弧、ハッシュ、カンマなどの句読点記号
• 0、1、…、9桁
• id や if など、単一の終端記号を表す太字の文字列

2.非端末:

• A、B、Cなどの大文字
• 小文字の斜体名: 式またはその一部

文脈自由文法

CFG は、その型の生成物を少なくとも XNUMX つ持つ左再帰文法です。 文脈自由文法のルールは主に再帰的です。 構文アナライザーは、特定のプログラムが文脈自由文法の規則をすべて満たしているかどうかをチェックします。 一致する場合、これらのルール構文アナライザーは、そのプログラムの解析ツリーを作成する可能性があります。

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

文法の導出

文法導出は、開始記号を文字列に変換する一連の文法規則です。 導出により、文字列が文法の言語に属していることが証明されます。

一番左の導出

入力の文形式がスキャンされ、左から右の順序で置き換えられる場合、それは左端の派生として知られます。 左端の導出により導出される文形式を左文形式と呼ぶ。

一番右の導出

右端の導出をスキャンし、右から左の順序で入力を生成ルールに置き換えます。 これは右端の派生として知られています。 右端の導出から導出される文形式は、右文形式として知られています。

構文と字句アナライザー

構文アナライザー	字句アナライザー
構文アナライザーは主に言語の再帰的な構造を処理します。	字句アナライザーは、構文アナライザーのタスクを容易にします。
構文アナライザーはソース プログラム内のトークンに作用して、プログラミング言語内の意味のある構造を認識します。	字句解析器は、ソース プログラム内のトークンを認識します。
字句解析器からトークンの形式で入力を受け取ります。	によって提供されるトークンの有効性を担当します。 構文アナライザー

構文アナライザーを使用するデメリット

• トークンが有効かどうかを判断することはありません
• トークンタイプに対して実行された操作が有効かどうかを判断するのに役立ちます
• トークンが使用される前に宣言および初期化されるかどうかを決定することはできません

まとめ

• 構文解析は、字句解析の後に行われるコンパイラ設計プロセスの第 XNUMX フェーズです。
• 構文アナライザーはコードにルールを適用するのに役立ちます
• 文、語彙素、トークン、キーワードと予約語、ノイズワード、コメント、区切り文字、文字セット、識別子は、コンパイラ構築における構文分析で使用される重要な用語です。
• 解析では、入力文字列が整形式であるかどうかをチェックし、整形式でない場合は拒否します。
• 解析手法は、トップダウン解析とボトムアップ解析の XNUMX つの異なるグループに分類されます。
• 語彙的、構文的、意味的、論理的なエラーは、メソッドの解析中に発生する一般的なエラーです
• 文法は言語を記述する一連の構造規則です
• 表記規則 記号は要素を角括弧で囲むことで示される。
• CFG は、次のタイプの生成物が少なくとも XNUMX つある左再帰文法です。
• 文法導出は、開始記号を文字列に変換する一連の文法規則です。
• 構文アナライザーは主に言語の再帰的な構造を処理しますが、字句アナライザーは構文アナライザーのタスクを容易にします。 DBMS
• 構文アナライザー方式の欠点は、トークンが有効かどうかを決して判断できないことです。