初投稿です

言語処理系 Advent Calender 4日目の記事のようです.

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

ScanRat とは

ScanRat - GitHub

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

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

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

コンビネータ

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

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

+ コンビネータ

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

PEG では sequence に対応します.


let twoDigits = digits + digits

// PEG: twoDigits <- digits digits

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

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


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 に対応します.


let eitherLeftOrRight = left |- right

// PEG: eitherLeftOrRight <- left / right

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


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

--> コンビネータ

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


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

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

~~ コンビネータ

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

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


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

// PEG: hello <- "hello"

oneOf コンビネータ

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


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

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

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


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

パースする

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

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


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>

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


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

再帰的文法の定義

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


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基礎文法最速マスターにある

左再帰

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

A ::= A "a"
    |

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

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

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 にあった, 間接左再帰を含む文法の例

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

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

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 が有名ですが, それとは違うアプローチを取っているようです.

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) を元に実装したようです.

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

その実装として IronMeta がまず生まれ, そのアルゴリズムの F# への移植が ScanRat なようです.

動く例

電卓つくってみました.

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 を使って型なしラムダのベータ簡約器のパーザを書きました.

ScanRat の紹介