Skip to content
Published on

[コンパイラ] 08. 構文指示翻訳 - SDDとSDT

🇰🇷KO🇺🇸EN🇯🇵JA
Split View
Authors

構文指示翻訳 - SDDとSDT

構文指示翻訳（Syntax-Directed Translation）は文法の各生成規則に**属性（attribute）と意味規則（semantic rule）**を付加して、解析と同時に翻訳を行う技法です。

1. 構文指示定義（SDD）の概要

**構文指示定義（Syntax-Directed Definition, SDD）**は文法に属性と意味規則を追加したものです。

属性の種類

  1. 合成属性（Synthesized Attribute）: 子ノードの属性値から下から上へ計算されます。
  2. 継承属性（Inherited Attribute）: 親や兄弟ノードの属性値から上から下へ計算されます。

合成属性の例: 算術式の評価

生成規則              意味規則
------------------------------------------------------
L -> E '\n'           L.val = E.val
E -> E1 + T           E.val = E1.val + T.val
E -> T                E.val = T.val
T -> T1 * F           T.val = T1.val * F.val
T -> F                T.val = F.val
F -> ( E )            F.val = E.val
F -> digit            F.val = digit.lexval

入力 3 * 5 + 4 に対する注釈付き構文木を見てみましょう。

              L (val = 19)
              |
           E (val = 19)
          / | \
    E(15)   +   T(4)
    |           |
  T(15)       F(4)
  / | \        |
T(3) * F(5)  digit(4)
|       |
F(3)  digit(5)
|
digit(3)

継承属性の例: 型宣言

生成規則              意味規則
------------------------------------------------------
D -> T L              L.inh = T.type
T -> int              T.type = integer
T -> float            T.type = float
L -> L1 , id          L1.inh = L.inh
                      addtype(id.entry, L.inh)
L -> id               addtype(id.entry, L.inh)

入力 float id1, id2, id3 に対する評価を見てみましょう。

       D
      / \
     T    L (inh = float)
     |   / | \
   float L  , id3  -> addtype(id3, float)
        / | \
       L  , id2    -> addtype(id2, float)
       |
      id1          -> addtype(id1, float)

L.inh 属性が親から子に伝播して全ての識別子に float 型を設定します。

2. 依存グラフ（Dependency Graph）

属性間の計算順序を決定するために依存グラフを構成します。

依存グラフの構成

  • 各属性インスタンスに対してノードを作成します。
  • 属性bの計算に属性aが必要な場合、aからbへ辺を追加します。
例: E -> E1 + T で E.val = E1.val + T.val

  E1.val ----+
              +--> E.val
  T.val  ----+

評価順序

依存グラフに**循環（cycle）**がなければ、**トポロジカルソート（topological sort）**を通じて属性を評価できます。

トポロジカルソートの結果（可能な評価順序）:
  digit(3).lexval -> F.val -> T.val ->
  digit(5).lexval -> F.val -> T1.val ->
  digit(4).lexval -> F.val -> T2.val ->
  E1.val -> E.val -> L.val

循環がある場合は属性を評価できず、これはSDDの設計エラーです。

3. S-属性定義とL-属性定義

S-属性定義（S-Attributed Definition）

合成属性のみを使用するSDDです。

特徴:
- 合成属性のみ使用
- 構文木の後順走査（post-order）で評価可能
- Bottom-Upパーシング（LRパーサ）と自然に結合

S-属性定義は最も単純で実装が容易です。LRパーサの還元動作時に意味規則を実行するだけです。

L-属性定義（L-Attributed Definition）

属性計算で左から右への順序が保証されるSDDです。

条件: A -> X1 X2 ... Xn で
  Xiの継承属性は以下にのみ依存可能:
  1. Aの継承属性
  2. X1, X2, ..., Xi-1の属性（Xiの左にある記号）
  3. Xi自身の属性（ただし循環がないこと）

L-属性定義の包含関係は以下の通りです。

S-属性定義 < L-属性定義

全てのS-属性定義はL-属性定義です。
L-属性定義はTop-DownパーシングとTop-Downパーシングと自然に結合します。

4. 構文指示翻訳スキーム（SDT）

**構文指示翻訳スキーム（Syntax-Directed Translation Scheme, SDT）は生成規則の本文の間に意味動作（semantic action）**を挿入したものです。

SDT表記

意味動作を中括弧で囲んで生成規則本文の中間に配置します。

// S-属性SDDをSDTに変換（動作が規則末尾に）
E -> E1 + T  { E.val = E1.val + T.val }
E -> T       { E.val = T.val }

// L-属性SDDをSDTに変換（動作が中間に）
D -> T { L.inh = T.type } L
T -> int  { T.type = integer }
T -> float { T.type = float }

5. Bottom-UpパーサでのSDT実装

LRパーサでS-属性定義を実装する方法です。

パーシングスタックに属性値を格納

パーシングスタック: 状態とともに属性値を格納

+------+------+------+------+------+------+
| s0   | s1   | s2   | s3   | s4   | s5   |
| -    | E    | +    | T    | *    | F    |
| -    | 15   | -    | 4    | -    | 2    |
+------+------+------+------+------+------+
         val          val          val

還元時の意味動作実行

規則: T -> T1 * F  { T.val = T1.val * F.val }

還元前のスタック:  ... | T(3) | * | F(5)
還元後のスタック:  ... | T(15)
  -> 計算: 3 * 5 = 15

