LoginSignup
130
129

More than 5 years have passed since last update.

@hiruberuto

えっ!?　１時間でオリジナルのプログラミング言語の開発を構文解析から!?

Last updated at Posted at 2016-10-03

出来らあ！　1時間で構文解析から評価器まで書けるって言ったんだよ！

上のエントリは、Lispの『S式』みたいな式で構成されたプログラムを実行するインタプリタを作るというお話です。ストックやブックマークが結構たくさんついていて、みんな自分のオリジナルなプログラミング言語とか作ることに興味があるんだなあって思いました。

元ネタのorelangは、式をJSONのサブセットにすることでJSONパーサを流用し構文解析の手間を省いているところがキモだと思いますが、実は構文解析は案外簡単で、わざわざ避けて通るほどのものではなかったりします。また、S式の範囲に収めるとそれ以上構文の工夫は望めないので、『自分のプログラミング言語を作る』ということの面白みが薄れてしまう気もします。他にも、JSONのパーサを流用すると、構文エラーであるはずのコードまで受理されてしまうという問題もあります。プログラミング言語を自分で作るという面白さを感じるには、やっぱり構文解析からできるようになったほうが楽しいのではないかと思いました。そこで、私も構文解析器からorelangのインタプリタを作ってみます。

あんまりガチな解説はしませんので、ゆるい読み物として御覧ください。プログラミング言語を作るってこんな感じなんだ、案外簡単かも、みたいに感じてくれたらいいなと思います。なお、今回インタプリタを作るために使う言語は（筆者の過去の記事を読んだことのあるかたならなんとなく予想がつくと思いますが）PureScriptという変な言語を使っていますが、なんとなく雰囲気でコードがわかる感じに紹介していくので、あんまり深く考えずに眺めてください。

今回書いたコードはgistに貼り付けておきました。全部で150行ほどです。必要に応じて、併せてご覧ください。

えっ!?　５分でこの言語の字句解析を!?

さて、なんとなく思いついたところからコーディングしていきます。構文解析をする前に、まずは『字句解析器』(LexerあるいはToken Parser)というプログラムを作る必要があります1。字句解析器の主な役割はコードをトークンに分割することですが、そのほかにも空白やコメントを読み飛ばしたり、後の構文解析でエラーが生じたときのためにトークンのソースコード上の位置を記録しておくなど、振る舞いは結構複雑です。といっても、今回の場合は、purescript-parsingというライブラリでデフォルトで定義されている構文解析器で十分でした。コードとしては実質的に次の一行だけです。

lexer = makeTokenParser emptyDef

できました。これで字句解析器lexerの完成です。このmakeTokenParserなる関数がポイントで、ほとんどすべてのプログラミング言語のソースコードの字句解析器はmakeTokenParser一発で作成することができます。makeTokenParserには11項目のオプションがあって、emptyDefはそのオプションのデフォルト設定で、今回のorelangではこのデフォルト設定で事足ります。JavaやHaskell、Rubyのようなもっと本格的で複雑なプログラミング言語のコードを構文解析する場合でも、オプションを変えてmakeTokenParserを呼び出すだけです。ぜんぜん難しくはありません。

えっ！この言語の構文解析を10分で!?

先ほどの字句解析器lexerを使って、次は構文解析器を作ります。できました。

program = lexer.whiteSpace *> expression *> eof
  where
    sign = char '-' <|> char '+'
    expression = fix \expression -> void lexer.stringLiteral
                                <|> void (sign *> lexer.naturalOrFloat)
                                <|> void (lexer.brackets (sepBy1 expression lexer.comma))

*>は『～のあとに～』と読んでください。例えば、sign *> lexer.naturalOrFloatというコードは、『プラスやマイナスの符号(sign)のあとに、自然数か浮動小数点数(naturalOrFloat)がある』というように読むことができます。sepBy1 expression lexer.commaは『式(expression)は、コンマ(comma)で区切られた一個以上の(sepBy1)、式である』というように読みます。

