F# Parsers combinators.

// F# Parsers combinators :))

open System

//A parser which successfully consumes the first character
//if the argument string is non-empty, and fails otherwise.
let item = Parser (fun cs -> match cs with
                             | "" -> []
                             | cs -> [cs.[0], cs.Substring(1)])
                            
//A combinator sat that takes a predicate, and yields a parser that
//consumes a single character if it satisfies the predicate, and fails otherwise.
let sat p = parser { let! c = item
                     if p c then
                      return c }
                      
//A parser for specific characters
let char c = sat (fun s -> c = s)
                                            
//Parse a specific string
let rec stringp s = match s with
                    | "" -> parser { return [] }
                    | xs -> parser { let! c = char xs.[0]
                                     let! cs = stringp (xs.Substring(1))
                                     return c::cs }                        
                                                          
//The many combinator permits zero
//or more applications of p, while many1 permits one or more.
let rec many1 p = parser { let! x = p
                           let! xs = many p
                           return (x::xs) }
and many p = (many1 p) +++ parser { return [] }

                            
//Parse repeated applications of a parser p, separated by applications of a parser
//op whose result value is an operator that is assumed to associate to the left,
//and which is used to combine the results from the p parsers.
and chainl1 p op = 
    let rec rest a = parser { let! f = op
                              let! b = p
                              return! rest (f a b) } +++ parser { return a }
    parser { let! a = p
             return! rest a } 
           
//Parse a string of spaces.
let space = many (sat (fun s -> Char.IsWhiteSpace s))

//Parse a token using a parser p, throwing away any trailing space.
let token p = parser { let! a = p
                       let! _ = space
                       return a }

//Parse a symbolic token:
let symb cs = token (stringp cs)

//Apply a parser p, throwing away any leading space:
let apply p = extract (parser { let! _ = space
                                let! r = p
                                return r })