F#+FParsecで電卓パーサーを作る

前がき

先日 Writing An Interpreter in Go を読み、とても感銘を受けました。

どうやら「再帰下降構文分析法」と「演算子順位構文解析法」を組み合わせて使うと、演算子を使うような構文をパースすることができるらしいです。

詳しく知りたい方は上記書籍を買って読んでください。

https://interpreterbook.com/

この本に触発され、私も何かしらのパーサーを書いてみたくなりました。

そこまで複雑でないパーサーを書いてみたい → 題材は電卓にしよう
好きな言語で書きたい → F#で書いてみよう
パーサーは一から作りたくない → パーサーコンビネーターを使おう

というわけで、F#+FParsecで電卓パーサーを書いてみようと思います。

FParsecとは

FParsecとはF#製のパーサーコンビネーターです。パーサーコンビネーターとは、小さなパーサーをどんどんつなげて複雑なパーサーを作っていく手法・およびそれを実現するツールのことです。

例えば、aiueoまたはkakikukekoの空白区切りの繰り返しは以下のように書けます。小さなパーサーを組み合わせていく雰囲気が何となく伝わりましたでしょうか。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#r "nuget: FParsec"

open FParsec

let aiueo = pstring "aiueo"
let kakikukeko = pstring "kakikukeko"

let aiueoまたはkakikukeko = aiueo <|> kakikukeko

let aiueoまたはkakikukekoの空白区切りでの繰り返し = sepBy aiueoまたはkakikukeko spaces1

let input = "aiueo kakikukeko"

match run (aiueoまたはkakikukekoの空白区切りでの繰り返し) input with
| Success(result, _, _) -> result.ToString() |> printfn "%s"
| Failure(errorMsg, _, _) -> failwith errorMsg

電卓パーサー

FParsecは演算子順位構文解析法をサポートしており、OperatorPrecedenceParser というものを使うと良さそうです。これを使って電卓を書いてみます。

演算子としては以下をサポートしてみましょう。

足し算・引き算
掛け算・割り算
冪乗
プレフィックスの＋やー

また、()を使って計算をグルーピングできるようにしてみましょう。

以下コードです。

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78


#r "nuget: FParsec"

open FParsec

// 数字と演算子を解析するための型
type Expr =
    | Number of float
    | Unary of char * Expr
    | Binary of Expr * char * Expr

let ws = spaces
let str_ws s = pstring s >>. ws

// 数値リテラルのパーサー
let number: Parser<Expr, unit> =
    pfloat .>> ws |>> Number

// 文字列を囲む括弧のパーサー
let parens p: Parser<Expr, unit> =
    between (str_ws "(") (str_ws ")") p

// 演算子の優先順位を定義
let opp = new OperatorPrecedenceParser<Expr, unit, unit>()

type PrefixOperator = PrefixOperator<Expr, unit, unit>
type InfixOperator = InfixOperator<Expr, unit, unit>

// 式のパーサーを初期化
let expr = opp.ExpressionParser

// 演算子を定義
// 前置演算子（符号変換など）
opp.AddOperator(PrefixOperator("-", ws, 1, true, fun x -> Unary('-', x)))
opp.AddOperator(PrefixOperator("+", ws, 1, true, fun x -> x))

// 加算、減算
opp.AddOperator(InfixOperator("+", ws, 1, Associativity.Left, fun x y -> Binary(x, '+', y)))
opp.AddOperator(InfixOperator("-", ws, 1, Associativity.Left, fun x y -> Binary(x, '-', y)))

// 乗算、除算
opp.AddOperator(InfixOperator("*", ws, 2, Associativity.Left, fun x y -> Binary(x, '*', y)))
opp.AddOperator(InfixOperator("/", ws, 2, Associativity.Left, fun x y -> Binary(x, '/', y)))

// 冪乗（右結合）
opp.AddOperator(InfixOperator("^", ws, 3, Associativity.Right, fun x y -> Binary(x, '^', y)))

// 括弧または数値リテラルを式として扱う
opp.TermParser <- (number <|> parens expr)

// 評価関数
let rec eval = function
    | Number n -> n
    | Unary('-', x) -> -eval x
    | Unary('+', x) -> eval x
    | Binary(x, '+', y) -> eval x + eval y
    | Binary(x, '-', y) -> eval x - eval y
    | Binary(x, '*', y) -> eval x * eval y
    | Binary(x, '/', y) -> eval x / eval y
    | Binary(x, '^', y) -> eval x ** eval y
    | _ -> failwith "Unsupported operation"

// 入力文字列を解析して評価する
let parseAndEval input =
    match run (ws >>. expr .>> eof) input with
    | Success(result, _, _) -> eval result
    | Failure(errorMsg, _, _) -> failwith errorMsg


let tests = [
    "1 + 2 * 3"    // 7
    "4 * (2 + 3)"  // 20
    "3 ^ 2 ^ 2"    // 81 (右結合)
    "-4 + 2"       // -2
    "(3 + 5) / 2"  // 4
]

for test in tests do
    printfn "Input: %s = %f" test (parseAndEval test)

実行してみます。

1
2
3
4
5
6


$ dotnet fsi calc_test.fsx  
Input: 1 + 2 * 3 = 7.000000
Input: 4 * (2 + 3) = 20.000000
Input: 3 ^ 2 ^ 2 = 81.000000
Input: -4 + 2 = -2.000000
Input: (3 + 5) / 2 = 4.000000

おお〜。動いてる。

まとめ

今回はF#+FParsecで電卓のパーサーを書いてみました。

電卓なんて世に溢れていますが、自分でパーサーを書くことで独自の演算子を追加できたり、演算の実行時に処理をカスタマイズできるので楽しそうです。

余談ですが、F#+fsxでスクリプトをさらっと記述できるの便利でとても重宝しています。利用するライブラリも同じスクリプトファイル内に記載できるのもいいですね。