- Authors
- Name
- Youngju Kim
- @fjvbn20031
簡単な構文指示翻訳器の構築
この記事では、コンパイラの核心原理を理解するために簡単な翻訳器を構築します。文法定義から始めて、構文木、構文指示翻訳の基礎を扱います。
1. 構文定義（Syntax Definition）
プログラミング言語の構文は**文脈自由文法（Context-Free Grammar, CFG）**で定義します。
文法の構成要素
文法は4つの要素で構成されます。
- 終端記号（Terminal）: トークンとも呼ばれ、言語の基本単位です（例:
+、*、id、num）。 - 非終端記号（Nonterminal）: 構文構造を表す変数です（例:
expr、stmt）。 - 生成規則（Production）: 非終端記号がどのように構成されるかを定義します。
- 開始記号（Start Symbol）: プログラム全体を表す非終端記号です。
文法の例: 算術式
expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> ( expr ) | num | id
この文法は加減算より乗除算の優先順位が高いことを表現しています。
2. 導出（Derivation）
導出とは、開始記号から出発して生成規則を繰り返し適用して文字列を生成する過程です。
例: 9 - 5 + 2 の導出
文法:
list -> list + digit | list - digit | digit
digit -> 0 | 1 | 2 | ... | 9
最左導出（Leftmost Derivation）:
list
=> list + digit
=> list - digit + digit
=> digit - digit + digit
=> 9 - digit + digit
=> 9 - 5 + digit
=> 9 - 5 + 2
導出の種類
- 最左導出（Leftmost Derivation）: 常に最も左の非終端記号を先に置換します。
- 最右導出（Rightmost Derivation）: 常に最も右の非終端記号を先に置換します。
3. 構文木（Parse Tree）
構文木は導出過程をツリー形式で表現したものです。
9 - 5 + 2 に対する構文木を見てみましょう。
list
/ | \
/ | \
list '+' digit
/ | \ |
/ | \ 2
list '-' digit
| |
digit 5
|
9
構文木の特徴は以下の通りです。
- ルート: 開始記号
- 内部ノード: 非終端記号（生成規則の適用）
- リーフノード: 終端記号（実際のトークン）
- リーフノードを左から右に読むと元の入力になります。
4. 曖昧性（Ambiguity）
一つの文字列に対して2つ以上の構文木が存在する場合、その文法は**曖昧（ambiguous）**であると言います。
曖昧な文法の例
string -> string + string | string - string | 0 | 1 | ... | 9
この文法で 9 - 5 + 2 を解析すると、2つの解釈が可能です。
解釈1: (9 - 5) + 2 = 6 解釈2: 9 - (5 + 2) = 2
string string
/ | \ / | \
/ | \ / | \
string + string string - string
/ | \ | | / | \
/ | \ 2 9 / | \
string - string string + string
| | | |
9 5 5 2
曖昧性の解消
曖昧性は**演算子優先順位（precedence）と結合法則（associativity）**を文法に反映して解消します。
// 曖昧な文法
expr -> expr + expr | expr * expr | num
// 曖昧性を解消した文法（乗算優先、左結合）
expr -> expr + term | term
term -> term * factor | factor
factor -> num
5. 演算子優先順位と結合法則
優先順位（Precedence）
文法の階層構造で表現します。低い優先順位の演算子がツリーのより高い位置に配置されます。
優先順位（低い -> 高い）:
|| (論理OR)
&& (論理AND)
== !=
< > <= >=
+ -
* / %
! - (単項)
結合法則（Associativity）
同じ優先順位の演算子が連続する場合にどの順序で結合するかを定義します。
左結合（Left-Associative）:
a - b - c = (a - b) - c
文法: expr -> expr - term | term
右結合（Right-Associative）:
a = b = c は a = (b = c)
文法: right -> letter = right | letter
ほとんどの二項演算子は左結合で、代入演算子（=）と累乗演算子（**）は右結合です。
6. 構文指示翻訳（Syntax-Directed Translation）の基礎
構文指示翻訳は文法の各生成規則に**意味動作（semantic action）**を付加して、解析と同時に翻訳を行う技法です。
属性（Attribute）
文法記号に関連付けられた値を属性と呼びます。属性には2種類あります。
- 合成属性（Synthesized Attribute）: 子ノードの属性から計算されます。
- 継承属性（Inherited Attribute）: 親や兄弟ノードの属性から計算されます。
構文指示定義（Syntax-Directed Definition）
各生成規則に**意味規則（semantic rule）**を連結します。
生成規則 意味規則
----------------------------------------------
expr -> expr1 + term expr.val = expr1.val + term.val
expr -> term expr.val = term.val
term -> num term.val = num.lexval
例えば、9 + 5 を評価すると次のようになります。
expr (val = 14)
/ | \
/ | \
expr + term (val = 9, val = 5)
| |
term num
| (5)
num
(9)
7. 後置記法（Postfix Notation）
後置記法（逆ポーランド記法）は演算子がオペランドの後に来る表現方式です。
中置記法（Infix） 後置記法（Postfix）
-------------------------------------------
9 - 5 + 2 9 5 - 2 +
9 - (5 + 2) 9 5 2 + -
a * b + c a b * c +
a + b * c a b c * +
後置記法の利点は以下の通りです。
- 括弧が不要: 演算順序が記法自体に埋め込まれています。
- スタックで簡単に評価できます。
後置記法の評価アルゴリズム
入力: 9 5 - 2 +
スタックの変化:
9を読む -> [9]
5を読む -> [9, 5]
-を読む -> [4] (9 - 5 = 4)
2を読む -> [4, 2]
+を読む -> [6] (4 + 2 = 6)
結果: 6
8. 中置から後置への翻訳の構文指示定義
中置式を後置式に翻訳する構文指示定義を書いてみましょう。
生成規則 意味動作
----------------------------------------------
expr -> expr1 + term print('+')
expr -> expr1 - term print('-')
expr -> term (なし)
term -> 0 print('0')
term -> 1 print('1')
...
term -> 9 print('9')
9 - 5 + 2 にこの翻訳体系を適用すると 9 5 - 2 + が出力されます。
9. 簡単な翻訳器の実装
再帰下降（recursive descent）方式で上記の翻訳器をJavaで実装してみましょう。
public class PostfixTranslator {
private String input;
private int pos;
private char lookahead;
public PostfixTranslator(String input) {
this.input = input;
this.pos = 0;
this.lookahead = input.charAt(0);
}
// expr -> term rest
// rest -> + term { print('+') } rest
// | - term { print('-') } rest
// | (epsilon)
void expr() {
term();
while (true) {
if (lookahead == '+') {
match('+');
term();
System.out.print('+');
} else if (lookahead == '-') {
match('-');
term();
System.out.print('-');
} else {
return;
}
}
}
// term -> 0 { print('0') } | 1 { print('1') } | ... | 9 { print('9') }
void term() {
if (Character.isDigit(lookahead)) {
System.out.print(lookahead);
match(lookahead);
} else {
throw new RuntimeException("Syntax error");
}
}
void match(char expected) {
if (lookahead == expected) {
pos++;
if (pos < input.length()) {
lookahead = input.charAt(pos);
} else {
lookahead = '\0'; // 入力の終わり
}
} else {
throw new RuntimeException("Expected " + expected);
}
}
public static void main(String[] args) {
PostfixTranslator translator = new PostfixTranslator("9-5+2");
translator.expr();
// 出力: 95-2+
}
}
実行フローの追跡
入力: 9-5+2
expr() 呼び出し
term() -> '9' 出力, lookahead = '-'
lookahead == '-':
match('-'), lookahead = '5'
term() -> '5' 出力, lookahead = '+'
'+' ではないので '-' 出力
lookahead == '+':
match('+'), lookahead = '2'
term() -> '2' 出力, lookahead = '\0'
'+' 出力
lookahead == '\0': return
最終出力: 95-2+
10. 抽象構文木（AST）の構築
翻訳器は後置記法の代わりに**抽象構文木（Abstract Syntax Tree, AST）**を生成することもできます。
ASTは構文木を簡素化したもので、不要な中間ノードを削除します。
構文木: AST:
expr +
/ | \ / \
expr + term - 2
/ | \ | / \
expr - term num:2 9 5
| |
term num:5
|
num:9
ASTノードの実装
abstract class ASTNode {
abstract int eval();
}
class NumNode extends ASTNode {
int value;
NumNode(int value) { this.value = value; }
int eval() { return value; }
}
class BinOpNode extends ASTNode {
char op;
ASTNode left, right;
BinOpNode(char op, ASTNode left, ASTNode right) {
this.op = op;
this.left = left;
this.right = right;
}
int eval() {
switch (op) {
case '+': return left.eval() + right.eval();
case '-': return left.eval() - right.eval();
case '*': return left.eval() * right.eval();
default: throw new RuntimeException("Unknown op: " + op);
}
}
}
まとめ
| 概念 | 核心内容 |
|---|---|
| 文脈自由文法 | 終端記号、非終端記号、生成規則、開始記号で構成 |
| 導出 | 開始記号から生成規則を適用して文字列を生成 |
| 構文木 | 導出過程のツリー表現 |
| 曖昧性 | 一つの文字列に2つ以上の構文木が存在 |
| 優先順位/結合法則 | 文法の階層と再帰方向で表現 |
| 構文指示翻訳 | 生成規則に意味動作を付加して翻訳 |
| 後置記法 | 演算子がオペランドの後に来る記法 |
| 合成属性 | 子ノードから計算される属性 |
この記事で構築した簡単な翻訳器はコンパイラの核心原理を示す縮小版です。次の記事では字句解析段階をより深く見ていきます。