ScanRat の紹介

# 初投稿です

[言語処理系 Advent Calender](http://qiita.com/advent-calendar/2015/lang_dev) 4日目の記事のようです.

適当に F# で何らかの処理系でも組むかと思ったら名状しがたいパーザコンビネータライブラリを見つけてしまい、完全に興味をそっちに持って行かれてしまったのでその紹介になります.

# ScanRat とは

[ScanRat - GitHub](https://github.com/pragmatrix/ScanRat)

F# 用の PEG の（ええ〜〜っ！？）パーザコンビネータライブラリです.

自動でパース結果をメモ化してくれます（ええ〜〜〜〜っ！？）.

直接左再帰が書けて、間接左再帰も書けます（ええ〜〜〜〜〜〜っ！？）.

# コンビネータ

ルールを組み合わせて新しいルールにします. すべて左結合です.

例があるものは公式 Readme からコピペ, ないのは自分で書いています. 原コードに適宜注釈を加えているものもあります.

* ```+``` コンビネータ

2つのルールを合体させます.

PEG では sequence に対応します.

```fsharp

let twoDigits = digits + digits

// PEG: twoDigits <- digits digits

```

派生として ```+.``` と ```.+``` があります.

```+``` が２つのルールのパース結果をタプルにして返すのに対し、これはドットがついている側のルールの結果のみを返し, ついていない側を無視します.

```fsharp

let digit = ...
// digit :: input -> int

let semicolon = ...
// semicolon :: input -> string

let digit_semi1 = digit + semi
// digit_semi1 :: input -> (int * string)

let digit_semi2 = digit .+ semi
// digit_semi2 :: input -> int

```

* ```|-``` コンビネータ

左のルールを試し, 成功したらパース結果, 失敗したら右のルールを試します.

PEG では ordered choice に対応します.

```fsharp

let eitherLeftOrRight = left |- right

// PEG: eitherLeftOrRight <- left / right

```

これは ```+``` より優先順位が低いので, ```+``` で構成される式を括弧で囲まなくてもよいです.

```fsharp

let driverDecision = accellerate + overtake |- driveSlowly
// driverDecision <- (accellerate overtake) / driveSlowly

```

* ```-->``` コンビネータ

コンビネータのパース結果を受け取り, 加工します.

```fsharp

let digit = ...
// digit :: input -> int

let twoDigitNumber = digit + digit --> fun (digit1, digit2) -> digit1 * 10 + digit2
// twoDigitNumber :: input -> int

```

* ```~~``` コンビネータ

```string``` 型にしか使えないコンビネータで, 文字列を受け取って単にその文字列にマッチするルールを返します.

ルールのパース結果の型は ```string``` です.

```fsharp

let hello = ~~"Hello"
// hello :: input -> string

// PEG: hello <- "hello"
```

* ```oneOf``` コンビネータ

```string``` 型にしか使えないコンビネータで, 文字列を受け取ってそのうちのどれか1文字にマッチするルールを返します.

```fsharp

let oneOrTwo = oneOf "12"
// oneOrTwo :: input -> char

// PEG: oneOrTwo <- "1" / "2"

```

これは以下のコードと同じ意味となります.

```fsharp

let oneOrTwo = (~~"1" |- ~~"2") --> fun str -> str.[0]
// oneOrTwo :: input -> char

```

# パースする

```parse``` 関数にルールを与えると, 文字列を受け取って成功ならば ```Success 結果```, 失敗ならば ```Failure エラー``` を返す関数になります.

今まで ```input -> a``` などとあたかも関数のように書いてましたがルール自体は関数じゃないです.

```fsharp

let digit = oneOf "0123456789" --> fun c -> int(c) - int('0')
// digit :: input -> int

let parsedigit = parse digit
// parsedigit :: string -> ParsingResult<int>

let r = parsedigit "3"
// r :: ParsingResult<int>
```

適当にパターンマッチに投げます.

```fsharp

match r with
  | Success s -> s.value
  | Failure f -> failwith "error"

```

# 再帰的文法の定義

```production``` 関数を使うと中身がないルールを作れるので, それに後付けでルールを入れます.

```fsharp

let digit = oneOf "0123456789" --> fun d -> int(d) - int('0')
// digit :: input -> int

let digits = production "digits"
// digits :: input -> ?

digits.rule
  <- digits + digit --> fun (a, b) -> a * 10 + b
  |- digit
// digits :: input -> int

// PEG: digits <- (digits + digit) / digit  (←！？)
```

これで思いっきり左再帰なものも普通に書けます.

例として, kmizu 氏の [PEG基礎文法最速マスター](http://kmizu.hatenablog.com/entry/20100203/1265183754) にある

> 左再帰
>
> PEGは再帰下降パーザの一種なので、左再帰をサポートしていません(左再帰をすると無限ループになります)。そのため、左再帰は明示的に繰り返しなどに変換してやる必要があります。たとえば、以下のような左再帰を使ったBNFは、

    A ::= A "a"
        | 

> 繰り返しを使って、"a"* と書くことができます。

を ScanRat ではそのまま書けます.

```fsharp
open ScanRat

let a = production "a"
a.rule 
  <- a + ~~"a" --> fun(x, a) -> x + a
  |- ~~""

let tryparsea s =
  match parse a s with
    | Success x -> x.value
    | Failure _ -> "error"

tryparsea "aaa" |> printfn "%A"
// "aaa"
tryparsea "bbb" |> printfn "%A"
// "error"
```

また, [白田 佳章 , 木山 真人 , 芦原 評: 「同一入力位置で複数発生する左再帰へ対応したPackrat Parsingの設計と実装」(情報処理学会論文誌 プログラミング（PRO） 4(2), pp.104-115, 情報処理学会, 2011-03-25) pp.106](http://ci.nii.ac.jp/naid/110008616680) にあった, 間接左再帰を含む文法の例

    S <- A
    A <- S b a | a

をもそのまま実装できます.

```fsharp
open ScanRat

let s = production "s" 
let a = production "a"
s.rule <- a
a.rule 
  <- s + ~~"ba" --> fun (s, ba) -> s + ba
  |- ~~"a"

let tryparses str =
  match parse s str with
    | Success x -> x.value
    | Failure _ -> "error"

tryparses "a" |> printfn "%A"
// "a"
tryparses "ababa" |> printfn "%A"
// "ababa"
tryparses "abba" |> printfn "%A"
// "error"
```

# おかしくないですか

左再帰を許す PEG を使ったパーザとしては直接左再帰の自動除去を採用した [Peggy](http://tanakh.github.io/Peggy) が有名ですが, それとは違うアプローチを取っているようです.

[S´ergio Medeiros, Fabio Mascarenhas, Roberto Ierusalimschy: "Left Recursion in Parsing Expression Grammars" (Science of Computer Programming Volume 96, Part 2, 15 December 2014, Pages 177–190)](http://arxiv.org/pdf/1207.0443v1.pdf) を元に実装したようです. 

これは PEG の意味論に対して、左再帰規則に適切な意味付けをできるような conservative extension を作ってやったという話っぽいです. すごいですね.

その実装として [IronMeta](https://github.com/kulibali/ironmeta) がまず生まれ, そのアルゴリズムの F# への移植が ScanRat なようです.

# 動く例

電卓つくってみました.

```fsharp
open System
open ScanRat

type Expr =
  | Num of int
  | Add of Expr * Expr
  | Sub of Expr * Expr

let rec compute e =
  match e with
    | Add (a, b) -> (compute a) + (compute b)
    | Sub (a, b) -> (compute a) - (compute b)
    | Num i -> i

let digit = oneOf "0123456789" --> fun d -> int(d) - int('0')

let digits = production "digits"
digits.rule
  <- digits + digit --> fun (a, b) -> a * 10 + b
  |- digit

let exp = production "exp"
exp.rule 
  <- exp .+ ~~"+" + exp --> Add
  |- exp .+ ~~"-" + exp --> Sub
  |- digits --> Num
  |- ~~"(" +. exp .+ ~~")"

let trycompute s =
  match parse exp s with
    | Success s -> compute s.value
    | Failure _ -> Exception("error") |> raise 

(=) (trycompute "1-2+3") (trycompute "(1-2)+3") |> printfn "%A"
// true
(=) (trycompute "1-2-3") (trycompute "1-(2+3)") |> printfn "%A"
// true
```

# おまけ

ScanRat を使って [型なしラムダのベータ簡約器のパーザ](https://github.com/cannorin/betareductionbot/blob/master/BetaReductionBot/Parser.fs)を書きました.