コンパイラ設計-セマンティック分析

構文解析フェーズで、パーサーが構文解析ツリーを構築する方法を学びました。そのフェーズで構築されたプレーンな解析ツリーは、ツリーの評価方法に関する情報を持たないため、通常、コンパイラーには役に立ちません。言語の規則を作る文脈自由文法の生成は、それらをどのように解釈するかに対応していません。

例えば

E → E + T

上記のCFGプロダクションには、それに関連付けられたセマンティックルールがなく、プロダクションの意味を理解するのに役立ちません。

セマンティクス

言語のセマンティクスは、トークンや構文構造など、その構造に意味を提供します。セマンティクスは、記号、それらのタイプ、およびそれらの相互関係を解釈するのに役立ちます。セマンティック分析は、ソースプログラムで構築された構文構造が何らかの意味を引き出すかどうかを判断します。

CFG + semantic rules = Syntax Directed Definitions

例えば:

int a = “value”;

字句解析および構文解析フェーズでは、字句および構造的に正しいため、エラーを発行するべきではありませんが、割り当てのタイプが異なるため、意味エラーを生成する必要があります。これらのルールは、言語の文法によって設定され、セマンティック分析で評価されます。セマンティック分析では、次のタスクを実行する必要があります。

  • スコープ解決
  • 型チェック
  • 配列境界チェック

セマンティックエラー

セマンティックアナライザが認識すると予想されるセマンティックエラーのいくつかについて説明しました。

  • 型の不一致
  • 宣言されていない変数
  • 予約済みの識別子の誤用。
  • スコープ内の変数の複数の宣言。
  • スコープ外の変数へのアクセス。
  • 実際のパラメータと正式なパラメータの不一致。

属性文法

属性文法は、状況依存情報を提供するために、いくつかの追加情報(属性)が1つ以上の非終端記号に追加される特殊な形式の文脈自由文法です。各属性には、整数、浮動小数点数、文字、文字列、式など、明確に定義された値のドメインがあります。

属性文法は、文脈自由文法にセマンティクスを提供するための媒体であり、プログラミング言語の構文とセマンティクスを指定するのに役立ちます。属性文法(解析ツリーとして表示される場合)は、ツリーのノード間で値または情報を渡すことができます。

Example:

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から値を取得できます。

Expansion :文法規則に従って非終​​端記号が終端記号に展開される場合

Reduction:文法規則に従って、終端記号が対応する非終端記号に縮小された場合。構文木はトップダウンで左から右に解析されます。削減が発生するたびに、対応するセマンティックルール(アクション)を適用します。

セマンティック分析では、Syntax DirectedTranslationsを使用して上記のタスクを実行します。

セマンティックアナライザーは、前の段階(構文解析)からAST(抽象構文木)を受け取ります。

セマンティックアナライザーは、属性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属性でもあると結論付けることができます。