正規表現を使わずに作る「最小の電卓（構文解析器 / Lexer & Parser）」――文字列が「木構造の計算」へと昇華するコンパイラの原点
1. 素朴な疑問：なぜコンピュータは 1 + 2 * 3 を 9 ではなく 7 と解けるのか？
プログラミングを始めたばかりの頃、誰もが何気なく書く計算式。
result = 1 + 2 * 3人間なら小学生でも「掛け算が先だから、2 × 3 = 6、それに 1 を足して答えは 7」と即答します。さらに (1 + 2) * 3 とカッコがつけば、「カッコの中が最優先だから、3 × 3 = 9」と柔軟に順序を入れ替えます。
しかし、コンピュータの視点に立ってみてください。 プログラムのソースコードとは、所詮**「ただの平文の文字列（1次元の文字の並び）」**に過ぎません。
['1', ' ', '+', ' ', '2', ' ', '*', ' ', '3']もしコンピュータがこの文字列を左から右へ愚直に1文字ずつ読み進めたら、何が起きるでしょうか？
まず 1 + 2 を計算して 3 になり、その 3 に * 3 を掛けて、「9」という間違った答えを出力してしまいます。
コンピュータに四則演算の優先順位を教え、カッコによる逆転を理解させ、平坦な文字列を「計算可能な立体構造（木構造）」へと組み替える技術。 それこそが、あらゆるプログラミング言語のコンパイラやインタプリタの心臓部である**「構文解析（Parsing）」**です。
今回は、便利な正規表現（re モジュール）や外部ライブラリを一切使わず、Pythonの素のループと再帰呼び出しだけで「四則演算とカッコを完璧に解く最小の電卓」をゼロから自作します。コンパイラ技術の最も美しく奥深い扉を開け放ちましょう。
2. コンパイラの2大関門：字句解析（Lexer）と構文解析（Parser）
プログラミング言語がテキストから意味を抽出するとき、必ず2つの独立したステップを踏みます。
なぜわざわざ2段階に分けるのでしょうか？ 「文字列を読みながら同時に計算ツリーを組む」と、コードの中に「空白文字の読み飛ばし」「2桁以上の数字の合成」「文法チェック」が雑多に入り乱れ、認知負荷でスパゲッティコードが爆発するからです。
① 字句解析（Lexer / Tokenizer）：文字を「単語」にスライスする
Lexerの役割はシンプルです。文字列を1文字ずつ走査し、無駄なスペースを捨て、意味を持つ最小単位**「トークン（Token）」**のリストへと変換します。
例えば、'12' という文字列は '1' と '2' という文字の連続ですが、Lexerを通ることで「整数 12」という単一の数値トークンへとまとめ上げられます。
② 構文解析（Parser）：単語の列を「木」へと立体化する
Parserの役割は、一次元に並んだトークンの列を受け取り、演算子の優先順位やカッコの入れ子構造を解決しながら、**「抽象構文木（AST：Abstract Syntax Tree）」**と呼ばれる階層的なツリー構造へと組み上げることです。
木構造ができあがってしまえば、あとは「木の一番深い枝（葉）から順番に計算していく」だけで、どんなに複雑な数式も絶対に計算順序を間違えることなく解くことができます。
3. 文法規則の幾何学：BNF記法と「優先順位の階層化」
構文解析器を書く前に、最も重要な数学的設計図を作ります。 計算式の文法を厳密に定義する世界共通のフォーマット、**「BNF（Backus-Naur Form：バッカス・ナウア記法）」**です。
「掛け算（*, /）は、足し算（+, -）より優先される」
「カッコ ( ) の中は、掛け算よりもさらに優先される」
この優先順位のルールを、コードの if 文で力づくで書くのではなく、**文法の「階層（ネスト）」**として定義します。
【電卓の文法規則（BNF）】
式 (expr) ::= 項 (term) ( ('+' | '-') 項 (term) )*
項 (term) ::= 因子 (factor) ( ('*' | '/') 因子 (factor) )*
因子 (factor) ::= 数値 (NUMBER) | '(' 式 (expr) ')'この文法定義には、息を呑むほど美しいからくりがあります。
exprはtermを呼ぶ： 足し算を計算しようとすると、まずその材料として掛け算（term）を先に解決しに行かなければなりません。これにより、掛け算が足し算よりも深いノードになり、先に計算されることが構造的に保証されます。termはfactorを呼ぶ： 掛け算を計算しようとすると、その材料として数値やカッコ（factor）を解決しに行きます。- カッコによる再帰のループ：
factorの中で(を見つけた瞬間、文法のトップであるexprを再帰的に呼び出します。 これによって、「カッコの中の式全体」が1つの独立した世界として最優先で評価され、その結果が1つの数値（factor）として親の掛け算へと還元されるのです。
この文法規則の関数をそのままコードに落とし込む手法を、**「再帰下降構文解析（Recursive Descent Parsing）」**と呼びます。
4. 完全実装：Pythonで作る最小の電卓
それでは、実装に入りましょう。
正規表現ライブラリ re も、外部パーサーライブラリも使いません。純粋なPythonの文字走査と関数再帰だけで実装します。
ファイル名を min_calc.py として保存してください。
# =====================================================================
# 1. トークンの定義と字句解析器（Lexer）
# =====================================================================
class TokenType:
NUMBER = "NUMBER"
PLUS = "PLUS"
MINUS = "MINUS"
MUL = "MUL"
DIV = "DIV"
LPAREN = "LPAREN"
RPAREN = "RPAREN"
EOF = "EOF"
class Token:
def __init__(self, type_: str, value=None):
self.type = type_
self.value = value
def __repr__(self):
return f"Token({self.type}, {repr(self.value)})"
class Lexer:
"""文字列を1文字ずつ走査し、トークン列へ分解する字句解析器"""
def __init__(self, text: str):
self.text = text
self.pos = 0 # 現在走査している文字インデックス
self.current_char = self.text[0] if len(text) > 0 else None
def advance(self):
"""カーソルを1文字進める"""
self.pos += 1
if self.pos < len(self.text):
self.current_char = self.text[self.pos]
else:
self.current_char = None
def skip_whitespace(self):
"""空白文字を読み飛ばす"""
while self.current_char is not None and self.current_char.isspace():
self.advance()
def number(self) -> int:
"""連続する数字を1つの整数値として組み立てる"""
digits = []
while self.current_char is not None and self.current_char.isdigit():
digits.append(self.current_char)
self.advance()
return int("".join(digits))
def get_next_token(self) -> Token:
"""次のトークンを1つ切り出す"""
while self.current_char is not None:
if self.current_char.isspace():
self.skip_whitespace()
continue
if self.current_char.isdigit():
return Token(TokenType.NUMBER, self.number())
if self.current_char == '+':
self.advance()
return Token(TokenType.PLUS, '+')
if self.current_char == '-':
self.advance()
return Token(TokenType.MINUS, '-')
if self.current_char == '*':
self.advance()
return Token(TokenType.MUL, '*')
if self.current_char == '/':
self.advance()
return Token(TokenType.DIV, '/')
if self.current_char == '(':
self.advance()
return Token(TokenType.LPAREN, '(')
if self.current_char == ')':
self.advance()
return Token(TokenType.RPAREN, ')')
raise SyntaxError(f"不正な文字を検知: '{self.current_char}' (位置: {self.pos})")
return Token(TokenType.EOF, None)
# =====================================================================
# 2. 抽象構文木（AST）ノードの定義
# =====================================================================
class ASTNode:
pass
class NumNode(ASTNode):
"""数値を表す葉ノード"""
def __init__(self, value: int):
self.value = value
def __repr__(self):
return f"{self.value}"
class BinOpNode(ASTNode):
"""二項演算（左辺 + 右辺）を表す節ノード"""
def __init__(self, left: ASTNode, op: str, right: ASTNode):
self.left = left
self.op = op
self.right = right
def __repr__(self):
return f"({self.left} {self.op} {self.right})"
# =====================================================================
# 3. 構文解析器（Parser：再帰下降パーサー）
# =====================================================================
class Parser:
"""文法規則（BNF）をそのままメソッドに落とし込んだ再帰下降パーサー"""
def __init__(self, lexer: Lexer):
self.lexer = lexer
self.current_token = self.lexer.get_next_token()
def eat(self, token_type: str):
"""期待するトークン型を確認して次のトークンへ進む"""
if self.current_token.type == token_type:
self.current_token = self.lexer.get_next_token()
else:
raise SyntaxError(f"予期しないトークン: 期待={token_type}, 実際={self.current_token.type}")
def factor(self) -> ASTNode:
"""factor ::= NUMBER | '(' expr ')'"""
token = self.current_token
if token.type == TokenType.NUMBER:
self.eat(TokenType.NUMBER)
return NumNode(token.value)
elif token.type == TokenType.LPAREN:
self.eat(TokenType.LPAREN)
# カッコの中身は、式（expr）として再帰的にパースする！
node = self.expr()
self.eat(TokenType.RPAREN)
return node
raise SyntaxError(f"構文エラー: 期待される数値またはカッコがありません ({token})")
def term(self) -> ASTNode:
"""term ::= factor ( ('*' | '/') factor )*"""
node = self.factor()
while self.current_token.type in (TokenType.MUL, TokenType.DIV):
token = self.current_token
if token.type == TokenType.MUL:
self.eat(TokenType.MUL)
elif token.type == TokenType.DIV:
self.eat(TokenType.DIV)
# 左結合で木を上に伸ばしていく
node = BinOpNode(left=node, op=token.value, right=self.factor())
return node
def expr(self) -> ASTNode:
"""expr ::= term ( ('+' | '-') term )*"""
node = self.term()
while self.current_token.type in (TokenType.PLUS, TokenType.MINUS):
token = self.current_token
if token.type == TokenType.PLUS:
self.eat(TokenType.PLUS)
elif token.type == TokenType.MINUS:
self.eat(TokenType.MINUS)
node = BinOpNode(left=node, op=token.value, right=self.term())
return node
def parse(self) -> ASTNode:
"""構文解析のエントリーポイント"""
tree = self.expr()
if self.current_token.type != TokenType.EOF:
raise SyntaxError(f"式が途中で終了していません: 残り={self.current_token}")
return tree
# =====================================================================
# 4. AST評価器（Evaluator）
# =====================================================================
def evaluate(node: ASTNode) -> int:
"""ASTを再帰的に巡回（深さ優先・後順走査）して計算結果を算出する"""
if isinstance(node, NumNode):
return node.value
elif isinstance(node, BinOpNode):
left_val = evaluate(node.left)
right_val = evaluate(node.right)
if node.op == '+':
return left_val + right_val
elif node.op == '-':
return left_val - right_val
elif node.op == '*':
return left_val * right_val
elif node.op == '/':
if right_val == 0:
raise ZeroDivisionError("0除算エラーが発生しました")
return left_val // right_val # 整数除算
raise ValueError(f"未知のASTノード: {type(node)}")
# =====================================================================
# 5. 実験と実行テスト
# =====================================================================
def calculate(expression: str):
print(f"\n入力された数式: '{expression}'")
# 1. 字句解析
lexer = Lexer(expression)
# 2. 構文解析（AST生成）
parser = Parser(lexer)
ast = parser.parse()
print(f"構築されたAST構造: {ast}")
# 3. 評価（計算）
ans = evaluate(ast)
print(f"計算結果: {ans}")
return ans
if __name__ == "__main__":
calculate("1 + 2 * 3") # 期待値: 7 (掛け算優先)
calculate("(1 + 2) * 3") # 期待値: 9 (カッコ優先)
calculate("100 - 5 * (4 + 6) / 2") # 期待値: 75 (複合式)5. 解剖と検証：1 + 2 * 3 が木を登りながら解かれる瞬間
このコードを実行すると、ターミナルには以下のように出力されます。
入力された数式: '1 + 2 * 3'
構築されたAST構造: (1 + (2 * 3))
計算結果: 7
入力された数式: '(1 + 2) * 3'
構築されたAST構造: ((1 + 2) * 3)
計算結果: 9
入力された数式: '100 - 5 * (4 + 6) / 2'
構築されたAST構造: (100 - ((5 * (4 + 6)) / 2))
計算結果: 75なぜ (1 + (2 * 3)) という木が自動生成されたのか？
1 + 2 * 3 をパースしたときの、関数の呼び出し軌跡（コールスタック）をスローモーションで追ってみましょう。
expr()が呼ばれ、すぐにterm()$\to$factor()と掘り下げて1を取得します。- 次のトークンが
+であるため、expr()は「よし、足し算ノードを作るぞ」と判断し、プラス記号の右側を解決するために2回目のterm()を呼びます。 - 2回目の
term()の中で2を取得した直後、トークンに*が現れます。 - ここで劇的な分岐が起きます。
*を処理する権限を持っているのはexpr()ではなくterm()の中のループです！ term()はexpr()に処理を戻さず、自分の内部で3を取得し、自力で(2 * 3)という掛け算ノードを組み立てます。- そして、完成した
(2 * 3)ノードを、親であるexpr()へと返します。 - 最後に
expr()が1と(2 * 3)をガッチャンコして、BinOpNode(1, '+', (2 * 3))を完成させます。
文法関数のネスト構造それ自体が、**「掛け算の演算子に出会ったら、足し算へ制御を戻さずに自分の中で吸い取ってしまう」**という物理的な重力場として機能しているのです。
触って試す：構文解析のステップ体験
🧮 構文解析のステップ体験
式を選んで「次のステップ」を押してください。① 字句解析（トークン化）→ ② 構文木（AST）の構築 → ③ 木をたどる評価、の3段階が順に進みます。掛け算が先に計算される理由が、木の形から見えてきます。
第1段階：字句解析（Lexer）― 文字列をトークンに切り分ける
第2段階：構文解析（Parser）― 抽象構文木（AST）を組み立てる
第3段階：評価（Evaluator）― 葉から根へ、計算を巻き上げる
式を選んだら、「次のステップ」を押してください。
6. 広がる世界：電卓からプログラミング言語の自作へ
「たかが電卓の四則演算を作っただけではないか」と思うかもしれません。 しかし、コンピュータサイエンスにおいて、この電卓パーサーが持つ意味は決定的に巨大です。
なぜなら、この電卓プログラムの骨格をほんの少し拡張するだけで、世界中のあらゆるデータ形式やプログラミング言語が自作できるからです。
- JSONパーサーへの拡張：
トークンに
{,},[,],:を追加し、expr()の代わりにparse_object()やparse_array()という関数を再帰的に呼び出すように改造すれば、json.loads()と全く同じ自作JSONパーサーが完成します。 - 自作プログラミング言語への拡張：
文法に
let x = 式（変数宣言）やif (式) { 処理 }（条件分岐）を追加し、ASTにAssignNodeやIfNodeを追加すれば、自分だけのスクリプト言語のインタプリタが完成します。 - 第1話の「CPUエミュレータ」との完全合体：
今回作った
evaluate(ast)の代わりに、ASTを巡回しながら第1話で自作した「仮想マシンの機械語（LOAD_IMM,ADDなど）」のバイト列を出力するように書き換えれば、**高級言語から機械語を生成する「完全な自作コンパイラ」**が手元で完成します。
私たちが普段使っているPythonも、JavaScriptのV8エンジンも、Rustのコンパイラも、すべてはこの再帰下降パーサーと同じ原理でコードの文字を読み、木構造へと変換することから旅を始めているのです。
7. まとめ：構文解析とは「1次元の文字列を多次元の知性へ編み直す技術」である
コンピュータにとって、ソースコードとは本来、何の区切りもない無機質な「バイトの川（1次元の配列）」に過ぎません。
そこから意味を汲み取り、知的なプログラムとして動かすために、人類は半世紀かけてこのエレガントなアルゴリズムを磨き上げました。
- 字句解析（Lexer）： 文字の海から余計なノイズを捨て、意味の単位であるトークンを抽出する。
- 優先順位の階層化（BNF）： 文法の深さによって演算子の強弱を表現し、カッコによる再帰呼び出しで順序を自在にひっくり返す。
- 抽象構文木（AST）： 文字列という平面を、親子関係を持った立体的な木へと昇華させ、ボトムアップに正しい順序で計算を実行する。
画面に打ち込まれた 1 + 2 * 3 という文字が、関数の再帰の波に乗って (1 + (2 * 3)) という美しい木へと組み上がり、鮮やかに 7 という答えを導き出す。
この仕組みを自分の手で一行ずつ書き上げた瞬間、あなたはもう「言語を使う側のプログラマー」から、「言語を創り出す側のエンジニア」へと、不可逆な一歩を踏み出しているのです。
📝 3行で頭に入る『試験・実務の要点まとめ』
- LexerとParserの分業： 文字列を単語（トークン）に切り分ける「字句解析」と、トークン列を文法規則に従って木構造（AST）に組む「構文解析」の2段階に分離することで設計の破綻を防ぐ。
- BNFと優先順位の必然： 優先度の高い演算子（
*,/）ほど文法階層の深い位置に配置することで、再帰下降パーサーが木の下位ノードとして先に評価する構造を自然に実現できる。 - ASTの評価原理： 木構造の葉（末端の数値）から親ノードへと深さ優先（ポストオーダー）で再帰的に計算を巻き上げていくため、カッコの入れ子や複雑な四則演算も狂いなく解くことができる。