1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

open System


let newToken = ""


let eatChar (nesting, (currentToken : String), (prevTokens : String list)) currentChar =
    match currentChar with
        (* Split a token on spaces only if it is at top level *)
        | ' ' -> if nesting = 0 then (0, newToken, List.append prevTokens [currentToken])
                 else (nesting, currentToken + currentChar.ToString(), prevTokens)
        | '(' -> if nesting = 0 then (1, newToken, List.append prevTokens [currentToken])
                 else (nesting + 1, currentToken + currentChar.ToString(), prevTokens)
        | ')' -> if nesting = 1 then (0, newToken, List.append prevTokens [currentToken])
                 else (nesting - 1, currentToken + currentChar.ToString(), prevTokens)
        | _   -> (nesting, currentToken + currentChar.ToString(), prevTokens)


let parse (string : String) =
    let (_, finalToken, tokens) = Seq.fold eatChar (0, "", []) string
    List.append tokens [finalToken] |> List.map (fun s -> s.Trim()) |> List.filter (String.length >> (<) 0)

1
2
3

> parse "(alpha (brown) (charlie delta)) echo (foxtrot golf)";;
val it : string list =
  ["alpha (brown) (charlie delta)"; "echo"; "foxtrot golf"]

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

 
type Data =
    | Atom of string
    | List of Data list

let parse (input:string) =
    let max = input.Length 
    let rec skipWS i =
        if i < max && input.[ i] = ' ' then skipWS (i+1) else i
    let rec parseList n =
        assert(input.[ n] = '(')
        let mutable i = skipWS(n+1)
        let l = new ResizeArray<_>()
        while i < max && input.[ i] <> ')' do
            let data, j = parseData i
            l.Add(data)
            i <- j
        if i=max then failwith "bad parse - missing )"
        assert(input.[ i] = ')')
        List(Seq.toList l), i+1
    and parseAtom n =
        let mutable i = skipWS(n)
        if i=max then failwith "bad parse - expected atom"
        let sb = new System.Text.StringBuilder()
        while i < max && input.[ i] <> ' ' && input.[ i] <> '(' && input.[ i] <> ')' do
            sb.Append(input.[ i]) |> ignore
            i <- i + 1
        if sb.Length = 0 then failwith "bad parse - expected atom"
        Atom(sb.ToString()), i
    and parseData n =
        let i = skipWS(n)
        if input.[ i] = '(' then
            parseList i
        else
            parseAtom i
    let r, i = parseList 0
    r
        
let s = "(alpha (brown) (charlie delta)) echo (foxtrot golf)"
printfn "%A" (parse ("("+s+")"))