Parsing Expression Grammar

Parser.fs

module Parser

//Copyright (c) 2015 plasma-effect
//
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in
//all copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//THE SOFTWARE.
type Rule =
    | FreeIndex of int
    | Char of char
    | Chars of System.String
    | Null
    | Sequence of Rule * Rule
    | Selection of Rule * Rule
    | Repeat of Rule
    | Ignorable of Rule
    | AndPredicate of Rule
    | NotPredicate of Rule
    static member (+) (x: Rule, y: Rule) = Sequence(x, y)
    static member (+) (x: System.String, y: Rule) = Sequence(Chars(x), y)
    static member (+) (x: Rule, y: System.String) = Sequence(x, Chars(y))
    static member (/) (x: Rule, y: Rule)=Selection(x, y)
    static member (/) (x: System.String, y: Rule) = Selection(Chars(x), y)
    static member (/) (x: Rule, y: System.String) = Selection(x, Chars(y))
    


type Optional<'T> =
    | None
    | Value of 'T

type ParseResult =
    | ResultIndex of (ParseResult * int)
    | ResultChar of char
    | ResultChars of System.String
    | ResultNull
    | ResultSequence of (ParseResult * ParseResult)
    | ResultRepeat of List<ParseResult>
    | ResultIgnorable of Optional<ParseResult>
    | ResultAndPredicate of ParseResult * (int * int)
    | ResultNotPredicate

module detail =
    let rec parse_i (rules: Rule[]) (str: System.String) rule t =
        match rule with
        | FreeIndex(n) ->
            match parse_i rules str rules.[n] t with
            | None -> None
            | Value(result, (x, y)) -> Value(ResultIndex(result, n),(x, y))
        | Char(c) -> if t < str.Length && c = str.Chars(t) then Value(ResultChar(c),(t, t+1)) else None
        | Chars(s) -> if (t + s.Length <= str.Length && str.Substring(t,s.Length) = s) then Value(ResultChars(s),(t,t + s.Length)) else None
        | Null -> Value(ResultNull,(t,t))
        | Sequence(exp0, exp1) ->
            match parse_i rules str exp0 t with
            | None -> None
            | Value(result0,(x,y)) ->
                match parse_i rules str exp1 y with
                | None -> None
                | Value(result1,(f,l)) -> Value(ResultSequence(result0,result1),(x,l))
        | Selection(exp0, exp1) ->
            match parse_i rules str exp0 t with
            | None -> 
                match parse_i rules str exp1 t with
                | None -> None
                | Value(result, (x, y)) -> Value(result,(x, y))
            | Value(result,(x, y)) -> Value(result,(x, y))
        | Repeat(exp) ->
            match parse_i rules str exp t with
            | None -> Value(ResultRepeat([]),(t,t))
            | Value(result, (x, y)) -> 
                match parse_i rules str rule y with
                | None -> Value(ResultRepeat([result]),(x, y))
                | Value(ResultRepeat(lis),(f, l)) -> Value(ResultRepeat(result::lis),(x,l))
                | Value(res,(f,l)) -> Value(res,(f, l))
        | Ignorable(exp) ->
            match parse_i rules str exp t with
            | None -> Value(ResultIgnorable(None),(t,t))
            | Value(result,(x, y)) -> Value(ResultIgnorable(Value(result)),(x, y))
        | AndPredicate(exp) ->
            match parse_i rules str exp t with
            | None -> None
            | Value(result, (x, y)) -> Value(ResultAndPredicate(result,(x, y)),(t, t))
        | NotPredicate(exp) ->
            match parse_i rules str exp t with
            | None -> Value(ResultNotPredicate,(t, t))
            | Value(result, (x, y)) -> None
                
let rec Parse (rules :Rule[]) str = detail.parse_i rules str rules.[0] 0;;
let rec DictionaryToArray (dic :System.Collections.Generic.Dictionary<Rule,Rule>)=
    Array.init dic.Count (fun index -> dic.Item(FreeIndex(index)));;
let rec ParseFromDictionary (rules :System.Collections.Generic.Dictionary<Rule,Rule>) str =
    let rs = DictionaryToArray rules
    Parse rs str

ParsingAssist.fs

module ParsingAssist

//Copyright (c) 2015 plasma-effect
//
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in
//all copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//THE SOFTWARE.
open Parser

let rec SelectChars (str: System.String) =
    if str.Length = 1 
        then Char(str.Chars(0)) 
        else Selection(Char(str.Chars(0)),SelectChars(str.Substring(1)))

let rec GetChar result =
    match result with
    | ResultChar(c) -> c
    | r -> GetChar r

module Detail =
    let rec get_string_i lis =
        match lis with
        | x::y -> System.String.Concat(GetChar(x),get_string_i(y))
        | [] -> ""

let rec GetString result =
    match result with
    | ResultRepeat(lis) ->Detail.get_string_i(lis)
    | ResultSequence(r0, r1) -> System.String.Concat(GetChar(r0),GetString(r1))
    | _ -> ""

let Num = SelectChars "0123456789"
let Alphabet = SelectChars "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
let SmallAlphabet = SelectChars "abcdefghijklmnopqrstuvwxyz"
let BigAlphabet = SelectChars "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Program.fs

//Copyright (c) 2015 plasma-effect
//
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in
//all copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//THE SOFTWARE.
open Parser
open ParsingAssist
let Rule = Repeat(Num)+(("," + FreeIndex(0)) / Null)

module Detail =
    let rec test r =
        match r with
        | ResultSequence(x, ResultSequence(_, ResultIndex(y, _))) -> GetString(x)::(test y)
        | ResultSequence(x, ResultNull) -> [GetString(x)]
        | _ -> []

let rec Test str =
    match Parse [|Rule|] str with
    | None -> []
    | Value(x,(_, _)) -> Detail.test x

[<EntryPoint>]
let main args =
    let target = "0,12,345,6789"
    let lis = Test target
    for str in lis do System.Console.WriteLine(str) 
    System.Console.WriteLine(lis.Length)
    0;;