プログラミング言語の自作を軽く体験してみるワークショップ #言語処理系

(この記事は2022/3/27開催のイベント『かごもく #54 プログラム言語を作るかもしれない?』)の資料です。

プログラミング言語作成の概略

プログラミング言語はざっくり以下のような流れで動いています。
言語によっては4が無かったり、もっと細かく別れてたり色々です。

1.字句解析
プログラムのソースコードをトークンという最小単位に分割するフェイズ。

2.構文解析
分割されたトークンの配列を抽象構文木に分割するフェイズ。

3.意味解析
抽象構文木の意味を解析するフェイズ。インタープリタ言語なら動作を行う。
コンパイラ言語なら、データ型の整合性をチェックや中間コードへの変換などを行う。

4.コード生成
機械語などに変換するフェイズ。

今日解説すること

全部やるのは大変なので、今日は面白いところだけつまみ食いします。
つまみ食いするだけでも動くものはちゃんと作れます。(パフォーマンスは犠牲になりますが…)

やるのは以下の２つです。

PEG(字句解析 + 構文解析)
PEG(Parsing Expression Grammar)はバッカス・ナウア記法っぽい記法で字句解析と構文解析を一度にやってくれる一石二鳥な文法です。ほとんどの言語でPEGのライブラリが提供されています。
本格的なプログラミング言語の実装には使われてないイメージでしたが、Pythonは3.9からPEGで実装されるようになったようです。
素朴なインタープリタ(意味解析)
実用的なプログラミング言語を作るならLLVM向けのバイトコードを吐くのが良いのだと思いますが、今回はサクッとエッセンスだけ味わいたいので、素朴なインタープリタを作ってみます。

PEGにコードを突っ込む → 抽象構文木が吐かれる → 抽象構文木を読み込んで処理を実行する

こういう流れになります。

抽象構文木とは

構文木とは文章を木構造で表したものです。

たとえば4*3+1という計算式があったとします。
これを構文木にすると以下のようになります。

この構文木を枝の方から計算していくと、『4*3=12』『12+1=13』…と答えが導き出せます。
抽象構文木はこの構文木から間のスペースや括弧など意味解析に不要なものを除いたものです。

プログラミングの話題から少し離れますが、構文木は日本語にも適用することができます。

図引用：構文木 - wikipadia

PEGとは

PEGの構文は実装言語によって表現は様々ですが、WikipediaのPEGのページに書かれている書き方でまずは説明します。

Integer ← [0-9]+ / '(' Expression ')'
Term ← Integer (('*' / '/') Integer)*
Expression ← Term (('+' / '-') Term)*

このPEGの定義では、Integerで値を、Termで乗除算を、Expressionで加減算を定義しています。

1行ずつ見ていきましょう。

Integer ← [0-9]+ / '(' Expression ')'

これは、
「Integerとは、0～9の数字が1以上続く文字、またはカッコで囲まれたExpressionである」
という意味です。
たとえば「42」はIntegerです。

[0-9]+は正規表現ですね。
Expressionについては後で出てきます。

Term ← Integer (('*' / '/') Integer)*

これは、
「Termとは、『Integer』『*または/』『Integer』の並び」
という意味です。後半の部分は0個以上繰り返されます。
たとえば「4 * 3 / 2」はTermです。「42」もTermです。

Expression ← Term (('+' / '-') Term)*

これは、
「Expressionとは、『Term』『+または-』『Term』の並び」
という意味です。後半の部分は0個以上繰り返されます。
たとえば「4 * 3 + 1」はExpressionです。「2 + 2」もExpressionです。「42」もExpressionです。

4 * 3 + 1

をPEGに突っ込むと以下のような抽象構文木が得られます。

末端の方から順番に解決していくと、13という計算結果が得られます。

Peggyを触ってみよう

PEGを扱うライブラリにPeggyというJavascriptのライブラリがあります。
これはライブラリとして使うこともできますし、WEB上でお試し実行もできるようになっています。

このページでPeggyを体験してみましょう。
https://peggyjs.org/online

Peggyは上で説明したPEGの構文とはちょっと違う表現になっているので、その補足です。

画面左側に以下のようなコードがあります。

Expression
  = head:Term tail:(_ ("+" / "-") _ Term)* {
      return tail.reduce(function(result, element) {
        if (element[1] === "+") { return result + element[3]; }
        if (element[1] === "-") { return result - element[3]; }
      }, head);
    }

これは先程のこれと等価です。

Expression ← Term (('+' / '-') Term)*

Peggyでは「:」を使って各パーツに変数名をつける事ができ、その変数「{}」で囲んだブロックの中で使うことができます。
そして解析された結果は「{}」のブロックでreturnした値に変換されます。

Peggyをいじってみよう

ただサンプルを見るだけではつまらないので、この定義を改造してみます。

https://peggyjs.org/online の左側の

Termの部分を以下のように置き換えてみてください。

Term
  = head:Factor tail:(_ ("*" / "/" / "😊") _ Factor)* {
      return tail.reduce(function(result, element) {
        if (element[1] === "*") { return result * element[3]; }
        if (element[1] === "/") { return result / element[3]; }
        if (element[1] === "😊") { return (result + element[3])/2; }
      }, head);
    }

そして右側のコード欄には以下の式を入れてみます。

(2 + 2 * 3) 😊 12

すると答えは10になったはずです。

😊演算子は「AとBを足して2で割った値」というオリジナルの演算子です。

このように、PEGの定義をいじれば簡単に独自の演算ルールを構築することができます。

Javascriptのインタープリタを作ってみよう

PeggyにはJavascript(ECMAScript5.1相当)の構文解析を行うサンプル定義が用意されています。
構文解析はサンプルに任せてインタープリタ部分だけ実装してみましょう。

とはいえそれでもインタープリタの実装には面倒な部分が多いので、

変数の定義
変数の利用
if文
print関数

まで実装した叩き台を用意しました。

まずはこちらを見てみましょう。

上のリポジトリをDLして$ npm run upすると、Javascriptを利用したインタープリタを起動することができます。

peggyの利用はmain.jsで行われています。

const parser = peggy.generate(peg_js)
const parsed = parser.parse(code)

peg_jsはPEGの定義の文字列です。
codeは解釈するコードです。
parsedはコードをパースした構文解析木です。

codeに「2+2=4」という文字列を渡すと、以下のような抽象構文木がJSONで得られます。

{
  "type": "Program",
  "body": [
    {
      "type": "ExpressionStatement",
      "expression": {
        "type": "BinaryExpression",
        "operator": "==",
        "left": {
          "type": "BinaryExpression",
          "operator": "+",
          "left": {
            "type": "Literal",
            "value": 2
          },
          "right": {
            "type": "Literal",
            "value": 2
          }
        },
        "right": {
          "type": "Literal",
          "value": 4
        }
      }
    }
  ]
}

この構文解析木から以下のようなことが読み取れます。

ProgramはBodyというプロパティを配列として持っている。
- BodyにはExpressionStatementが入っている。
  - ExpressionStatementのexpressionはBinaryExpressionで、operatorは==である。
    - BinaryExpressionのleftにはBinaryExpressionが入っており、operatorは+である。
      - BinaryExpressionのleftにはLiteralが入っており、valueは2である。
      - BinaryExpressionのrightにはLiteralが入っており、valueは2である。
    - BinaryExpressionのrightにはLiteralが入っており、valueは4である。

これが「2+2=4」の構文解析木です。

Programとは何でしょうか？ExpressionStatementとは何でしょうか？

ここに全部載っています。
https://github.com/estree/estree/blob/master/es5.md

PeggyのJavascriptサンプルが吐き出す構文解析木はESTree Specという規格に準拠しています。
これはmozillaのエンジニアが公開した規格で、babelのパーサーもESTreeをベースにしているようです。

ESTreeの定義を読んで見ると以下のようなことがなんとなく分かります。

Programはプログラム全体を指す。複数の式や文を持つ。
ExpressionStatementは式。expressionを持つ。
BinaryExpressionはleftとrightとoperatorを持つ式。operatorには「==」や「+」などがある。
Literalは数字や文字列や真偽値などの値を意味する。

これらを解釈するコードを１つ１つ書いていけば、インタープリタが完成します。

インタープリタの叩き台はevaluter.mjsで定義しています。
https://github.com/kurehajime/lang_sandbox/blob/main/src/evaluter.mjs

こんな感じです。

    evalute(env, tree) {
        if (tree == undefined || tree.type == undefined) {
            return tree
        }
        // ノードのタイプ
        const type = tree.type

        switch (type) {
            case "Identifier":
                return this.Identifier(env, tree.name)
            case "Program":
                return this.Program(env, tree.body)
            case "Literal":
                return this.Literal(env, tree.value)
...
            default:
                console.log(JSON.stringify(tree, null, 2))
                break;
        }
    }

return this.Program(env, tree.body)と呼び出し先で何が行われているのか見てみましょう。

    Program(env, body) {
        for (const item of body) {
            this.evalute(env, item)
        }
    }

evaluteメソッドで呼び出されたProgramメソッドは、ループを回してevaluteメソッドを呼び出しています。
再起です。基本はこれです。

今度はLiteralを見てみます。

    Literal(env, value) {
        return value;
    }

valueを返してるだけですね。

次はif文を実現するIfStatementを見てみましょう。

    IfStatement(env, test, consequent, alternate) {
        const result = this.evalute(env, test)
        if (result) {
            this.evalute(env, consequent)
        } else if (alternate) {
            this.evalute(env, alternate)
        }
    }

testをevaluteに渡して結果を受け取り、正ならばconsequentを、偽ならばalternateをevaluteに渡しています。

if文はたったのこれだけです。

evaluter.mjsは基本的にこのように動いています。

構文解析木を受け取る。
子を持つ場合は子の抽象構文木を再帰的に解釈する。
子の解釈が終わったら、ノードの種類に応じた制御を行う。

実に単純ですね。

それでは最後に、ESTreeの資料を読みながら、Whileの実装を自力でやってみてください。
これができれば、後は地道に実装していくだけでプログラミング言語が出来上がります。