💱

JuliaのPEGパーサ、PEG.jlの使い方メモ

2023/03/12に公開

JuliaのPEGパーサであるPEG.jlを使ってみました。
https://github.com/wdebeaum/PEG.jl

PEGパーサについては、Rubyの parslet を少し触った程度の知識なので、詳しいことは書けませんが簡単な使い方をまとめます。

概要

@rule マクロでルールを作って、
parse_whole 関数でルールを元に文字列をパースします。

例1: 文字列"key: value"を、JuliaのDict型に変換する

using PEG

@rule word = r"\w+"
@rule pair = word & ": " & word |> w -> Dict(w[1] => w[3])

parse_whole(pair, "foo: bar")

上記を実行すると以下が取得できます。

Dict{SubString{String}, SubString{String}} with 1 entry:
  "foo" => "bar"

文字列 "foo:bar" から、Dict型の "foo" => "bar" を取得できました。

@rule の評価式は、正規表現や文字列、他のルールを & でつなげて書けます。
"foo: bar" をパースして、["foo", ": ", "bar"] という具合に分解したいので、正規表現で書いた word ルールと ": " をつなげます。

|> は、Julia のパイプ処理の記法で、word & ": " & word で取得できた Vector を変数 w に入れて無名関数でDict型に変換しています。

また、以下のように書けば、パースと変換を一度に行わずに、パース → 変換というように分けて行なうこともできます。

using PEG

@rule word = r"\w+"
@rule pair = word & ": " & word
result = parse_whole(pair, "foo: bar")

function transform(parsed)
    Dict(parsed[1] => parsed[3])
end

transform(result) # == "foo" => "bar"

例2: 文字列で書かれた数式を評価する

using PEG

@rule formula   = integer & operation & integer |> calculate
@rule integer   = r"\s*\d+\s*" |> i -> parse(Int, i)
@rule operation = "+", "-"

function calculate(expression)
    left, op, right = expression
    return eval(Symbol(op))(left, right)
end

parse_whole(formula, "1 + 2") # == 3
parse_whole(formula, "1 - 2") # == -1

|> には無名関数ではなく普通の関数も渡せます。
@rule operation = "+", "-" のように , で区切るとORで評価することができます。

calculate 関数の中は括弧が多いですが、やってることは以下です。

Symbol("+")    # == :+
eval(:+)(1, 2) # == 3

基本型の変換

数字

using PEG

@rule int1 = r"-?(0|[1-9]\d*)"
@rule int2 = r"-?(0|[1-9]\d*)" |> i -> parse(Int, i)
@rule int3 = r"-?(0|[1-9]\d*)" |> Meta.parse
parse_whole(int1, "123") # == "123"
parse_whole(int2, "123") # == 123
parse_whole(int3, "123") # == 123

メタプログラミング用の Julia の Meta.parse 関数は便利そうです。

Meta.parse("123") == 123 # == true

https://docs.julialang.org/en/v1/manual/metaprogramming/

文字列

using PEG

@rule word1 = r"\S+"
@rule word2 = r"\S+"w
@rule word3 = r"\S+"p
@rule str1  = word1[+]
@rule str2  = word2[+]
@rule str3  = word3[+]
parse_whole(str1, "test")          # == ["test"]
parse_whole(str1, "test ")         # ERROR
parse_whole(str2, "test ")         # == ["test"]
parse_whole(str2, "test 123\n")    # == ["test", "123"]
parse_whole(str2, "test 123 #1\n") # ERROR
parse_whole(str3, "test 123 #1\n") # => ["test", "123", "#1"]

ルールの後ろに[+]をつけると、1回以上の繰り返しというルールになります。
0回以上なら[*]、0もしくは1回なら[:?]を使います。

PEG.jl では、正規表現の後ろに w, p をつけることで、後続の空白文字を除去してキャプチャできます。
w なら単語の区切りまでの正規表現になります。(\b)

ブーリアン

using PEG

