LoginSignup
6
4

More than 3 years have passed since last update.

@junjis0203

作って理解JavaScript：JOKE開発記その1 - 処理系の基本構造

Last updated at Posted at 2020-05-08

はじまり

ある日のこと。
「RubyやPythonではクラス定義とはコード実行そのものだけど1、JavaScriptってどうなってるんだろ」
「そもそもclassはES2015で導入されたわけだがどう処理されてるのだろう、Babelみたいに昔のコードにしてから処理されてる？2」
「前々からJavaScript処理系読んでみたいとは思ってるけど読みならV8、でも読む量が多くてめんどくさそうだな」
「じゃあ作ってみるか」

ということでJavaScript処理系を自作することでJavaScriptのいろんな謎挙動について理解してみることになりました。
https://github.com/junjis0203/joke

方針

JokeScriptとJOKE

JavaScript、というかECMAScript仕様全部を実装するのは辛すぎるのでやりません。
そこでECMAScript仕様（特にES2015）の中から興味のあるものをピックアップして実装してみることにしました。JavaScriptを名乗ることはできないのでJokeScriptという名前を付けました（名前先行）
その後、「JOKE is OfuzaKe ecmascript Engine」という再帰的定義を思いつきました（名前先行）

動作確認方法

「本物」のJavaScriptコードが動かせることを確認する。JavaScriptと言えばコールバックなので以下のコードが動かせることを第1目標にする。

const hello = (callback) => {
  console.log("Hello");
  callback();
};

hello(() => {
  console.log("World");
});

と思ったのですがそもそも動いていることを確認する（画面出力する）ためにはconsole.log3というメソッド呼び出しが必要なので、ステップ1では以下のコードが動くことを目標に改めました(笑)

step/step0001.js
console.log("Hello");

実装言語とそれによって生じた目標

JOKEはJavaScriptを使って実装します。
つまり、JavaScript処理系の上でJavaScript処理系が動くということです。とてもjokeっぽい。

そしてある言語の処理系をある言語自身で実装するとなるとお決まりの目標が出てきます。
そう、セルフホスティングです。

なお効率（実行速度や使用メモリ等）については当分追求しません。

JOKEの基本構造

ここからはステップ1時点の実装（tag: step0001）に沿ってプログラム構造を説明していきます。言語処理系なのでお決まりの字句解析、構文解析、コード生成、コード実行という流れになります。

字句解析：Scanner

字句解析を行うオブジェクトはまんまScanner（ファイルはlib/scanner.js）です。4
まずはステップ1のプログラムが解析できる最小限の処理を実装しています。具体的には以下。

  • コメント（一行および複数行）
  • 文字列（ただしエスケープシーケンスとかの処理は保留）
  • 変数などの識別子（特定単語をキーワードとする処理は未実装）
  • これ以外は全部「文字」

実装の工夫、というほどのことではないのですが、インデントをあまり深くしたくなかったので字句解析処理本体はscannerMainというただの関数にしています。昔のJavaScriptだと「グローバル汚染がー」となりますがES Modulesなのでexportしてない限りは汚染は起こりません。
また、「現在のトークン」はScannerオブジェクトのtokenプロパティとして持っているのですがいまいち感が強いので他にいい方法を思いついたら変えたいです。

トークンはJavaScriptのオブジェクトとして切り出されます5。ステップ1のプログラムを字句解析すると以下のようになります。ENDは要らない気もしますがこれがないと何らかのトークンが返ってくると想定しているところがtypeプロパティを参照して死ぬので必要かなとも思います。

{ type: 'IDENTIFIER', identifier: 'console' }
{ type: 'CHAR', char: '.' }
{ type: 'IDENTIFIER', identifier: 'log' }
{ type: 'CHAR', char: '(' }
{ type: 'STRING', string: 'Hello' }
{ type: 'CHAR', char: ')' }
{ type: 'CHAR', char: ';' }
{ type: 'END' }

なおASIについては慣れてくると便利なのですがルールも複雑なので当面サポートしません。

ファイルの入力方法

Scannerオブジェクトの作成方法は以下のようになっています。

const scanner = new Scanner(sourceFile, data);

sourceFileは「ソースファイルの名前」、dataは「（別途読み込んだ）ソースファイルの中身」です。
Scannerの中で読み込めばいいやんというご意見がありそうですが、ブラウザ上でも動く妄想（例えばテキストエリアに入力されたものをプログラムとして実行する）を考慮し、JOKE本体部分ではファイル読み込みは行わないようにしています。

