パーザコンビネータをつくろう

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>

Multiple items
val Failure : message:string -> exn

Full name: Microsoft.FSharp.Core.Operators.Failure

--------------------
active recognizer Failure: exn -> string option

Full name: Microsoft.FSharp.Core.Operators.( |Failure|_| )

union case Option.Some: Value: 'T -> Option<'T>

module String

from Microsoft.FSharp.Core

val length : str:string -> int

Full name: Microsoft.FSharp.Core.String.length

val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf

union case Option.None: Option<'T>

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

パーザコンビネータをつくろう

PEGと構文解析に関するアレコレの勉強会 Vol.1

自己紹介

icon

なかやん・ゆーき / ぺんぎん / もみあげ
@pocketberserker
Microsoft MVP for F# .NET (2015/04/01～ 2016/03/31)
パーザコンビネータライブラリはてきとーにwatchしてる

パーザコンビネータ is 何

Wikipedia 曰く

In functional programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output.

てきとー訳

関数プログラミングでは、パーザコンビネータは入力としていくつかのパーザを受け取り、出力として新しいパーザを返す高階関数です。

なるほどね

パーザコンビネータライブラリ

他にもたくさん

私とパーザコンビネータ

FsAttoparsec 作ってみたり
SmlSharpContrib にそれっぽいもの作ってみたり
atto に手を入れたり
仕事で Boost.Spirit 使ってみたり

ところで

会場に

パーザコンビネータ使ったことがある方
パーザコンビネータ実装したことがある方

が多い場合、以降の発表内容を考える?

パーザコンビネータの学び方

FP in Scala の第9章

どゆこと?

実装方法を知れば使い方もわかるよね、的な
というわけで、簡単なものを作ってみましょう
F# で

解析を実行する関数の型を考える

パーザと入力を受け取って解析結果を返せばよい…気がする

1:	`val run: Parser<'T> -> string -> Result<'T>`

Parser: パーザ
Result: 解析結果
'Tは解析成功時に得られるデータ

それっぽい

Parser<'T> について考える

解析開始位置があれば解析できそう
何か操作をすれば Result<'T> を返そう

Parser<'T> の実態

1: 
2: 
3: 
4: 
5: 
6: 
7:

// なんかレコード
type State = {
  Input: string
  Pos: int
}
// 今回は単なる関数のtype alias
type Parser<'T> = State -> Result<'T>

実装次第では pos だけでいい

Result<'T> その1

1: 
2:

// Haskell だと Maybe
type Result<'T> = 'T option

要件は満たす
が、解析失敗時の情報が全くない
もうちょっと情報を増やそう

Result<'T> その2

1: 
2:

// Haskell だと Either
type Result<'T> = Choice<'T, string>

成功時は 'T、失敗時は string
よさげ
でも名前がわかりにくい
ちょっと定義し直し

Result<'T> その3

1: 
2: 
3:

type Result<'T> =
| Success of 'T
| Failure of string

string ではなく NonEmptyList[String] とかのほうがいいけど今回は略
なんか足りない気がする

Result<'T> その4

解析成功時のpositionがあったほうが合成しやすそう

1: 
2: 
3:

type Result<'T> =
| Success of 'T * int
| Failure of string

'T * State のほうがよさそうだけど今回は略

run 関数実装

1: 
2: 
3:

let run (parser: Parser<'T> input =
  let init = { Input = input; Pos = 0 }
  parser init

実際にパーザを作る

指針がほしいので、以下の二つを足がかりにする

PEG
Parser Monad

以降のスライドでは一部実装を省略します

文字列リテラル(PEG)

1: 
2: 
3: 
4: 
5: 
6: 
7:

// val pstring: string -> Parser<string>
let pstring str = fun s ->
  match State.extract s with
  // 入力の先頭に一致したら成功
  | Some target when target.StartsWith(str) -> Success(str, s.Pos + String.length str)
  | Some _ -> Failure (sprintf "文字列\"%s\"にマッチしませんでした" str)
  | None -> Failure "pstring: もう入力がないよ"

ワイルドカード(PEG)

1: 
2: 
3: 
4: 
5: 
6:

// val any: Parser<char>
let any = fun s ->
  match State.extract s with
  // 1文字あればよい
  | Some target when not <| String.IsNullOrEmpty(target) -> Success(target.Chars(0), s.Pos + 1)
  | _ -> Failure "any: もう入力がないよ"

連接(PEG)

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9:

// val (<.>) : Parser<'T> -> Parser<'U> -> Parser<'T * 'U>
let (<.>) a b = fun s ->
  a s
  |> Result.bind (fun r1 rpos1 ->
    // 一つ目の解析に成功したらpositionを更新し
    State.update rpos1 s
    |> b
    // 二つめの解析を試みる
    |> Result.map (fun r2 rpos2 -> ((r1, r2), rpos2)))

両方に成功しないと成功とみなさない

選択(PEG)

a に失敗したら b で解析を試みる

1: 
2: 
3: 
4: 
5:

// val (</>): Parser<'T> -> Parser<'T> -> Parser<'T>
let (</>) a b = fun s ->
  match a s with
  | Success _ as p -> p
  | _ -> b s

繰り返し(PEG)

1: 
2: 
3: 
4: 
5: 
6: 
7:

// val many: Parser<'T> -> Parser<'T list>
let many p =
  let rec inner acc s =
    match p s with
    | Success(v, rpos1) -> inner (v :: acc) (State.update rpos1 s)
    | Failure _ -> Success(List.rev acc, s.Pos)
  fun s -> inner [] s

失敗するまでひたすらpositionを更新しながら解析
many1 は andThen と List.cons を使えばよい

0回または1回(PEG)

1: 
2: 
3: 
4: 
5:

// val opt: Parser<'T> -> Parser<'T option>
let opt p = fun s ->
  match p s with
  | Success(v, p) -> Success(Some v, p)
  | Failure _ -> Success(None, s.Pos)

否定先読み(PEG)

1: 
2: 
3: 
4: 
5:

// val bang: Parser<'T> -> Parser<unit>
let bang p = fun s ->
  match p s with
  | Success _ -> Failure "bang"
  | Failure _ -> Success((), s.Pos)

ok関数(Monad, return の代わり)

1: 
2:

// val ok: 'T -> Parser<'T>
let ok value = fun s -> Success(value, s.Pos)

パーザ内で条件分岐させた後にパーザを返したりするときに便利

bind関数(Monad)

1: 
2: 
3: 
4: 
5:

// val bind: ('T -> Parser<'U>) -> Parser<'T> -> Parser<'U>
let bind f p = fun s ->
  match p s with
  | Success(value, pos) -> s |> State.update pos |> f value
  | Failure r -> Failure r

map関数(Functor)

1: 
2: 
3: 
4: 
5:

// val map: ('T -> 'U) -> Parser<'T> -> Parser<'U>
let map f (p: Parser<_>) = fun s ->
  match p s with
  | Success(value, pos) -> Success(f value, pos)
  | Failure r -> Failure r

解析結果を変換したいよね？

まとめ

パーザコンビネータの仕組み自体は簡単、こわくない
実際はパフォーマンスチューニングのためにもっと色々やってるけど
実際はエラー出力のために(ry
構文解析楽しく学ぼう