How to parse boolean expressions as a list?

[gmedori]

So I am trying to write a ParserPrinter for an arbitrary boolean expression with the following rules:

1. If two expressions are separated by a space like expr1 expr2, you should AND them together.
2. If two expressions are separated by "or" like expr1 or expr2, you should OR them together.
3. OR has higher precedence than AND. For example expr1 expr2 or expr3 is equivalent to expr1 (expr2 or expr3).

I already have parser-printers that can operate on individual terms, so now I'm just working on the boolean-ness. Here's my biggest requirement:

The resulting syntax tree should group together identical operations at the same depth in a list rather than a tree structure. What I mean by that can be visualized like so:

Given the following input where each single character is a term: A B or C or D E, the resulting syntax tree should look like this:

.and([
    A,
    .or([
        B,
        C,
        D,
    ]),
    E
])

So all the AND operations at the same level accumulate into a list rather than a binary tree, same as the OR operations one level deeper.

I've looked at a few examples from the repo for inspiration. Specifically, I looked at the arithmetic parser to understand how I might achieve precedence, and I looked at the JSON parser to see how I might achieve the plurality I'm looking for, but I've spent so much time thinking about this that my brain feels like mush and I'm having trouble piecing together the puzzle.

Can anyone provide any guidance as to how I might achieve what I'm looking for?

[mbrandonw]

Hi @gmedori, building on top of the arithmetic parser demo I was able to come up with this:

import Parsing
import Testing

indirect enum Expr: Equatable {
  case and(Expr, Expr)
  case or(Expr, Expr)
  case value(String)
}

@Suite struct ExprTests {
  @Test func expr() throws {
    var output: Expr!
    let input = "A B or C or D E"[...].utf8
    output = try ExprParser().parse(input)
    #expect(
      output
      == .and(
        .and(
          .value("A"),
          .or(
            .or(
              .value("B"),
              .value("C")
            ),
            .value("D")
          )
        ),
        .value("E")
      )
    )
  }
}

struct ExprParser: Parser {
  var body: some Parser<Substring.UTF8View, Expr> {
    InfixOperator(associativity: .left) {
      " ".utf8.map { Expr.and }
    } lowerThan: {
      Or()
    }
  }
}

struct Or: Parser {
  var body: some Parser<Substring.UTF8View, Expr> {
    InfixOperator(associativity: .left) {
      " or ".utf8.map { Expr.or }
    } lowerThan: {
      Factor()
    }
  }
}

struct Factor: Parser {
  var body: some Parser<Substring.UTF8View, Expr> {
    OneOf {
      Parse {
        "(".utf8
        ExprParser()
        ")".utf8
      }

      OneOf {
        Prefix(while: { $0 != .init(ascii: " ") })
        Rest()
      }
      .map { Expr.value(String(Substring($0))) }
    }
  }
}

public struct InfixOperator<Input, Operator: Parser, Operand: Parser>: Parser
where
  Operator.Input == Input,
  Operand.Input == Input,
  Operator.Output == (Operand.Output, Operand.Output) -> Operand.Output
{
  public let `associativity`: Associativity
  public let operand: Operand
  public let `operator`: Operator

  @inlinable
  public init(
    associativity: Associativity,
    @ParserBuilder<Input> _ operator: () -> Operator,
    @ParserBuilder<Input> lowerThan operand: () -> Operand
  ) {
    self.associativity = `associativity`
    self.operand = operand()
    self.operator = `operator`()
  }

  @inlinable
  public func parse(_ input: inout Input) rethrows -> Operand.Output {
    switch associativity {
    case .left:
      var lhs = try self.operand.parse(&input)
      var rest = input
      while true {
        do {
          let operation = try self.operator.parse(&input)
          let rhs = try self.operand.parse(&input)
          rest = input
          lhs = operation(lhs, rhs)
        } catch {
          input = rest
          return lhs
        }
      }
    case .right:
      var lhs: [(Operand.Output, Operator.Output)] = []
      while true {
        let rhs = try self.operand.parse(&input)
        do {
          let operation = try self.operator.parse(&input)
          lhs.append((rhs, operation))
        } catch {
          return lhs.reversed().reduce(rhs) { rhs, pair in
            let (lhs, operation) = pair
            return operation(lhs, rhs)
          }
        }
      }
    }
  }
}

public enum Associativity {
  case left
  case right
}

The only thing it does not do is collapse nested or's (e.g. or(A, or(B, C))) into a flat array (.or([A, B, C])). That is definitely possible to do though.

[gmedori]

This is getting me close to where I need to go I think! Thank you! However I have two challenges when trying to adopt this approach. For reference, here's my source for the parser and the syntax tree type. Note that I'm deferring the collapsing of operands to a post-processing step.

public indirect enum BooleanQuery: Sendable, Equatable {
  case and([BooleanQuery])
  case or([BooleanQuery])
  case term(SingleQuery)

  @Sendable static func andFunc(left: BooleanQuery, right: BooleanQuery) -> Self {
    .and([left, right])
  }

  @Sendable static func orFunc(left: BooleanQuery, right: BooleanQuery) -> Self {
    .or([left, right])
  }
}

// MARK: - Parser

import Parsing

extension BooleanQuery {
  struct AndParser: Parser {
    var body: some Parser<Substring, BooleanQuery> {
      InfixOperator(associativity: .left) {
        " ".map { BooleanQuery.andFunc }
      } lowerThan: {
        OrParser()
      }
    }
  }

  struct OrParser: Parser {
    var body: some Parser<Substring, BooleanQuery> {
      InfixOperator(associativity: .left) {
        " or ".map { BooleanQuery.orFunc }
      } lowerThan: {
        TermParser()
      }
    }
  }

  struct TermParser: ParserPrinter {
    var body: some ParserPrinter<Substring, BooleanQuery> {
      // SingleQuery.Parser's implementation is omitted but it's similar to the Factor parser presented above.
      SingleQuery.Parser().map(.case(BooleanQuery.term))
    }
  }
}

Challenge 1: Weird Sendable errors?

I'm seeing an error saying "Converting non-sendable function value to '(BooleanQuery.OrParser.Output, BooleanQuery.OrParser.Output) -> BooleanQuery.OrParser.Output' may introduce data races" at both callsites to InfixOperator. I marked all my static initializers with @Sendable thinking that was the problem, but that doesn't seem to have made a difference. After trying everything I thought made sense, I started throwing @Sendable on just about every closure to no avail. Any idea what's going on here?

Challenge 2: I need a parser and a printer

The InfixOperator type seems like it's doing a lot of heavy lifting here, and while I understand it at a superficial level, it's not immediately clear to me how I'd transform it to be a printer as well as a parser. A first step would be to require Operator and Operand to conform to ParserPrinter, and then I suppose I'd need to store the substring for the operation as well so I can insert it into the appropriate places.

Alternatively, maybe I use InfixOperator for parsing and I provide my own bespoke implementation for print?

[gmedori]

I actually went ahead and copied your code @mbrandonw into my project instead of just adapting it, and the same error is triggering on your code verbatim. I wonder what the heck is going on.

[gmedori]

Looks like removing the @ParserBuilder<Input> from each of the parameters in the InfixOperator initializer fixed the build failure for me, though I'm not sure why that happened. I'm continuing to work on the ParserPrinter and will report back here when I have a solution that fits my needs.

Currently, implementing the printer kind of sucks because my transformation that goes from binary tree to collapsed arrays is a one-way transformation, so the part of the printer that checks for round-tripping is angry.