ただ、importを実装するにはソースファイル中に出てきたモジュール（別のソースファイル）を読み込む必要があるのでコールバックでファイル名渡されたら読み込んで返すようにする必要があるかなとも思います。このコールバックを初めから入れようとするといきなり難しくなる（うえに初めに作っておいてもどうせ想定外のケースがあり直すことになる）ので現時点ではこのようなファイル入力方法になっています。

構文解析：Parser

構文解析を行うオブジェクトはParser（lib/parser.js）です。ECMAScript仕様のBNFに沿って淡々と実装していきます。
yaccは使えないのでjocc（ジョック）という劣化yaccをまず作るか？とも思ったのですがBNFを構文解析するブートストラップ問題もあるため再帰下降でパーサを書いています。こちらもまずはステップ1のプログラムが解析できるように最低限の部分を実装しました。

  • オブジェクト参照
  • メソッド呼び出し（関数含む）
  • ステップ1では対象外だがfoo().bar()みたいな呼び出し（foo関数がオブジェクトを返し、そのオブジェクトのbarメソッドを呼ぶ）にも対応

基本的にはBNFに対して一つの関数を対応させています。ただNewExpressionとCallExpressionについては以下のようにMemberExpressionが共通でカッコがあるかどうかでNewExpressionなのかCallExpressionなのか変わるというBNFのため、一つ上のLeftHandSideExpressionでまずMemberExpressionを処理し、カッコがあるかどうかで処理を分けています。ひょっとして再帰下降だと処理できない規則がある？と一抹の不安が残ります。

NewExpression :
    MemberExpression

CallExpression :
    MemberExpression Arguments
    ※他のルールは省略

LeftHandSideExpression :
    NewExpression
    CallExpression

また、メソッドの引数、つまり式のBNFは演算子の優先順位に応じて細かく分かれています。演算をサポートするのはもう少し後ですが、後から変更するのもめんどくさそうなので単に下の規則に流すだけの関数を作成しています。

構文解析の結果は以下のようなノード（入れ子オブジェクト）として返されます6。これについてが今までコードを読んだことある言語処理系のやり方を踏襲し、JavaScriptで表現しただけとなります。

{
  type: 'STATEMENTS',
  statements: [
    {
      type: 'CALL',
      target: {
        type: 'MEMBER',
        object: { type: 'IDENTIFIER', identifier: 'console' },
        property: 'log'
      },
      arguments: [ { type: 'STRING', string: 'Hello' } ]
    }
  ]
}

コード生成：Assembler

構文解析でできたノードをたどって実行コードを作ります。コード生成を担当するオブジェクトはAssemblerです（lib/assembler.js）
どのようなコードを生成し、それを実行するかは言語仕様で定義されるものではなく完全にオレオレな範囲なので、作りやすいスタックマシンにしました。6
上記の構文解析結果ノードに対応する実行コード列は以下のようになります。

[
  { command: 'PUSH', operand: 'console' },
  { command: 'PUSH', operand: 'log' },
  { command: 'LOOKUP' },
  { command: 'PUSH', operand: 'Hello' },
  { command: 'CALL', operand: 1 }
]

方針で書いたように効率は追求しないので、コマンドに整数を割り当てオペランドも含めて固定長の「バイトコード」にする、ということは行いません。

コード実行：Vm

最後に命令コードを実行するオレオレスタックマシンのVmオブジェクト（lib/vm.js）です。分岐やループを実装する段階になると複雑になってくると思いますが現段階では単に一つずつ命令コードを実行するだけです。

オブジェクト空間の実装（仮）

命令コードで指定されているconsoleやそのメソッドlogを用意しないといけません。
というわけで暫定的に以下のように「とても薄いラッパー」を作りました。createScopeとcreateObjectもexportしてるのは「多分これでコード内で定義される変数とかもいけるだろう」と考えているためです。

lib/object.js
export function createScope() {
    return {
        getObject(name) {
            return this[name];
        }
    };
}

export function createObject() {
    return {
        getProperty(name) {
            return this[name];
        }
    };
}

export function initializeGlobalScope() {
    const jkConsole = createObject();
    jkConsole['log'] = (...args) => console.log(...args);

    const globalScope = createScope();
    globalScope['console'] = jkConsole;

    return globalScope;
}

さてこれでできました。実行しましょう。

PS C:\work\joke> node --experimental-modules joke.js step/step0001.js
(node:15932) ExperimentalWarning: The ESM module loader is experimental.
(node:15932) ExperimentalWarning: Package name self resolution is an experimental feature. This feature could change at any time
Hello

おぉぉ表示されたぁ！
ともちろんここまで何のエラーもなく処理系が書けたわけではないのでHelloと表示されたときはそこそこ感動しました。

ファサードオブジェクト：JokeEngine

