More than 3 years have passed since last update.

fluorite-8　実装の軌跡　Part 2　中間言語と四則演算

fluorite-8

Last updated at 2020-11-07Posted at 2020-11-03

初回

←前回

インタプリタからコンパイラ（トランスコンパイラ）に

目標

前回ラストのpegjsコードは、実行すると機械語や中間コードなどにコンパイルされた何かではなく、計算結果が直接帰ってきます。

**[開閉]**

Root     = _ main:Formula _ {
             return main;
           }
Formula  = head:Term tail:(_ "+" _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = result + tail[i][3];
             }
             return result;
           }
Term     = Integer
         / Brackets
Integer  = main:$[0-9]+ {
             return parseInt(main, 10);
           }
Brackets = "(" _ main:Formula _ ")" {
             return main;
           }
_        = [ \t\r\n]*

柔軟さや実装の簡単さ的にはこれでよいですが、この方法でプログラミング言語を実装していくと、経験的に色々と悩まされることになります。これを解決するために、パーサの挙動をインタプリタ型からコンパイラ型に変更します。

目標としては、

入力

100 + 20 * 3 ^ 5

というfluorite-8コードを入力したら、

中間コード

((100) + ((20) * (Math.pow((3), (5)))))

というJavaScriptコードが出てきてくれたら嬉しいです。

中間言語としてJavaScriptを生成する利点は次のようなものです。

コンパイル処理が多少重くても実行速度はそれに影響されない。
中間コード自体はJavaScriptと同じ速度で実行できる。
evalで簡単に実行できる。
コンパイル結果を文字列として自然に保存できる。
コンパイル済みのコードを一般的なJavaScriptから直接呼び出しできる。
文字列を結合するだけで生成できる。
変数や関数を生成する命令が簡潔に記述できる。
JavaScriptの関数を呼び出せる。
一応人力で読める。

そこで、中間言語にコンパイルして、それを実行するようにしてみます。

コンパイラにした

できました。

Root     = _ main:Formula _ {
             return [eval(main), main];
           }
Formula  = head:Term tail:(_ "+" _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = "(" + result + " + " + tail[i][3] + ")";
             }
             return result;
           }
Term     = Integer
         / Brackets
Integer  = main:$[0-9]+ {
             return "(" + parseInt(main, 10) + ")";
           }
Brackets = "(" _ main:Formula _ ")" {
             return main;
           }
_        = [ \t\r\n]*

入力

12 + (34 + ((5)))

というfluorite-8コードを入力したら、

中間コード

((12) + ((34) + (5)))

という文字列が得られました。

変更箇所

Integerにおいて、
return parseInt(main, 10);が
return "(" + parseInt(main, 10) + ")";になりました。

数値は文字列化され、括弧で囲まれました。これで数値からJavaScriptコードを表す文字列になりました。Integerは、先頭と末尾が( )であるJavaScriptコード断片である文字列です。ちなみにわざわざ文字列を数値化して文字列化する理由は、先頭のゼロの扱いが異なるためです。

Formulaにおいて、
result = result + tail[i][3];が
result = "(" + result + " + " + tail[i][3] + ")";になりました。

Formulaも先頭と末尾が( )であるJavaScriptコード断片である文字列です。よって、Termもそういうデータなので、resultもtail[i][3]もそういうデータです。"(" + result + " + " + tail[i][3] + ")"部分は、((何か) + (何か))という形の文字列になるということになります。

Rootが中間コードとその実行結果を返すように変わりました。

減算の追加

目標

現状のFormula

現状

Formula  = head:Term tail:(_ "+" _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = "(" + result + " + " + tail[i][3] + ")";
             }
             return result;
           }

は+演算子しか受け付けません。

これを、-演算子を入力したら中間コード側にも-演算子が現れるようにしたいと思います。

戦略

減算を受け入れるには、以下の変更が必要です。

演算子定義の部分が+でも-でもマッチするようにする。
どちらにマッチしたかで出力を変える。

1を満たすには、1行目の"+"が("+" / "-")となればよいです。

2を満たすには、4行目の" + "が、tail[i][1]の値によって変わるようになっていればよいです。