<|>は『～または～』と読んでください。expression = ......という部分は、『式とは、文字列リテラル、または自然数か浮動小数点数、または角括弧で囲まれた(brackets)コンマで区切られた一個以上の式』という意味です。sign = char '-' <|> char '+'は、『符号(sign)は文字-または文字+』というように読めます。

この定義がS式の構造を直感的に表現していることが、なんとなくわかると思います。なお、voidというのはとりあえずの型合わせで使っているだけで、構文解析の振る舞いとは関係がないので気にしなくてもいいです。実質5行くらいしかありませんが、これでorelangの構文解析器programは出来上がりです2。構文解析なんてぜんぜん恐れるに足りないことがわかると思います。

構文解析器ができたので、あとはファイルからソースコードを読み取って構文解析を実行するだけです。readTextFile関数でファイルを読み取ってrunParser関数で構文解析を実行しているだけで、特に面白くもなんともないので解説は省略します。詳しくは先述のgistを御覧ください。

えっ？5分で抽象構文木の定義を？

先ほどの構文解析器は構文解析の結果をすべて捨ててしまっているので、せいぜい構文のチェックに使えるくらいです。インタプリタとして動作させるには、構文解析の結果を構文木として取得する必要があります。元ネタのほうでは構文木にJSONデータをそのまま利用しているのですが、今回はJSONを使いませんので、まずは構文木のデータ構造を定義しておきましょう。orelangにおける式は次のようなものです。

  • 真偽値リテラル(true, false)は式
  • 数値リテラル(42, 3.14など)は式
  • 文字列リテラル("Hello"など)は式
  • リスト(["set", "pi", 3.14]など)も式

これに対応するデータ型を定義するだけです。

data Expression = Boolean Boolean
                | Number Number
                | String String
                | List (List Expression)

あまり詳細な説明はしませんが、=を『～とは、～』、|を『～または～』と読んでください。『式とは、真偽値または数値または文字列またはリスト』というように書かれているのが、なんとなくわかるかと思います。

えっ？ 5分で構文解析からの構文木構築を？

それから、構文解析の結果をこのデータ型のデータへと移し替えるように先ほどの構文解析器programを改造します。ちょっと複雑になりました。

program = lexer.whiteSpace *> expression <* eof
  where
    sign = (char '-' *> pure negate) <|> (char '+' *> pure id) <|> pure id
    number = Number <$> (sign <*> (either toNumber id <$> lexer.naturalOrFloat))
    string = String <$> lexer.stringLiteral
    list expression = List <$> lexer.brackets (sepBy1 expression lexer.comma)
    expression = fix \expression -> string <|> number <|> list expression

<$>、<*>、*>、<*といった謎演算子のオンパレードにHaskell/PureScriptの深い闇を感じますが、実はこれ筆者が簡潔なコーディングのためにこれらの演算子を多用しているだけで、別にこれらの演算子を使わなくても書くことができます。Haskell/PureScriptでは<$>は+や==よりも使用頻度が高い演算子で、慣れるとすごく便利で簡潔だと思えるようになるはずです。この辺りはここではとても説明しきれないHaskellのダークサイドなので、詳細はあまり気にしないでください。

なんにせよ、orelangやLispのようなS式ベースの構文なら、まともなライブラリを使えば、

  • 構文木のデータ型の定義：　5行くらい
  • 字句解析器：　1行くらい
  • 構文解析器：　10行くらい

というとても短いコードで

  • (JSONとしてはOKでも)orelangとしてはエラーであるようなコードを確実にエラーにできる
  • 構文エラーがあった時に、問題のあった位置と何の文字を期待していたかという意味のあるエラーメッセージを出せる

というまともな構文解析器を作ることが可能です。なお、これはPureScriptだからこんなに短いというわけではなくて、今回使ったpurescript-parsingのようないわゆるパーサコンビネータというライブラリのお陰です。パーサコンビネータの実装は他の言語でも普通にあるので、自分の好きな言語で使ってみるといいんじゃないかと思います。パーサコンビネータに慣れると、可読性が最低で構文エラーの理由もまともにわからない正規表現なんて使う理由がなくなります。

