1 + 2 * 3 を計算するプログラムを、文字列の左から順に処理して書くと 9 になります。正解は 7 です。
この「掛け算が先」という、誰でも知っているはずの規則をプログラムに教えるところで、言語処理系の話の8割が終わります。 変数も if も関数も、そのあとに足す部品にすぎません。
この記事は、四則演算の電卓から始めて、変数と if と while と関数が動く小さな言語まで、200行くらいで作る回です。正規表現エンジンを自作した回と同じで、「木にしてから辿る」という同じ形がまた出てきます。
対象レベル: 中級 / 区分: 必要に応じて読む
この記事でわかること
- 言語処理系が3つの部品(字句解析・構文解析・評価)でできていること
- 演算子の優先順位が、関数の呼び出しの深さで表せること(ここが山場)
- 式と文の違い。なぜ
ifは値を返さない言語が多いのか - 変数の有効範囲(スコープ)が、ただの親子関係であること
- インタプリタとコンパイラがどこまで同じで、どこから違うのか
この記事でやること
- まず、素朴に書いて
9という間違った答えを出す - 文字の列を「語」の列にする(字句解析)
- 語の列を木にする(構文解析・山場①)
- 木を辿って計算する(評価)
- 変数・
if・while・関数を足す(山場②) - エラーに行番号を付ける(山場③)
先に知る言葉
この記事で初めて出てくる言葉です。 詳しくは用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| 字句解析(トークナイズ) | 文字の列を「語」に切る。1+23 → 1 + 23 |
| 構文解析(パース) | 語の列を、意味のつながった木にする |
| AST | その木のこと。抽象構文木。ただの入れ子のオブジェクト |
| 再帰下降 | 文法の階層をそのまま関数の呼び出しにする書き方。手で書ける構文解析 |
| 環境 | 変数名 → 値の対応表。関数を呼ぶたびに新しく作る |
準備
mkdir -p ~/mylang
cd ~/mylang
node -v
v22.14.0
① まず、間違える
先に間違った答えを見ておきます。 ここを飛ばすと、このあとの面倒くささが何のためなのか分からなくなります。
cat > naive.js <<'EOF'
// 左から順に計算する(素朴だが間違い)
const src = "1 + 2 * 3";
const tokens = src.split(/\s+/);
let acc = Number(tokens[0]);
for (let i = 1; i < tokens.length; i += 2) {
const op = tokens[i], n = Number(tokens[i + 1]);
acc = op === "+" ? acc + n : op === "-" ? acc - n : op === "*" ? acc * n : acc / n;
}
console.log(acc);
EOF
node naive.js
9
9 です。 1 + 2 を先にやってしまっています。優先順位は「後回しにする仕組み」が無いと表現できません。
② 字句解析 —— 文字を語に切る
まず、文字の列を扱いやすい単位に切ります。ここは難しくありません。
cat > lexer.js <<'EOF'
export function tokenize(src) {
const tokens = [];
let i = 0, line = 1;
const KEYWORDS = new Set(["let", "if", "else", "while", "fn", "return", "print"]);
while (i < src.length) {
const c = src[i];
if (c === "\n") { line++; i++; continue; }
if (/\s/.test(c)) { i++; continue; }
if (c === "#") { while (i < src.length && src[i] !== "\n") i++; continue; }
if (/[0-9]/.test(c)) { // 数
let s = i;
while (i < src.length && /[0-9.]/.test(src[i])) i++;
tokens.push({ type: "num", value: Number(src.slice(s, i)), line });
continue;
}
if (/[A-Za-z_]/.test(c)) { // 名前かキーワード
let s = i;
while (i < src.length && /[A-Za-z0-9_]/.test(src[i])) i++;
const word = src.slice(s, i);
tokens.push({ type: KEYWORDS.has(word) ? word : "name", value: word, line });
continue;
}
const two = src.slice(i, i + 2); // 2文字の記号を先に見る
if (["==", "!=", "<=", ">="].includes(two)) {
tokens.push({ type: two, line }); i += 2; continue;
}
if ("+-*/()<>={},;".includes(c)) {
tokens.push({ type: c, line }); i++; continue;
}
throw new Error(`${line}行目: 読めない文字 '${c}'`);
}
tokens.push({ type: "eof", line });
return tokens;
}
EOF
2文字の記号を先に見るのが要点です。 1文字ずつ見ると
<=が<と=に割れて、そのあと絶対に直せません。長いものから試すのは、字句解析の鉄則です。
③ 優先順位を、関数の深さで表す
ここがこの記事の中心です。 「掛け算が先」を、条件分岐ではなく関数の呼び出し順で表します。
式 := 比較
比較 := 足し算 ( ("=="|"!="|"<"|">"|"<="|">=") 足し算 )*
足し算 := 掛け算 ( ("+"|"-") 掛け算 )*
掛け算 := 単項 ( ("*"|"/") 単項 )*
単項 := "-" 単項 | 基本
基本 := 数 | 名前 | 名前"(" 引数 ")" | "(" 式 ")"
下にあるものほど先に計算されます。 「足し算」は、自分の仕事を始める前に必ず「掛け算」を呼びます。だから掛け算のほうが先にまとまります。優先順位という概念を、呼び出しの深さに置き換えているわけです。
cat > parser.js <<'EOF'
export function parse(tokens) {
let p = 0;
const peek = () => tokens[p];
const eat = (type) => {
if (tokens[p].type !== type)
throw new Error(`${tokens[p].line}行目: ${type} が必要ですが ${tokens[p].type} が来ました`);
return tokens[p++];
};
function expr() { return comparison(); }
function comparison() {
let node = addsub();
while (["==", "!=", "<", ">", "<=", ">="].includes(peek().type)) {
const op = tokens[p++].type;
node = { kind: "binary", op, left: node, right: addsub() };
}
return node;
}
function addsub() {
let node = muldiv();
while (peek().type === "+" || peek().type === "-") {
const op = tokens[p++].type;
node = { kind: "binary", op, left: node, right: muldiv() };
}
return node;
}
function muldiv() {
let node = unary();
while (peek().type === "*" || peek().type === "/") {
const op = tokens[p++].type;
node = { kind: "binary", op, left: node, right: unary() };
}
return node;
}
function unary() {
if (peek().type === "-") { p++; return { kind: "neg", value: unary() }; }
return primary();
}
function primary() {
const t = tokens[p];
if (t.type === "num") { p++; return { kind: "num", value: t.value }; }
if (t.type === "(") { p++; const e = expr(); eat(")"); return e; }
if (t.type === "name") {
p++;
if (peek().type === "(") { // 関数呼び出し
p++;
const args = [];
while (peek().type !== ")") {
args.push(expr());
if (peek().type === ",") p++;
}
eat(")");
return { kind: "call", name: t.value, args, line: t.line };
}
return { kind: "var", name: t.value, line: t.line };
}
throw new Error(`${t.line}行目: 式が来るはずの場所に ${t.type} があります`);
}
// ここから下は文の解析(文法は⑥で説明します)
function block() {
eat("{");
const stmts = [];
while (peek().type !== "}" && peek().type !== "eof") stmts.push(statement());
eat("}");
return stmts;
}
function statement() {
const t = peek();
if (t.type === "let") {
p++; const name = eat("name").value; eat("=");
const value = expr(); eat(";");
return { kind: "let", name, value };
}
if (t.type === "print") { p++; const value = expr(); eat(";"); return { kind: "print", value }; }
if (t.type === "return") { p++; const value = expr(); eat(";"); return { kind: "return", value }; }
if (t.type === "if") {
p++; eat("("); const cond = expr(); eat(")");
const then = block();
let els = null;
if (peek().type === "else") { p++; els = block(); }
return { kind: "if", cond, then, else: els };
}
if (t.type === "while") {
p++; eat("("); const cond = expr(); eat(")");
return { kind: "while", cond, body: block() };
}
if (t.type === "fn") {
p++; const name = eat("name").value; eat("(");
const params = [];
while (peek().type !== ")" && peek().type !== "eof") {
params.push(eat("name").value);
if (peek().type === ",") p++;
}
eat(")");
return { kind: "fn", name, params, body: block() };
}
if (t.type === "name" && tokens[p + 1].type === "=") { // 代入(== は字句解析で別の語になっている)
p += 2; const value = expr(); eat(";");
return { kind: "assign", name: t.value, value };
}
const value = expr(); eat(";"); // 式だけの文
return { kind: "expr", value };
}
function program() { // ファイル全体 = 文の並び
const stmts = [];
while (peek().type !== "eof") stmts.push(statement());
return stmts;
}
return { expr, program, eat, peek, at: () => p, set: (v) => (p = v), tokens };
}
EOF
木になったことを、目で見る
node --input-type=module -e '
import { tokenize } from "./lexer.js";
import { parse } from "./parser.js";
const api = parse(tokenize("1 + 2 * 3"));
console.log(JSON.stringify(api.expr(), null, 1));
'
{
"kind": "binary",
"op": "+",
"left": { "kind": "num", "value": 1 },
"right": {
"kind": "binary",
"op": "*",
"left": { "kind": "num", "value": 2 },
"right": { "kind": "num", "value": 3 }
}
}
掛け算が、足し算の内側に入っています。 この時点で優先順位は解決済みで、あとはこの木を辿るだけです。「難しいことは、計算の前に終わらせておく」という形が、ここでもそのまま出てきます。
④ 評価 —— 木を辿るだけ
cat > eval.js <<'EOF'
export const hooks = {}; // 関数呼び出しの中身は⑥で run.js が入れる
export function evaluate(node, env) {
switch (node.kind) {
case "num": return node.value;
case "call": return hooks.call(node, env);
case "neg": return -evaluate(node.value, env);
case "var": {
const scope = env.find(node.name);
if (!scope) throw new Error(`${node.line}行目: ${node.name} は定義されていません`);
return scope.vars.get(node.name);
}
case "binary": {
const a = evaluate(node.left, env), b = evaluate(node.right, env);
switch (node.op) {
case "+": return a + b;
case "-": return a - b;
case "*": return a * b;
case "/":
if (b === 0) throw new Error("0 では割れません");
return a / b;
case "==": return a === b ? 1 : 0;
case "!=": return a !== b ? 1 : 0;
case "<": return a < b ? 1 : 0;
case ">": return a > b ? 1 : 0;
case "<=": return a <= b ? 1 : 0;
case ">=": return a >= b ? 1 : 0;
}
}
}
throw new Error(`評価できない節: ${node.kind}`);
}
EOF
20 行しかありません。 難しい仕事は構文解析が終わらせているので、評価は木の形どおりに再帰するだけです。
⑤ 変数を足す —— 環境は、ただの Map
cat > env.js <<'EOF'
export class Env {
constructor(parent = null) { this.vars = new Map(); this.parent = parent; }
find(name) { // 自分に無ければ親へ聞きに行く
if (this.vars.has(name)) return this;
return this.parent ? this.parent.find(name) : null;
}
define(name, value) { this.vars.set(name, value); }
assign(name, value) {
const scope = this.find(name);
if (!scope) throw new Error(`${name} は定義されていません`);
scope.vars.set(name, value);
}
}
EOF
スコープの正体は、この parent の1本の線です。 「関数の中から外の変数が見える」「外から中の変数は見えない」——どちらも find が親にしか登らない、というだけで説明が付きます。
⑥ 式と文を分ける
1 + 2 は値になります。while は値になりません。この違いを、木の種類として分けます。
文 := "let" 名前 "=" 式 ";"
| "print" 式 ";"
| "if" "(" 式 ")" ブロック ( "else" ブロック )?
| "while" "(" 式 ")" ブロック
| "fn" 名前 "(" 引数 ")" ブロック
| "return" 式 ";"
| 名前 "=" 式 ";"
| 式 ";"
cat > run.js <<'EOF'
import { readFileSync } from "node:fs";
import { tokenize } from "./lexer.js";
import { parse } from "./parser.js";
import { evaluate, hooks } from "./eval.js";
import { Env } from "./env.js";
function execBlock(stmts, env) {
for (const s of stmts) {
const r = exec(s, env);
if (r && r.return) return r; // return を上へ伝える
}
return null;
}
function exec(node, env) {
switch (node.kind) {
case "let": env.define(node.name, evaluate(node.value, env)); return null;
case "assign": env.assign(node.name, evaluate(node.value, env)); return null;
case "print": console.log(evaluate(node.value, env)); return null;
case "if":
return evaluate(node.cond, env)
? execBlock(node.then, new Env(env))
: (node.else ? execBlock(node.else, new Env(env)) : null);
case "while": {
let guard = 0;
while (evaluate(node.cond, env)) {
const r = execBlock(node.body, new Env(env));
if (r && r.return) return r;
if (++guard > 1_000_000) throw new Error("ループが100万回を超えました");
}
return null;
}
case "fn": env.define(node.name, { params: node.params, body: node.body, env }); return null;
case "return": return { return: true, value: evaluate(node.value, env) };
case "expr": evaluate(node.value, env); return null; // 式だけの文
}
}
EOF
whileに上限を入れているのは、わざとです。 自作の言語でwhile (1) {}を書くと、端末ごと固まります。止められない仕組みを作るときは、止める仕掛けを先に入れる——正規表現エンジンを書いたときに、暴走する入力で学んだのと同じことです。
関数呼び出し —— 新しい環境を作る
cat >> run.js <<'EOF'
hooks.call = (node, env) => { // eval.js の case "call" から呼ばれる
const f = env.find(node.name)?.vars.get(node.name);
if (!f) throw new Error(`${node.line}行目: 関数 ${node.name} がありません`);
if (f.params.length !== node.args.length)
throw new Error(`${node.line}行目: ${node.name} は引数 ${f.params.length} 個です`);
const local = new Env(f.env); // ⚠️ 呼び出し元ではなく、定義された場所の環境を親にする
f.params.forEach((p, i) => local.define(p, evaluate(node.args[i], env)));
const r = execBlock(f.body, local);
return r ? r.value : 0;
};
// ファイルを読んで、字句解析 → 構文解析 → 実行
const src = readFileSync(process.argv[2], "utf8");
execBlock(parse(tokenize(src)).program(), new Env());
EOF
評価器(eval.js)は関数の中身を実行する execBlock を知らないので、case "call" は run.js が入れた hooks.call に任せています。これで run.js がそろいました。
new Env(f.env) の1行が、クロージャの正体です。 呼び出し元の環境を親にすると、関数の中身が「どこから呼ばれたか」で変わってしまいます。定義された場所を覚えているから、JavaScript の関数は外側の変数を見られます。
⑦ 動かす
cat > sample.ml <<'EOF'
# 階乗を出す
fn fact(n) {
if (n <= 1) { return 1; }
return n * fact(n - 1);
}
let i = 1;
while (i <= 5) {
print fact(i);
i = i + 1;
}
EOF
node run.js sample.ml
1
2
6
24
120
自分で決めた文法で書いたファイルが、自分で書いたプログラムで動きました。
⑧ エラーに行番号を付ける
ここを省くと、自作言語は使えません。 どこで間違えたか分からないからです。
let x = ;
1行目: 式が来るはずの場所に ; があります
行番号は字句解析のときにしか分かりません。 構文解析の段階では、もう文字の位置が失われているからです。だから tokenize で全トークンに line を付けておき、以降はそれを運びます。
エラーの読み方の回で「下から読む」と書いたのは、この構造の裏返しです。 処理系は、起きた場所から呼び出し元へ向かってメッセージを積み上げます。一番下(一番内側)が、実際に落ちた場所です。
⑨ インタプリタとコンパイラは、どこから違うのか
| 工程 | インタプリタ | コンパイラ |
|---|---|---|
| 字句解析 | 同じ | |
| 構文解析 | 同じ | |
| 木ができたあと | その場で辿って実行する | 機械語やバイトコードに書き出す |
| 実行の速さ | 遅い(毎回木を辿る) | 速い(変換は1回) |
| エラーに気づく時期 | そこへ到達したとき | 変換のとき |
前半は完全に同じです。 違うのは「木をどうするか」だけ。TypeScript が「実行時には消える」のも、同じ話で、型の検査は木ができた時点で終わっていて、出力する JavaScript には型が残りません。
作らなかったもの
| 省いたもの | なぜ |
|---|---|
| 文字列型・配列 | 評価器に型の判定が増えるだけで、新しい理解が増えない |
| バイトコード | 木を辿る形が見えなくなる。速さは目的ではない |
| ガベージコレクション | JavaScript が持っているものに任せる |
| エラーからの復帰 | 最初の1つで止める。複数まとめて報告するのは別の設計 |
完成の判定
| # | 確かめること | 合格の形 |
|---|---|---|
| 1 | 優先順位 | print 1 + 2 * 3; が 7 |
| 2 | 括弧 | print (1 + 2) * 3; が 9 |
| 3 | 再帰 | fact(5) が 120 |
| 4 | スコープ | 関数の中で let した変数が、外から見えない |
| 5 | エラー | 未定義の変数で行番号付きで止まる |
4 と 5 が本番です。 1〜3 は電卓でも通ります。
つまずいたところ
1 + 2 * 3 が 9 のまま
addsub が muldiv を呼んでいません。文法の階層と、関数の呼び出しの階層は同じ形でなければいけません。片方だけ直しても合いません。
括弧を閉じ忘れると、無限ループになる
while (peek().type !== ")") のような判定は、eof を考えていないと止まりません。終端を必ず条件に入れます。
while (peek().type !== ")" && peek().type !== "eof") { … }
関数の中から外の変数が見えない
new Env(f.env) ではなく new Env() にしています。親を渡さないと、find が登れません。
再帰が深いと落ちる
RangeError: Maximum call stack size exceeded
これは自作言語ではなく、下で動いている JavaScript のスタックが尽きています。 評価器が再帰で書かれているので、対象言語の再帰の深さが、そのままホスト言語のスタックの深さになります。スタックとキューの回で見たエラーが、ここでそのまま出ます。
後片づけ
cd ~
rm -rf mylang
よくある質問
- なぜ再帰下降で書くのですか。構文解析器の生成ツールは使わないのですか
- 手で書けて、文法の形がそのままコードの形になるからです。生成ツールを使うと、文法ファイルは短くなりますが、生成されたコードは読めないので「なぜ掛け算が先になるのか」が見えません。実際、多くの本番の処理系も手書きの再帰下降を採用しています。エラーメッセージを自分で作り込めることが大きな理由です。
- この言語は実用になりますか
- なりません。文字列も配列もなく、数値だけを扱う言語だからです。目的は実用ではなく、言語処理系が3つの部品でできていることを手で確かめることにあります。ここまで作ってあれば、文字列型を足す作業が字句解析と評価の2か所で済むこと、それが設計として自然であることも見えるようになります。
- 優先順位を変えたいときは何を直しますか
- 関数の呼び出し順を変えます。たとえば累乗を掛け算より優先させたいなら、掛け算の関数が呼ぶ相手を、単項ではなく新しい累乗の関数にします。条件分岐や優先順位の表を書き換えるのではなく、階層そのものを組み替えるのがこの書き方の特徴です。
- while に回数の上限を入れるのは邪道ではありませんか
- 学習用としては入れたほうが安全です。無限ループを書いたときに端末ごと固まると、原因が分からないまま強制終了することになり、何も学べません。上限に当たったときに明示的なエラーを出せば、自分が無限ループを書いたことがその場で分かります。本番の処理系では入れませんが、その場合は実行を外から止められる仕組みが別にあります。
- コンパイラを作るなら、どこから変えればよいですか
- 評価器を置き換えます。字句解析と構文解析はそのまま使えるので、木を辿って計算する代わりに、木を辿って命令列を出力する関数を書きます。最初は自分で決めたバイトコードにして、それを実行する小さな仮想機械を書くのが分かりやすい順番です。いきなり機械語を出そうとすると、レジスタの割り当てという別の難問が同時に来ます。
まとめ — 理解できたこと
- 言語処理系は3つの部品でできている。 字句解析・構文解析・評価
- 優先順位は、関数の呼び出しの深さで表す。 深いほど先にまとまる
- 難しい仕事は構文解析で終わる。 評価は木のとおりに再帰するだけで 20 行
- スコープの正体は
parentの1本の線。 関数が「定義された場所」を覚えているのがクロージャ - 行番号は字句解析でしか取れない。 あとから足せないものは、最初に持たせる
- インタプリタとコンパイラは、木ができるまで同じ。 違うのはその後だけ
参考リンク
次に読む
この記事は 【番外編】roadmap.sh の外 の 30 / 35 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 正規表現が固まる理由 — エンジンを100行で自作する |
| → 次の記事 | 512バイトに入らなくなる — メモリ管理とマルチタスク |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。

コメント