Parser combinators simple example

This snippet is an example of how to implement parser combinators in a simple way.

 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:

type ParserResult<'a> =
    | Success of 'a * list<char> 
    | Failure
    
type Parser<'a> = list<char> -> ParserResult<'a>
 
let CharParser c : Parser<char> =
    let p stream =
        match stream with
        | x::xs when x = c -> Success(x, xs)
        | _ -> Failure
    in p
 
let Either (p1: Parser<'a>) (p2: Parser<'a>) : Parser<'a> =
    let p stream =
        match p1 stream with
        | Failure -> p2 stream
        | res -> res 
    in p
 
let DigitParser =
    ['0'..'9']
    |> List.map CharParser
    |> List.reduce Either
 
let Apply (p: Parser<'a>) (f: 'a -> 'b) : Parser<'b> =
    let q stream =
        match p stream with
        | Success(x, rest) -> Success(f x, rest)
        | Failure -> Failure
    in q
 
let DigitParserInt = Apply DigitParser (fun c -> (int c) - (int '0'))
 
let rec Many (p: Parser<'a>) : Parser<List<'a>> =
    let q stream =
        match p stream with
        | Failure -> Success([], stream)
        | Success(x, rest) ->  (Apply (Many p) (fun xs -> x::xs)) rest
    in q
 
let IntegerParser : Parser<int> =
    Apply (Many DigitParserInt) (List.reduce (fun x y -> x * 10 + y))
 
printfn "%A" (IntegerParser ['1'; '2'; '3'; '4'])

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 CharParser : c:char -> Parser<char>

Full name: Script.CharParser

val c : char

val p : (char list -> ParserResult<char>)

val stream : char list

val x : char

val xs : char list

union case ParserResult.Failure: ParserResult<'a>

val Either : p1:Parser<'a> -> p2:Parser<'a> -> Parser<'a>

Full name: Script.Either

val p1 : Parser<'a>

val p2 : Parser<'a>

val p : (char list -> ParserResult<'a>)

val res : ParserResult<'a>

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 Apply : p:Parser<'a> -> f:('a -> 'b) -> Parser<'b>

Full name: Script.Apply

val p : Parser<'a>

val f : ('a -> 'b)

val q : (char list -> ParserResult<'b>)

val x : 'a

val rest : char list

val DigitParserInt : Parser<int>

Full name: Script.DigitParserInt

Multiple items
val int : value:'T -> int (requires member op_Explicit)

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

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

val Many : p:Parser<'a> -> Parser<List<'a>>

Full name: Script.Many

val q : (char list -> ParserResult<'a list>)

val xs : List<'a>

val IntegerParser : Parser<int>

Full name: Script.IntegerParser

val x : int

val y : int

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

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

Raw view Test code New version

More information

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