@ledsun blog

Hのキーがhellで、Sのキーがslaveだ、と彼は思った。そしてYのキーがyouだ。

Node.jsでつくるNode.js その2

ledsun.hatenablog.com

の続きです。四則演算の対応するオペレーター(演算子)を増やします。

オペレーターを増やす

前回+に対応しました。 次に、-, *,/,%に対応します。

実装

switch文に演算子ごとの分岐を追加するだけです。

const esprima = require('esprima')
const util = require('util')

console.assert(test('1 + 1') === 2)
console.assert(test('1 + 2') === 3)
console.assert(test('1 - 2') === -1)
console.assert(test('2 * 2') === 4)
console.assert(test('10 / 2') === 5)
console.assert(test('100 % 49') === 2)

function test(expresssion) {
  const parsed = esprima.parse(expresssion)

  console.log(util.inspect(parsed, false, null))

  const body = parsed.body
  for (const statement of body) {
    return evaluate(statement)
  }
}

function evaluate(statement) {
  switch (statement.type) {
    case 'ExpressionStatement':
      switch (statement.expression.type) {
        case 'BinaryExpression':
          let left, right
          switch (statement.expression.operator) {
            case '+':
              [left, right] = getOperandFromBinaryExpression(statement.expression)
              return left + right
              break;
            case '-':
              [left, right] = getOperandFromBinaryExpression(statement.expression)
              return left - right
              break;
            case '*':
              [left, right] = getOperandFromBinaryExpression(statement.expression)
              return left * right
              break;
            case '/':
              [left, right] = getOperandFromBinaryExpression(statement.expression)
              return left / right
              break;
            case '%':
              [left, right] = getOperandFromBinaryExpression(statement.expression)
              return left % right
              break;
            default:
              console.log(`unknown operator ${statement.expression.operator}`);
          }
          break;
        default:
          console.log(`unknown expression ${statement.expression}`);
      }
      break;
    default:
      console.log(`unknown type ${statement.type}`);
  }
}

function getOperandFromBinaryExpression(expression) {
  let left;
  if (expression.left.type === 'Literal') {
    left = expression.left.value
  } else {
    console.log(`unknown type ${expression.left.type}`);
  }

  let right;
  if (expression.right.type === 'Literal') {
    right = expression.right.value
  } else {
    console.log(`unknown type ${expression.right.type}`);
  }

  return [left, right]
}

leftとrightの値をとる処理をgetOperandFromBinaryExpression関数にしました。

項数を増やす

1 + 1 + 1のように式の項数を増やします。

この時、ASTは

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

leftの中にBinaryExpressionが入れ子になっています。

これに対応すると、小町算を計算できるようになります。

(1 + 2) / 3 * 4 * (56 / 7 + 8 + 9) = 100

実装

BinaryExpressionの評価を再帰的にしたいので、evaluateBinaryExpression関数を作って再起呼び出しします。

const esprima = require('esprima')
const util = require('util')

console.assert(test('1 + 1') === 2)
console.assert(test('1 + 2') === 3)
console.assert(test('1 - 2') === -1)
console.assert(test('2 * 2') === 4)
console.assert(test('10 / 2') === 5)
console.assert(test('100 % 49') === 2)
console.assert(test('1 + 1 + 1') === 3)
console.assert(test('(1 + 2) / 3 * 4 * (56 / 7 + 8 + 9)') === 100)

function test(expresssion) {
  const parsed = esprima.parse(expresssion)

  console.log(util.inspect(parsed, false, null))

  const body = parsed.body
  for (const statement of body) {
    return evaluateStatement(statement)
  }
}

function evaluateStatement(statement) {
  switch (statement.type) {
    case 'ExpressionStatement':
      switch (statement.expression.type) {
        case 'BinaryExpression':
          return evaluateBinaryExpression(statement.expression)
          break;
        default:
          console.log(`unknown expression ${statement.expression}`);
      }
      break;
    default:
      console.log(`unknown type ${statement.type}`);
  }
}

