構文指示翻訳 - 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 | 生成規則本文に意味動作を挿入 |
| マーカー非終端記号 | 中間動作を規則末尾に移動するための技法 |
構文指示翻訳はパーシング結果に意味を付与する核心技法です。次の記事では、これを活用して中間コードを生成する方法を扱います。
현재 단락 (1/210)
構文指示翻訳（Syntax-Directed Translation）は文法の各生成規則に**属性（attribute）**と**意味規則（semantic rule）**を付加して、解析と同時に翻訳...