🅿️

Elmで数式の再帰下降構文解析を実装

2023/09/03に公開

はじめに

「低レイヤを知りたい人のための C コンパイラ作成入門」^[1]で再帰下降構文解析を学んだ。再帰下降構文解析の wikipedia^[2]を参照すると「Haskell や ML などの関数型言語での再帰下降構文解析の実装は特に簡単である。」と記載されている。

そこで、この記事では関数型言語である Elm を用いて再帰下降構文解析を実装して本当に簡単に実装できるのか試してみる。

取り扱う文字列

この記事では以下のような数式を

30 + (4 - 2) * -5

以下のような抽象構文木に変換し

Add (Int 30) (Mul (Sub (Int 4) (Int 2)) (Neg (Int 5)))

20と計算できるコードを書く。

BNF 記法と代数的データ型

この数式を BNF 記法で記述すると次のようになる。

expr    = mul ("+" mul | "-" mul)*
mul     = unary ("*" unary | "//" unary)*
unary   = "-"? primary
primary = int | "(" expr ")"

厳密にはスペースも考慮して記述する必要があるが、今回は無視している。

また抽象構文木は、代数的データ型を用いて次のように定義する。

type Expr
    = Int Int
    | Neg Expr
    | Add Expr Expr
    | Sub Expr Expr
    | Mul Expr Expr
    | Div Expr Expr

Expr, Mul, Unary, Primaryと 4 つの型を定義することもできるが、今回は細かく分離はしない。（BNF 記法に合わせて細かく型を分離する実装は一般的には行わないようである。細かく分離すると言語が大きくなるにつれて破綻するのだろうか。）

パーサーの実装

上記で定義した数式をパースする関数を記述する。

この記事ではelm/parserを用いて実装を行う。elm/parser の詳細な使い方については後述の参考文献を見てほしい。elm/parser は次のように使う。Parser.runに自分で定義したパーサー(今回の場合はexpr)をと文字列を渡すことで、Result 型に包まれた Expr 型のデータが返ってくる。

import Parser exposing ((|.), (|=), Parser, Step(..), andThen, chompWhile, int, lazy, oneOf, succeed, symbol, spaces)

parse : String -> Result (List Parser.DeadEnd) Expr
parse p =
    Parser.run expr p

Parser.runに自分で定義したパーサー(今回の場合はexpr)をと文字列を渡すことで、Result 型に包まれた Expr 型のデータが返ってくる。

次にexprを定義する。

-- expr = mul ("+" mul | "-" mul)*

expr : Parser Expr
expr =
    let
        exprHelp : Expr -> Parser Expr
        exprHelp left =
            oneOf
                [ succeed (Add left)
                    |. symbol "+"
                    |= lazy (\_ -> mul)
                    |> andThen exprHelp
                , succeed (Sub left)
                    |. symbol "-"
                    |= lazy (\_ -> mul)
                    |> andThen exprHelp
                , succeed left
                ]
    in
    mul |> andThen exprHelp

oneOf は与えられたパーサーのリストをはじめから順番に実行していき、最初にマッチしたものでパースする。ただ、途中までパースが進んでしまうと(backtrackable^[3]を使わない限り)戻れないため、はじめに最初のmul項だけパースした後に"+"or"-"を見て分岐するように実装している。また、mulを呼ぶときは lazy にしないと遅くなる。これは Elm が正格評価であることに起因する。

同様にmulを定義する。

-- mul = unary ("*" unary | "//" unary)*

mul : Parser Expr
mul =
    let
        mulHelp : Expr -> Parser Expr
        mulHelp left =
            oneOf
                [ succeed (Mul left)
                    |. symbol "*"
                    |= lazy (\_ -> unary)
                    |> andThen mulHelp
                , succeed (Div left)
                    |. symbol "//"
                    |= lazy (\_ -> unary)
                    |> andThen mulHelp
                , succeed left
                ]
    in
    unary |> andThen mulHelp

同様にunaryを定義する。

-- unary = "-"? primary

unary : Parser Expr
unary =
    succeed identity
        |. spaces
        |= oneOf
            [ succeed Neg
                |. symbol "-"
                |= primary
            , succeed identity
                |= primary
            ]

同様にprimaryを定義する。

-- primary = int | "(" expr ")"

primary : Parser Expr
primary =
    succeed identity
        |= oneOf
            [ succeed Int
                |= int
            , succeed identity
                |. symbol "("
                |= lazy (\_ -> expr)
                |. symbol ")"
            ]
        |. spaces

このように再帰関数だけでパースするやり方の他にも、演算の束縛力の強さを数値化してパースするやり方もある。(Pratt パーサーと呼ばれている。)

評価

Exprは以下の関数で実行できる。

evaluate : Expr -> Int
evaluate e =
    case e of
        Int x ->
            x

        Neg x ->
            -(evaluate x)

        Add x y ->
            evaluate x + evaluate y

        Sub x y ->
            evaluate x - evaluate y

        Mul x y ->
            evaluate x * evaluate y

        Div x y ->
            evaluate x // evaluate y

おわりに

Elm で再帰下降構文解析を実装した。確かに記述量は短くなったが、for 文や while 文を使えない分、少し実装は難しかったように感じる。代数的データ型は struct に比べて所持できる値が少ないため、安全にコードは書けそうではある。

参考文献

elm/parser のドキュメント

elm/parser にもこの記事と同様の数式パースの例がある。この例では算術演算の左結合を再現するために一回リスト構造にしてから reverse する手法が取られている。

elm/parser の日本語の解説記事。基本的な使い方はこれで学べる。

elm で Pratt パーサーを使って数式計算を実装した記事。

elm で TaPL を実装した記事。

脚注