Python 構文解析ライブラリLarkを使って簡単な自作言語処理系をつくる

概要

とある目的のためにDSLを作成してみたいと思うことがありました。
そこでまずは基礎知識をつけようということで、簡単な自作言語の処理系を実装してみようと思いたち、ごくごく簡単なプログラミング言語を作ってみました。

環境としてはPython3系を使いました。

処理系の作成

プログラミング言語の処理は、字句解析(トークナイズ)構文解析(パース)実行コード生成という３つ段階があります。

字句解析とはただの文字の並びであるソースコードを読んで、functionとかvarとか19のような終端記号(トークン)の塊の並びに変換することです。ただし、この時点ではそれぞれの終端記号はただの文字列であって意味までは与えられていません。

次の構文解析は字句解析で得られた終端記号の列を読んで、プログラムのコードとしての構造を抽出することです。字句解析の出力からconst hoge = 1 ;というトークンの列が得られたら、これは変数の宣言と代入をしているところなんだな、という解釈をするのが構文解析です。ASTというツリー構造を生成するのが主流だそうですが、それ以外の方法もあるようです。

(これは長いのでWikipediaから画像を借ります)

そして最後に、得られた構造を実際に実行できるコードに変換するのが実行コード生成です。実行できる、といっても機械語には限らずJVMバイトコードだったり別のプログラミング言語のソースコードだったりします。(JSのトランスパイラなんかをイメージしていただければ。)

パーサジェネレータとBNF・EBNF記法

構文解析器を作り上げるのはとてもとても大変です。そこで、「文法」を渡してあげるとその文法にもとずく言語を処理できるパーサを返してくれるパーサジェネレータというものを使うのが一般的です。
「文法」を定義するためにはBNF(バッカス・ナウア記法)やEBNF(拡張バッカス・ナウア記法)という表記法を使うのがこれまた一般的です。
怖くないバッカスナウア記法(BNF)入門

Lark

さて、前置きが長くなってしまいましたが字句解析・構文解析の部分はライブラリにまかせてしまいましょう。
Pythonの場合、いろいろなライブラリが選択可能ですが、私はLarkというライブラリを選択しました。

概要

EBNFで文法規則と終端記号の規則を渡すと、字句解析から構文解析まで行ってくれます。

Pythonの字句/構文解析ライブラリ (2014.11初調査、一部追記)にのっていないくらい、新し目のライブラリです。

使い方

構文解析したいソースコードがprogram.txt、文法規則が'grammer.txt'に保存されているとします。

program = open('program.txt').read()
rule = open('grammer.txt').read()

# 文法規則をパーサジェネレータに渡してパーサを生成(字句解析もやってくれる)
parser = Lark(rule, start='program', parser='lalr')

# プログラムを字句解析＆構文解析
tree = parser.parse(program)

自作言語

さて、実際に作った自作言語の説明をしていきます。シンプル極まりない言語なので、SIMPLELANGという名前にしました。
この言語は、数字の四則演算と関数定義・呼び出し(動的スコープ)を行えるだけの言語です。

文法規則

前述の通り、文法規則と終端記号の規則を書くだけで字句解析と構文解析はLarkに任せることができます。

?program: [(state)+]

// statement
?state: expr ";"
      | function
      | assignment ";"
      | return_state ";"
function: "def" new_symbol "(" [parameter ("," parameter)*] ")" "{" program "}"
assignment: new_symbol "=" expr
return_state: "return" expr

// expression
?expr: term
     | addition
     | substraction
     | function_call
addition: expr "+" term
substraction: expr "-" term
function_call: symbol "[" [expr ("," expr)*] "]"

?term: fact
     | multiplication
     | division
multiplication: term "*" fact
division: term "/" fact

?fact: number
     | symbol
     | priority
?priority: "(" expr ")"
symbol: WORD
number: SIGNED_NUMBER

new_symbol: WORD
parameter: WORD

%import common.WORD
%import common.SIGNED_NUMBER
%import common.WS
%ignore WS

実行コード生成

実行コードを生成する部分は自分で実装します。

# 名前を束縛するための環境を表すクラス
class Environment():
    def __init__(self, parent_env):
        self._parent_env = parent_env
        self._env = dict()

    def get(self, key):
        value = self._env.get(key, None)
        if not value:
            value = self._parent_env.get(key)
        return value

    def set(self, key, value):
        self._env[key] = value

# 関数を表すクラス
class Function():
    def __init__(self, parameters, tree):
        self._parameters = parameters
        self._tree = tree

    def parameters(self):
        return self._parameters

    def tree(self):
        return self._tree


# ツリーをたどって実行コードを生成するVisitorクラス
class Visitor():
    def __default__(self, tree, env):
        raise

    def program(self, tree, env):
        for sub_tree in tree.children:
            r = self.visit(sub_tree, env)
            if sub_tree.data == 'return_state':
                return r

    def assignment(self, tree, env):
        key = self.visit(tree.children[0], env)
        value = self.visit(tree.children[1], env)
        env.set(key, value)

    def return_state(self, tree, env):
        return self.visit(tree.children[0], env)

    def new_symbol(self, tree, env):
        return tree.children[0].value

    def parameter(self, tree, env):
        return tree.children[0].value

    def function(self, tree, env):
        key = self.visit(tree.children[0], env)
        parameters = []
        if len(tree.children) > 2:
            parameters = [self.visit(child, env) for child in tree.children[1:-1] ]
        ast = tree.children[-1]

        func = function.Function(parameters, ast)
        env.set(key, func)

    def function_call(self, tree, env):
        func = self.visit(tree.children[0], env)

        arguments = [self.visit(c, env) for c in tree.children[1:]]
        if len(arguments) != len(func.parameters()):
            raise BaseException('Number of arguments is wrong')

        local_env = environment.Environment(env)
        for (k, v) in zip(func.parameters(), arguments):
            local_env.set(k, v)

        return self.visit(func.tree(), local_env)

    def addition(self, tree, env):
        left = self.visit(tree.children[0], env)
        right = self.visit(tree.children[1], env)
        return left + right

    def substraction(self, tree, env):
        left = self.visit(tree.children[0], env)
        right = self.visit(tree.children[1], env)
        return left - right

    def multiplication(self, tree, env):
        left = self.visit(tree.children[0], env)
        right = self.visit(tree.children[1], env)
        return left * right

    def divisiton(self, tree, env):
        left = self.visit(tree.children[0], env)
        right = self.visit(tree.children[1], env)
        return left / right

    def symbol(self, tree, env):
        key = tree.children[0].value
        return env.get(key)

    def number(self, tree, env):
        return float(tree.children[0].value)

    def visit(self, tree, env):
        f = getattr(self, tree.data, self.__default__)
        return f(tree, env)

例

たとえば、次のようなプログラムはSIMPLELANGのプログラムとして実行可能です。

a = 5;

def func ( b , c ) {
  a = 4;
  return a + b * c;
}

c =  func [ 2 , 4 ];

return c;

もちろん、答えは12。

最後に

学生時代クックパッドさんでインターンシップに参加した際に、Javascriptのコンパイラを作るという講義をうけたことがあります。
(クックパッド サマーインターンシップ2016の資料を公開しますの「6日目 プログラミングパラダイム (青木峰郎)」のところです)

今回のDSLづくりをやっていて、すっかり忘れていた(と思っていた)この講義の内容がフラッシュバックしてくることがありました。長く役に立つ知識を学べる機会を与えてくれたんだなぁと今更ながら感謝です。