Back to Questions
2.9k
views1
comment
parsing INI file
f#parsingcomplexity

Hi,

I'm very new in learning F# and was working on a simple program to parse an INI-type file. The INI file looks something like:

1
2
3
4
5
6

[sectionName1]
key1=value1
key2=value2

[SectionName2]
key3=value3

I'd like my algorithm to return a Dictionary where the keys are the section names and the sub-section items are a stored as a List of (key, value) tuples. To be precise, the return value of my function should be:

1

System.Collections.Generic.Dictionary<String, List<String * String>>()

I'm really struggling to use F# to construct this data structure. My goal is to perform the transformation in-place, e.g. O(n). This means that doing a ReadToEnd(), Split by sections, Split by lines, etc approach to build the data structure is unacceptable as the computational complexity would not be O(n).

I believe in order to implement this algorithm in O(n), I need to maintain a sort-of state machine as I process each line of the file in such a way that the state machine would correctly process each line. For instance, when reading a section such as "[sectionName]" it is necessary to insert a new key / value pair into the resulting data structure and all subsequent "key=value" lines are to be appended to the List corresponding to that section.

I hope that I'm clear with the approach I'm trying to take.

Is there a clever way to do this? Here is the approach that I took that I'm not very happy with.

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

let fp = new System.IO.StreamReader(filePath)
let m_SectionHash = new System.Collections.Generic.Dictionary<String, List<String * String>>()

member this.Sections() =
        try
            if (fp.BaseStream.Seek(0L, SeekOrigin.Begin)) <> 0L then
                raise (new System.IO.IOException("Failed to seek"))

            let curList : List<String * String> = null
            let p = ref curList

            let elementParserList (list : List<String * String>) text = 
                let m = Regex.Match(text, "^(\S+)[\s]*=[\s]*(.*)$") in
                    if m.Success then
                        list.Add((m.Groups.Item(1).Value,
                                  m.Groups.Item(2).Value))
                ()

            let sectionParser text =
                let m = Regex.Match(text, "^\[(\S+)\]$") in
                    if m.Success then
                        let sectionName = m.Groups.Item(1).Value
                        p := new List<String * String>()
                        m_SectionHash.Add(sectionName, !p)
                ()                
    
            let lines = Seq.unfold(fun line ->
                if line = null then
                    None
                else
                    Some(line, fp.ReadLine())) (fp.ReadLine())

            let doit line =
                sectionParser line
                elementParserList !p line
                ()

            Seq.iter doit lines
        with
            | _ -> reraise()

I'd love to get some feedback. Thanks!

.

How about this one? A bit more "functional" with no mutables or side effects... 

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

#light

let (|RegexMatch|_|) regex str =
   let m = System.Text.RegularExpressions.Regex(regex).Match(str)
   if m.Success
   then Some (List.tail [ for x in m.Groups -> x.Value ])
   else None

let loadConfig fn = 
    System.IO.File.ReadAllLines(fn)
    |> Array.fold
        (fun acc l ->
            match l with 
            | RegexMatch "^\[(\S+)\]$" [section] -> (section, []) :: acc            
            | RegexMatch "^(\S+)[\s]*=[\s]*(.*)$" [prop; value] -> (fst acc.Head, (prop, value)::(snd acc.Head))::(acc.Tail)
            | _ -> acc
        )
        List.empty
    |> Map.ofList

 

//Testing

let loadAndPrintConfig =
    loadConfig >>
    Seq.iter (fun (KeyValue(s, pvl)) -> printfn "%s" s; pvl |> Seq.iter (fun (p, v) -> printfn "\t%s=%s" p v))

loadAndPrintConfig "test.ini"

Thanks!
FZSharp

By on 5/18/2011 10:14 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper