はじめに

21年新卒で入社したバックエンドエンジニアの榎本です。

7月にアルゴリズムの研修でステガノグラフィを題材とした課題が渡されました。

研修は以下のように3段階のレベルが用意されています。

ステガノグラフィでは画像に文字を埋め込み、それを抽出する
抽出した文字をインタプリタに渡して実行
自分で開発した言語のコードを埋め込み、自作言語に渡して実行する

今回はこの研修の中で、思ったよりも簡単に開発できるんだという発見があった言語開発について共有したいと思います。

タイトルにあるように、Larkというライブラリを用いて開発するのですが、

Larkを選んだ理由は比較的新しいライブラリを使ってみたかったので、こちらを参照して新しいものを採択したまでです。

きちんと選定したい方は上記リンクを参照すると良いと思います。

使った感想としては、簡単でデバッグもしやすいと感じたのでLarkを使うのも悪くないと思いました。

この記事での目標

以下のサンプルを解釈し、関数呼び出しが可能な言語を目指す。

関数 main(){
    出力("Hello world")
}

関数 main(){

出力("Hello world")

}

こちらが実装できれば変数の保持なども可能になると思うので簡単な言語は自由に作れると思います。

準備運動

larkをインストールする

$ pip install lark-parser

1	$ pip install lark-parser

（余談）pythonはanyenv, pyenv, pyenv-virtualenvの構成が気に入ってます

文字列が解釈できるだけのパーサを作成する。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from lark import Lark

grammar = '''
    ?start: statement+
    statement: string
    string: CHAR+
    CHAR: "a" .. "y"
    
    %ignore "z"
'''

text = "abcz"

parser = Lark(grammar, parser='lalr')

print(parser.parse(text))
print(parser.parse(text).pretty())

#!/usr/bin/env python

# -*- coding: utf-8 -*-

from lark import Lark

grammar = '''

?start: statement+

statement: string

string: CHAR+

CHAR: "a" .. "y"

%ignore "z"

'''

text = "abcz"

parser = Lark(grammar, parser='lalr')

print(parser.parse(text))

print(parser.parse(text).pretty())

7 ~12行目の文字列がこの言語の文法を定義している部分です。公式のリファレンスはこちら。 How to useにチートシートも載っています。

?start: がこの言語の根元にあたり、Larkはデフォルトで?startを根元として扱います。

%ignoreは解釈しないものを定義する場所で、CHARはあえてa ~ yで定義しておいて、%ignoreで定義したzが無視されることを確認します。

19行目が実行で、結果が返ってきます。20行目のようにpretty関数を呼び出すと、木構造を整形して返してくれるので、デバッグに役立ちます。

実行結果は以下になります。

$ python main.py
Tree('statement', [Tree('string', [Token('CHAR', 'a'), Token('CHAR', 'b'), Token('CHAR', 'c')])])
statement
  string
    a
    b
    c

$ python main.py

Tree('statement', [Tree('string', [Token('CHAR', 'a'), Token('CHAR', 'b'), Token('CHAR', 'c')])])

statement

string

zが除外されていて、想定通りの結果となりました。

次に、実際に解析器を作成していきます。

基本はlarkからTransformerというクラスをインポートし、継承して作成します。

from lark import Lark, Transformer

4	from lark import Lark, Transformer

class Main(Transformer):
    def string(self, tokens):
        return "".join(tokens)

text = "abcz"

parser = Lark(grammar, parser='lalr', transformer=Main())

class Main(Transformer):

def string(self, tokens):

return "".join(tokens)

text = "abcz"

parser = Lark(grammar, parser='lalr', transformer=Main())

文法定義した名前をメソッド名にすると、treeに手を加えることができます。

今回はstringのtreeが来た時にcharを連結して返すようにしてみました。

結果は、以下になります。

$ python main.py
Tree('statement', ['abc'])
statement	abc

$ python main.py

Tree('statement', ['abc'])

statement abc

stringがchar tokenの集合ではなく、文字列として処理されたことがわかると思います。

また、処理された木は単純になりました。pretty関数でNoneが返ってきたら木が全て解釈されたということなので、エラーが出たときや順番に実装する時にはpretty関数で木構造の確認がおすすめです。

以上のことを理解したら実際に目標の言語を作っていきます。

実装

文法は以下のように定義します。

（余談）.lark拡張子にしておくとエディタによって拡張機能で補完とハイライトをつけることが可能です。

?start: statement+

?statement: function
    | instruction
    | function_call

