How to parse a boolean expression

Question

I'm pretty new to F#, and I'm trying to use recursion to solve a problem.

The function receives a string, and returns a bool. The string gets parsed, and evaluated. This is bool logic, so

• (T|F) returns true
• (T&(T&T)) returns true
• ((T|T)&(T&F)) returns false
• (F) = returns false

My idea was that every time I found a ), replace the part of the string from the previous ( to that ) with the result of the Comparison match. Doing this over and over until only T or F remains, to return true or false.

EDIT: I expect it to take the string, and keep swapping out what is in between the ( and ) with the result of the comparison until it comes down to a T or F. What is happening, is an error about an incomplete structured construct. The error is in the for loop.

As I am so new to this language, I'm not sure what I'm doing wrong. Do you see it?

let ComparisonSolver (comp:string) =

    let mutable trim = comp
    trim <- trim.Replace("(", "")
    trim <- trim.Replace(")", "")

    match trim with
    | "T" -> "T"
    | "F" -> "F"
    | "!T" -> "F"
    | "!F" -> "T"
    | "T&T" -> "T"
    | "F&F" -> "T"
    | "T&F" -> "F"
    | "F&T" -> "F"
    | "T|T" -> "T"
    | "F|F" -> "F"
    | "T|F" -> "T"
    | "F|T" -> "T"
    | _ -> ""

let rec BoolParser arg =
    let mutable args = arg

    if String.length arg = 1 then 
        match arg with
        | "T" -> true
        | "F" -> false
    else
        let mutable ParseStart = 0
        let endRange = String.length args

        for letter in [0 .. endRange]
            if args.[letter] = "(" then
                ParseStart <- letter
            else if args.[letter] = ")" then
                args <- args.Replace(args.[ParseStart .. letter], ComparisonSolver args.[ParseStart .. letter])
                BoolParser args

let result = BoolParser "(T)&(F)"

Answer 1

There are a few things you need to correct.

• for letter in [0 .. endRange] is missing a do at the end of it - it should be for letter in [0 .. endRange] do
• The if comparisons in the for loop are comparing chars with strings. You need to replace "(" and ")" with '(' and ')'
• for letter in [0 .. endRange] will go out of range: In F# the array construct [x..y] will go from x to y inclusive. It's a bit like in C# if you had for (int i = 0; i <= array.Length; i++). In F# you can also declare loops like this: for i = 0 to endRange - 1 do.
• for letter in [0 .. endRange] will go out of range again: It's going from 0 to endrange, which is the length of args. But args is getting shortened in the for loop, so it will eventually try to get a character from args that's out of range.

Now, the problem with the if..then..else statements, which is what I think you were looking at from the beginning.

if args.[letter] = '(' then
 ParseStart <- letter
else if args.[letter] = ')' then
 args <- args.Replace(args.[ParseStart .. letter], ComparisonSolver args.[ParseStart .. letter])
 BoolParser args

Let's take the code within the two branches as two separate functions.

The first does ParseStart <- letter, which assigns letter to ParseStart. This function returns unit, which is F# equivalent of void.

The second does:

args <- args.Replace(args.[ParseStart .. letter], ComparisonSolver args.[ParseStart .. letter])
BoolParser args

This function returns a bool.

Now when you put them together in an if..then..else statement you have in one branch that results a unit and in the other in a bool. In this case it doesn't know which one to return, so it shows an "expression was expected to have type" error.

I strongly suspect that you wanted to call BoolParser args from outside the for/if loop. But it's been indented so that F# treats it as part of the else if statement.

Answer 2

There are many ways to parse a boolean expression. It might be a good idea to look at the excellent library FParsec.

http://www.quanttec.com/fparsec/

Another way to implement parsers in F# is to use Active Patterns which can make for readable code

https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/active-patterns

It's hard to provide good error reporting through Active Patterns but perhaps you can find some inpiration from the following example:

let next s i = struct (s, i) |> Some

// Skips whitespace characters
let (|SkipWhitespace|_|) struct (s, i) =
  let rec loop j =
    if j < String.length s && s.[j] = ' ' then
      loop (j + 1)
    else
      next s j
  loop i

// Matches a specific character: ch
let (|Char|_|) ch struct (s, i) =
  if i < String.length s && s.[i] = ch then
    next s (i + 1)
  else
    None

// Matches a specific character: ch
//  and skips trailing whitespaces
let (|Token|_|) ch =
  function
  | Char ch (SkipWhitespace ps) -> Some ps
  | _                           -> None

// Parses the boolean expressions
let parse s =
  let rec term =
    function
    | Token 'T' ps                        -> Some (true, ps)
    | Token 'F' ps                        -> Some (false, ps)
    | Token '(' (Parse (v, Token ')' ps)) -> Some (v, ps)
    | _ -> None
  and opReducer p ch reducer = 
    let (|P|_|) ps = p ps
    let rec loop l =
      function
      | Token ch (P (r, ps))  -> loop (reducer l r) ps
      | Token ch _            -> None
      | ps                    -> Some (l, ps)
    function
    | P (l, ps) -> loop l ps
    | _         -> None 
  and andExpression ps  = opReducer term           '&' (&&) ps
  and orExpression ps   = opReducer andExpression  '|' (||) ps
  and parse ps          = orExpression ps
  and (|Parse|_|) ps    = parse ps
  match (struct (s, 0)) with
  | SkipWhitespace (Parse (v, _)) -> Some v
  | _                             -> None

module Tests = 
  // FsCheck allows us to get better confidence in that the parser actually works
  open FsCheck

  type Whitespace = 
    | Space

  type Ws = Ws of (Whitespace [])*(Whitespace [])

  type Expression =
    | Term  of Ws*bool
    | And   of Expression*Ws*Expression
    | Or    of Expression*Ws*Expression

    override x.ToString () =
      let orPrio              = 1
      let andPrio             = 2
      let sb                  = System.Text.StringBuilder 16
      let ch c                = sb.Append (c : char)  |> ignore
      let token (Ws (l, r)) c = 
        sb.Append (' ', l.Length) |> ignore
        sb.Append (c : char)      |> ignore
        sb.Append (' ', r.Length) |> ignore
      let enclose p1 p2 f     = 
        if p1 > p2 then ch '('; f (); ch ')'
        else f ()
      let rec loop prio =
        function
        | Term (ws, v)    -> token ws (if v then 'T' else 'F')
        | And  (l, ws, r) -> enclose prio andPrio <| fun () -> loop andPrio l; token ws '&' ;loop andPrio r
        | Or   (l, ws, r) -> enclose prio orPrio  <| fun () -> loop orPrio l ; token ws '|' ;loop orPrio r
      loop andPrio x
      sb.ToString ()

    member x.ToBool () =
      let rec loop =
        function
        | Term (_, v)     -> v
        | And  (l, _, r)  -> loop l && loop r
        | Or   (l, _, r)  -> loop l || loop r
      loop x

  type Properties() =
    static member ``Parsing expression shall succeed`` (expr : Expression) =
      let expected  = expr.ToBool ()  |> Some
      let str       = expr.ToString ()
      let actual    = str             |> parse
      expected      = actual

  let fscheck () =
    let config = { Config.Quick with MaxTest = 1000; MaxRejected = 1000 }
    Check.All<Properties> config