0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

fluorite-8 実装の軌跡 Part 9 文字列と実行時ライブラリ

Last updated at Posted at 2020-11-22

初回

←前回

今回の目標

今回は文字列の追加を目指します。

そして、それによって発生する任意コードの実行が可能になる問題の解決を行います。

文字列リテラルの追加

ここでは簡素な**文字列リテラル'string'**を追加します。埋め込み系文法("a = $a"など)や置換処理(「\n→改行」みたいなの)はありません。

目標

以下の仕様を満たす文字列リテラル'string'を追加します。

  1. 'abc'と書くと、"abc"というJavaScriptコードになる。
  2. \に続いて1文字書くと、先の\が消えて後に置かれた文字を表す。
  3. '\''と書くと、"'"というJavaScriptコードになる。
  4. '\\'と書くと、"\\"というJavaScriptコードになる。
  5. '\n'と書くと、"n"というJavaScriptコードになる。
  6. ' \以外の文字は、半角英数字も記号も全角文字もヌル文字も改行もサロゲートペアも全部そのまま文字として現れる。

実装

文字列は中間コード上でも単なる文字列リテラルとして与えることにします。文字列をJavaScriptコードにするにはJSON.stringifyを使っておきます。

    // 文字列をJavaScriptコードにするのはJSON.stringifyで可能
    env.registerOperatorHandler("get", "string", (env, token) => toOperation("", "(" + JSON.stringify(token.argument) + ")"));
Factor   = Integer
         / String        // 増やした
         / Identifier
         / Brackets