code_block: "{" statement+ "}"
function: "関数" new_symbol "(" ")" code_block
function_call: symbol "(" ")"
instruction: "出力" "(" string ")" -> out

string    : ESCAPED_STRING
symbol    : WORD
new_symbol: WORD

%import common.ESCAPED_STRING
%import common.WORD
%import common.WS
%ignore WS

?start: statement+

?statement: function

| instruction

| function_call

code_block: "{" statement+ "}"

function: "関数" new_symbol "(" ")" code_block

function_call: symbol "(" ")"

instruction: "出力" "(" string ")" -> out

string : ESCAPED_STRING

symbol : WORD

new_symbol: WORD

%import common.ESCAPED_STRING

%import common.WORD

%import common.WS

%ignore WS

準備段階でstringを自分で定義していましたが、実はlarkが標準で用意してくれているものがあるのでインポートするだけで良いです。（L16~22）

今回やりたいのは関数定義、出力という関数、定義した関数の呼び出しだけなのでstatementはL3~5のようになります。あとは右側で出てきたものをきちんと定義してあげれば完成です。

instructionの矢印はエイリアスを作成しています。今回は予約関数が一つだけなのであまり効果はみられませんが、名前をつけておくとエイリアスの名前がtreeの名前(data)になるため、複数の予約語がある場合に名前によってメソッドを切り替えることができます。

次にパーサのクラスを実装します。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from lark import Lark, Transformer

def out(string):
    print(string[0])

class Main(Transformer):
    def __init__(self):
        self._functions = {}

    def function(self, token):
        self._functions[token[0]] = token[1:]
    
    def function_call(self, token):
        function = self._functions[token[0]]
        for state in function:
            eval(state.data)(state.children)

    def code_block(self, tree):
        return tree[0]

    def new_symbol(self, token):
        return token[0].value
    
    def symbol(self, token):
        return token[0].value

    def string(self, token):
        return token[0][1:-1]

text = '''
    関数 main(){
        出力("Hello world")
    }
    main()
    '''

# ファイル分けしたので、中身全部読んで変数に入れる
grammar = ""
with open('grammar.lark', 'r', encoding='utf-8') as a_file:
    grammar = ''.join([line for line in a_file])

parser = Lark(grammar, parser='lalr', transformer=Main())
parser.parse(text)

#!/usr/bin/env python

# -*- coding: utf-8 -*-

from lark import Lark, Transformer

def out(string):

print(string[0])

class Main(Transformer):

def __init__(self):

self._functions = {}

def function(self, token):

self._functions[token[0]] = token[1:]

def function_call(self, token):

function = self._functions[token[0]]

for state in function:

eval(state.data)(state.children)

def code_block(self, tree):

return tree[0]

def new_symbol(self, token):

return token[0].value

def symbol(self, token):

return token[0].value

def string(self, token):

return token[0][1:-1]

text = '''

関数 main(){

出力("Hello world")

}

main()

'''

# ファイル分けしたので、中身全部読んで変数に入れる

grammar = ""

with open('grammar.lark', 'r', encoding='utf-8') as a_file:

grammar = ''.join([line for line in a_file])

parser = Lark(grammar, parser='lalr', transformer=Main())

parser.parse(text)

関数定義がされた時はフィールド変数にツリー状のまま束縛するのがポイントです。

そのためには、予約語はクラスの外に書く必要があります。（パーサ働いてしまってツリーが解釈される）

そのほかはpythonの基本が分かれば読めるぐらい単純です。

実行結果は以下の通りになります。

$ python main.py
Hello world

1 2	$ python main.py Hello world

おまけ

実行部分を以下のように変更すると簡単にPythonのインタプリタっぽいものもできます。

message = '>>> '
text = ''
while True:
    try:
        s = input(message)
        if s == 'exit()': break
        text += s
        parser.parse(text)
        text = ""
        message = '>>> '
    except:
        message = '... '

message = '>>> '

text = ''

while True:

try:

s = input(message)

if s == 'exit()': break

text += s

parser.parse(text)

text = ""

message = '>>> '

except:

message = '... '

まとめ

今回は単純に関数が定義できて、実行できるというものを作成しましたが、言語としてはいまいちです。

ただ、初めて言語開発をしてみましたが、ライブラリを用いればこんなに簡単に作れるんだという発見もありました。

今後の展望としては、最低でも変数の定義、関数の引数を渡せるようにしてみようと思います。

月	火	水	木	金	土	日
« 10月
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30