fluorite-8 実装の軌跡 Part 1 背景とPEG.jsの基礎

背景

fluorite-7について

fluorite-7は、2020年2月あたりから実装および公開が進められている創作プログラミング言語です。

fluorite-7の文書化が進んでいない

fluorite-7の始まりはTwitterのネタであったため、かなり長い間、非公開の場で開発が進められていました。

fluorite-7はのちに公開状態となりましたが、公開前に作られた機能の大半は文書化されていません。そして、文書化は実装に比べて地道で大変な作業となるので、あまり行われていません。

fluorite-7の現行バージョン（2020年11月1日）には、ソースコードにだけ書かれた機能が多数存在します。

臭いものに蓋

fluorite-7は次のような問題を抱えており、フルオライト財団はfluorite-7の文書化に苦戦しています。

• ソースファイルが5000行以上あり、非常に読みづらい。
• 後付けの機能によって参照関係がごちゃごちゃでリファクタリングが難しい。
• 後方互換性のために不条理な仕様を維持しなければならない。

フルオライト財団は、fluorite言語シリーズを世に広めるためにfluorite-7の開発と公開を行っている今考えた架空の組織です。

文書化ができないと公開を進めていくうえで困る。そこで、フルオライト財団はfluorite-8（fl8）の開発に乗り出しました。

fluorite-8は初期段階から実装過程を解説することで、積極的にfluorite言語シリーズというミームの種を蒔いていこうという方針で、この記事が作られました。

また、この実装の軌跡がインターネット上でアクセスできる「小規模なプログラミング言語の実装過程の具体例」として残り、そこからなんかなれば幸いです。

回の一覧

• Part 1　背景とPEG.jsの基礎
• Part 2　中間言語と四則演算
• Part 3　構文木の経由と符号
• Part 4　関数と識別子名管理
• Part 5　変数の宣言と参照
• Part 6　代入文と文脈
• Part 7　エラー発生位置の出力
• Part 8　配列と文脈リダイレクション
• Part 9　文字列と実行時ライブラリ
• Part 10　静的型と静的オーバーロード

開発環境

• PEG.js 0.10.0

PEG.js

Web上で自作の文法を表現できます。

暫くこのオンライン版を使います。

• https://pegjs.org/online

PEG.jsの使い方

PEGは正規表現みたいなやつのちょっと違うやつ

PEGとは、正規表現みたいなやつのちょっと違うやつです。

専門的なことはともかく、Perlの正規表現みたいなことができます。

例えば、

"100-1234" =~ /^[0-9][0-9][0-9]-[0-9][0-9][0-9][0-9]$/

というPerl正規表現があった場合、PEG.jsでは、

郵便番号 = [0-9] [0-9] [0-9] "-" [0-9] [0-9] [0-9] [0-9]

のように記述できます。

文法に違反した文字列を与えた場合は次のようになります。

郵便番号という文法は3文字と4文字の数字の部分に別れていますが、100-12345という入力は後半が5文字あり、想定された「文字列の終端」が存在しなかったため、構文エラーになりました。

文法にマッチした場合、右の中段の部分が薄緑になります。

ルールの一部分を分離・再利用できる

郵便番号 = [0-9] [0-9] [0-9] "-" [0-9] [0-9] [0-9] [0-9]

というルールは、[0-9]という文字列が何度も出てきて少々冗長です。あとから16進数に変えたくなった場合に、

郵便番号 = [0-9A-Fa-f] [0-9A-Fa-f] [0-9A-Fa-f] "-" [0-9A-Fa-f] [0-9A-Fa-f] [0-9A-Fa-f] [0-9A-Fa-f]

のように7か所も改変しなければなりません。

そこで、

郵便番号 = Number Number Number "-" Number Number Number Number
Number = [0-9]

のように書くことで、[0-9]という文字列を1か所に分離できました。これで後から16進数にしたい場合もコピペ地獄に悩まされずに済みます。

オンライン版PEG.jsでは、一番上に書かれたルールが主要なルールとして使われます。

入れ子括弧

次の文法を見てみましょう。

Formula  = Integer / Brackets
Integer  = [0-9]+
Brackets = "(" Formula ")"

Formulaは式です。式は整数と括弧のどちらかです。
Integerは1文字以上の数字の塊、つまり整数です。
Bracketsは括弧です。括弧の中には式が入ります。

この文法は0組以上の丸括弧で囲われた整数にマッチします。

キャッシュの使用をオンに

ここで再帰的にルールをループするようなコードが書けるようになりましたが、そのようなコードはキャッシュを使わなければ構文解析が劇的に重くなります。

以降、オンライン版PEG.jsはUse results cacheをオンにして使用してください。

足し算

前節の文法に足し算を追加してみましょう。

Formula  = Term ("+" Term)*
Term     = Integer / Brackets
Integer  = [0-9]+
Brackets = "(" Formula ")"

Termは項です。項は整数か括弧です。
Formula（式）が変わりました。式は1個の項の後に、0個以上の項が+記号により連結されたものです。

この文法は((1+2+345)+((67)))+89のようなごく単純な数式にマッチします。

計算の結果を出したい！

折角数式が入力できるようになったので、計算をしてみたいと思います。

このOutput欄には現在構文木が見えていますが、PEG.jsではこの部分の挙動を自由に実装できます。

