Node.jsでつくるNode.js - Step 3: +演算子を評価する

はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) と PythonでつくるPythonに影響を受けて、Node.jsでミニNode.js作りにチャンレンジ中です。

前回はソースをパースして作ったASTを単純化するsimplify()を一部実装してみました。今回は 「+ 演算子」を評価して足し算ができるところまで進めてみます。

• もくじ

+演算子のASTを単純化

'1+2' のASTは、このようになりました。

Script {
  type: 'Program',
  body:
   [ ExpressionStatement {
       type: 'ExpressionStatement',
       expression:
        BinaryExpression {
          type: 'BinaryExpression',
          operator: '+',
          left: Literal { type: 'Literal', value: 1, raw: '1' },
          right: Literal { type: 'Literal', value: 2, raw: '2' } } } ],
  sourceType: 'script' }

これを、次の形まで単純化できるように、simplify()の実装を変更します。

[ '+', [ 'lit', 1 ], [ 'lit', 2 ] ]

やっている途中で simplify()を再帰的に呼び出す必要があることがわかったので、最初のAST全体の処理と、途中のノードの処理を分離することにしました。ソースをパースした直後のASTをmakeTree()に渡すと、中でノードごとにsimplify()を再帰的に呼び出します。この段階では、定数（リテラル）と、+演算子だけ処理しています。

function makeTree(ast) {
  const exp = ast.body[0].expression;
  return simplify(exp);
}

function simplify(exp) {
  if (exp.type === 'Literal') {
    return ['lit', exp.value];
  }
  if (exp.type === 'BinaryExpression') {
    if (exp.operator === '+') {
      return ['+', simplify(exp.left), simplify(exp.right)]
    }
  }

  println('-- ERROR: unknown type in simplify) ---');
  printObj(exp);
  return null;
}


function println(str) {
  console.log(str);
}

これで '1+2' や '3+10' といった単純な+演算子を読み込めるようになりました。

+演算子を評価する

いよいよ単純化した抽象構文木treeを実行する、evaluate()を作ります。これも'1+2'が実行できることだけを目指します。識別できるのは次の2つだけです。

• 'lit' ...　リテラル
• '+' ... +演算子

function evaluate(tree) {
  if (tree[0] === 'lit') {
    return tree[1];
  }
  if (tree[0] === '+') {
    return evaluate(tree[1]) + evaluate(tree[2]);
  }

  println('-- ERROR: unknown node in evluate() ---');
  printObj(tree);
  return null;
}

ここに先ほどの単純化したtree

 [ '+', [ 'lit', 1 ], [ 'lit', 2 ] ] 

渡してあげると、答えの 3 が返ってきました。ミニNode.js の原型ができあがりました。

次回

• Step 4: 四則演算で電卓を作る

今回のソースコード

Step3までの全体のコードはこちらです。

// -------------------------
// mininode.js - Node.js by Node.js
// Step3:
// - Evaluate '+' (Binary Operator)
// -------------------------

const esprima = require("esprima");

// --- parser ----
function parseSrc(src) {
  const ast = esprima.parseScript(src);
  return ast;
}

function makeTree(ast) {
  const exp = ast.body[0].expression;
  return simplify(exp);
}

function simplify(exp) {
  if (exp.type === 'Literal') {
    return ['lit', exp.value];
  }
  if (exp.type === 'BinaryExpression') {
    if (exp.operator === '+') {
      return ['+', simplify(exp.left), simplify(exp.right)]
    }
  }

  println('-- ERROR: unknown type in simplify) ---');
  printObj(exp);
  return null;
}

// --- common ----
function printObj(obj) {
  console.dir(obj, {depth: 10});
}

function println(str) {
  console.log(str);
}

// --- evaluator ---
function evaluate(tree) {
  if (tree[0] === 'lit') {
    return tree[1];
  }
  if (tree[0] === '+') {
    return evaluate(tree[1]) + evaluate(tree[2]);
  }

  println('-- ERROR: unknown node in evluate() ---');
  printObj(tree);
  return null;
}

// --------

const ast = parseSrc('1 + 2');
printObj(ast);

const tree = makeTree(ast);
printObj(tree); // expect: ['+', ['lit', 1], ['lit, 2]]

const answer = evaluate(tree);
println(answer); // expect: 3