2018年04月05日 SpoonSpoon

開発動機


トランプや将棋、オセロ、TRPG、人狼などのアナログゲームのルール説明書を移植するのに適した簡単で優しいプログラミング言語を開発する運びになりました。 そもそも言語開発に興味が前々からあったのも大きな理由です。

自作言語名


Radius(ラディウス)という名前です。開発した言語を利用するアプリがcircleというので、円の構成要素ということで半径(radius)になりました。

さてと、そもそもの話…


『プログラミング言語を作るって、具体的には何をどうすればいいの?』
巷にはCやJava、PythonやRuby…などたくさんのプログラミング言語がありますが、
何をどうしたら言語を作ったって言えるの?というわけです。

プログラミング言語は、二つにわけると「プログラミング」と「言語」です。
まずは言語のほうから見ていきます。
言語には「文法」があります。日本語にもあります。
「私は図書館にいく」は正しい文法ですが、「私より図書館でいかった」は間違った文法なので、意味が通りません。
言語を作るためには、まずは文法を作ります。
つまり、作成者はこの文法を「自由に決めることができます。」
つまり、「何が正しい(=意味がわかる)文なのか、自由に決めることができます。
すごいですね。もはや神になった気分です。

でも、考えただけでは、使い物になりません。コンピュータがその文法をわかっていなければ利用できないからです。
「おい、コンピュータ。『ぽぷてぴぴぴっぽぷ』だ」
Syntax Error(貴様が何を言っているか分からない)。
というわけです。

ですから、文法を決めたら、コンピュータにその文法と、それに対する処理を教えなくてはいけません。
つまり、「『ぽぷてぴぴぴっぽぷ』という文章が入力されたら、『某指定暴力団を破壊する』という処理をする」ようなプログラムを作ります。
もうちょっと正確にいうと「文が入力されたら、その文に従った処理を行う」プログラムです。
このプログラムを処理系(プロセッサ)と言います。専門的な話は専門用語が多くてこんがらがりますね。