function evaluateBinaryExpression(expression) {
  let left, right
  switch (expression.operator) {
    case '+':
      [left, right] = getOperandFromBinaryExpression(expression)
      return left + right
      break;
    case '-':
      [left, right] = getOperandFromBinaryExpression(expression)
      return left - right
      break;
    case '*':
      [left, right] = getOperandFromBinaryExpression(expression)
      return left * right
      break;
    case '/':
      [left, right] = getOperandFromBinaryExpression(expression)
      return left / right
      break;
    case '%':
      [left, right] = getOperandFromBinaryExpression(expression)
      return left % right
      break;
    default:
      console.log(`unknown operator ${expression.operator}`);
  }
}

function getOperandFromBinaryExpression(expression) {
  return [getOperandValue(expression.left), getOperandValue(expression.right)]
}

function getOperandValue(operand) {
  switch (operand.type) {
    case 'Literal':
      return operand.value
    case 'BinaryExpression':
      return evaluateBinaryExpression(operand)
    default:
      console.log(`unknown type ${operand.type}`);
  }
}

getOperandValue関数はleftとrightにコピペするのが面倒だったので、関数にしました。

RubyでつくるRubyとの違い

EsprimaのASTはstatementとexpressionの二階層になっています。 一方minirubyのASTたexpressionだけの一階層です。

Rubyで作るRubyソースコードは本を買って確認してください。

式と文の取り扱い

これは言語仕様の違いによるものです。

Ruby

プログラムは式を並べたものです

プログラム・文・式 (Ruby 2.4.0)

式と文に区別はありません。

JavaScriptでは式と文は区別されます。 例えば

1 + 1

は式です。

var i = 1

は文です。JavaScriptの文は値を返しません。

Node.jsでつくるNode.js その1

ledsun.hatenablog.com

の続きです。Node.jsで動くJavaScriptインタプリタを実装しようとする試みです。

作戦

  • パーサにはEsprimaを使う
  • TDD的なスモールスタート戦略で進める(最初はセルフホスティングを意識しない)

下調べ

EsprimaがどのようなASTを返すか確認します。

準備

Esprimaをインストールします。

npm init -y
npm install esprima

ASTを見る

REPLでパース結果を確認します。

nodeコマンドでREPLを起動し

~ node
> const esprima = require('esprima')
undefined
> const util = require('util')
undefined
> console.log(util.inspect(esprima.parse('1 + 1'), false, null))
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: 1, raw: '1' } } } ],
  sourceType: 'script' }
undefined

木構造JSONが帰ってきます。

1 + 1を実行する

const esprima = require('esprima')
const util = require('util')

console.assert(test('1 + 1') === 2)

function test(expresssion) {
  const parsed = esprima.parse(expresssion)

  console.log(util.inspect(parsed, false, null))

  const body = parsed.body
  for (const statement of body) {
    return evaluate(statement)
  }
}

function evaluate(statement) {
  switch (statement.type) {
    case 'ExpressionStatement':
      switch (statement.expression.type) {
        case 'BinaryExpression':
          switch (statement.expression.operator) {
            case '+':
              let left;
              if (statement.expression.left.type === 'Literal') {
                left = statement.expression.left.value
              } else {
                console.log(`unknown type ${statement.expression.left.type}`);
              }
              let right;
              if (statement.expression.right.type === 'Literal') {
                right = statement.expression.right.value
              } else {
                console.log(`unknown type ${statement.expression.right.type}`);
              }
              return left + right
              break;
            default:
              console.log(`unknown operator ${statement.expression.operator}`);
          }
          break;
        default:
          console.log(`unknown expression ${statement.expression}`);
      }
      break;
    default:
      console.log(`unknown type ${statement.type}`);
  }
}
  • console.assertを使って実行結果を評価
  • ASTを表示(見ながら実装を進めたい)
  • test関数でスクリプトを実行
  • evaluate関数で文を実行(「RubyでつくるRuby」の最終形に引きづられた、evaluateStatementがベター?)
  • for ofもTemplate literalも使う(現時点でセルフホスティングは考えない)
  • 二項分岐なのにswitchを使った(「RubyでつくるRuby」の最終形に引きづられた、ifで十分)
  • ;有無は統一していない(普段は無し派、ESLintの助けが必要)

実行すると

~ node .
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: 1, raw: '1' } } } ],
  sourceType: 'script' }

ASTを表示するだけです。 結果が間違っているときは、console.assertで引っかかってAssertionErrorがでます。

とりあえずここまでです。 次は対応するoperator(-, *, /)を増やします。