💬

個人的に最強のパーサジェネレータLarkについて

2022/07/29に公開

Python

構文解析

Lark

tech

パーサとは?

文字列を一定のルールをもとに解析するプログラムのことです。
例えば各 OS のターミナルアプリは入力された文字列をシェルスクリプトというルールに基づいて解析・実行します。

入力

# 入力
ls -l -a
⏬ ⏬ ⏬
# 解析
- コマンドは「ls」  # コマンドを解析
- オプションは「-l」と「-a」  # オプションを解析
⏬ ⏬ ⏬
# 実行
- lsはファイルの一覧を探すコマンドだからファイル一覧を表示
- -lオプションがあるからリスト形式で表示する
- -aオプションがあるから隠しファイルも表示する

パーサジェネレータとは?

パーサを作るためのプログラムのことです。今回紹介したい Lark は Python のパーサジェネレータになります。

何ができるの?

いわゆる俺俺言語が作れます。

作ってみよう

今回は下のようなしょうもない言語を作って Lark を体験してみたいと思います。

自作言語記述例

変数 x に 10 を代入  //<-代入する値は数字のみ
x を表示

できることは

「変数 <変数名> に <数字> を代入」と書くと変数に値を代入する
「<変数名または数字> を表示」と書くと画面に「表示: <対象>」と表示する

準備

Python の環境構築が必須です
pip install larkで Lark をインストールしましょう
VSCode にLark grammar syntax supportという拡張機能があるので検索してインストールしましょう

Lark の基本

適当なディレクトリにプロジェクトディレクトリをきったら、その下にファイルを 2 つ作成します。

プロジェクトディレクトリ
+ mylang.lark
+ mylang.py

mylang.lark には Lark の文法に則ってパーサの文法を記述します。（後述）
mylang.py にはmylang.larkを読み取り、実行するための Python スクリプトを記述します。

mylang.lark に文法を記述

まずは簡単な文法を定義してみましょう。とりあえず以下の通り書いてください。(Lark では大体以下の文が必須になりがち)

mylang.lark

?start      : cmd   //文法のトップ、全ての入力文字列はここを起点に解析される

cmd         : //🌟ここに書いていく🌟

%import common.WS  // commonからWS(スペースなどの空白文字)をインポート

%ignore WS  // 空白文字は無視する

「//🌟 ここに書いていく 🌟」に色々書いていきます

今回 1 回の入力で受け取った文字列「? を表示」はか「変数 ? に ? を代入」のどちらかしかないので、前者をshow、後者をvarという名前でおいておきます。よって cmd には以下のように書きます。（A|Bが A または B を表す）

mylang.lark

//...
cmd         : var | show  //varとshowは後で実装
//...

次にvarとshowについてそれぞれ実装します。
変数が当てはまるところにはvar_name,数字が当てはまるところにはnumberをおいてこれらも後で実装しましょう。

mylang.lark

//...
cmd         : var | show
var         : "変数" var_name "に" number "を代入"
show        : (var_name|number) "を表示"
//...

var_nameとnumberについてですが、それぞれ変数名や数字に適したパターンがあらかじめ common というところに定義してあるので%import common ◯◯でインポートして使用します。

mylang.lark

//...
%import common.NUMBER
%import common.CNAME

var_name    : CNAME
number      : NUMBER
//...

これで文法が完成しました。以下が mylang.lark 全体です。

mylang.lark

?start      : cmd

cmd         : show | var

var         : "変数" var_name "に" number "を代入"
show        : (var_name|number) "を表示"

var_name    : CNAME
number      : NUMBER

%import common.NUMBER
%import common.CNAME
%import common.WS

%ignore WS

mylang.py で実行処理を定義

実は Lark でのパーサの実行はいくつかやり方があるのですが、今回のような俺俺言語を作りたい時にうってつけのパターンで紹介します。

まずは下のように Lark クラスをインスタンス化して parse メソッドを呼び出すプログラムを書きます。

mylang.py

from lark import Lark

parser = Lark(
    open("./mylang.lark"),  # mylang.larkを読み込む
    parser='lalr'
)

パース結果 = parser.parse("入力文字列")

ここの Lark クラスのコンストラクタに Transformer というものを渡します。これは入力文字列を解析して解析木(=Tree,構文解析木,後述)にした後に文字列の配列をいろいろなオブジェクトに変換したり、任意の処理を実行するためのクラスです。

以下のように Transformer を継承した ToMyLang クラスを実装し、

mylang.py

class ToMyLang(Transformer):
    # 後で色々書く

Lark クラスのコンストラクタにtransformer=ToMyLang()といった形で指定します。

mylang.py

  parser = Lark(
      open("./mylang.lark"),
      parser='lalr',
+     transformer=ToMyLang()
  )

ToMyLang クラスには ①Tree を受け取って、② 何かに変換したり処理を実行して、③ 変換した結果を返すメソッドを記述します。これらのメソッド名はmylang.larkで定義した各ルール名(◯◯ : ...の ◯◯)と対応づけるようにします。

