Pythonで作る自作インタプリタ入門シリーズ
Part1【字句解析】 | Part2【構文解析】 | Part3【AST構築】 | Part4【評価器】 | Part5【スコープ】
はじめに
前回はソースコードをトークン列に変換した。
"let x = 1 + 2 * 3;"
→ [LET, IDENT("x"), EQ, NUMBER(1), PLUS, NUMBER(2), STAR, NUMBER(3), SEMICOLON]
でも、これだけじゃ計算できない。なぜなら...
「1 + 2 * 3 は 1 + 6 なのか 3 * 3 なのか」
この情報がない！
今回は、トークン列をAST（抽象構文木）に変換するパーサーを作る。
ASTとは
AST（Abstract Syntax Tree） = 抽象構文木
プログラムの構造を木で表現したもの。
例
1 + 2 * 3
これのASTは：
BinOp(+)
/ \
1 BinOp(*)
/ \
2 3
木構造にすると、下から上に計算すればいいことがわかる：
-
2 * 3= 6 -
1 + 6= 7
演算子の優先順位が木の深さで表現されてるんだ！
演算子の優先順位
プログラミング言語では、演算子に優先順位がある：
| 優先順位 | 演算子 | 説明 |
|---|---|---|
| 高 |
* / %
|
乗除 |
| ↓ |
+ -
|
加減 |
| ↓ |
< > <= >=
|
比較 |
| ↓ |
== !=
|
等値 |
| ↓ | && |
論理AND |
| 低 | ` |
なぜ優先順位が必要？
if a < b && c > d || e == f { ... }
これを正しくパースするには、優先順位を考慮してASTを作る必要がある。
ASTノードを設計する
Pythonの dataclass を使うと、ASTノードの定義がめちゃくちゃ楽。
式（Expression）
from dataclasses import dataclass
from typing import List, Optional, Union
@dataclass
class NumberLit:
"""数値リテラル"""
value: Union[int, float]
@dataclass
class StringLit:
"""文字列リテラル"""
value: str
@dataclass
class BoolLit:
"""ブールリテラル"""
value: bool
@dataclass
class Var:
"""変数参照"""
name: str
@dataclass
class BinOp:
"""二項演算"""
op: str
left: 'Expr'
right: 'Expr'
@dataclass
class UnaryOp:
"""単項演算"""
op: str
expr: 'Expr'
@dataclass
class Call:
"""関数呼び出し"""
name: str
args: List['Expr']
# 式の型
Expr = Union[NumberLit, StringLit, BoolLit, Var, BinOp, UnaryOp, Call]
@dataclass 神。__init__ も __repr__ も自動生成。
文（Statement）
@dataclass
class LetStmt:
"""変数宣言: let x = 10;"""
name: str
value: Expr
@dataclass
class AssignStmt:
"""代入文: x = 20;"""
name: str
value: Expr
@dataclass
class IfStmt:
"""if文"""
condition: Expr
then_body: List['Stmt']
else_body: Optional[List['Stmt']]
@dataclass
class WhileStmt:
"""while文"""
condition: Expr
body: List['Stmt']
@dataclass
class ReturnStmt:
"""return文"""
value: Optional[Expr]
@dataclass
class PrintStmt:
"""print文"""
value: Expr
@dataclass
class FnDef:
"""関数定義"""
name: str
params: List[str]
body: List['Stmt']
@dataclass
class Program:
"""プログラム全体"""
statements: List['Stmt']
再帰下降パーサー
再帰下降パーサー（Recursive Descent Parser）は、文法規則を再帰関数で表現するパーサー。
手書きで一番わかりやすい。
基本構造
class Parser:
"""再帰下降パーサー"""
def __init__(self, tokens: List[Token]):
self.tokens = tokens
self.pos = 0
def current(self) -> Token:
"""現在のトークン"""
if self.pos >= len(self.tokens):
return self.tokens[-1] # EOF
return self.tokens[self.pos]
def peek(self, offset: int = 1) -> Token:
"""先読み"""
pos = self.pos + offset
if pos >= len(self.tokens):
return self.tokens[-1]
return self.tokens[pos]
def advance(self) -> Token:
"""次のトークンに進む"""
token = self.current()
self.pos += 1
return token
def expect(self, token_type: TokenType) -> Token:
"""期待するトークンを消費"""
token = self.current()
if token.type != token_type:
raise SyntaxError(
f"Expected {token_type.name}, got {token.type.name} at line {token.line}"
)
return self.advance()
def match(self, *types: TokenType) -> bool:
"""現在のトークンが指定した型か"""
return self.current().type in types
式のパース（優先順位対応）
ここがポイント！優先順位が低い演算子からパースする。
def parse_expr(self) -> Expr:
"""式をパース（優先順位最低から）"""
return self.parse_or()
def parse_or(self) -> Expr:
"""|| をパース"""
left = self.parse_and()
while self.match(TokenType.OR):
self.advance()
right = self.parse_and()
left = BinOp("||", left, right)
return left
def parse_and(self) -> Expr:
"""&& をパース"""
left = self.parse_equality()
while self.match(TokenType.AND):
self.advance()
right = self.parse_equality()
left = BinOp("&&", left, right)
return left
def parse_equality(self) -> Expr:
"""== != をパース"""
left = self.parse_comparison()
while self.match(TokenType.EQEQ, TokenType.NOTEQ):
op = "==" if self.current().type == TokenType.EQEQ else "!="
self.advance()
right = self.parse_comparison()
left = BinOp(op, left, right)
return left
def parse_comparison(self) -> Expr:
"""< <= > >= をパース"""
left = self.parse_additive()
while self.match(TokenType.LT, TokenType.LTEQ, TokenType.GT, TokenType.GTEQ):
op_map = {
TokenType.LT: "<",
TokenType.LTEQ: "<=",
TokenType.GT: ">",
TokenType.GTEQ: ">=",
}
op = op_map[self.current().type]
self.advance()
right = self.parse_additive()
left = BinOp(op, left, right)
return left
def parse_additive(self) -> Expr:
"""+ - をパース"""
left = self.parse_multiplicative()
while self.match(TokenType.PLUS, TokenType.MINUS):
op = "+" if self.current().type == TokenType.PLUS else "-"
self.advance()
right = self.parse_multiplicative()
left = BinOp(op, left, right)
return left
def parse_multiplicative(self) -> Expr:
"""* / % をパース"""
left = self.parse_unary()
while self.match(TokenType.STAR, TokenType.SLASH, TokenType.PERCENT):
op_map = {
TokenType.STAR: "*",
TokenType.SLASH: "/",
TokenType.PERCENT: "%",
}
op = op_map[self.current().type]
self.advance()
right = self.parse_unary()
left = BinOp(op, left, right)
return left
各関数が「自分より優先順位が高い関数」を呼ぶ。これで優先順位が自然に実現される。
単項演算と基本式
def parse_unary(self) -> Expr:
"""単項演算子 - ! をパース"""
if self.match(TokenType.MINUS, TokenType.NOT):
op = "-" if self.current().type == TokenType.MINUS else "!"
self.advance()
expr = self.parse_unary() # 再帰！
return UnaryOp(op, expr)
return self.parse_primary()
def parse_primary(self) -> Expr:
"""基本式をパース"""
token = self.current()
# 数値
if token.type == TokenType.NUMBER:
self.advance()
return NumberLit(token.value)
# 文字列
if token.type == TokenType.STRING:
self.advance()
return StringLit(token.value)
# true/false
if token.type in (TokenType.TRUE, TokenType.FALSE):
self.advance()
return BoolLit(token.value)
# 括弧
if token.type == TokenType.LPAREN:
self.advance()
expr = self.parse_expr()
self.expect(TokenType.RPAREN)
return expr
# 識別子（変数参照 or 関数呼び出し）
if token.type == TokenType.IDENT:
name = token.value
self.advance()
# 関数呼び出し
if self.match(TokenType.LPAREN):
self.advance()
args = []
if not self.match(TokenType.RPAREN):
args.append(self.parse_expr())
while self.match(TokenType.COMMA):
self.advance()
args.append(self.parse_expr())
self.expect(TokenType.RPAREN)
return Call(name, args)
return Var(name)
raise SyntaxError(f"Unexpected token {token.type.name} at line {token.line}")
文のパース
def parse_stmt(self) -> Stmt:
"""文をパース"""
token = self.current()
if token.type == TokenType.LET:
return self.parse_let()
if token.type == TokenType.IF:
return self.parse_if()
if token.type == TokenType.WHILE:
return self.parse_while()
if token.type == TokenType.RETURN:
return self.parse_return()
if token.type == TokenType.PRINT:
return self.parse_print()
if token.type == TokenType.FN:
return self.parse_fn()
# 代入 or 式文
if token.type == TokenType.IDENT and self.peek().type == TokenType.EQ:
return self.parse_assign()
return self.parse_expr_stmt()
def parse_let(self) -> LetStmt:
"""let文をパース: let x = 10;"""
self.expect(TokenType.LET)
name = self.expect(TokenType.IDENT).value
self.expect(TokenType.EQ)
value = self.parse_expr()
self.expect(TokenType.SEMICOLON)
return LetStmt(name, value)
def parse_if(self) -> IfStmt:
"""if文をパース"""
self.expect(TokenType.IF)
condition = self.parse_expr()
self.expect(TokenType.LBRACE)
then_body = self.parse_block()
self.expect(TokenType.RBRACE)
else_body = None
if self.match(TokenType.ELSE):
self.advance()
self.expect(TokenType.LBRACE)
else_body = self.parse_block()
self.expect(TokenType.RBRACE)
return IfStmt(condition, then_body, else_body)
def parse_fn(self) -> FnDef:
"""関数定義をパース"""
self.expect(TokenType.FN)
name = self.expect(TokenType.IDENT).value
self.expect(TokenType.LPAREN)
params = []
if not self.match(TokenType.RPAREN):
params.append(self.expect(TokenType.IDENT).value)
while self.match(TokenType.COMMA):
self.advance()
params.append(self.expect(TokenType.IDENT).value)
self.expect(TokenType.RPAREN)
self.expect(TokenType.LBRACE)
body = self.parse_block()
self.expect(TokenType.RBRACE)
return FnDef(name, params, body)
動かしてみる
テストコード：
source = '''
let x = 10;
let y = 20;
fn add(a, b) {
return a + b;
}
if x > 5 {
print(add(x, y));
} else {
print(0);
}
while x > 0 {
print(x);
x = x - 1;
}
'''
lexer = Lexer(source)
tokens = lexer.tokenize()
parser = Parser(tokens)
ast = parser.parse_program()
print_ast(ast)
実行結果
=== AST ===
Program:
Let x =
Number(10)
Let y =
Number(20)
Function add(a, b):
Return:
BinOp(+):
Var(a)
Var(b)
If:
condition:
BinOp(>):
Var(x)
Number(5)
then:
Print:
Call add:
Var(x)
Var(y)
else:
Print:
Number(0)
While:
condition:
BinOp(>):
Var(x)
Number(0)
body:
Print:
Var(x)
Assign x =
BinOp(-):
Var(x)
Number(1)
完璧！トークン列がASTに変換された！
Pythonだと楽すぎる理由
-
dataclass: ASTノード定義が一瞬 -
Union型: 式や文の型を簡潔に表現 - 動的型付け: 型キャストなしでノード操作
-
matchいらない:ifで十分読みやすい
C++やRustだと、ノード定義だけで100行くらい書く羽目になる。Pythonは本当に楽。
まとめ
今回作ったもの：
- ASTノード（式と文）
- 再帰下降パーサー
- 演算子の優先順位対応
再帰下降パーサーは、文法規則がそのままコードになるのが最大の利点。
次回は、このASTを実際に評価するインタプリタを作る！
次回予告
Part3: AST構築、dataclassが神すぎる
ASTをさらに洗練させて、インタプリタの準備を整える！