上記の字句解析～コード実行までは一段階ずつ作って試してという形で進めていったわけですが、使う側、というか次に説明するテストの際に同じような処理手順を書くのは記述が重複するので、一連の処理を実行するファサードオブジェクトのJokeEngine7（lib/joke.js）を作りました。
JokeEngine利用側は以下のように非常にシンプルになります（前述のようにファイルの内容はあらかじめ読み込んでから渡す必要があります）

const joke = new JokeEngine();
joke.run(sourceFile, data);

テスト方法

今回実装対象とする部分は手動で動かしてみるとして、以前のステップ検証用に作ったコードが正しく実行できるか（実行できなくなっていないか）をテストするためにstepディレクトリに置かれている検証用プログラムを一通り動かしてみてエラーになるものがあれば止まるテストプログラムを作成しました。8

test.js
async function check(checkProgramDir) {
    const dir = await fs.promises.opendir(checkProgramDir);
    for await (const dirent of dir) {
        const sourceFile = dirent.name;
        const sourcePath = path.join(checkProgramDir, sourceFile);
        const data = await fs.promises.readFile(sourcePath, 'utf8');
        try {
            const joke = new JokeEngine();
            joke.run(sourcePath, data);
            console.log(`${sourceFile}: OK`);
        } catch(e) {
            console.log(`${sourceFile}: NG`);
            console.error(`${e.name}: ${e.message}`);
            throw e;
        }
    }
}

check('./step')
.catch(err => {
    process.exit(1);
});

package.jsonのscripts.testで上記のtest.jsを動かすようにしてnpm testを実行。

PS C:\work\joke> npm test

> joke@0.1.0 test C:\work\joke
> node --experimental-modules test.js

(node:18780) ExperimentalWarning: The ESM module loader is experimental.
(node:18780) ExperimentalWarning: Package name self resolution is an experimental feature. This feature could change at any time
Hello
step0001.js: OK

Helloはstep0001.jsを実行することで出力されたもので、出力が変になってないかも検証しないといけないよなと思っており、先ほど方法は思いついたのですが、ステップ2を実装するときに合わせてテストプログラムの改修も行うことにします。

今回のまとめと今後の予定

以上、JavaScriptの挙動を理解するために処理系作ってみるかというノリで開始したJOKEの説明を行いました。基本構造はできたので後は淡々と機能を追加していけばいいはずです（多分数回大幅な構造変更が必要になるでしょう）

セルフホスティングを行うためには以下の機能を実装する必要があります。めんどいのでJOKE実装に使う構文を限定するのは本末転倒なので頑張って実装していこうと思います。

  • if文
  • switch文
  • for文
  • while文
  • 変数
  • 数値演算
  • 比較演算、論理演算
  • エスケープシーケンス
  • テンプレート文字列
  • 配列（メソッド含む）
  • オブジェクト
  • 関数（文での定義とアロー関数）
  • 例外処理
  • クラス
  • モジュール（importとexport）

多いなｗ。今年中にできるかな。

なお次のステップとしては変数（letとconst。varなどない）を実装する予定です。もちろん分割代入などの高度な初期化はまだ実装しません。
letやconstは同じ変数を2回定義するとSyntaxErrorになるのですが、文法（BNF）的に判断はできないと思うので、おそらくコード生成の前に意味解析を導入する必要があると思われます。

  1. Pythonでクラス定義が実行される様子についてはこちらの記事をご覧ください。 ↩

  2. 確認したわけではないですがその後の検討で「昔のコードにしてから処理しなくても同じ動作をする命令列を出力すればいいだろう」という考えに至りました。 ↩

  3. ちなみにconsoleオブジェクトはECMAScript仕様にはありません。 ↩

  4. 字句解析部分作った後にECMAScriptの仕様を見たら字句解析に当たる部分もBNFとして表現されていました。まあでも一般的には字句解析は構文解析とは独立して行うのがいいかなと思います。 ↩

  5. エラー表示を考えるとトークンの位置（ファイル名と行数、できれば列数）も要るかなと思いますがとりあえず保留。 ↩

  6. 入れ子が深いオブジェクトを出力するにはconsole.logではなくconsole.dirを使います。ブラウザでもNode.jsでも使えますがNode.jsでは第2引数としてdepth: null}を指定しないと3段階目以降が[Object]や[Array]になります。 ↩

  7. JOKEはJOKE is OfuzaKe ecmascript Engineの略ではなかったか？だとするとJokeEngineはJOKE is OfuzaKe ecmascript Engine Engineとなってしまうのではないか？と細かいことを気にしてはいけません。 ↩

  8. asyncとawaitを使っていますがテストプログラムなのでセルフホスティングの対象外です。async, awaitはES2017ですがこれらも挙動がおもしろいのでできれば実装したいです。 ↩

6
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
4