Compiler-design-semantic-analysis
コンパイラ設計-セマンティック分析
構文解析フェーズでパーサーが構文解析ツリーを構築する方法を学びました。 そのフェーズで構築されたプレーンな解析ツリーは、ツリーを評価する方法の情報を保持していないため、一般にコンパイラーにとっては役に立ちません。 言語の規則を作る文脈自由文法の生成は、それらを解釈する方法に適応しません。
例えば
E → E + T
上記のCFGプロダクションには、関連するセマンティックルールがなく、プロダクションの意味を理解するのに役立ちません。
意味論
言語のセマンティクスは、トークンや構文構造など、その構造に意味を提供します。 セマンティクスは、シンボル、そのタイプ、および相互の関係を解釈するのに役立ちます。 意味解析は、ソースプログラムで構築された構文構造が意味を導き出すかどうかを判断します。
CFG + semantic rules = Syntax Directed Definitions
例えば:
int a = “value”;
字句的および構文解析段階では、字句的および構造的に正しいため、エラーを発行するべきではありませんが、割り当てのタイプが異なると意味的エラーを生成するはずです。 これらのルールは、言語の文法によって設定され、セマンティック分析で評価されます。 セマンティック分析では、次のタスクを実行する必要があります。
- スコープ解決
- 型チェック
- 配列バインドのチェック
- {ブランク}
セマンティックエラー
セマンティックアナライザーが認識することが期待されるセマンティクスエラーのいくつかに言及しました。
- 型の不一致
- 宣言されていない変数
- 予約済み識別子の誤用。
- スコープ内の変数の複数の宣言。
- スコープ外の変数へのアクセス。
- 実際のパラメータと正式なパラメータの不一致。
属性文法
属性文法は、コンテキストに依存しない情報を提供するために、いくつかの追加情報(属性)が非端末の1つ以上に追加される、コンテキストフリー文法の特別な形式です。 各属性には、整数、浮動小数点数、文字、文字列、式など、明確に定義された値のドメインがあります。
属性文法は、文脈自由文法に意味を提供する媒体であり、プログラミング言語の構文と意味を指定するのに役立ちます。 属性構文(解析ツリーとして表示される場合)は、ツリーのノード間で値または情報を渡すことができます。
例:
E → E + T { E.value = E.value + T.value }
CFGの右側には、文法の解釈方法を指定するセマンティックルールが含まれています。 ここでは、非端末EとTの値が加算され、結果が非端末Eにコピーされます。
セマンティック属性は、解析時にドメインから値に割り当てられ、割り当て時または条件時に評価されます。 属性が値を取得する方法に基づいて、属性は、合成属性と継承属性の2つのカテゴリに大きく分けることができます。
合成された属性
これらの属性は、子ノードの属性値から値を取得します。 説明のために、次の生産を想定します。
S → ABC
Sがその子ノード(A、B、C)から値を取得している場合、ABCの値はSに合成されるため、合成属性と呼ばれます。
前の例のように(E→E + T)、親ノードEはその子ノードから値を取得します。 合成された属性は、親ノードまたは兄弟ノードから値を取ることはありません。
継承された属性
合成された属性とは対照的に、継承された属性は、親や兄弟から値を取得できます。 次の生産のように、
S → ABC
AはS、B、Cから値を取得できます。 Bは、S、A、およびCから値を取得できます。 同様に、CはS、A、およびBから値を取ることができます。
拡張:文法規則に従って非端末が端末に展開される場合
縮小:文法規則に従って端末が対応する非端末に縮小されるとき。 構文ツリーは、トップダウンで左から右に解析されます。 削減が発生するたびに、対応するセマンティックルール(アクション)を適用します。
セマンティック分析では、構文指向翻訳を使用して上記のタスクを実行します。
セマンティックアナライザーは、その前の段階(構文解析)からAST(Abstract Syntax Tree)を受け取ります。
セマンティックアナライザーは、属性情報をASTに添付します。これは、属性付きASTと呼ばれます。
属性は、2つのタプル値、<属性名、属性値>です
例えば:
int value = 5;
<type, “integer”>
<presentvalue, “5”>
プロダクションごとに、セマンティックルールを添付します。
S属性SDT
SDTが合成属性のみを使用する場合、S属性SDTと呼ばれます。 これらの属性は、生成後にセマンティックアクションが記述されたS属性SDTを使用して評価されます(右側)。
上記のように、親ノードの値は子ノードの値に依存するため、S属性SDTの属性はボトムアップ解析で評価されます。
L属性SDT
この形式のSDTは、合成された属性と継承された属性の両方を使用し、適切な兄弟から値を取得しないという制限があります。
L属性SDTでは、非端末はその親、子、および兄弟ノードから値を取得できます。 次の生産のように
S → ABC
Sは、A、B、およびC(合成済み)から値を取得できます。 AはSからのみ値を取得できます。 BはSとAから値を取得できます。 Cは、S、A、およびBから値を取得できます。 非端末は、その右側の兄弟から値を取得できません。
L属性SDTの属性は、深さ優先および左から右への解析方法によって評価されます。
定義がS属性である場合、L属性定義がS属性定義を囲むため、定義もL属性であると結論付けることができます。