数字の配列を数値にする

今は500という整数ですら、数字が3個集まった配列として処理されています。それは、Integer = [0-9]+の[0-9]の部分が数字1個の文字列を表し、+がそれが1個以上集まった配列を表すからです。[0-9]+は文字列の配列です。

PEG.jsでは、文法要素の左に名前:を付け、文法要素列の右端に{ return 式; }と書くことで、データを加工することができます。例えば、各数字で構成された配列ではなく、各数字を|で結合した文字列を返すようにするには、次のようにします。

Formula  = Term ("+" Term)*
Term     = Integer / Brackets
Integer  = main:[0-9]+ {
             return main.join("|");
           }
Brackets = "(" Formula ")"

[0-9]+は「「1文字の数字で出来た文字列」の配列」ですが、それをmainという名前に割り当てました。式中でその文字列の配列をmainという名前で受け取り、演算を行って、main:[0-9]+部分が表す値として返すことができます。Integerのデータ型は、文字列の配列から文字列に変わりました。

---

数値化という特殊な計算を行うには、この式部分を少し変えれば良いわけです。

Formula  = Term ("+" Term)*
Term     = Integer / Brackets
Integer  = main:[0-9]+ {
             return parseInt(main.join(""), 10);
           }
Brackets = "(" Formula ")"

---

また、joinするのが面倒なので、代わりにmain:$[0-9]+とすることで代用できます。これはmain:($([0-9]+))と同じ意味です。前置$は、付けられた文法要素のデータをその文法要素にマッチした部分の文字列にします。

Formula  = Term ("+" Term)*
Term     = Integer / Brackets
Integer  = main:$[0-9]+ {
             return parseInt(main, 10);
           }
Brackets = "(" Formula ")"

括弧を無機能化する

括弧のルールBrackets = "(" Formula ")"を見ると、文法要素が3個並んでいます。このままでは次のように3要素の配列になります。

欲しいのは中央部だけなので、中央部に名前を付けて取り出してみましょう。

Formula  = Term ("+" Term)*
Term     = Integer / Brackets
Integer  = main:$[0-9]+ {
             return parseInt(main, 10);
           }
Brackets = "(" main:Formula ")" {
             return main;
           }

見事、括弧が無視されるようになりました。

足し算を行う

Formula = Term ("+" Term)*の部分の話です。

ここでは、

Formula  = head:Term tail:("+" Term)* {
             何か
           }

に何かを入れて各Termの和を返したいです。しかし、困ったことにTermは数値が来るとは限りません。Term = Integer / Bracketsが示すように、IntegerもしくはBracketsのどちらかのデータがやってきます。Integerは必ず数値を返すのでいいですが、Bracketsの値はFormulaに対応しています。

逆に言うと、Formulaが常に数値を返すならば、Termも常に数値を返すのです！

Formula  = head:Term tail:("+" Term)* {
             return 0;
           }
Term     = Integer
         / Brackets
Integer  = main:$[0-9]+ {
             return parseInt(main, 10);
           }
Brackets = "(" main:Formula ")" {
             return main;
           }

これでTermは何があっても数値だけがやってきます。Formulaの右辺にあるheadも数値です。tail:("+" Term)*は、次のようなデータ構造になっています。

[
  [
    "+",
    数値
  ],
  ...
]

ということは、headをまず変数に格納して、その変数にtailの各要素の添え字1の要素をすべて加算していけば、その変数は最終的に和を表すことになります。

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

見事計算が出来ました！同じ式をGoogle検索に突っ込むと同じ値が帰ってきます。

スペースを許容したい！

スペースを入れられるということは、トークンとトークンの間に「任意個の空白系文字」を追加してもよいという規則になります。「任意個の空白系文字」はPEG.jsの記法で表すと_ = [ \t\r\n]*のようになります。これを、「トークンとトークンの間」に1個1個差し込んでいきましょう。

ここでいうトークンは物理的に存在する概念ではなく、人間が「この文字の塊は1個のトークンにしたいなぁ」と思ったら、それがトークンです。

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]*

FormulaはTerm+Term+Termのようなルールです。+演算子とTermの間にはスペースが入ってもよいため、ここに_を追加します。これにより、tailのデータ構造が変わり、result = result + tail[i][3]に添え字部分が変わりました。

Termはそれ自体のルール中にトークンが連続する構造がないため、スペースを入れる場所はありません。/はどちらでもよいという意味なので、/の片側に注目する際は他方の項を無視して考えます。

Integerはそれ全体で一つのトークンと解釈したいので、数字と数字の間にスペースは許容（するようにもできるけど）しません。

Bracketsは左右括弧という2個のトークンがあり、main部分とはトークンが分裂しています。なのでその間に_を入れます。

更に、Rootというルールを一番上に追加し、式全体の前後にも空白を許容するようにしました。

これで、自由にスペースや改行が入れられるようになりました。

この章のまとめ

ここまでで、オンライン版PEG.jsのデフォルト画面に出ているサンプル文法から減算・乗算・除算を除いたものと同等の文法が出来ました。

• https://pegjs.org/online

まとめ

• 前作fluorite-7は拡張の限界が見えてきた
• fluorite-8は実装の軌跡も資料として公開していきたい
• PEG.jsの基礎的な使い方を解説した
• fluorite-8の実装の話はまだ出てきてない

次回→