Documentation and examples are quite sparse

[JonasHedEng]

Hi!
This seems like a really nice lib and I've tried to use it for a quite simple expression parser, inspired by clarkmcc/cel-rust.

My attempt so far (trying to keep things minimal until I get something working) is the pasted snippet at the bottom.
When running it, it seems to get into some infinite loop but I'm not really sure how to address it? I'm assuming I'm infinitely recursing down the lhs but I'm also not sure how to express it otherwise?

I've tried looking at the documentation and the examples but I can't really figure out how to map them to my use case. I'd appreciate any kind of help and I'll gladly contribute such a lexer/parser as example/testing back upstream if I get something representable working!

import gleam/io
import gleam/list
import gleam/option.{None, Some}
import gleam/set
import nibble.{type Parser}
import nibble/lexer

type TokenT {
  // Arithmetic
  AddT
  SubT
  MulT
  DivT
  ModT

  // Relation
  LessThanT
  LessThanEqT
  GreaterThanT
  GreaterThanEqT
  EqualsT
  NotEqualsT
  InT

  // Atom
  IntT(Int)
  // AUInt(Int)
  FloatT(Float)
  StringT(String)
  BoolT(Bool)
  NullT

  // Ident
  IdentT(String)

  LParen
  RParen
}

pub type ArithmeticOp {
  Add
  Sub
  Mul
  Div
  Mod
}

pub type RelationOp {
  LessThan
  LessThanEq
  GreaterThan
  GreaterThanEq
  Equals
  NotEquals
  In
}

pub type Atom {
  Int(Int)
  Float(Float)
  // String(String)
  Bool(Bool)
  Null
}

pub type Expression {
  Arithmetic(Expression, ArithmeticOp, Expression)
  Relation(Expression, RelationOp, Expression)
  Atom(Atom)
  Ident(String)
}

type Context {
  // InList
  // InMap
  // InTernary
  InSubExpr
}

fn lexer() {
  let reserved_literals = set.from_list(["false", "in", "null", "true"])
  let reserved_host =
    set.from_list([
      "as", "break", "const", "continue", "else", "for", "function", "if",
      "import", "let", "loop", "package", "namespace", "return", "var", "void",
      "while",
    ])

  let reserved = set.intersection(reserved_literals, reserved_host)

  let grouping = [lexer.token("(", LParen), lexer.token(")", RParen)]
  let arithmetic_op = [
    lexer.token("+", AddT),
    lexer.token("-", SubT),
    lexer.token("*", MulT),
    lexer.token("/", DivT),
    lexer.token("%", ModT),
  ]

  let relation_op = [
    // Relation
    lexer.token("<", LessThanT),
    lexer.token(">", GreaterThanT),
    lexer.token("<=", LessThanEqT),
    lexer.token(">=", GreaterThanEqT),
    lexer.token("==", EqualsT),
    lexer.token("!=", NotEqualsT),
    lexer.token("in", InT),
  ]
  let value = [
    // Value
    lexer.token("true", BoolT(True)),
    lexer.token("false", BoolT(False)),
    lexer.number(IntT, FloatT),
    // lexer.then -> UInt
    lexer.string("\"", StringT),
    lexer.string("'", StringT),
    lexer.token("null", NullT),
  ]

  lexer.simple(
    list.flatten([
      grouping,
      arithmetic_op,
      relation_op,
      value,
      [
        // Identifier
        lexer.identifier("[_a-zA-Z][_a-zA-Z0-9]*", "[^\\s=]", reserved, IdentT),
        // Comments
        lexer.comment("//", fn(_) { Nil }) |> lexer.ignore(),
        // Whitespace
        lexer.whitespace(Nil)
          |> lexer.ignore(),
      ],
    ]),
  )
}

fn parser() -> Parser(Expression, TokenT, Context) {
  use expr <- nibble.do(arith_add_sub_full_parser())
  nibble.succeed(expr)
}

fn arith_add_sub_full_parser() -> Parser(Expression, TokenT, Context) {
  nibble.one_of([arith_add_sub_inner_parser(), arith_mul_div_mod_full_parser()])
}

fn arith_add_sub_inner_parser() -> Parser(Expression, TokenT, Context) {
  use lhs <- nibble.do(nibble.lazy(arith_add_sub_full_parser))
  use op <- nibble.do(op_add_sub_parser())
  use rhs <- nibble.do(arith_mul_div_mod_full_parser())

  nibble.return(Arithmetic(lhs, op, rhs))
}

