4 people like it.

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