実装

Formula  = head:Term tail:(_ (
             "+"
           / "-"
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               let operator;
               if (tail[i][1] === "+") operator = "+";
               if (tail[i][1] === "-") operator = "-";
               result = "(" + result + " " + operator + " " + tail[i][3] + ")";
             }
             return result;
           }

これで減算に対応しました。

乗除算の追加

目標

ここまでで+ -演算子が実装されました。さらに* /演算子も実装したいと思います。

乗除算は加減算よりも優先的に結合し、項を作ります。

戦略

ここまでのPEG.jsコードはこれです。

現状

Root     = _ main:Formula _ {
             return [eval(main), main];
           }
Formula  = head:Term tail:(_ (
             "+"
           / "-"
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               let operator;
               if (tail[i][1] === "+") operator = "+";
               if (tail[i][1] === "-") operator = "-";
               result = "(" + result + " " + operator + " " + tail[i][3] + ")";
             }
             return result;
           }
Term     = Integer
         / Brackets
Integer  = main:$[0-9]+ {
             return "(" + parseInt(main, 10) + ")";
           }
Brackets = "(" _ main:Formula _ ")" {
             return main;
           }
_        = [ \t\r\n]*

目標を達成するには、次のように定義を変えればよいです。

現状

Termは、「IntegerもしくはBrackets」である。

↓

改変後

Termは、「IntegerもしくはBrackets」もしくは複数のそれらが1個以上の「"*"もしくは"/"」で結合されたものである。

より簡単にいうと、

改変後

Termは、1個以上の「IntegerもしくはBrackets」が「"*"もしくは"/"」で結合されたものである。

より実装内容に沿った言い方をすると、

改変後

Termは、1個のFactorの後に、0個以上の「「"*"もしくは"/"」およびFactor」が続いたものである。
Factorは、IntegerもしくはBracketsである。

となります。

実装

できました。

Root     = _ main:Formula _ {
             return [eval(main), main];
           }
Formula  = head:Term tail:(_ (
             "+"
           / "-"
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               let operator;
               if (tail[i][1] === "+") operator = "+";
               if (tail[i][1] === "-") operator = "-";
               result = "(" + result + " " + operator + " " + tail[i][3] + ")";
             }
             return result;
           }
Term  = head:Factor tail:(_ (
             "*"
           / "/"
           ) _ Factor)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               let operator;
               if (tail[i][1] === "*") operator = "*";
               if (tail[i][1] === "/") operator = "/";
               result = "(" + result + " " + operator + " " + tail[i][3] + ")";
             }
             return result;
           }
Factor   = Integer
         / Brackets
Integer  = main:$[0-9]+ {
             return "(" + parseInt(main, 10) + ")";
           }
Brackets = "(" _ main:Formula _ ")" {
             return main;
           }
_        = [ \t\r\n]*

(53 + 42 * 86 / 10 / 48 - 29 * 48) / (7 - (8 + 9) * 10) * 86

オペレータ定義を1行にまとめたい

目標

現状の演算子定義

現状

Formula  = head:Term tail:(_ (
             "+"
           / "-"
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               let operator;
               if (tail[i][1] === "+") operator = "+";
               if (tail[i][1] === "-") operator = "-";
               result = "(" + result + " " + operator + " " + tail[i][3] + ")";
             }
             return result;
           }

は、以下の点で不便です。

演算子を追加する度に離れた2か所の改変が必要。
(Math.pow(a, b))のような凝った順序でトークンを挿入する演算を出力できない。

そこで、これを解決したいと思います。

戦略

2行目・3行目は現在記号1文字で構成された文字列を返しますが、これを2個のJSコードを取ってJSコードを返す関数が返るようにすればすべてうまくいきます。

実装

Formula  = head:Term tail:(_ (
             "+" { return (a, b) => "(" + a + " + " + b + ")"; }
           / "-" { return (a, b) => "(" + a + " - " + b + ")"; }
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = tail[i][1](result, tail[i][3]);
             }
             return result;
           }
