うごかん・・・

Parser.swift

import Foundation

struct Parsed<Token> {
    var token: Token
    var remaining: String

    init(_ token: Token, remaining: String) {
        self.token = token
        self.remaining = remaining
    }
}

struct Parser<Token> {
    let parse: (String) -> Parsed<Token>?

    /// <^>
    /// 同じロジックのまま、出力だけが違うパーサを作る
    func map<U>(_ transform: @escaping (Token) -> U) -> Parser<U> {
        return flatMap { token in pure(transform(token)) }
    }

    /// >>-
    func flatMap<U>(_ f: @escaping (Token) -> Parser<U>) -> Parser<U> {
        return Parser<U> { input in
            if let parsed = self.parse(input) {
                return f(parsed.token).parse(parsed.remaining)
            } else {
                return nil
            }
        }
    }
}

/// 文字を消費せず、tokenとして引数そのままを生み出す
func pure<A>(_ a: A) -> Parser<A> {
    return Parser { Parsed(a, remaining: $0) }
}

func empty<A>() -> Parser<A> {
    return Parser { _ in nil }
}

/// <|>
func alternative<A>(_ p: Parser<A>, _ q: Parser<A>) -> Parser<A> {
    return Parser { input in
        return p.parse(input) ?? q.parse(input)
    }
}

/// <*>
func sequence<A, B>(_ p: Parser<(A) -> B>, _ q: Parser<A>) -> Parser<B> {
    return p.flatMap { f in q.map(f) }
}

/// <*
func sequenceLeft<A, B>(_ p: Parser<A>, _ q: Parser<B>) -> Parser<A> {
    return sequence(p.map { const($0) }, q)
//    return p.flatMap { t in q.map(const(t)) }
}

/// *>
func sequenceRight<A, B>(_ p: Parser<A>, _ q: Parser<B>) -> Parser<B> {
    return p.flatMap { _ in q }
}

func const<T, U>(_ value: T) -> ((U) -> T) {
    return { _ in value }
}

func satisfy(predicate: @escaping (Character) -> Bool) -> Parser<Character> {
    return Parser { input in
        guard let firstCharacter = input.first, predicate(firstCharacter) else {
            return nil
        }
        return Parsed(firstCharacter, remaining: String(input.dropFirst()))
    }
}

func many<A>(_ p: Parser<A>) -> Parser<[A]> {
    return alternative(many1(p), pure([]))
}

func many1<A>(_ p: Parser<A>) -> Parser<[A]> {
    return sequence(p.map { const([$0]) }, many(p))
}

func skipMany<A>(_ p: Parser<A>) -> Parser<()> {
    return alternative(skipMany1(p), pure(()))
}

func skipMany1<A>(_ p: Parser<A>) -> Parser<()> {
    return sequenceRight(p, skipMany(p))
}

func skipSpaces() -> Parser<()> {
    return skipMany(space())
}

func space() -> Parser<Void> {
    return char(" ").map(const(()))
}

func char(_ c: Character) -> Parser<Character> {
    return satisfy { $0 == c }
}

private func _string<S: StringProtocol>(_ str: S) -> Parser<S> {
    if let first = str.first {
        return sequenceRight(sequenceRight(char(first), _string(str.dropFirst())), pure(str))
    } else {
        return pure("")
    }
}

func string(_ str: String) -> Parser<String> {
    return _string(str)
}

func symbol(_ str: String) -> Parser<String> {
    return sequenceLeft(sequenceRight(skipSpaces(), string(str)), skipSpaces())
}