Skip to content

Instantly share code, notes, and snippets.

@ha1f
Created Oct 8, 2020
Embed
What would you like to do?
うごかん・・・
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())
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment