Cコンパイラを自作してみる回です。今更Cコンパイラと言われるかもしれませんが、直接機械語を触れながら、かつネット上に参考文献が多数落ちているという観点で、今回は実装してみることにしました。
コンパイラの仕組みを理解することは、プログラミング言語がどのように動作しているのかを深く理解する上で非常に有益です。本記事では、最も基本的な四則演算をコンパイルできるコンパイラを、Pythonを使ってステップバイステップで実装していきます。
本記事の内容
- コンパイラの基本的な構成要素（字句解析・構文解析・コード生成）
- 四則演算の式を解析する再帰下降構文解析
- x86-64アセンブリへのコード生成とPythonでの実装
コンパイラの基本構成
コンパイラは大きく以下の3つのフェーズで動作します。
- 字句解析（Lexer / Tokenizer）: ソースコード文字列をトークンの列に分割する
- 構文解析（Parser）: トークン列を抽象構文木（AST）に変換する
- コード生成（Code Generator）: ASTからターゲットのアセンブリコードを生成する
例えば、3 + 5 * 2 という式は以下のように処理されます。
ソースコード: "3 + 5 * 2"
↓ 字句解析
トークン列: [NUM(3), PLUS, NUM(5), STAR, NUM(2)]
↓ 構文解析
AST: (+)
/ \
(3) (*)
/ \
(5) (2)
↓ コード生成
アセンブリ: x86-64命令列
字句解析の実装
字句解析器（Lexer）は、入力文字列をトークンの列に変換します。今回扱うトークンは、数値（NUM）、演算子（+, -, *, /）、括弧（(, )）です。
from enum import Enum, auto
from dataclasses import dataclass
from typing import List, Union
class TokenKind(Enum):
"""トークンの種類"""
NUM = auto()
PLUS = auto()
MINUS = auto()
STAR = auto()
SLASH = auto()
LPAREN = auto()
RPAREN = auto()
EOF = auto()
@dataclass
class Token:
"""トークン"""
kind: TokenKind
value: Union[int, None] = None
def tokenize(source: str) -> List[Token]:
"""ソースコードをトークン列に変換する"""
tokens = []
i = 0
while i < len(source):
c = source[i]
# 空白をスキップ
if c.isspace():
i += 1
continue
# 数値
if c.isdigit():
num_str = ""
while i < len(source) and source[i].isdigit():
num_str += source[i]
i += 1
tokens.append(Token(TokenKind.NUM, int(num_str)))
continue
# 演算子と括弧
op_map = {
'+': TokenKind.PLUS, '-': TokenKind.MINUS,
'*': TokenKind.STAR, '/': TokenKind.SLASH,
'(': TokenKind.LPAREN, ')': TokenKind.RPAREN,
}
if c in op_map:
tokens.append(Token(op_map[c]))
i += 1
continue
raise ValueError(f"不正な文字: {c}")
tokens.append(Token(TokenKind.EOF))
return tokens
tokenize 関数は入力文字列を1文字ずつ読み進め、対応するトークンを生成します。数値は複数桁にも対応しています。
構文解析の実装
構文解析では、トークン列を抽象構文木（AST）に変換します。四則演算の演算子優先順位を正しく扱うために、再帰下降構文解析（Recursive Descent Parsing）を用います。
扱う文法は以下のBNFで定義されます。
$$ \text{expr} \to \text{term} \; ((‘+’ \mid ‘-‘) \; \text{term})^* $$
$$ \text{term} \to \text{factor} \; ((‘*’ \mid ‘/’) \; \text{factor})^* $$
$$ \text{factor} \to \text{NUM} \mid ‘(‘ \; \text{expr} \; ‘)’ $$
この文法では、* と / は + と - より優先順位が高くなります。これは term が factor を先にまとめ、expr が term をまとめるという階層構造で実現されます。
@dataclass
class NumNode:
"""数値ノード"""
value: int
@dataclass
class BinOpNode:
"""二項演算ノード"""
op: str
left: Union['NumNode', 'BinOpNode']
right: Union['NumNode', 'BinOpNode']
class Parser:
"""再帰下降構文解析器"""
def __init__(self, tokens: List[Token]):
self.tokens = tokens
self.pos = 0
def current(self) -> Token:
return self.tokens[self.pos]
def consume(self, kind: TokenKind) -> Token:
"""期待するトークンを消費する"""
tok = self.current()
if tok.kind != kind:
raise ValueError(f"期待: {kind}, 実際: {tok.kind}")
self.pos += 1
return tok
def parse_expr(self):
"""expr = term (('+' | '-') term)*"""
node = self.parse_term()
while self.current().kind in (TokenKind.PLUS, TokenKind.MINUS):
op = '+' if self.current().kind == TokenKind.PLUS else '-'
self.pos += 1
right = self.parse_term()
node = BinOpNode(op, node, right)
return node
def parse_term(self):
"""term = factor (('*' | '/') factor)*"""
node = self.parse_factor()
while self.current().kind in (TokenKind.STAR, TokenKind.SLASH):
op = '*' if self.current().kind == TokenKind.STAR else '/'
self.pos += 1
right = self.parse_factor()
node = BinOpNode(op, node, right)
return node
def parse_factor(self):
"""factor = NUM | '(' expr ')'"""
tok = self.current()
if tok.kind == TokenKind.NUM:
self.pos += 1
return NumNode(tok.value)
if tok.kind == TokenKind.LPAREN:
self.pos += 1
node = self.parse_expr()
self.consume(TokenKind.RPAREN)
return node
raise ValueError(f"予期しないトークン: {tok}")
コード生成の実装
ASTを走査して、x86-64アセンブリを生成します。スタックマシン方式を採用し、計算結果をスタックに積み上げていく方法を用います。
x86-64の rax レジスタを主な計算用レジスタとし、中間結果をスタックにpushする戦略です。
class CodeGenerator:
"""x86-64アセンブリコード生成器"""
def __init__(self):
self.output = []
def emit(self, line: str):
"""アセンブリ命令を出力バッファに追加"""
self.output.append(line)
def generate(self, node) -> str:
"""ASTからアセンブリコードを生成"""
# アセンブリのヘッダ
self.emit(".intel_syntax noprefix")
self.emit(".globl main")
self.emit("main:")
# AST を再帰的に評価
self.gen_expr(node)
# rax に結果が入っている状態で return
self.emit(" ret")
return "\n".join(self.output)
def gen_expr(self, node):
"""ASTノードを再帰的にコード生成"""
if isinstance(node, NumNode):
self.emit(f" mov rax, {node.value}")
return
# 二項演算
# 左辺を評価してスタックに退避
self.gen_expr(node.left)
self.emit(" push rax")
# 右辺を評価（結果は rax）
self.gen_expr(node.right)
# 左辺をスタックから復元
self.emit(" pop rdi")
# 演算を実行
if node.op == '+':
self.emit(" add rax, rdi")
elif node.op == '-':
# rdi - rax (左辺 - 右辺)
self.emit(" sub rdi, rax")
self.emit(" mov rax, rdi")
elif node.op == '*':
self.emit(" imul rax, rdi")
elif node.op == '/':
# rdi / rax (左辺 / 右辺)
self.emit(" mov rcx, rax")
self.emit(" mov rax, rdi")
self.emit(" cqo")
self.emit(" idiv rcx")
全体を結合して実行
これまでの3つのフェーズを結合し、入力式からアセンブリコードを生成するコンパイラを完成させましょう。
def compile_expr(source: str) -> str:
"""式をコンパイルしてx86-64アセンブリを返す"""
tokens = tokenize(source)
parser = Parser(tokens)
ast = parser.parse_expr()
codegen = CodeGenerator()
return codegen.generate(ast)
# テスト
expressions = ["3 + 5 * 2", "(3 + 5) * 2", "100 / 4 - 10", "42"]
for expr in expressions:
print(f"=== {expr} ===")
asm = compile_expr(expr)
print(asm)
print()
実行すると、各式に対応するx86-64アセンブリが出力されます。例えば 3 + 5 * 2 の場合は以下のようになります。
=== 3 + 5 * 2 ===
.intel_syntax noprefix
.globl main
main:
mov rax, 3
push rax
mov rax, 5
push rax
mov rax, 2
pop rdi
imul rax, rdi
pop rdi
add rax, rdi
ret
5 * 2 が先に計算され（演算子の優先順位が正しく処理され）、その後に 3 と加算されていることがアセンブリからも確認できます。
ASTの可視化
構文解析の結果を可視化して、ASTの構造を確認してみましょう。
import matplotlib.pyplot as plt
import matplotlib.patches as patches
def ast_to_dict(node):
"""ASTを辞書形式に変換"""
if isinstance(node, NumNode):
return {"label": str(node.value), "children": []}
return {
"label": node.op,
"children": [ast_to_dict(node.left), ast_to_dict(node.right)]
}
def compute_positions(tree, x=0, y=0, dx=1.5, dy=1.2):
"""ノードの描画位置を計算"""
positions = []
positions.append((x, y, tree["label"]))
edges = []
children = tree["children"]
if len(children) == 2:
# 左の子
lx, ly = x - dx, y - dy
positions_l, edges_l = compute_positions(children[0], lx, ly, dx/2, dy)
positions += positions_l
edges += edges_l
edges.append((x, y, lx, ly))
# 右の子
rx, ry = x + dx, y - dy
positions_r, edges_r = compute_positions(children[1], rx, ry, dx/2, dy)
positions += positions_r
edges += edges_r
edges.append((x, y, rx, ry))
return positions, edges
# 式 "3 + 5 * 2" のASTを可視化
tokens = tokenize("3 + 5 * 2")
parser = Parser(tokens)
ast = parser.parse_expr()
tree = ast_to_dict(ast)
positions, edges = compute_positions(tree)
fig, ax = plt.subplots(figsize=(8, 5))
# エッジを描画
for x1, y1, x2, y2 in edges:
ax.plot([x1, x2], [y1, y2], 'k-', linewidth=1.5)
# ノードを描画
for x, y, label in positions:
circle = plt.Circle((x, y), 0.3, color='steelblue', ec='black', linewidth=1.5, zorder=5)
ax.add_patch(circle)
ax.text(x, y, label, ha='center', va='center', fontsize=14, color='white', fontweight='bold', zorder=6)
ax.set_xlim(-3, 3)
ax.set_ylim(-4, 1)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title("AST: 3 + 5 * 2", fontsize=14)
plt.tight_layout()
plt.show()
この可視化により、* が + より深い階層に配置され、先に評価されることが視覚的に確認できます。
まとめ
本記事では、Cコンパイラ自作の第一歩として、四則演算をコンパイルする仕組みを解説しました。
- 字句解析: ソースコード文字列をトークン列に分割する処理
- 構文解析: 再帰下降構文解析で演算子の優先順位を考慮したASTを構築
- コード生成: ASTを走査してスタックマシン方式のx86-64アセンブリを出力
コンパイラの基本的な3フェーズ（字句解析・構文解析・コード生成）の仕組みを理解することで、プログラミング言語がどのように機械語に変換されるかのイメージが掴めたかと思います。次のステップとしては、変数の導入やif文・ループ文のサポート、関数呼び出しなどを追加していくことで、より実用的なコンパイラへと発展させることができます。