Yaccでの実装

expr : expr '+' term   { $$ = $1 + $3; }
     | term            { $$ = $1; }
     ;

$$ は左辺の非終端記号の属性、$1、$2、$3 は右辺の記号の属性です。

6. Top-DownパーサでのSDT実装

再帰下降パーサでL-属性定義を実装する方法です。

継承属性はパラメータ、合成属性は戻り値

// D -> T L
// T.typeは合成属性、L.inhは継承属性
void D() {
    String type = T();    // Tの合成属性を戻り値として受け取る
    L(type);              // Lの継承属性をパラメータとして渡す
}

String T() {
    if (lookahead == INT) {
        match(INT);
        return "integer";
    } else if (lookahead == FLOAT) {
        match(FLOAT);
        return "float";
    }
    throw new SyntaxError("Expected type");
}

void L(String inheritedType) {
    if (lookahead == ID) {
        addType(currentToken, inheritedType);
        match(ID);
        if (lookahead == COMMA) {
            match(COMMA);
            L(inheritedType);  // 継承属性を渡す
        }
    }
}

7. SDTの活用例

7.1 中置から後置への変換

E -> T R
R -> + T { print('+') } R | - T { print('-') } R | epsilon
T -> num { print(num.val) }

入力 9 - 5 + 2 に対する動作を追跡します。

E -> T R
  T: print(9)     -> 出力: 9
  R -> - T R
    T: print(5)   -> 出力: 5
    print('-')     -> 出力: -
    R -> + T R
      T: print(2) -> 出力: 2
      print('+')   -> 出力: +
      R -> epsilon

最終出力: 9 5 - 2 +

7.2 配列型の生成

// 文法: int [2][3] のような配列型宣言の処理
B -> int                 { B.type = integer }
   | float               { B.type = float }

C -> [ num ] C1          { C.type = array(num.val, C1.type) }
   | epsilon             { C.type = B.type }

T -> B C                 { T.type = C.type }

int [2][3] に対する評価を見てみましょう。

B.type = integer
C -> [2] C1
  C1 -> [3] C2
    C2 -> epsilon
    C2.type = integer        (B.typeを継承)
  C1.type = array(3, integer)
C.type = array(2, array(3, integer))
T.type = array(2, array(3, integer))

8. マーカー非終端記号と動作変換

Bottom-Upパーサで中間動作を処理するには、動作を生成規則の末尾に移動する必要があります。このために**マーカー非終端記号（marker nonterminal）**を使用します。

マーカー非終端記号変換

// 元のSDT
B -> a { action1 } b { action2 }

// マーカー非終端記号を使用した変換
B -> a M b { action2 }
M -> epsilon { action1 }

マーカー非終端記号 M は空文字列に還元されながら action1 を実行します。

例: 型宣言でのマーカーの使用

// 元のSDT（L-属性）
D -> T { L.inh = T.type } L

// マーカー非終端記号変換
D -> T M L
M -> epsilon  { /* T.typeをスタックからコピーしてL.inhとして使用 */ }

9. 属性文法の応用

構文指示翻訳はコンパイラの様々な段階で活用されています。

適用分野

段階                    属性の活用
------------------------------------------------------
字句解析               トークンの属性値（整数値、文字列値）
構文解析               構文木/AST構成
型検査                 型属性の合成と検証
中間コード生成          3番地コードの合成
コード最適化            データフロー属性
コード生成             レジスタ割り当て、命令選択

型検査のSDD例

E -> E1 + E2   { E.type = if E1.type == integer and E2.type == integer
                          then integer
                          else if E1.type == float or E2.type == float
                          then float
                          else type_error }

E -> num       { E.type = integer }
E -> num.num   { E.type = float }
E -> id        { E.type = lookup(id.entry) }

10. 実装戦略のまとめ

どのSDD型を選ぶべきか？

+------------------+-------------------+--------------------+
| 特性              | S-属性定義         | L-属性定義          |
+------------------+-------------------+--------------------+
| 属性の種類        | 合成のみ          | 合成 + 継承          |
| 評価方向          | 下 -> 上          | 左 -> 右            |
| パーサの種類      | Bottom-Up (LR)   | Top-Down (LL)      |
| 実装の複雑さ      | 単純             | 中程度              |
| 表現力            | 制限的           | 豊富                |
+------------------+-------------------+--------------------+

実際のコンパイラのアプローチ

ほとんどの現代のコンパイラはパーシング段階でASTを構成し、その後ASTを複数回走査しながら属性を計算します。この方式はSDDの制約から自由でありながら体系的な実装が可能です。

第1段階: パーシング -> AST構成（合成属性を使用）
第2段階: AST走査 -> シンボルテーブル構築（継承属性を模倣）
第3段階: AST走査 -> 型検査
第4段階: AST走査 -> 中間コード生成

まとめ

概念核心内容
合成属性子から親へ伝播、下から上へ計算
継承属性親/兄弟から子へ伝播、上から下へ計算
依存グラフ属性間の計算順序を決定する有向グラフ
S-属性定義合成属性のみ使用、LRパーサと自然に結合
L-属性定義左から右への評価を保証、LLパーサと結合
SDT生成規則本文に意味動作を挿入
マーカー非終端記号中間動作を規則末尾に移動するための技法

構文指示翻訳はパーシング結果に意味を付与する核心技法です。次の記事では、これを活用して中間コードを生成する方法を扱います。

Discuss on Twitter • View on GitHub