えっ？2時間で構文木の評価器を？

さてそれでは、実際にプログラムを実行する評価器を作っていきます。評価といっても、数値や文字列は評価してもそのままですし、S式のリストである場合に限り、対応する演算子を検索して実行するだけです。評価器の本体部分はとてもシンプルで、この辺りでやっている事は元ネタのJavaのソースコードと大して変わりません。

newtype State = State {
    operators :: Map String (List Expression -> StateT State (Either String) Expression),
    variables :: Map String Expression
}

eval :: Expression -> StateT State (Either String) Expression
eval (Number n) = lift $ Right (Number n)
eval (String s) = lift $ Right (String s)
eval (Boolean b) = lift $ Right (Boolean b)
eval (List (String op : args)) = do
    State st <- get
    maybe (lift $ Left $ "Unknown operator: " <> op) ((#) args) (lookup op st.operators)
eval _ = lift $ Left "Invalid expression"

評価器の状態Stateと評価を行う関数evalは、元ネタのCallOperatorクラスにだいたい対応しています3。eval関数の本体部はほんの数行ですが、モナド変換子というもうひとつのHaskellの闇を利用しているので、コードを読もうとするとSAN値がガリガリ削られます。狂気に冒されるまえに目を逸らしておきましょう。筆者も正直モナド変換子なんてやめときゃよかったと思いました。

演算子はoperatorsというテーブルを参照するようになっていますが、この辺りも元ネタの意図を汲み取ってわざと振る舞いを似せました。固定のセットなら別にテーブルに入れる必要はなく、分岐すればいいだけですが、将来的に動的に演算子を定義したりする機能を追加したかったのかもしれません。

元ネタと同じ演算子のセットも定義したのですが、これは結構長いのでぜんぶをそのまま掲載するのはやめておきます。例として比較的簡潔なstep演算子だけを載せておきます。

    Tuple "step" \args -> case args of
        x: xs -> foldl (*>) (eval x) (eval <$> xs)
        _ -> lift $ Left "too few args"

結局のところ、この評価器と演算子のセットを作るのが一番大変で、1時間ではとても無理でした。

えっ！　S式以外の構文を？

おまけとして、この処理系をさらに魔改造し、S式以外の構文へと拡張してみます。もちろん、すべてがS式であるというシンプルさがLisp/Scheme系の言語の価値なので、S式以外の構文を含めるとその存在意義が失われてしまうのですが、『自分のオリジナル言語を作る』という面白さを感じたいなら、きっとS式以外の構文も扱いたくなるはずです。JSONの構文解析器を流用する場合はJSON以上の構文は扱えませんが、今回は自力で構文解析器を書いたので、簡単に任意の構文へと拡張することができます。

ここでは、pi = 3.1415というような形式での代入文を構文に追加してみましょう。まずは、構文木のデータ構造Expressionに次のような新たな定義を付け加えます4。

data Expression = Boolean Boolean
                | Number Number
                | String String
                | List (List Expression)
                | Assignment String Expression  -- new!

それから、構文解析器も代入文を受け付けるように改造します。次のような代入文の定義assignmentを付け加えました。『代入文(assignment)とは、まず識別子(identifier)があって、そのあとに=記号(lexer.symbol "=")、それから式(expression)』というようになんとなく読めるのがわかると思います。なんとなく。

assignment expression = Assignment <$> lexer.identifier <*> (lexer.symbol "=" *> expression)

また、式の定義も、『式(expression)とは、stringまたはnumberまたはlistまたはassignment』に変えました。

expression = fix \expression -> string <|> number <|> list expression <|> assignment expression

更に、Asssignmentを評価できるように評価器へパターンを付け加えます。中身はset演算子とほとんど同じです。

eval (Assignment key value) = do
    value' <- eval value
    modify \(State s) -> State s { variables = insert key value' s.variables }
    lift (pure value')

7行ほど付け加えただけですが、これで例えば次のようなコードが実行できるようになります。

["step",
  i = 10,
  sum = 0,
  ["until", ["=", ["get", "i"], 0], [
    "step",
    sum = ["+", ["get", "sum"], ["get", "i"]],
    i = ["+", ["get", "i"], -1]
  ]],
  ["get", "sum"]
]

もはやJSONでもなんでもありませんが、["set", "sum", 0]の代わりにsum = 0のような簡潔な代入文を書けるようになったのがわかります。もはや元ネタのorelangではなくなってしまったので別の名前をつける必要がありますが、それではこの言語はPoorScriptと名付けたいと思います。PureScriptとの語呂合わせで、機能が足りなくて実用性に乏しいので"Poor"です。

["get", "sum"]の代わりにsumだけで変数を参照できるようにしたり、["step", x, y]の代わりに{ x; y; }のように中括弧で表現するようにすれば、もっと普通の言語っぽくなると思います。そのような改造も簡単です。

えっ？　これで終わり!?

今回は元ネタにあわせてインタプリタを作りましたが、JavaバイトコードやCILみたいな比較的高レベルな中間言語ならコンパイラを作るのも難しくはないと思いますし、JavaScriptのような高レベルな言語へのトランスパイラはもっと簡単です。コンパイラの開発も試してみたらいいと思います。

また、ちゃんとしたライブラリを使えば構文解析は簡単ですから、もっと頑張れば本格的なプログラミング言語も作れると思います。ただしそのためにはまだまだ沢山の構文を付け加えなければなりませんし、特に静的型付けの言語では、データ型の定義を扱ったり型の整合性のチェックなんかもしなければなりません。実用的な言語を作るのは並大抵ではないと思いますが、挑戦してみるのも面白いんじゃないでしょうか。コードを書くよりこの記事を書くほうが大変でした。今回はぜんぜん1時間で終わりませんでしたが、これでpurescript-parsingのコツやorelangの細かい挙動もわかったし、モナド変換子のリハビリもできたので、もう一度書き直せば一時間切れるかもしれません。そんな根性はないですけど。

オマケ：拡張可能作用版

まったくの余談なんですが、実装の別バージョンを作ったのでPureScriptに興味がある人向けに紹介しておきます。先ほどはHaskellのときのクセでなんとなくモナド変換子を使っていたんですが、よく考えたらPureScriptには拡張可能作用なる神機能があって、これを使えばlift関数に目眩を覚えながらモナド変換子を使う必要がないことに気が付きました。先程のモナド変換子版だと、実行に失敗した時はLeftなる変な関数を使いましたが、拡張可能作用版ではthrow関数というものを使えます。このthrow関数、内部的にはJavaScriptのthrow文そのものだったりします。

えっ？　参考文献とか思いつかない!?

  1. 昔はこの字句解析器を作るためにlexなるツールを使って、専用の構文で書かれた定義からコードを生成することが多かったようです。でも、ツールの使い方を覚えたり、専用の構文を覚えるのが面倒くさいですし、ビルドの過程がちょっとだけ複雑になるのも微妙に嫌です。現代人はそんな手間を掛ける必要はなく、構文解析用のライブラリを使うだけで充分です。 ↩

  2. 余談なんですが、上の構文解析器にはfixなる変な関数が登場していることに気づいた人もいるかもしれません。このfixっていうのは数学でいうところの不動点コンビネータというというやつで、不思議なことに遅延評価のHaskellではこのfixを使わずに同じ機能のコードが書けるのです。この辺りにPureScriptとHaskellの違いが見え隠れしています。余談過ぎました。 ↩

  3. 御存知の通り、オブジェクト指向の『クラス』は『状態』と『操作』を一体にして定義したものですからね。PureScriptはオブジェクト指向ではないので、データ型の定義と関数の定義が、別々になっているというだけの話です。 ↩

  4. 構文木を改造する方法の他に、構文解析した時点で、sum = 0のような代入文を["set", "sum", 0]のようなset演算子の呼び出しへと変換してしまう手もあります。つまり、sum = 0を["set", "sum", 0]の構文糖とみなしてしまうわけです。 ↩

130
129
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
Sign upLogin
130
129