@rule bool1 = r"true|false"
@rule bool2 = r"true|false" |> b -> parse(Bool, b)
@rule bool3 = r"true|false" |> Meta.parse
@rule bool4 = r"true|false" |> Meta.parse |> Int
parse_whole(bool1, "true")  # == "true"
parse_whole(bool2, "true")  # == true
parse_whole(bool2, "false") # == false
parse_whole(bool3, "true")  # == true
parse_whole(bool3, "false") # == false
parse_whole(bool4, "true")  # == 1
parse_whole(bool4, "false") # == 0

日付、時刻

using PEG
using Dates

@rule date =
    r"\d{4}" & date_sep & r"\d{2}" & date_sep & r"\d{2}" >
    (y,_,m,_,d) -> Date("$y-$m-$d")
@rule date_sep = ("-", "/")[:?]
@rule datetime =
    date & r"\s?T?" & r"\d{2}" & r"\:?" & r"\d{2}" & r"\:?" & r"(\d{2})?" >
    (date,_,h,_,m,_,s) -> DateTime("$(date)T$h:$m:$s")

parse_whole(date, "2013-01-18") # == 2013-01-16
parse_whole(date, "20130118")   # == 2013-01-16
parse_whole(date, "2013/01/18") # == 2013-01-16
parse_whole(datetime, "2013-01-18T12:34:56") # == 2013-01-18T12:34:56
parse_whole(datetime, "2013/01/18 12:34:56") # == 2013-01-18T12:34:56
parse_whole(datetime, "20130118123456")      # == 2013-01-18T12:34:56
parse_whole(datetime, "2013/01/18 12:34")    # == 2013-01-18T12:34:00

|> ではなく、> で渡すと引数を展開して受け取れます。
r"\d{4}" & date_sep & r"\d{2}" & date_sep & r"\d{2}" で欲しいのは、date_sep 以外なので、> (y,_,m,_,d) -> Date("$y-$m-$d") として必要なところだけ受け取ってパースします。

Julia の文字列展開は "$y-$m-$d" のように $ を使います。

配列

using PEG

@rule value = r"\w+"p
@rule arr1  = "[" & (value & (r"\,"p & value)[*])[:?] & "]" |> (a) -> a
@rule arr2  = "[" & (value & (r"\,"p & value)[*] > (h, arr) 
	-> [h, map(x -> x[2], arr)])[:?] & "]" |> (a) -> a[2]

@rule arr3  = "[" & (value & (r"\,"p & value)[*] > array_format)[:?] & "]" |> (a) -> a[2]
array_format(head, others) = [head, map(x -> x[2], others)...]

@rule arr4  = "[" & (value & (r"\,"p & value)[*] > array_format)[:?] & "]" |> (a) -> isempty(a[2]) ? [] : a[2][1]

parse_whole(arr1, "[1, 2, 3]")
# == 3-element Vector{Any}:
#     "["
#     Any[Any["1", Any[Any[",", "2"], Any[",", "3"]]]]
#     "]"
parse_whole(arr2, "[1, 2, 3]")
# == 1-element Vector{Any}:
#     Any["1", SubString{String}["2", "3"]]

parse_whole(arr3, "[1, 2, 3]")
# == 1-element Vector{Any}:
#     SubString{String}["1", "2", "3"]

parse_whole(arr4, "[1, 2, 3]")
# == 3-element Vector{SubString{String}}:
#     "1"
#     "2"
#     "3"

parse_whole(arr4, "[1, 2, 3]") == ["1", "2", "3"] # == true

