3 people like it.

Workflows and parser combinators

Example on the use of Workflows in parser combinators.

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
 10: 
 11: 
 12: 
 13: 
 14: 
 15: 
 16: 
 17: 
 18: 
 19: 
 20: 
 21: 
 22: 
 23: 
 24: 
 25: 
 26: 
 27: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
type ParserResult<'a> =
    | Success of 'a * list<char>
    | Failure

type Parser<'a> = list<char> -> ParserResult<'a>

let Return (x: 'a): Parser<'a> =
    let p stream = Success(x, stream)
    in p

let Bind (p: Parser<'a>) (f: 'a -> Parser<'b>) : Parser<'b> =
    let q stream =
        match p stream with
        | Success(x, rest) -> (f x) rest
        | Failure -> Failure
    in q

let (>>=) = Bind

/// If parser p succeeds returns x as a result.
let (>>%) p x : Parser<'b> =
    p >>= (fun _ -> Return x)

/// Applies parsers p1 and p2 returning the result of p2.
let (>>.) p1 p2 : Parser<'b> =
    p1 >>= (fun _ -> p2)

/// Applies parsers p1 and p2 returning the result of p1.
let (.>>) p1 p2 : Parser<'a> =
    p1 >>= (fun x -> p2 >>% x)
    
/// Applies parsers p1 and p2 returning both results.
let (.>>.) p1 p2: Parser<'a*'b> =
    p1 >>= (fun x -> p2 >>= (fun y -> Return (x, y)))

type ParserBuilder() =
    member x.Bind(p, f) = Bind p f
    member x.Return(y) = Return y

let parse = new ParserBuilder()

let Either (p1: Parser<'a>) (p2: Parser<'a>) : Parser<'a> =
    let p stream =
        match p1 stream with
        | Failure -> p2 stream
        | res -> res
    in p

// This is the Either combinator defined in the previous blog post.
let (<|>) = Either

let rec Many p : Parser<list<'a>> =
    parse {
        let! x = p          // Applies p
        let! xs = (Many p)  // Applies (Many p) recursively
        return x :: xs      // returns the cons of the two results
    } <|> Return []

let Many1 p : Parser<list<'a>> =
    parse {
        let! x = p          // Applies p
        let! xs = (Many p)  // Applies (Many p) recursively
        return x :: xs      // returns the cons of the two results
    }

let CharParser (c: char) : Parser<char> =
    let p stream =
        match stream with
        | x::xs when x = c -> Success(x, xs)
        | _ -> Failure
    in p

let DigitParser : Parser<char> =
    ['0'..'9']
    |> List.map CharParser
    |> List.reduce Either

/// Parses float numbers which match /[+-]?(\d+(\.\d*)?|\d*\.\d+)([eE][+-]?\d+)?/
let FloatParser: Parser<float> =
    parse {
        let! s = (CharParser '+' <|> CharParser '-') <|> Return '+'     // [+-]?
        let! l = (parse {                                               // (
            let! l = Many1 DigitParser                                  //  \d+
            let! pd = (parse {                                          //  (
                let! p = CharParser '.'                                 //   \.
                let! d = Many DigitParser                               //   \d*
                return p::d
                } <|> Return [])                                        //  )?
            return l @ pd
            } <|>                                                       //  |
            parse {
                let! l = Many DigitParser                               // \d*
                let! p = CharParser '.'                                 // \.
                let! d = Many1 DigitParser                              // \d+
                return l @ p::d
            }
        )
        let! e = (parse {
            let! e = CharParser 'e' <|> CharParser 'E'                  // ([eE]
            let! s = (CharParser '+' <|> CharParser '-') <|> Return '+' //   [+-]?
            let! x = Many1 (DigitParser)                                //   \d+
            return e::s::x                                              // )?
        } <|> Return [])
        return float (new System.String(s::(l @ e) |> List.toArray))
    }

printfn "%A" (FloatParser ("-1.23e45" |> Seq.toList))
union case ParserResult.Success: 'a * char list -> ParserResult<'a>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
val char : value:'T -> char (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.char

--------------------
type char = System.Char

Full name: Microsoft.FSharp.Core.char
Multiple items
union case ParserResult.Failure: ParserResult<'a>

--------------------
active recognizer Failure: exn -> string option

Full name: Microsoft.FSharp.Core.Operators.( |Failure|_| )
type Parser<'a> = char list -> ParserResult<'a>

Full name: Script.Parser<_>
type ParserResult<'a> =
  | Success of 'a * char list
  | Failure

Full name: Script.ParserResult<_>
val Return : x:'a -> Parser<'a>

Full name: Script.Return
val x : 'a
val p : (char list -> ParserResult<'a>)
val stream : char list
val Bind : p:Parser<'a> -> f:('a -> Parser<'b>) -> Parser<'b>

Full name: Script.Bind
val p : Parser<'a>
val f : ('a -> Parser<'b>)
val q : (char list -> ParserResult<'b>)
val rest : char list
union case ParserResult.Failure: ParserResult<'a>
val x : 'b
val p1 : Parser<'a>
val p2 : Parser<'b>
val p2 : Parser<'a>
val y : 'b
Multiple items
type ParserBuilder =
  new : unit -> ParserBuilder
  member Bind : p:Parser<'b> * f:('b -> Parser<'c>) -> Parser<'c>
  member Return : y:'a -> Parser<'a>

Full name: Script.ParserBuilder

--------------------
new : unit -> ParserBuilder
val x : ParserBuilder
member ParserBuilder.Bind : p:Parser<'b> * f:('b -> Parser<'c>) -> Parser<'c>

Full name: Script.ParserBuilder.Bind
val p : Parser<'b>
val f : ('b -> Parser<'c>)
member ParserBuilder.Return : y:'a -> Parser<'a>

Full name: Script.ParserBuilder.Return
val y : 'a
val parse : ParserBuilder

Full name: Script.parse
val Either : p1:Parser<'a> -> p2:Parser<'a> -> Parser<'a>

Full name: Script.Either
val res : ParserResult<'a>
val Many : p:Parser<'a> -> Parser<'a list>

Full name: Script.Many
val xs : 'a list
val Many1 : p:Parser<'a> -> Parser<'a list>

Full name: Script.Many1
val CharParser : c:char -> Parser<char>

Full name: Script.CharParser
val c : char
val p : (char list -> ParserResult<char>)
val x : char
val xs : char list
val DigitParser : Parser<char>

Full name: Script.DigitParser
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val reduce : reduction:('T -> 'T -> 'T) -> list:'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.reduce
val FloatParser : Parser<float>

Full name: Script.FloatParser


 Parses float numbers which match /[+-]?(\d+(\.\d*)?|\d*\.\d+)([eE][+-]?\d+)?/
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val s : char
val l : char list
val pd : char list
val p : char
val d : char list
val e : char list
val e : char
val x : char list
namespace System
Multiple items
type String =
  new : value:char -> string + 7 overloads
  member Chars : int -> char
  member Clone : unit -> obj
  member CompareTo : value:obj -> int + 1 overload
  member Contains : value:string -> bool
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EndsWith : value:string -> bool + 2 overloads
  member Equals : obj:obj -> bool + 2 overloads
  member GetEnumerator : unit -> CharEnumerator
  member GetHashCode : unit -> int
  ...

Full name: System.String

--------------------
System.String(value: nativeptr<char>) : unit
System.String(value: nativeptr<sbyte>) : unit
System.String(value: char []) : unit
System.String(c: char, count: int) : unit
System.String(value: nativeptr<char>, startIndex: int, length: int) : unit
System.String(value: nativeptr<sbyte>, startIndex: int, length: int) : unit
System.String(value: char [], startIndex: int, length: int) : unit
System.String(value: nativeptr<sbyte>, startIndex: int, length: int, enc: System.Text.Encoding) : unit
val toArray : list:'T list -> 'T []

Full name: Microsoft.FSharp.Collections.List.toArray
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
module Seq

from Microsoft.FSharp.Collections
val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
Raw view Test code New version

More information

Link:http://fssnip.net/hB
Posted:11 years ago
Author:Santi Albo
Tags: workflows , parser combinators