peg-3-checkForLeftRecursion.fs

let checkForLeftRecursion (rules:Map<string,Expression>) =
    let rec leftRules = function
    | Terminal _ | TerminalOneOf _ | TerminalUnicode _ | TerminalWildcard | Epsilon -> []
    | NonTerminal x -> [x]
    | ZeroOrMore x | OneOrMore x | Optional x | Not x | And x -> leftRules x
    | Choice x ->
        List.concat <| List.map leftRules x
    | Sequence x ->
        let rec processList = function
        | [] -> []
        | (head :: tail) ->
            match head with
            | Optional _ | Not _ | And _ | ZeroOrMore _ | OneOrMore _ -> List.append (leftRules head) (processList tail)
            | x -> leftRules head
        processList x
    | Rule _ -> failwith "Internal error"

    let rec checkRule name prior = 
        if List.exists ((=) name) prior then
            failwithf "Left recursion calling %s" <| List.reduce (fun a b -> (b + " -> " + a)) (name :: prior)
        match Map.tryFind name rules with
        | None -> failwithf "Unknown rule %s" name
        | Some x ->
            let leftchoices = leftRules x
            let sp = (name :: prior)
            for rule in leftchoices do checkRule rule sp done

    try
        Map.iter (fun k _ -> checkRule k []) rules
    with
    | ex -> eprintfn "Grammar error: %s" ex.Message
            failwith "Invalid Grammar"