fn arith_mul_div_mod_full_parser() -> Parser(Expression, TokenT, Context) {
  nibble.one_of([arith_mul_div_mod_inner_parser(), atom_parser()])
}

fn arith_mul_div_mod_inner_parser() -> Parser(Expression, TokenT, Context) {
  use lhs <- nibble.do(nibble.lazy(arith_mul_div_mod_full_parser))
  use op <- nibble.do(op_mul_div_mod_parser())
  use rhs <- nibble.do(atom_parser())

  nibble.return(Arithmetic(lhs, op, rhs))
}

fn op_mul_div_mod_parser() -> Parser(ArithmeticOp, TokenT, Context) {
  use tok <- nibble.take_map("*,/,%")

  case tok {
    MulT -> Some(Mul)
    DivT -> Some(Div)
    ModT -> Some(Mod)
    _ -> None
  }
}

fn op_add_sub_parser() -> Parser(ArithmeticOp, TokenT, Context) {
  use tok <- nibble.take_map("+,-")

  case tok {
    AddT -> Some(Add)
    SubT -> Some(Sub)
    _ -> None
  }
}

fn atom_parser() -> Parser(Expression, TokenT, Context) {
  nibble.backtrackable({
    use t <- nibble.do(nibble.any())

    case t {
      IntT(n) -> nibble.return(Atom(Int(n)))
      FloatT(n) -> nibble.return(Atom(Float(n)))
      BoolT(n) -> nibble.return(Atom(Bool(n)))
      NullT -> nibble.return(Atom(Null))
      _ -> nibble.fail("Expected a literal value")
    }
  })
}

pub fn main() {
  let assert Ok(lexed) = lexer.run("5 + a", lexer())

  let _ =
    nibble.run(lexed, parser())
    |> io.debug

  "done"
}

[hayleigh-dot-dev]

Howdy! Your parser suffers from a common problem known as "left recursion". This is where you have a parser defined in terms of itself, that recurses before ever consuming any input. The offending parts are here:

fn arith_add_sub_full_parser() -> Parser(Expression, TokenT, Context) {
  nibble.one_of([arith_add_sub_inner_parser(), arith_mul_div_mod_full_parser()])
}