Term  = head:Factor tail:(_ (
             "*" { return (a, b) => "(" + a + " * " + b + ")"; }
           / "/" { return (a, b) => "(" + a + " / " + b + ")"; }
           ) _ Factor)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = tail[i][1](result, tail[i][3]);
             }
             return result;
           }

これで演算子の追加が非常に簡単なものとなりました。

べき乗演算子`^`の追加

目標

a ^ bというfl8コードがMath.pow(a, b)というJavaScriptコードになる。
べき乗は乗除算よりも結合優先度が高い。
右優先結合である。

戦略

安直な実装は次のものです。これは結合優先度の条件は満たしますが、右優先結合の条件を満たしません。

安直な実装

Pow  = head:Factor tail:(_ (
             "^" { return (a, b) => "(Math.pow(" + a + ", " + b + "))"; }
           ) _ Factor)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = tail[i][1](result, tail[i][3]);
             }
             return result;
           }

なぜ左優先結合（1+2+3+4が((1+2)+3)+4と解釈される）になるのかというと、最初に変数にheadを入れて、それをtailの先頭とくっつけていくからです。これに従って結合すると、構文木が左側に向かって深く伸びていきます。

なので、定義を以下のように変えます。

安直な実装

Powは、1個のFactorの後に、0個以上の「べき乗演算子およびFactor」が続いたものである。

↓

改変後

Powは、0個以上の「Factorおよびべき乗演算子」の後に、1個のFactorが続いたものである。

これに従って処理をtailに対してheadの末尾から順番にくっつけていくように改変すると、右優先結合の演算子の実装となります。

実装

できました。

Pow      = head:(Factor _ (
             "^" { return (a, b) => "(Math.pow(" + a + ", " + b + "))"; }
           ) _)* tail:Factor {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = head[i][2](head[i][0], result);
             }
             return result;
           }

10000 * 4 ^ 3 ^ 2 * 2 + 4 ^ 2

まとめ

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

**[開閉]**

Root     = _ main:Formula _ {
             return [eval(main), main];
           }
Formula  = head:Term tail:(_ (
             "+" { return (a, b) => "(" + a + " + " + b + ")"; }
           / "-" { return (a, b) => "(" + a + " - " + b + ")"; }
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = tail[i][1](result, tail[i][3]);
             }
             return result;
           }
Term  = head:Pow tail:(_ (
             "*" { return (a, b) => "(" + a + " * " + b + ")"; }
           / "/" { return (a, b) => "(" + a + " / " + b + ")"; }
           ) _ Pow)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = tail[i][1](result, tail[i][3]);
             }
             return result;
           }
Pow      = head:(Factor _ (
             "^" { return (a, b) => "(Math.pow(" + a + ", " + b + "))"; }
           ) _)* tail:Factor {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = head[i][2](head[i][0], result);
             }
             return result;
           }
Factor   = Integer
         / Brackets
Integer  = main:$[0-9]+ {
             return "(" + parseInt(main, 10) + ")";
           }
Brackets = "(" _ main:Formula _ ")" {
             return main;
           }
_        = [ \t\r\n]*

JavaScript中間コードを生成するようにすると色々恩恵があるので、それを採用した。
減算のような同じ結合優先度の演算子を追加するには、-演算子を受理するようにして、それによって出力内容を変えればよい。
乗除算のような異なる結合優先度の演算子を追加するには、ルールを増やせばよい。
演算子が演算子を表す文字列ではなく関数を返すようにして、演算子の扱いを簡単にした。
べき乗のような右優先結合の演算子を追加するには、演算子の定義を前後逆にすればよい。

ここまでで、加減乗除べき乗括弧が入力できる言語のJavaScriptへのトランスコンパイラが出来ました。

次回→

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

fluorite-8 実装の軌跡 Part 2 中間言語と四則演算

インタプリタからコンパイラ（トランスコンパイラ）に

目標

コンパイラにした

変更箇所

減算の追加

目標

戦略

実装

乗除算の追加

目標

戦略

実装

オペレータ定義を1行にまとめたい

目標

戦略

実装

べき乗演算子^の追加

目標

戦略

実装

まとめ

fluorite-8　実装の軌跡　Part 2　中間言語と四則演算

べき乗演算子`^`の追加