式をパースする：抽象構文木（AST）と再帰下降構文解析の深淵
現代のフロントエンド開発において、「式をパースする」という技術は、もはやコンパイラエンジニアだけの特権ではありません。ノーコードツールのロジックエディタ、高度なスプレッドシート機能、あるいは独自のDSL（ドメイン固有言語）を実装する際、文字列として与えられた数式や条件式をプログラムが解釈可能な形式に変換する能力は、アプリケーションの拡張性を劇的に高めます。本稿では、数式をパースし、計算可能な状態にするためのアーキテクチャと実装手法を徹底的に解説します。
構文解析の基礎：字句解析からAST生成まで
式をパースするプロセスは、大きく分けて「字句解析（Lexical Analysis）」と「構文解析（Syntactic Analysis）」の二段階に分かれます。
字句解析は、入力された文字列を「トークン」と呼ばれる意味のある最小単位に分解する工程です。例えば「3 + 5 * (2 – 1)」という文字列は、[NUMBER(3), PLUS, NUMBER(5), MULTIPLY, LPAREN, NUMBER(2), MINUS, NUMBER(1), RPAREN]といったトークンの列に変換されます。この段階では、まだ式の構造は考慮されません。
続く構文解析では、これらのトークン列を読み込み、文法規則に従って「抽象構文木（AST）」を構築します。ASTは、演算子をノード、数値をリーフ（葉）とするツリー構造であり、演算子の優先順位や括弧による結合の強さが木構造の中に自動的にエンコードされます。この木構造さえ完成すれば、あとはツリーを再帰的に走査（評価）するだけで、計算結果を得ることができます。
再帰下降構文解析の理論と実践
数式のパースにおいて最も一般的かつ強力な手法が「再帰下降構文解析（Recursive Descent Parsing）」です。これは、文法規則をそのまま関数呼び出しの連鎖として実装する手法です。
数式には「演算子の優先順位」という概念が存在します。例えば、乗算は加算よりも先に評価される必要があります。これを表現するために、文法を階層化します。
1. Expression（式）: 加算・減算を扱う
2. Term（項）: 乗算・除算を扱う
3. Factor（因子）: 数値や括弧を扱う
この階層構造により、再帰的に関数を呼び出すことで、自然と優先順位を考慮したパースが可能になります。
実装：数式パーサーの構築
以下に、TypeScriptを用いたシンプルな数式パーサーの実装例を示します。この実装は、トークナイザーと、再帰下降パーサー、そしてASTを評価するエバリュエーターで構成されています。
type TokenType = 'NUMBER' | 'PLUS' | 'MINUS' | 'MULTIPLY' | 'DIVIDE' | 'LPAREN' | 'RPAREN' | 'EOF';
interface Token { type: TokenType; value: string; }
class Tokenizer {
private pos = 0;
constructor(private input: string) {}
tokenize(): Token[] {
const tokens: Token[] = [];
while (this.pos < this.input.length) {
const char = this.input[this.pos];
if (/\s/.test(char)) { this.pos++; continue; }
if (/\d/.test(char)) {
let val = '';
while (this.pos < this.input.length && /\d/.test(this.input[this.pos])) {
val += this.input[this.pos++];
}
tokens.push({ type: 'NUMBER', value: val });
continue;
}
const map: Record = { '+': 'PLUS', '-': 'MINUS', '*': 'MULTIPLY', '/': 'DIVIDE', '(': 'LPAREN', ')': 'RPAREN' };
if (map[char]) { tokens.push({ type: map[char], value: char }); this.pos++; continue; }
throw new Error(`Unexpected character: ${char}`);
}
tokens.push({ type: 'EOF', value: '' });
return tokens;
}
}
interface Node { type: string; value?: number; left?: Node; right?: Node; operator?: string; }
class Parser {
private pos = 0;
constructor(private tokens: Token[]) {}
parse(): Node { return this.expression(); }
private expression(): Node {
let node = this.term();
while (this.tokens[this.pos].type === 'PLUS' || this.tokens[this.pos].type === 'MINUS') {
const token = this.tokens[this.pos++];
node = { type: 'BinaryExpression', operator: token.value, left: node, right: this.term() };
}
return node;
}
private term(): Node {
let node = this.factor();
while (this.tokens[this.pos].type === 'MULTIPLY' || this.tokens[this.pos].type === 'DIVIDE') {
const token = this.tokens[this.pos++];
node = { type: 'BinaryExpression', operator: token.value, left: node, right: this.factor() };
}
return node;
}
private factor(): Node {
const token = this.tokens[this.pos++];
if (token.type === 'NUMBER') return { type: 'Literal', value: parseFloat(token.value) };
if (token.type === 'LPAREN') {
const node = this.expression();
this.pos++; // skip RPAREN
return node;
}
throw new Error('Unexpected token');
}
}
function evaluate(node: Node): number {
if (node.type === 'Literal') return node.value!;
const left = evaluate(node.left!);
const right = evaluate(node.right!);
switch (node.operator) {
case '+': return left + right;
case '-': return left - right;
case '*': return left * right;
case '/': return left / right;
default: return 0;
}
}
const input = "3 + 5 * (2 - 1)";
const tokens = new Tokenizer(input).tokenize();
const ast = new Parser(tokens).parse();
console.log(evaluate(ast)); // 出力: 8
実務における設計指針と最適化
実務でパーサーを実装する際、単に動作するだけでなく、メンテナンス性と堅牢性が重要になります。
まず、「エラーハンドリング」の徹底です。ユーザーが入力する式には必ず誤りが含まれます。`Unexpected token`のような曖昧なエラーではなく、「何文字目のどの位置で、期待していたトークンは何だったのか」を明確に示すパーサーは、UXを劇的に向上させます。例外をスローする際、トークンの位置情報（行・列）を保持しておく設計が不可欠です。
次に、「パフォーマンス」の考慮です。JavaScriptのエンジンは非常に高速ですが、極端に長い式や深いネストを持つ式をパースする場合、再帰によるコールスタックの上限に達するリスクがあります。必要に応じて、再帰を使わないスタックベースのパーサー（Shunting-yard法など）への切り替えを検討すべきです。
また、ASTの「拡張性」も重要です。将来的に関数（`SUM()`, `AVG()`など）や変数（`price * tax_rate`）をサポートする可能性があるなら、`BinaryExpression`だけでなく、`CallExpression`や`Identifier`といったノードタイプを柔軟に追加できるインターフェースを設計しておいてください。Visitorパターンを導入することで、ASTに対する操作（評価、最適化、静的解析）をノードクラスから分離し、保守性を高めることができます。
さらに、複雑な文法を扱う場合は、手書きのパーサーに固執せず、`Nearley.js`や`PEG.js`といったパーサー生成器（Parser Generator）の採用を検討してください。これらはEBNF形式の文法定義からパーサーを自動生成するため、手書きよりもバグが少なく、文法の変更にも即座に対応可能です。
まとめ：式のパースが切り拓く可能性
式をパースするという技術は、フロントエンド開発者が「静的なUI」から「動的なロジックエンジン」へと領域を広げるための鍵となります。文字列という自由度の高い入力に対し、厳密な構造を与えることで、ユーザーに柔軟なカスタマイズ性を提供することが可能になります。
今回解説した再帰下降構文解析の基礎は、プログラミング言語のコンパイラから、検索クエリのパーサー、Excelライクな計算エンジンの構築まで、あらゆる場面で応用可能です。まずはシンプルな数式から始め、徐々に変数や関数、論理演算子を取り入れていくことで、その奥深さと面白さを体感してください。
技術の抽象度を一段上げることは、複雑な要件をシンプルに解決する力に直結します。ぜひ、あなた自身のパーサーを実装し、アプリケーションの可能性を拡張してみてください。
コメント