例えば以下のように書きます。

mylang.py

class ToMyLang(Transformer):
    def number(self, tree):　# ①Treeを受け取る
        token = tree[0].value
        return float(token) # ②,③ 変換したり、処理を実行氏、変換結果を返す

print 関数で tree を表示するとわかりやすいのですが tree は Tree クラスのインスタンスが入った配列になっています。Tree インスタンスは value プロパティを参照することで該当パターンにマッチした文字列を受け取ることができます。

treeのイメージ-1

# 入力文字列 : "10 20"
# .larkファイルに指定した該当パターン : NUMBER NUMBER
#   の時に受け取るtree
[ Tree('10') , Tree('20') ]

# よって以下のように"10"と"20"にアクセスできる
first = tree[0].value  # "10"
second = tree[1].value  # "10"

numberやvar_nameは比較的簡単なのでそれぞれメソッドを以下のように実装しましょう。

mylang.py

class ToMyLang(Transformer):
    def number(self, tree):
        token = tree[0].value
        return float(token)
    def var_name(self, tree):
        token = tree[0].value
        return str(token)

それぞれ 1 つ目を受け取って数字や文字列に変換しています。

続いてvarとshowメソッドも実装しましょう。

これらも先ほどと同じ要領で実装できるのですが 1 つだけ注意点があります。

mylang.py

variables = {}  # 変数一覧を保持する
class ToMyLang(Transformer):
    def var(self, tree):
        name = tree[0]
        value = tree[1]
        variables[name] = value

mylang.larkではvarは"変数" var_name "に" number "を代入"と定義したので tree の 1 番目には var_name に対応するものが、2 番目には number に対応するものが取得できます。が Lark ではvar_name や number は先ほど定義したそれぞれに対応するメソッドの戻り値が tree の各要素に渡される仕様になっています。

よって tree[0]には var_name メソッドの実行結果が、tree[1]には number メソッドの実行結果が代入されます。なのでtree[０].valueのようにvalue プロパティを参照するとエラーになります(数字リテラルには value プロパティがないため)。

それを踏まえて show メソッドも実装しましょう。

mylang.py

  class ToMyLang(Transformer):
      def var(self, tree):
          name = tree[0]
          value = tree[1]
          variables[name] = value
+     def show(self, tree):
+         target = tree[0]
+         if(type(target) == str):
+             target = variables[target] # 変数名がtargetの変数の値を参照
+         elif(type(target) == int):
+             target = float(target)
+         print("表示:", target)

これで各処理を実装できました。

最後に一番最後に実行する部分で俺俺言語のプログラムを渡してみましょう。

mylang.py

parser.parse(r"変数 x に 10 を代入")
parser.parse(r"変数 y に 10 を代入")
parser.parse(r"変数 z に 10 を代入")
parser.parse(r"x を表示")
parser.parse(r"40 を表示")

これで一通り mylang.py を実装できました。
この時点でmylang.pyの内容は以下の通りになっているはずです。

mylang.py

from lark import Lark, Transformer

variables = {}

class ToMyLang(Transformer):
    def number(self, tree):
        print(tree)
        token = tree[0].value
        return float(token)

    def var_name(self, tree):
        token = tree[0].value
        return str(token)

    def var(self, tree):
        name = tree[0]
        value = tree[1]
        variables[name] = value

    def show(self, tree):
        target = tree[0]
        if(type(target) == str):
            target = variables[target]
        elif(type(target) == int):
            target = float(target)
        print("表示:", target)


parser = Lark(
    open("./cmd.lark"), parser='lalr',
    transformer=ToMyLang()
)

parser.parse(r"変数 x に 10 を代入")
parser.parse(r"変数 y に 10 を代入")
parser.parse(r"変数 z に 10 を代入")
parser.parse(r"x を表示")
parser.parse(r"40 を表示")

完成したので実行してみましょう。以下のように実行できたら成功です！

表示: 10.0
表示: 40.0

Lark の押しポイント

文法が正規表現+BNF(ebnf というそうです)なので親しみやすい(覚えやすい)ですし、正規表現をゴリゴリ書くよりもわかりやすいかと思います。公式のレファレンスを見れば頷ける文法も多いはず。

lark ファイルと python スクリプトでの対応づけが気持ちいくらいにわかりやすいです。このパターンにはこのメソッドが対応するといった感じで文法が 1 つのクラスに対応するようになってます。

今回紹介したのは Lark の文法・機能のほんの一部です。興味を持った方は是非ご自身で公式レファレンスをご一読ください。

素晴らしいライブラリ Lark のご紹介でした 😁

パーサとは?

パーサジェネレータとは?

何ができるの?

作ってみよう

準備

Lark の基本

mylang.lark に文法を記述

mylang.py で実行処理を定義

Lark の押しポイント

Discussion