String   = "'" main:(                      // 左側の「'」
             [^'\\]                        // 「'」と「\」以外の文字
           / "\\" main:. { return main; }  // 「\」に続く1文字
           )* "'" {                        // 右側の「'」
             return token("string", main.join(""), location());
           }

テスト

fl8
'asdあいう 123[
][\'][\\]["][\0][\n][\t][\
]🍰'

image.png


上の実行結果はエスケープされているので分かりにくいですが、文字列として出力して見るとちゃんと\が直後の文字だけ残して消えていることが分かります。\\の場合にのみ\が結果の文字列中に現れます。

image.png

疑似eval問題

次のfl8コードを評価してみましょう。

fl8ソースコード
[]['constructor']['constructor']('
  return Math.sqrt(144);
')(0)

image.png

結果はMath.sqrt(144)というJavaScript式の結果である12です。

これまでに文字列をJavaScriptコードとして解釈し実行する機能を実装していないにもかかわらず、そのような処理が行われています。

危険なJavaScriptのFunction

この現象は、中間コード上のv_2に対応する[]['constructor']['constructor']の部分がFunctionというJavaScript関数を表し、それを呼び出すことでJavaScriptコードを表す文字列をJavaScript関数にコンパイルできることで起こります。

中間コード
const v_0 = [];
const v_1 = (v_0)[("constructor")];
const v_2 = (v_1)[("constructor")];
const v_3 = (v_2)(("\n  return Math.sqrt(144);\n"));
const v_4 = (v_3)((0));
(v_4)

image.png

image.png


Function関数は引数をJavaScriptコードとして解釈し、実行可能な関数にコンパイルする動作をします。

メカニズム

この問題は次のような要因によって起こります。

  1. []でJavaScriptの配列と同じものが得られる。
  2. 配列要素アクセサarray[index]indexに文字列が来ても同じ演算子を呼び出す。
  3. JavaScriptの配列はconstructorプロパティからFunction関数を辿れるようになっている。
  4. 検査なしで関数を呼び出してもよいということをコンパイル時に保証する仕組みが無い。
  5. fl8で扱う関数とJavaScriptの関数の区別がないので、fl8上からJavaScriptの関数も実行できる。

1の要因は、[]で得られる配列オブジェクトをオリジナルのものにして、constructorプロパティにアクセスしても何も得られないようにすることで解消することができます。しかし、実は配列の代わりに数値を使って1['constructor']['constructor']のように書いてもFunction関数が得られるので、結局根本的な解決のためには色々書き直さなければならなくなります。

2の要因は、配列要素アクセサarray[index]が常にそのままarray[index]というようなJavaScript中間コードにコンパイルされることで起こります。これは、例えばif (typeof index !== "number") throw new Error("Illegal array index: " + index);のような実行時型チェックによって数値を強制することで解消できます。

3の要因は、解消しようとするとJavaScript環境を改変しなければならないので現実的ではありません。

4の要因は、関数の安全性を保証しようとすると高度な型機能が必要となり、fl8の趣旨を外れてしまいます。

5の要因は、fl8上で呼び出し可能な関数にはデータ上の印を付けて、関数呼び出し演算子function(argument)がそのような関数しか呼び出せないようにすることで解消できます。しかし、fl7で実装されたそれは外部JavaScriptライブラリとの連携を不可能にし、fluorite言語の可能性を縮小させました。

対策

fl8では、実行時型チェックにより文字列での配列要素アクセスを禁止することで対応することにします。

また、fl8で扱うオブジェクトは何もprototypeとして継承しないようにして、obj['constructor']obj['__proto__']といった形で生のJavaScriptオブジェクトに簡単にアクセスする手段を排除します。

配列要素アクセサarray[index]に実行時型チェックを追加

配列要素アクセサarray[index]は、arrayが配列であり、indexが数値であることを実行時にチェックするようにします。

改変後
    env.registerOperatorHandler("get", "right_square", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      env.pushAliasFrame();
      const o2 = env.compile("get", token.argument[1]);
      env.popAliasFrame();
      const uid = env.getNextUid();
      return toOperation(
        o1.head +
        o2.head +
        // 中間コード上で配列とインデックスの型を実行時チェックする
        // どこで発生したエラーなのかも追加しておく
        // ↓ この2行が追加
        `if (!(${o1.body} instanceof Array)) throw new Error("" + ${o1.body} + " is not an Array " + ${JSON.stringify(loc(env, token))});\n` +
        `if (typeof ${o2.body} !== "number") throw new Error("" + ${o2.body} + " is not a number " + ${JSON.stringify(loc(env, token))});\n` +
        // ↑
        "const v_" + uid + " = " + o1.body + "[" + o2.body + "];\n",
        "(v_" + uid + ")"
      );
    });

テスト

まずは正しい入力を与えてみるテストです。

fl8
array : [500; 456];
index : 1;
array[index]

image.png


中間コード
let v_0;
const v_1 = [];
v_1[v_1.length] = (500);
v_1[v_1.length] = (456);
v_0 = (v_1);
let v_2;
v_2 = (1);
if (!((v_0) instanceof Array)) throw new Error("" + (v_0) + " is not an Array " + "(OnlineDemo,L:32,C:6)");
if (typeof (v_2) !== "number") throw new Error("" + (v_2) + " is not a number " + "(OnlineDemo,L:32,C:6)");
const v_3 = (v_0)[(v_2)];
(v_3)

変数v_0に配列を作り、変数v_2にインデックスを読み込み、それぞれ実行時に型チェックを行い、v_0[v_2]というアクセスを試みます。


この場合は!((v_0) instanceof Array)にもtypeof (v_2) !== "number"にも該当しないため、配列要素アクセスが行われた結果が出てきます。

結果
456

arrayが配列でない場合、そのようなエラーとなります。

image.png


indexが数値でない場合もエラーとなります。

image.png


これで任意コードが実行される問題は解決しました。

中間コードが肥大化する問題

ここで、次のfl8ソースコードから生成されるJavaScript中間コードを見てみます。

fl8
array : [[[[[12345]]]]];
array[0][0][0][0][0]

中間コード
let v_0;
const v_5 = [];
const v_4 = [];
const v_3 = [];
const v_2 = [];
const v_1 = [];
v_1[v_1.length] = (12345);
v_2[v_2.length] = (v_1);
v_3[v_3.length] = (v_2);
v_4[v_4.length] = (v_3);
v_5[v_5.length] = (v_4);
v_0 = (v_5);
if (!((v_0) instanceof Array)) throw new Error("" + (v_0) + " is not an Array " + "(OnlineDemo,L:31,C:6)");
if (typeof (0) !== "number") throw new Error("" + (0) + " is not a number " + "(OnlineDemo,L:31,C:6)");
const v_6 = (v_0)[(0)];
if (!((v_6) instanceof Array)) throw new Error("" + (v_6) + " is not an Array " + "(OnlineDemo,L:31,C:9)");
if (typeof (0) !== "number") throw new Error("" + (0) + " is not a number " + "(OnlineDemo,L:31,C:9)");
const v_7 = (v_6)[(0)];
if (!((v_7) instanceof Array)) throw new Error("" + (v_7) + " is not an Array " + "(OnlineDemo,L:31,C:12)");
if (typeof (0) !== "number") throw new Error("" + (0) + " is not a number " + "(OnlineDemo,L:31,C:12)");
const v_8 = (v_7)[(0)];
if (!((v_8) instanceof Array)) throw new Error("" + (v_8) + " is not an Array " + "(OnlineDemo,L:31,C:15)");
if (typeof (0) !== "number") throw new Error("" + (0) + " is not a number " + "(OnlineDemo,L:31,C:15)");
const v_9 = (v_8)[(0)];
if (!((v_9) instanceof Array)) throw new Error("" + (v_9) + " is not an Array " + "(OnlineDemo,L:31,C:18)");
if (typeof (0) !== "number") throw new Error("" + (0) + " is not a number " + "(OnlineDemo,L:31,C:18)");
const v_10 = (v_9)[(0)];
(v_10)

どう考えても長いです。しかも、今後string[index]で文字が得られるとかobject[key]でプロパティアクセスできるみたいな機能を追加するとどんどん長くなっていきます。


せめて次のようにしたいところです。

理想的な中間コードA
function arrayAccess(array, index, location) {
  if (!(array instanceof Array)) throw new Error("" + array + " is not an Array " + location);
  if (typeof index !== "number") throw new Error("" + index + " is not a number " + location);
  return array[index];
}

let v_0;
const v_5 = [];
const v_4 = [];
const v_3 = [];
const v_2 = [];
const v_1 = [];
v_1[v_1.length] = (12345);
v_2[v_2.length] = (v_1);
v_3[v_3.length] = (v_2);
v_4[v_4.length] = (v_3);
v_5[v_5.length] = (v_4);
v_0 = (v_5);
const v_6 = arrayAccess((v_0), (0), "(OnlineDemo,L:33,C:6)");
const v_7 = arrayAccess((v_6), (0), "(OnlineDemo,L:33,C:9)");
const v_8 = arrayAccess((v_7), (0), "(OnlineDemo,L:33,C:12)");
const v_9 = arrayAccess((v_8), (0), "(OnlineDemo,L:33,C:15)");
const v_10 = arrayAccess((v_9), (0), "(OnlineDemo,L:33,C:18)");
(v_10)

また、このarrayAccess関数の中身はfl8コンパイラのバージョンが変わらない限り変動しないため、中間コードの外に出したいところです。

理想的な中間コードB
// 中間コードはライブラリを受け取ったら実行する関数になっている
const main = (function(library) {
  let v_0;
  const v_5 = [];
  const v_4 = [];
  const v_3 = [];
  const v_2 = [];
  const v_1 = [];
  v_1[v_1.length] = (12345);
  v_2[v_2.length] = (v_1);
  v_3[v_3.length] = (v_2);
  v_4[v_4.length] = (v_3);
  v_5[v_5.length] = (v_4);
  v_0 = (v_5);
  const v_6 = library.arrayAccess((v_0), (0), "(OnlineDemo,L:33,C:6)");
  const v_7 = library.arrayAccess((v_6), (0), "(OnlineDemo,L:33,C:9)");
  const v_8 = library.arrayAccess((v_7), (0), "(OnlineDemo,L:33,C:12)");
  const v_9 = library.arrayAccess((v_8), (0), "(OnlineDemo,L:33,C:15)");
  const v_10 = library.arrayAccess((v_9), (0), "(OnlineDemo,L:33,C:18)");
  return (v_10);
});
// ↑↑↑↑ここまでが中間コード↑↑↑↑

// 別途読み込んで使いまわすライブラリ
const library = {
  arrayAccess(array, index, location) {
    if (!(array instanceof Array)) throw new Error("" + array + " is not an Array " + location);
    if (typeof index !== "number") throw new Error("" + index + " is not a number " + location);
    return array[index];
  }
};

// 中間コードにライブラリを与えることで初めて実行される
main(library)

配列要素アクセスをするたびに関数を呼び出して型チェックを行うのでオーバーヘッドが増えてしまいますが、記述の冗長さは改善された感じがあります。

中間コードの実行時にライブラリを与えるようにする

ライブラリを変数に格納し、関数呼び出し演算子が生成する中間コードをライブラリ関数を利用するように変更します。

Rootルールから見える場所に追加
  const library = {
    arrayAccess(array, index, location) {
      if (!(array instanceof Array)) throw new Error("" + array + " is not an Array " + location);
      if (typeof index !== "number") throw new Error("" + index + " is not a number " + location);
      return array[index];
    },
  };
改変後
    env.registerOperatorHandler("get", "right_square", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      env.pushAliasFrame();
      const o2 = env.compile("get", token.argument[1]);
      env.popAliasFrame();
      const uid = env.getNextUid();
      return toOperation(
        o1.head +
        o2.head +
        // ライブラリの関数を呼ぶように変更
        "const v_" + uid + " = library.arrayAccess(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });

上のまま実行しても中間コード上からlibraryが見えないため、libraryを受け取る関数で中間コード全体を囲うroot文脈ドメインを追加します。

root文脈ドメインでのコンパイル結果は、root挙動オブジェクトではなくJavaScript中間コードが直接文字列として返ってくることにします。

root文脈ドメインでの関数生成時には、ラムダ式arg -> formulaと同様に関数に名前を付けます。これでトップレベルで発生したエラーにも<root>という場所のヒントが与えられるようになりました。

customizeEnvironment内に追加
    env.registerCompilerHandler("root", (env, token, options) => {
      let operation;
      operation = env.tryCompile("get", token, options);
      if (operation !== null) {
        const label = `<root>${loc(env, token)}`;  // 関数名は<root>
        const uidSymbol = env.getNextUid();        // 関数名を入れる一時変数
        const uid = env.getNextUid();              // 関数を入れる一時変数
        return (
          // 関数名を生成
          "const v_" + uidSymbol + " = Symbol(" + JSON.stringify(label) + ");\n" +
          // 関数を生成
          "const v_" + uid + " = " + "{[v_" + uidSymbol + "]: function(library) {\n" +
          indent(
            operation.head +
            "return " + operation.body + ";\n"
          ) +
          "}}[v_" + uidSymbol + "];\n" +
          // 生成した関数を返す
          "(v_" + uid + ")"
        );
      }
      throw new Fluorite8CompileError("Unknown operator: root/" + token.type, env, token);
    });
改変後
Root     = _ main:Formula _ {
             const token = main;
             let code;                            // root文脈ドメインの戻り値はコード文字列になった
             try {
               const env = new Environment();
               env.setFile("OnlineDemo");
               customizeEnvironment(env);
               code = env.compile("root", main);  // 文脈ドメインをrootに
             } catch (e) {
               console.log(e);
               return ["CompileError: " + e, token];
             }
             let result;
             try {
               result = eval(code)(library);      // どこかで定義されているlibraryで呼び出す
             } catch (e) {
               console.log(e);
               return ["RuntimeError: " + e, code, token];
             }
             return [result, code, token];
           }

テスト

中間コードは全体がlibraryを受け取る関数生成で囲われるようになりました。配列要素アクセス時にはlibrary.arrayAccessが呼び出されています。

fl8
array : [12345];
array[0]
中間コード
const v_3 = Symbol("<root>(OnlineDemo,L:32,C:16)");
const v_4 = {[v_3]: function(library) {
  let v_0;
  const v_1 = [];
  v_1[v_1.length] = (12345);
  v_0 = (v_1);
  const v_2 = library.arrayAccess((v_0), (0), "(OnlineDemo,L:33,C:6)");
  return (v_2);
}}[v_3];
(v_4)

image.png


インデックスに文字列を指定するとエラーが発生します。

fl8
array : [12345];
array['0']

image.png

image.png


これで中間コードの肥大化が改善されました。

いくつかの演算子に実行時型チェックを追加

特定の型を想定した演算子や型によって挙動が変わる演算子に対して実行時型チェックを追加します。以下の演算子が該当します。

  • 三項演算子condition ? then : else
  • 加算演算子a + b
  • 減算演算子a - b
  • 乗算演算子a * b
  • 除算演算子a / b
  • べき乗演算子a ^ b
  • 正号演算子+number
  • 負号演算子-number
  • 長さ演算子$#array
  • 関数呼び出し演算子function(argument)
  • 配列要素アクセサarray[index] (対処済み)
libraryに追加
    checkNumber(value, location) {
      if (typeof value !== "number") throw new Error("" + value + " is not a number " + location);
    },
    add(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a + b;
    },
    sub(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a - b;
    },
    mul(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a * b;
    },
    div(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a / b;
    },
    pow(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return Math.pow(a, b);
    },
    toPositive(number, location) {
      if (typeof number !== "number") throw new Error("" + number + " is not a number " + location);
      return number;
    },
    toNegative(number, location) {
      if (typeof number !== "number") throw new Error("" + number + " is not a number " + location);
      return -number;
    },
    getLength(array, location) {
      if (!(array instanceof Array)) throw new Error("" + array + " is not an Array " + location);
      return array.length;
    },
    call(func, arg, location) {
      if (!(func instanceof Function)) throw new Error("" + func + " is not a Function " + location);
      return func(arg);
    },
改変後
    env.registerOperatorHandler("get", "ternary_question_colon", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const o3 = env.compile("get", token.argument[2]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head +
        "let v_" + uid + ";\n" +
        // ↓チェックを行うライブラリ関数
        "library.checkNumber(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");" +
        "if (" + o1.body + ") {\n" +
        indent(
          o2.head +
          "v_" + uid + " = " + o2.body + ";\n"
        ) +
        "} else {\n" +
        indent(
          o3.head +
          "v_" + uid + " = " + o3.body + ";\n"
        ) +
        "}\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + o2.head + "const v_" + uid + " = library.add(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "minus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + o2.head + "const v_" + uid + " = library.sub(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "asterisk", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + o2.head + "const v_" + uid + " = library.mul(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "slash", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + o2.head + "const v_" + uid + " = library.div(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "circumflex", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + o2.head + "const v_" + uid + " = library.pow(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "right_round", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      env.pushAliasFrame();
      const o2 = env.compile("get", token.argument[1]);
      env.popAliasFrame();
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + o2.head + "const v_" + uid + " = library.call(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + "const v_" + uid + " = library.toPositive(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_minus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + "const v_" + uid + " = library.toNegative(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_dollar_hash", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        // ↓ライブラリ関数を呼び出すように変更
        o1.head + "const v_" + uid + " = library.getLength(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });

これで型を制御できるようになりました。

もはや関数と関数を中置+で結合しても謎の文字列が2個連続したものになることはなく、エラーになります。

今後ライブラリ関数の中身を変えることによって、関数同士の「加算」を関数の合成にするといった挙動が簡単に追加できます。

まとめ

ここまでに出来上がったPEG.jsコードです。

**[開閉]**
{

  function loc(env, token) {
    return `(${env.getFile()},L:${token.location.start.line},C:${token.location.start.column})`;
  }

  class Fluorite8CompileError extends Error {
    constructor(message, env, token) {
      super(message + " " + loc(env, token));
      this.name = "Fluorite8CompileError";
      this.file = env.getFile();
      this.token = token;
    }
  }

  class Environment {

    constructor() {
      this._nextUid = 0;
      this._aliasFrame = Object.create(null);
      this._operatorRegistry = Object.create(null);
      this._compilerRegistry = Object.create(null);
      this._file = "anonymous";
      this._suggestedName = undefined;
    }

    getNextUid() {
      return this._nextUid++;
    }

    registerAlias(alias, handlerTable) {
      this._aliasFrame[alias] = handlerTable;
    }
    resolveAlias(alias) {
      return this._aliasFrame[alias];
    }
    pushAliasFrame() {
      this._aliasFrame = Object.create(this._aliasFrame);
    }
    popAliasFrame() {
      this._aliasFrame = Object.getPrototypeOf(this._aliasFrame);
    }

    registerOperatorHandler(domain, type, handler) {
      if (this._operatorRegistry[domain] === undefined) this._operatorRegistry[domain] = Object.create(null);
      this._operatorRegistry[domain][type] = handler;
    }
    registerCompilerHandler(domain, handler) {
      this._compilerRegistry[domain] = handler;
    }
    tryCompile(domain, token, options) {
      const handlerTable = this._operatorRegistry[domain];
      if (handlerTable === undefined) return null;
      const handler = handlerTable[token.type];
      if (handler === undefined) return null;

      const suggestedName = this._suggestedName;
      this._suggestedName = options.suggestedName;
      const operation = handler(this, token);
      this._suggestedName = suggestedName;

      return operation;
    }
    compile(domain, token, options = {}) {
      const handler = this._compilerRegistry[domain];
      if (handler === undefined) throw new Fluorite8CompileError("Unknown compiler: " + domain, this, token); 
      return handler(this, token, options);
    }

    setFile(file) {
      this._file = file;
    }
    getFile() {
      return this._file;
    }

    getSuggestedName() {
      if (this._suggestedName === undefined) return "anonymous";
      return this._suggestedName;
    }

  }

  const library = {
    arrayAccess(array, index, location) {
      if (!(array instanceof Array)) throw new Error("" + array + " is not an Array " + location);
      if (typeof index !== "number") throw new Error("" + index + " is not a number " + location);
      return array[index];
    },
    checkNumber(value, location) {
      if (typeof value !== "number") throw new Error("" + value + " is not a number " + location);
    },
    add(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a + b;
    },
    sub(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a - b;
    },
    mul(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a * b;
    },
    div(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a / b;
    },
    pow(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return Math.pow(a, b);
    },
    toPositive(number, location) {
      if (typeof number !== "number") throw new Error("" + number + " is not a number " + location);
      return number;
    },
    toNegative(number, location) {
      if (typeof number !== "number") throw new Error("" + number + " is not a number " + location);
      return -number;
    },
    getLength(array, location) {
      if (!(array instanceof Array)) throw new Error("" + array + " is not an Array " + location);
      return array.length;
    },
    call(func, arg, location) {
      if (!(func instanceof Function)) throw new Error("" + func + " is not a Function " + location);
      return func(arg);
    },
  };

  function customizeEnvironment(env) {

    function indent(code) {
      return "  " + code.replace(/\n(?!$)/g, "\n  ");
    }
    function toOperation(head/* string */, body/* string */) {
      return {head, body};
    }
    function toOperationSet(accept/* operationGet => operationRun */, suggestedName = undefined/* string */) {
      return {accept, suggestedName};
    }
    function toOperationArray(generate/* operationSet => operationRun */) {
      return {generate};
    }
    function toOperationRun(head/* string */) {
      return {head};
    }
    function registerDefaultCompilerHandler(domain) {
      env.registerCompilerHandler(domain, (env, token, options) => {
        let operation;
        operation = env.tryCompile(domain, token, options);
        if (operation !== null) return operation;
        throw new Fluorite8CompileError("Unknown operator: " + domain + "/" + token.type, env, token);
      });
    }

    env.registerCompilerHandler("root", (env, token, options) => {
      let operation;
      operation = env.tryCompile("get", token, options);
      if (operation !== null) {
        const label = `<root>${loc(env, token)}`;
        const uidSymbol = env.getNextUid();
        const uid = env.getNextUid();
        return (
          "const v_" + uidSymbol + " = Symbol(" + JSON.stringify(label) + ");\n" +
          "const v_" + uid + " = " + "{[v_" + uidSymbol + "]: function(library) {\n" +
          indent(
            operation.head +
            "return " + operation.body + ";\n"
          ) +
          "}}[v_" + uidSymbol + "];\n" +
          "(v_" + uid + ")"
        );
      }
      throw new Fluorite8CompileError("Unknown operator: root/" + token.type, env, token);
    });
    registerDefaultCompilerHandler("get");
    registerDefaultCompilerHandler("set");
    registerDefaultCompilerHandler("run");
    env.registerCompilerHandler("array", (env, token, options) => {
      let operation;
      operation = env.tryCompile("array", token, options);
      if (operation !== null) return operation;
      operation = env.tryCompile("get", token, options);
      if (operation !== null) return toOperationArray(oSet => oSet.accept(operation));
      throw new Fluorite8CompileError("Unknown operator: array/" + token.type, env, token);
    });

    env.registerOperatorHandler("get", "integer", (env, token) => toOperation("", "(" + parseInt(token.argument, 10) + ")"));
    env.registerOperatorHandler("get", "string", (env, token) => toOperation("", "(" + JSON.stringify(token.argument) + ")"));
    env.registerOperatorHandler("get", "identifier", (env, token) => {
      const handlerTable = env.resolveAlias(token.argument);
      if (handlerTable === undefined) throw new Fluorite8CompileError("Unknown identifier: " + token.argument, env, token);
      const handler = handlerTable["get"];
      if (handler === undefined) throw new Fluorite8CompileError("Unreadable identifier: " + token.argument, env, token);
      return handler(env);
    });
    env.registerOperatorHandler("get", "round", (env, token) => {
      env.pushAliasFrame();
      const o1 = env.compile("get", token.argument[0], {
        suggestedName: env.getSuggestedName(),
      });
      env.popAliasFrame();
      return o1;
    });
    env.registerOperatorHandler("get", "square", (env, token) => {
      const o1 = env.compile("array", token.argument[0]);
      const uid = env.getNextUid();
      const o2 = o1.generate(toOperationSet(o => toOperationRun(
        o.head +
        "v_" + uid + "[v_" + uid + ".length] = " + o.body + ";\n"
      )));
      return toOperation(
        "const v_" + uid + " = [];\n" +
        o2.head,
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "empty_square", (env, token) => {
      const uid = env.getNextUid();
      return toOperation(
        "const v_" + uid + " = [];\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = library.toPositive(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_minus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = library.toNegative(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_dollar_hash", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = library.getLength(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "right_round", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      env.pushAliasFrame();
      const o2 = env.compile("get", token.argument[1]);
      env.popAliasFrame();
      const uid = env.getNextUid();
      return toOperation(
        o1.head + o2.head + "const v_" + uid + " = library.call(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "right_square", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      env.pushAliasFrame();
      const o2 = env.compile("get", token.argument[1]);
      env.popAliasFrame();
      const uid = env.getNextUid();
      return toOperation(
        o1.head +
        o2.head +
        "const v_" + uid + " = library.arrayAccess(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + o2.head + "const v_" + uid + " = library.add(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "minus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + o2.head + "const v_" + uid + " = library.sub(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "asterisk", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + o2.head + "const v_" + uid + " = library.mul(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "slash", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + o2.head + "const v_" + uid + " = library.div(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "circumflex", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + o2.head + "const v_" + uid + " = library.pow(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "ternary_question_colon", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const o3 = env.compile("get", token.argument[2]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head +
        "let v_" + uid + ";\n" +
        "library.checkNumber(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");" +
        "if (" + o1.body + ") {\n" +
        indent(
          o2.head +
          "v_" + uid + " = " + o2.body + ";\n"
        ) +
        "} else {\n" +
        indent(
          o3.head +
          "v_" + uid + " = " + o3.body + ";\n"
        ) +
        "}\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "minus_greater", (env, token) => {
      const name = token.argument[0].argument;
      const uidBody = env.getNextUid();
      env.pushAliasFrame();
      env.registerAlias(token.argument[0].argument, {
        get: (env, token) => toOperation("", "(v_" + uidBody + ")"),
      });
      const operationBody = env.compile("get", token.argument[1]);
      env.popAliasFrame();
      const label = `${env.getSuggestedName()}${loc(env, token)}`;
      const uidSymbol = env.getNextUid();
      const uid = env.getNextUid();
      return toOperation(
        "const v_" + uidSymbol + " = Symbol(" + JSON.stringify(label) + ");\n" +
        "const v_" + uid + " = " + "{[v_" + uidSymbol + "]: function(v_" + uidBody + ") {\n" +
        indent(
          operationBody.head +
          "return " + operationBody.body + ";\n"
        ) +
        "}}[v_" + uidSymbol + "];\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "semicolons", (env, token) => {
      const heads = [];
      for (let i = 0; i < token.argument.length - 1; i++) {
        const operation = env.compile("run", token.argument[i]);
        heads.push(operation.head);
      }
      const operation = env.compile("get", token.argument[token.argument.length - 1]);
      return toOperation(
        heads.join("") +
        operation.head,
        operation.body
      );
    });

    env.registerOperatorHandler("set", "identifier", (env, token) => {
      const handlerTable = env.resolveAlias(token.argument);
      if (handlerTable === undefined) throw new Fluorite8CompileError("Unknown identifier: " + token.argument, env, token);
      const handler = handlerTable["set"];
      if (handler === undefined) throw new Fluorite8CompileError("Readonly identifier: " + token.argument, env, token);
      return handler(env);
    });

    env.registerOperatorHandler("array", "semicolons", (env, token) => {
      return toOperationArray(oSet => toOperationRun(
        token.argument.map(token2 => env.compile("array", token2).generate(oSet).head).join("")
      ));
    });

    env.registerOperatorHandler("run", "colon", (env, token) => {
      const name = token.argument[0].argument;
      const uid = env.getNextUid();
      env.registerAlias(name, {
        get: (env, token) => toOperation("", "(v_" + uid + ")"),
        set: (env, token) => toOperationSet(o => toOperationRun(o.head + "v_" + uid + " = " + o.body + ";\n"), name),
      });
      const operation = env.compile("get", token.argument[1], {
        suggestedName: name,
      });
      return toOperationRun(
        "let v_" + uid + ";\n" +
        operation.head +
        "v_" + uid + " = " + operation.body + ";\n"
      );
    });
    env.registerOperatorHandler("run", "equal", (env, token) => {
      const operationSetLeft = env.compile("set", token.argument[0]);
      const operationGetRight = env.compile("get", token.argument[1], {
        suggestedName: operationSetLeft.suggestedName,
      });
      return toOperationRun(
        operationSetLeft.accept(operationGetRight).head
      );
    });

    env.registerAlias("PI", {
      get: (env, token) => toOperation("", "(" + Math.PI + ")"),
    });

  }

  function token(type, argument, location) {
    return {type, argument, location};
  }

}
Root     = _ main:Formula _ {
             const token = main;
             let code;
             try {
               const env = new Environment();
               env.setFile("OnlineDemo");
               customizeEnvironment(env);
               code = env.compile("root", main);
             } catch (e) {
               console.log(e);
               return ["CompileError: " + e, token];
             }
             let result;
             try {
               result = eval(code)(library);
             } catch (e) {
               console.log(e);
               return ["RuntimeError: " + e, code, token];
             }
             return [result, code, token];
           }
Formula  = Semicolons
Semicolons = head:Lambda tail:(_ (";" { return location(); }) _ Lambda)* {
             if (tail.length == 0) return head;
             return token("semicolons", [head, ...tail.map(s => s[3])], tail[0][1]);
           }
Lambda   = head:(If _ (
             "->" { return ["minus_greater", location()]; }
           / ":" { return ["colon", location()]; }
           / "=" { return ["equal", location()]; }
           ) _)* tail:If {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][2][0], [head[i][0], result], head[i][2][1]);
             }
             return result;
           }
If       = head:Add _ operator:("?" { return location(); }) _ body:If _ ":" _ tail:If {
             return token("ternary_question_colon", [head, body, tail], operator);
           }
         / Add
Add      = head:Term tail:(_ (
             "+" { return ["plus", location()]; }
           / "-" { return ["minus", location()]; }
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1][0], [result, tail[i][3]], tail[i][1][1]);
             }
             return result;
           }
Term  = head:Left tail:(_ (
             "*" { return ["asterisk", location()]; }
           / "/" { return ["slash", location()]; }
           ) _ Left)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1][0], [result, tail[i][3]], tail[i][1][1]);
             }
             return result;
           }
Left     = head:((
             "+" { return ["left_plus", location()]; }
           / "-" { return ["left_minus", location()]; }
           / "$#" { return ["left_dollar_hash", location()]; }
           ) _)* tail:Pow {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][0][0], [result], head[i][0][1]);
             }
             return result;
           }
Pow      = head:Right _ operator:(
             "^" { return ["circumflex", location()]; }
           ) _ tail:Left {
             return token(operator[0], [head, tail], operator[1]);
           }
         / Right
Right    = head:Factor tail:(_ (
             "(" _ main:Formula _ ")" { return ["right_round", [main], location()] }
           / "[" _ main:Formula _ "]" { return ["right_square", [main], location()] }
           ))* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1][0], [result, ...tail[i][1][1]], tail[i][1][2]);
             }
             return result;
           }
Factor   = Integer
         / String
         / Identifier
         / Brackets
Integer  = main:$[0-9]+ {
             return token("integer", main, location());
           }
String   = "'" main:(
             [^'\\]
           / "\\" main:. { return main; }
           )* "'" {
             return token("string", main.join(""), location());
           }
Identifier = main:$([a-zA-Z_] [a-zA-Z0-9_]*) {
             return token("identifier", main, location());
           }
Brackets = main:(
             "(" _ main:Formula _ ")" { return ["round", [main], location()]; }
           / "[" _ main:Formula _ "]" { return ["square", [main], location()]; }
           / "[" _ "]" { return ["empty_square", [], location()]; }
           ) {
             return token(main[0], main[1], main[2]);
           }
_        = [ \t\r\n]*

この時点で次の特徴があります。

  • ソースコードから構文木の生成
  • 構文木から中間コードの生成
  • 中間コードの評価
  • 副作用を持つ演算の適切な順序での実行
  • エラー出力の改善
  • トークンの文脈の管理
  • 識別子の文脈の管理
  • トークンの出現場所の管理
  • ソースファイル名の管理
  • 関数名の推測 (改善)
  • 文脈ドメインごとのコンパイラの管理
  • 実行時ライブラリ (新規)
  • スペース
  • 識別子
    • 組み込み定数 (ドメイン:get
      • PI
    • 引数 (ドメイン:get
    • 変数 (ドメイン:get set
  • getドメイントークン
    • 整数リテラル123
    • 文字列リテラル'string' (新規)
    • 識別子identifier
    • 丸括弧(formula)
    • 空配列初期化子[]
    • 配列初期化子[values]
    • 関数呼び出しfunction(argument) (改善)
    • 配列要素アクセサarray[index] (改善)
    • べき乗a ^ b (改善)
    • 符号 +a -a (改善)
    • 長さ演算子$#array (改善)
    • 加減乗除 a + b a - b a * b a / b (改善)
    • 三項演算子cond ? then ? else (改善)
    • ラムダ式arg -> formula
    • ;
  • setドメイントークン
    • 識別子 identifier
  • arrayドメイントークン
    • 配列要素区切り;
  • runドメイントークン
    • 変数宣言variable : value
    • 代入acceptor = value

今回は文字列の追加を行い、それに伴って発生した型に関する問題を解決するために実行時ライブラリの概念を追加し、型チェックを行うようにしました。

次回→

0
0
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
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?