まとめると、プログラミング言語を作るということは、

  • 文法…「どの文が正しい(=意味が通る)のか、という決まり」
  • 処理系…「文が入力されたら、それに従った処理を行うプログラム」

  • この二つを作ればよいことになります。イメージがつかめたでしょうか。

    処理系の仕組み

    処理系はどんな風にコードに対応した処理をしているのでしょうか。
    ためしに、次のコードが入力された時、どのような段階を踏んでプログラムコードを実行しているのか見てみましょう。

    a = 3+5;
    print(a);

    これを解析するために、まずは単語(これをまたはトークン)に正規表現を利用して分けていきます。
    分けるついでに、その単語の分類もそれぞれの単語に付与していきます。
    処理系のなかで、この処理をする部分を字句解析器(レクサー)といいます。
    器(うつわ)という字面に混乱しないでください。字句を解析するプログラムの意味です。そのままです。
    結果として次のような二次元配列が得られます。

    [[:IDENTIFIER, "a"], ["=", "="], [:NUMBER, 3.0], ["+", "+"], [:NUMBER, 5.0], [";", ";"], [:IDENTIFIER, "print"], ["(", "("], [:IDENTIFIER, "a"], [")", ")"], [";", ";"]]

    それぞれのカッコの左側がトークン分類、右側がトークンです。
    IDENTIFIERは識別子、つまり、名前です。
    aという変数名、printという関数名ですね。
    NUMBERはそのまんま数字を表しています。

    次に、この二次元配列を順に読み込んでいって、入力されたプログラムがそもそも正しい構造なのかを調べながら、文のデータ構造を生成します。
    処理系の中でこの処理をする部分を構文解析器(パーサ)といいます。
    同じく器(うつわ)という字面に混乱しないでください。構文を解析するプログラムの意味です。

    その結果、次のような木構造が生成されます。

    ["STMTS", ["=", ["IDENTIFIER", "a"], ["+", ["NUMBER", 3.0], ["NUMBER", 5.0]]], ["FUNC_CALL", ["IDENTIFIER", "print"], [["IDENTIFIER", "a"]]]]

    複雑ですね。

    そして、最後に実行器です。
    この木構造を順に解析しながら、各命令を実行していきます。
    たとえば
    ["=", ["IDENTIFIER", "a"], ["+", ["NUMBER", 3.0], ["NUMBER", 5.0]]]
    が出てきたら、
    まずは3.0と5.0を+して、
    その結果(8.0)が帰ってきて、
    aに8.0が=(代入)する、というように実行されていきます。

    長くなりましたが、これがradiusの言語処理系の手順です。
    字句解析→構文解析→実行
    これで、どんなコードが入力されても、実行することが可能です。

    文法を考える


    先ほどの処理系の中で、一番重要なのは構文解析器の部分です。
    作るのも最も大変なのですが、実は、「『構文解析器』生成器」(パーサ・ジェネレータ)というものがあります。
    文法データを入力すると、「構文を解析するプログラム」を自動で出力してくれるプログラムです。すごいですね。
    有名なものにyacc(yet another compiler compiler)があります。これは「プログラムを解析するC言語のプログラム」を自動で出力してくれるプログラムです。
    これのRuby版にraccがありましたので、これを利用してradiusのパーサを自動生成しています。

    racc(もといyacc)の文法の定義の仕方が面白いので、それを紹介します。
    適当に、次のような文法を考えてみます。プログラムとは関係ないので、頭を柔らかくして考えてみてください。

    規則1 ●は正しい文である。
    規則2 ●は□■□と等しい(置き換えられる)
    規則3 □は▲△と等しい(置き換えられる)

    さて、□■▲△は正しい文ですか?

    ちんぷんかんぷんだと思います。答えはこうです。
    まず規則3から、▲△は□と等しいので、
    □■▲△→□■□

    規則2から、□■□は●と等しいので、
    □■□→●

    規則1から、●は正しい文なので、□■▲△は正しい文です。

    ちょっと抽象的すぎますね。具体的に行きましょう。足し算の文法を、定義しましょう。
    1+3は正しく、1+6+4も正しいですが、++164は間違い、とするような文法は次のように作ります。

    規則1 「式」は正しい文である
    規則2 「式」は「式+式」と等しい
    規則3 「式」は「数字」と等しい

    これだと、1+4+6について、次のように考えられます。(1,4,6は数字だとわかってるものとします)
    数字 + 数字 + 数字
    ↓規則3から「数字」と「式」は正しいので
    式 + 式 + 数字
    ↓規則2から「式」は「式+式」と等しいから
    式 + 数字
    ↓規則3から
    式 + 式
    ↓規則2から

    規則1から正しい文である
    逆に、+1+46は、次のように考えられます。
    + 数字 + 数字 数字
    ↓規則3から
    + 式 + 式 数字
    ↓規則2から
    + 式 数字
    適用できる規則がないので、正しくありません。

    では次に四則演算まで、グレードをあげましょう。どのような規則を作ればいいでしょうか。ちょっと考えてみてください。

    こうです。

    規則1 「式」は正しい文である
    規則2 「式」は「式+式」と等しい
    規則3 「式」は「式-式」と等しい
    規則4 「式」は「式*式」と等しい
    規則5 「式」は「式/式」と等しい
    規則6 「式」は「数字」と等しい

    規則が増えましたね。でもこれで、四則演算ができます。

    1+2-5*9-19/3について考えてみます。(もちろん、数字部分は数字だとわかっていることが前提です)
    数字+数字-数字*数字-数字/数字
    ↓規則6から、数字は全て式に置き換え可能です。
    式+式-式*式-式/式
    ↓規則2より
    式-式*式-式/式
    ↓規則4より
    式-式-式/式
    ↓規則5より
    式-式-式
    ↓規則3より
    式-式
    ↓規則3より

    よって正しい!と言えるわけですね。ふー疲れた。
    途中で適用できる規則がなくなったにもかかわらず、ゴール(この場合は式)にたどり着けなかった場合、正しい文法ではない、と言えるわけです。
    このようにして、厳密に文法を定義しているのですね。

    かなり端折ったり、専門的なことをすっとばしてここまできましたが、
    言語の処理系と構文解析について、少しでも興味を持っていただけたらと思っています。

    それではー。