parser.swift

class Parser<I: CollectionType, T> {
    func parse(ts: I) -> [(T, I)] { return [] }
    
    func parse_all(ts: I) -> [(T, I)] {
        return parse(ts).filter { isEmpty($0.1) }
    }
}

class charParser<I, T>: Parser<String, Character> {
    let c: Character
    
    init(c: Character) { self.c = c }
    
    override func parse(ts: String) -> [(Character, String)] {
        return ts.c == c ? [(ts[0], ts.s)] : []
    }
}
typealias CharParser = charParser<String, Character>

class AltParser<I: CollectionType, T>: Parser<I, T> {
    let p: I -> [(T, I)]
    let q: I -> [(T, I)]
    
    init(p: I -> [(T, I)], q: I -> [(T, I)]) { self.p = p; self.q = q }
    
    override func parse(ts: I) -> [(T, I)] {
        return p(ts) + q(ts)
    }
}

class SeqParser<I: CollectionType, T, S>: Parser<I, (T, S)> {
    let p: I -> [(T, I)]
    let q: I -> [(S, I)]
    
    init(p: I -> [(T, I)], q: I -> [(S, I)]) { self.p = p; self.q = q }
    
    override func parse(ts: I) -> [((T, S), I)] {
        var acc = [((T, S), I)]()
        for (head1, tail1) in p(ts) {
            for (head2, tail2) in q(tail1) {
                acc += [((head1, head2), tail2)]
            }
        }
        return acc
    }
}

class FunParser<I: CollectionType, T, S>: Parser<I, S> {
    let p: I -> [(T, I)]
    let f: T -> S
    
    init(p: I -> [(T, I)], f: T -> S) { self.p = p; self.f = f }
    
    override func parse(sb: I) -> [(S, I)] {
        var acc = [(S, I)]()
        for (head, tail) in p(sb){
            acc += [(f(head), tail)]
        }
        return acc
    }
}

class stringParser<I, T>: Parser<String, String> {
    let s: String
    
    init(s: String) { self.s = s }
    
    override func parse(sb: String) -> [(String, String)] {
        let (prefix, suffix) = (sb[0..<s.count], sb[s.count..<sb.count])
        return prefix == s ? [(prefix, suffix)] : []
    }
}
typealias StringParser = stringParser<String, String>

class numParser<I, T>: Parser<String, Int> {
    override func parse(sb: String) -> [(Int, String)] {
        let reg = "[0-9]+"
        if let match = sb.rangeOfString(reg, options: .RegularExpressionSearch) {
            if match.startIndex == sb.startIndex {
                let dis: Int = distance(sb.startIndex, match.endIndex)
                return [(sb[0..<dis].toInt()!, sb[dis..<sb.count])]
            }
        }
        return []
    }
}
typealias NumParser = numParser<String, Int>

func E() -> (String) -> [(Int, String)] {
    return  (T() ~ StringParser(s: "+").parse ~ E() ==> { let ((x, y), z) = $0; return x+z } ) || T()
}

func T() -> (String) -> [(Int, String)] {
    return (F() ~ StringParser(s: "*").parse ~ T() ==> { let ((x, y), z) = $0; return x*z } ) || F()
}

func F() -> (String) -> [(Int, String)] {
    return (StringParser(s: "(").parse ~ E() ~ StringParser(s: ")").parse ==> { let ((x, y), z) = $0; return y } ) || NumParser().parse
}

func ||<I: CollectionType, T>(p: I -> [(T, I)], q: I -> [(T, I)]) -> I -> [(T, I)] { return AltParser(p, q).parse }

infix operator ==> {associativity left}
func ==><I: CollectionType, T, S>(p: I -> [(T, I)], f: T -> S) -> I -> [(S, I)]  { return FunParser(p, f).parse }

func ~<I: CollectionType, T, S>(p: I -> [(T, I)], q: I -> [(S, I)]) -> I -> [((T, S), I)] { return SeqParser(p, q).parse }