fn arith_add_sub_inner_parser() -> Parser(Expression, TokenT, Context) {
  use lhs <- nibble.do(nibble.lazy(arith_add_sub_full_parser))

It's pretty easy to see why this hangs if we just say out loud how this code will work:

• run arith_add_sub_full_parser
• attempt the first parser in the one_of, that's arith_add_sub_inner_parser
• the first step is to do arith_add_sub_full_parser
• ... repeat infinitely without consuming input.

This isn't a problem specific to nibble, its a common trap folks run into when they first start thinking about expression parsers!

---

The good news is nibble comes with a built in way to handle recursive expressions with binary (and unary) operators, that's that nibble/pratt module. You can read about pratt parsers yourself if you're interested, but suffice to say this is an abstraction specifically there for writing expression parsers ^^ Let's take a look at what your parser would look like if you used it.

First, let's set up the "atomic" parsers, the bits that mostly just consume one token:

fn atom_parser(_) -> Parser(Expression, TokenT, Context) {
  use tok <- nibble.take_map("INT | FLOAT | BOOL | NULL | IDENT")
  
  case tok {
    IntT(n) -> Int(n) |> Some
    FloatT(n) -> Float |> Some
    // ...
    _ -> None
  }
}

fn arithmetic_operator_parser(op: ArithmeticOperator) -> Parser(...) {
  use tok <- nibble.take_map("+ | - | * | / | %")
  
  case tok, op {
    AddT, Add -> Some(Add)
    SubT, Sub -> Some(Sub)
    // ...
    _, _ -> None
  } 
}

fn arithmetic_binop(op: ArithmeticOperator) -> fn(Expression, Expression) -> Expression {
  fn(lhs, rhs) {
    Arithmetic(lhs, op, rhs)
  }
}

Now, let's use the pratt module to create an expression parser:

fn expression_parser() -> Parser(...) {
  pratt.expression(
    one_of: [atom_parser],
    and_then: [
      pratt.infix_left(6, arithmetic_operator_parser(Add), arithmetic_binop(Add)),
      pratt.infix_left(6, arithmetic_operator_parser(Sub), arithmetic_binop(Sub)),
      pratt.infix_left(7, arithmetic_operator_parser(Mul), arithmetic_binop(Mul)),
      pratt.infix_left(7, arithmetic_operator_parser(Div), arithmetic_binop(Div)),
    ],
    dropping: nibble.succeed(Nil),
  )
}

Somewhat intuitively, we can kind of grok what this does. First take one_of our atoms, and_then construct one of our infix expressions.

Some things to note:

• infix_left and infix_right are about operator associativity. That's what behaviour the operator should have when you have a composite expression like 1 + 2 + 3. In a left associative operator, this would be parsed as (1 + 2) + 3.
• The number given to each operator is its precedence. When we have an expression like 1 + 2 * 3 we want to make sure it is parsed correctly: without any precedence this expression would parse as (1 + 2) * 3, but if we assign multiplication a higher precedence than addition it is correctly parsed as 1 + (2 * 3)
• the dropping is a parser that consumes no input in this case, but it might be a parser that takes whitespace or comments or any other token that is not part of your expression language.

---

I hope this gets you off on the right foot. If you'd like to solve this without using nibble's pratt parser (specifically if you dont care about operator precedence in this little exercise, it's tricky to roll your own) then the trick to solving your left recursion problem is to make sure you consume some input first before you move on. So you might do:

fn expression_parser() {
  // always consume something
  use lhs <- atom_parser()

  nibble.one_of([
    // try and parse a binop, carry the left hand side
    // through
    binop_expression_parser(lhs),
    // else we just have an atom on its own
    nibble.return(lhs)
  ])
}

fn binop_expression_parser(lhs) {
  use op <- nibble.do(arithmetic_operator_parser())
  use rhs <- nibble.do(nibble.lazy(expression_parser))
  
  case op {
    Add -> Arithmetic(lhs, Add, rhs)
    // ...
  }
}

fn arithmetic_operator_parser() {
  use tok <- nibble.take_map("+ | - | ... ")

  case tok {
    AddT -> Some(Add)
    // ...
  }
}

Notice how this parser never backtracks. The way nibble works is that as soon as a parser consumes input it will continue down that path until success or failure, and not try anything else even if it is in a one_of. This is important because backtracking in a parser is incredibly expensive. Instead, we factor out the parts that are common and do those first: in this case that means always parsing an atom and only then do we either try to parse a binop or just succeed with the expression.

Another way to think about backtracking is that its a system for arbitrary lookahead. You might see some parsers described as "LR(1)" which means "left-to-right with one token lookahead". Because of how nibble works, when you introduce backtracking it is incredibly easy to end up with a LR(k) parser where k is unbounded: infinite lookahead! Once you throw recursive parsers into the mix you end up with a complexity explosion that will make your parser very slow.

[JonasHedEng]

Thank you so much for such a great and extensive answer and explanation ❤️

The parser that I linked to (cel-rust) seems to me like the operator precedence is "implicit" through the hierarchy, (relation expression is <relation operator arithmetic_add_sub> or <arithmetic_add_sub> while the arithmetic_add_sub is left recursive the same way but with arithmetic_mul_div for the "base case". My understanding from your answer is that such a left associative (recursive?) parser is not possible to implement the same way with "just" nibble/parser, did I understand you correct?

I'll give pratt another go now that I've gotten a bit more insight and some guiding! I tried it before but got confused when I was supposed to take/consume/discard the Config pratt provides. I'll give that a go first, maybe try some more with the pratt+backtrack-less approach and then get back to you here with how it goes. Again, thank you so much for the amazing answer!

[hayleigh-dot-dev]

You cannot look at the grammar for a parser generator, translate it directly into code, and assume it works 1:1. I've never seen that particular grammar syntax before, but it is entirely possible that whatever parser generator they are using is able to factor out left recursion automatically but all it will be doing is turning that grammar into code that is not left recursive: the parser has to move forward somehow eventually!

got confused when I was supposed to take/consume/discard the Config pratt provides.

Really the only thing to do is pass the config down to pratt.subexpression ^^ but aye without any docs its not very easy to Just Know how this stuff fits together.

[JonasHedEng]

I've gotten a bit further now, I think I made it much more difficult for myself initially by trying to split up the pratt.expression into arithmetic/relation/etc instead of having it in the top level one. I'm now stuck on the ternary expression though, any input on how I can achieve that? I wanted to try the pratt.subexpression but the Context is opaque and I didn't find any other way to construct it? Is it something obvious I'm overlooking?

Currently, I have this (the subexpression obviously doesn't work here, the rest seems to work correctly though!)

fn expression_parser() -> Parser(Expression, lexer.Token, Context) {
  let add = fn(lhs, rhs) { Arithmetic(lhs, Add, rhs) }
  let sub = fn(lhs, rhs) { Arithmetic(lhs, Sub, rhs) }
  let mul = fn(lhs, rhs) { Arithmetic(lhs, Mul, rhs) }
  let div = fn(lhs, rhs) { Arithmetic(lhs, Div, rhs) }
  let mod = fn(lhs, rhs) { Arithmetic(lhs, Mod, rhs) }

  let lte = fn(lhs, rhs) { Relation(lhs, LessThanEq, rhs) }
  let lt = fn(lhs, rhs) { Relation(lhs, LessThan, rhs) }
  let gte = fn(lhs, rhs) { Relation(lhs, GreaterThanEq, rhs) }
  let eq = fn(lhs, rhs) { Relation(lhs, Equals, rhs) }
  let neq = fn(lhs, rhs) { Relation(lhs, NotEquals, rhs) }
  let in = fn(lhs, rhs) { Relation(lhs, In, rhs) }

  let and = fn(lhs, rhs) { Logical(lhs, And, rhs) }
  let or = fn(lhs, rhs) { Logical(lhs, Or, rhs) }

  let not = fn(expr) { Unary(Not, expr) }
  let unary_sub = fn(expr) { Unary(UnarySub, expr) }

  pratt.expression(
    one_of: [
      atom_parser,
      ident_parser,
      parens_parser,
      pratt.prefix(8, nibble.token(lexer.ExclamationMark), not),
      pratt.prefix(8, nibble.token(lexer.Sub), unary_sub),
      pratt.sub_expression(conditional_parser, 2),
    ],
    and_then: [
      pratt.infix_left(7, nibble.token(lexer.Mul), mul),
      pratt.infix_left(7, nibble.token(lexer.Div), div),
      pratt.infix_left(7, nibble.token(lexer.Mod), mod),
      pratt.infix_left(6, nibble.token(lexer.Add), add),
      pratt.infix_left(6, nibble.token(lexer.Sub), sub),
      pratt.infix_left(5, nibble.token(lexer.LessThanEq), lte),
      pratt.infix_left(5, nibble.token(lexer.LessThan), lt),
      pratt.infix_left(5, nibble.token(lexer.GreaterThanEq), gte),
      pratt.infix_left(5, nibble.token(lexer.GreaterThan), gte),
      pratt.infix_left(5, nibble.token(lexer.Equals), eq),
      pratt.infix_left(5, nibble.token(lexer.NotEquals), neq),
      pratt.infix_left(5, nibble.token(lexer.In), in),
      pratt.infix_left(4, nibble.token(lexer.And), and),
      pratt.infix_left(3, nibble.token(lexer.Or), or),
    ],
    dropping: nibble.succeed(Nil),
  )
}

fn conditional_parser() {
  use cond <- nibble.do_in(InSubExpr, nibble.lazy(expression_parser))
  use _ <- nibble.do(nibble.token(lexer.Colon))
  use then <- nibble.do_in(InSubExpr, nibble.lazy(expression_parser))
  use _ <- nibble.do(nibble.token(lexer.QuestionMark))
  use otherwise <- nibble.do_in(InSubExpr, nibble.lazy(expression_parser))

  nibble.return(Ternary(cond, then, otherwise))
}

Also, I'm trying to use the operator precedence from the cel-spec (seemingly same order as the wiki on operator precedence) but the operator precedence in their table seem to be reversed from pratt-s order?

[Aurora2500]

fn conditional_parser() {
use cond <- nibble.do_in(InSubExpr, nibble.lazy(expression_parser))
use _ <- nibble.do(nibble.token(lexer.Colon))
use then <- nibble.do_in(InSubExpr, nibble.lazy(expression_parser))
use _ <- nibble.do(nibble.token(lexer.QuestionMark))
use otherwise <- nibble.do_in(InSubExpr, nibble.lazy(expression_parser))

nibble.return(Ternary(cond, then, otherwise))
}

Looks like the queston mark & colon tokens are swapped from the usual way you'd expect them to behave in a ternary.