パーサーコンビネータ

parser.swift

//
//  ParserCombinator
//
//  Created by 後藤誉昌 on 2016/10/06.
//

import Foundation

// モナド
struct Parser<Input, Output> {
    enum Reply<Input, Output> {
        case done(Input, Output)
        case failed
    }

    let parse: (Output) -> Reply<Input, Output>
}


// 基礎関数
func pure<A, B>(a: A) -> Parser<A, B> {
    return Parser { .done(a, $0) }
}

func empty<A, B>() -> Parser<A, B> {
    return Parser { _ in .failed }
}


// 文字列
func token(by token: String) -> Parser<String, String> {
    return Parser { target in
        let length = token.count

        guard target.count >= length, target.prefix(length) == token else {
            return .failed
        }

        return .done(token, String(target.suffix(target.count - length)))
    }
}

token(by: "hoge").parse("hogehoge")
token(by: "hoge").parse("fugahoge")


// 繰り返し
func many<A, B>(parser: Parser<A, B>) -> Parser<[A], B> {
    return Parser { target in
        var results: [A] = []
        var tail = target

        loop: while true {
            switch parser.parse(tail) {
            case .done(let result, let _tail):
                results.append(result)
                tail = _tail
            case .failed:
                break loop
            }
        }

        return .done(results, tail)
    }
}

let parser = token(by: "hoge")
many(parser: parser).parse("hogehoge")
many(parser: parser).parse("hogehogefuga")


// 選択
func choice<A, B>(parser1: Parser<A, B>, parser2: Parser<A, B>) -> Parser<A, B> {
    return Parser { target in
        let result = (parser1.parse(target), parser2.parse(target))

        switch result {
        case (.done, _):
            return result.0
        case (_, .done):
            return result.1
        default:
            return .failed
        }
    }
}

let parser2 = token(by: "fuga")
choice(parser1: parser, parser2: parser2).parse("hoge")
choice(parser1: parser, parser2: parser2).parse("fuga")
choice(parser1: parser, parser2: parser2).parse("piyo")


// 加工
func map<A, B, C>(parser: Parser<A, C>, transform: @escaping (A) -> B) -> Parser<B, C> {
    return Parser { target in
        let result = parser.parse(target)
        
        switch result {
        case .done(let _result, let tail):
            return .done(transform(_result), tail)
        default:
            return .failed
        }
    }
}

let parser4 = map(parser: parser) { "\($0)パースした" }
parser4.parse("hoge")
parser4.parse("fuga")


// 連結
func seq<A, B>(parsers: [Parser<[A], B>]) -> Parser<[A], B> {
    return Parser { target in
        var results: [A] = []
        var tail = target
        
        for parser in parsers {
            switch parser.parse(tail) {
            case .done(let result, let _tail):
                results.append(contentsOf: result)
                tail = _tail
            case .failed:
                return .failed
            }
        }
        
        return .done(results, tail)
    }
}

func seq<A, B>(parsers: Parser<[A], B>...) -> Parser<[A], B> {
    return seq(parsers: parsers)
}

func seq<A, B>(parsers: Parser<A, B>...) -> Parser<[A], B> {
    return seq(parsers: parsers.map { map(parser: $0) { [$0] } })
}

let parser3 = token(by: "piyo")
seq(parsers: parser, parser2, parser3).parse("hogefugapiyo")
seq(parsers: parser, parser2, parser3).parse("hogefugafuga")


// オプション
func option<A, B>(parser: Parser<A, B>) -> Parser<A?, B> {
    return Parser { target in
        let result = parser.parse(target)

        switch result {
        case .done(let result, let tail):
            return .done(.some(result), tail)
        case .failed:
            return .done(nil, target)
        }
    }
}

option(parser: parser).parse("hoge")
option(parser: parser).parse("")


// 再帰
func lazy<A, B>(callback: @escaping () -> Parser<A, B>) -> Parser<A, B> {
    return Parser { target in callback().parse(target) }
}

var expression: Parser<[String], String>!
let factor = map(parser: option(parser: seq(parsers: map(parser: parser) { [$0] }, lazy { expression } ))) { $0 ?? [] }
expression = factor
expression.parse("hogehogehogehogefugahoge")
expression.parse("fugahogehoge")


// 特定の文字
func char(of chars: String) -> Parser<String, String> {
    return Parser { target in
        for char in chars {
            if target.prefix(1) == String(char) {
                return .done(String(char), String(target.suffix(target.count - 1)))
            }
        }
        
        return .failed
    }
}

char(of: "0123456789").parse("10")
char(of: "0123456789").parse("a")


// 実例: 数式
let digit = char(of: "0123456789")
let number = map(parser: many(parser: digit)) { $0.joined() }
let `operator` = char(of: "+-*/")
var expression2: Parser<[String], String>!

let head = map(parser: token(by: "(")) { [$0] }
let tail = map(parser: token(by: ")")) { [$0] }
let parenthesis_0 = lazy { seq(parsers: head, expression2, tail) }
let parenthesis = parenthesis_0

let atom_0 = map(parser: number) { [$0] }
let atom_1 = choice(parser1: atom_0, parser2: parenthesis)
let atom = atom_1

let expression2_0 = map(parser: `operator`) { [$0] }
let expression2_1 = seq(parsers: expression2_0, atom)
let expression2_2 = many(parser: expression2_1)
let expression2_3 = map(parser: expression2_2) { $0.flatMap { $0 } }
let expression2_4 = seq(parsers: atom, expression2_3)
expression2 = expression2_4

expression2.parse("0+a")
expression2.parse("0")
expression2.parse("1+1-1*1/1")
expression2.parse("1+(1-1)")