(value & (r"\,"p & value)[*]) では、["1", [[",", "2"], [",", "3"]] が取れるので、配列の先頭とそれ以外で取り出し方を分ける必要があります。
先頭はそのまま。それ以外は [",", "2"] のようにカンマも一緒に入っているので、2番目のみ取り出します。
単に取り出しただけではフラットにならないので、[head, map(x -> x[2], others)...] のように ... をつけて配列を展開します。

[1, [2,3]...] # == [1, 2, 3]

ただし、それがそのまま返ってくればよいですが、(value & (r"\,"p & value)[*] > array_format)[:?] のように [:?] を末尾につけるとVectorで返ってきます。
正規表現で書いた場合と挙動が違うので注意が必要です。

using PEG
@rule one_or_nothing1 = "foo"[:?]
@rule one_or_nothing2 = r"(foo)?"
parse_whole(one_or_nothing1, "foo")
# == 1-element Vector{Any}:
#     "foo"
parse_whole(one_or_nothing2, "foo") # == "foo"

そのため、 arr4 のように [["1", "2", "3"]] のような1要素のVectorから最初の要素を取得するため isempty(a[2]) ? [] : a[2][1] をしています。

応用

TOMLをJSONに変換する

using PEG
using Dates
using JSON

toml ="""
# This is a TOML document

title = "TOML Example"

[owner]
name = "Tom Preston-Werner"
dob = 1979-05-27T07:32:00-08:00

[database]
enabled = true
ports = [ 8000, 8001, 8002 ]
data = [ ["delta", "phi"], [3.14] ]
temp_targets = { cpu = 79.5, case = 72.0 }

[servers]

[servers.alpha]
ip = "10.0.0.1"
role = "frontend"

[servers.beta]
ip = "10.0.0.2"
role = "backend"
"""

@rule document = block[+] |> v -> filter(!isnothing, v) |> d -> merge(d...)
@rule block    = comment, chunk, pair, crlf
@rule crlf     = r"\r?\n"p |> x -> nothing
@rule comment  = r"#"p & r"[^\n]*"p    > (_,c)     -> nothing
@rule chunk    = head & crlf & pair[*] > (h,_,arr) -> Dict(h => isempty(arr) ? [] : merge(arr...))
@rule head     = "[" & key & "]"       > (_,k,_)   -> k
@rule pair     = key & r"="p & value   > (k,_,v)   -> Dict(k => v)
@rule key      = r"(\w|\.)+"w
@rule value    = string, datetime, date, boolean, array, object, number

@rule string   = r"\"[^\"]*\""p |> s -> replace(s, "\"" => "")
@rule number   = r"-?(0|[1-9]\d*)(\.\d+)?"p |> Meta.parse
@rule boolean  = r"true|false"w             |> Meta.parse
@rule date =
    r"\d{4}" & date_sep & r"\d{2}" & date_sep & r"\d{2}" >
    (y,_,m,_,d) -> Date("$y-$m-$d")
@rule date_sep = ("-", "/")[:?]
@rule datetime =
    date & r"\s?T?" & r"\d{2}" & r"\:?" & r"\d{2}" & r"\:?" & r"(\d{2})?" & r"(-\d{2}\:\d{2})?"p >
    (date,_,h,_,m,_,s,z) -> DateTime("$(date)T$h:$m:$s")

@rule array    = r"\["p & (value & (r"\,"p & value)[*] > comma_format)[:?] & r"\]"p |> (a) -> isempty(a[2]) ? [] : a[2][1]
@rule object   = r"\{"p & (pair  & (r"\,"p & pair)[*] > comma_format) & r"\}"p > (_, p, _) -> merge(p...)

comma_format(head, others) = [head, map(x -> x[2], others)...]

result = parse_whole(document, toml)
# == Dict{SubString{String}, Any} with 6 entries:
#    "servers"       => Any[]
#    "servers.beta"  => Dict{SubString{String}, String}("role"=>"backend", "ip"=>"10.0.0.2")
#    "owner"         => Dict{SubString{String}, Any}("name"=>"Tom Preston-Werner", "dob"=>DateTime("1979-05-27T07:32:00"))
#    "title"         => "TOML Example"
#    "servers.alpha" => Dict{SubString{String}, String}("role"=>"frontend", "ip"=>"10.0.0.1")
#    "database"      => Dict{SubString{String}, Any}("data"=>Vector[["delta", "phi"], [3.14]], "enabled"=>true, "ports"=>[8000, 8001, 8002], "temp_targets…

write("toml_parsed.json", json(result))
toml_parsed.json
{
  "servers": [],
  "servers.beta": {
    "role": "backend",
    "ip": "10.0.0.2"
  },
  "owner": {
    "name": "Tom Preston-Werner",
    "dob": "1979-05-27T07:32:00"
  },
  "title": "TOML Example",
  "servers.alpha": {
    "role": "frontend",
    "ip": "10.0.0.1"
  },
  "database": {
    "data": [
      ["delta", "phi"],
      [3.14]
    ],
    "enabled": true,
    "ports": [8000, 8001, 8002],
    "temp_targets": {
      "cpu": 79.5,
      "case": 72.0
    }
  }
}

作業中は Julia 公式のアドオンを入れた VSCode で、ctrl-Enter でこまごま選択範囲を実行して結果を確かめながらテストを書いてました。
ちょっとした変更で直前まで動いていたものが壊れるので、テストコード大事だなと思いました。

using Test

@testset "basic" begin
    @test parse_whole(crlf, "\n") |> isnothing
    @test parse_whole(string, "\"TOML Example\"") == "TOML Example"
    @test parse_whole(head, "[owner]") == "owner"
    @test parse_whole(datetime, "1979-05-27T07:32:00-08:00") |> typeof == DateTime
    @test parse_whole(boolean, "true") == true
    @test parse_whole(number, "8000") == 8000
    @test parse_whole(key, "servers.alpha") == "servers.alpha"
end

@testset "combination" begin
    @test parse_whole(pair, "name = \"Tom Preston-Werner\"")   == Dict("name" => "Tom Preston-Werner")
    @test parse_whole(pair, "dob = 1979-05-27T07:32:00-08:00") == Dict("dob" => DateTime("1979-05-27T07:32:00"))
    @test parse_whole(value, "1979-05-27T07:32:00-08:00") |> !isnothing
    @test parse_whole(value, "\"TOML Example\"") |> !isnothing
    @test parse_whole(value, "8000") |> !isnothing
    @test parse_whole(array, "[ 8000, 8001, 8002 ]") == [8000, 8001, 8002]
    @test parse_whole(array, "[ [\"delta\", \"phi\"], [3.14] ]") |> typeof == Vector{Vector}
    @test parse_whole(object, "{ cpu = 79.5, case = 72.0 }") == Dict("cpu" => 79.5, "case" => 72.0)
end

@testset "block" begin
    @test parse_whole(comment, "# This is a TOML document") |> isnothing
    @test parse_whole(chunk, "[servers]\n") == Dict("servers" => [])
    @test parse_whole(chunk, """
    [owner]
    name = "Tom Preston-Werner"
    dob = 1979-05-27T07:32:00-08:00
    """) == Dict("owner" => Dict(
        "name" => "Tom Preston-Werner",
        "dob"  => DateTime("1979-05-27T07:32:00")
    ))
    @test parse_whole(chunk, """
    [database]
    enabled = true
    ports = [ 8000, 8001, 8002 ]
    data = [ ["delta", "phi"], [3.14] ]
    temp_targets = { cpu = 79.5, case = 72.0 }
    """) == Dict("database" => Dict(
        "enabled" => true,
        "ports"   => [8000, 8001, 8002],
        "data"    => [ ["delta", "phi"], [3.14] ],
        "temp_targets" => Dict(
            "cpu"  => 79.5,
            "case" => 72.0,
        ),
    ))
end

@testset "document" begin
    @test parse_whole(document, """
    [servers]

    [servers.alpha]
    ip = "10.0.0.1"
    role = "frontend"
    """) == Dict(
        "servers" => [],
        "servers.alpha" => Dict(
            "ip"   => "10.0.0.1",
            "role" => "frontend"
        )
    )
end

できたものはここに置いてます。
https://github.com/tkmfujise/PEG.jl_examples

Discussion