This repository contains a port of Bob Nystorm's Bantam Pratt Parser example to the Odin language.

I was interested in building a Pratt Parser in Odin because it is different enough from the language used by Bob Nystrom (Java). Odin is a procedural language without the Object-Oriented features used in Bantam (no interfaces, no class, no inheritance based polymorphism). Instead Odin has tagged unions (Sum Types by another name) which are useful to build Abstract Syntax Trees.

Bob Nystorm has a great explanation for Pratt Parser in this blog post and I would recommend reading it before going through the code. It is also a good idea to look at Bob Nystorm's Java code on github since it relates closely to the article. I tried to keep procedure and type names close to the original to facilitate comparison between the two code bases.

The name Bantam refers to a type of small chicken. Barbu D'Uccle is a famous Bantam race (if you are into such a thing as chicken). I needed a name and Barbu is cute, the rest is history.

The code in this repository is distributed under the MIT license (consistent for the Java Bantam code). This code heavily borrows from Bob Nystorm's Java Bantam project (Copyright for the Java code is (c) 2011 Bob Nystorm). The Odin code is Copyrighted (c) 2026 Robert Monnet.

When building a parser for a programming language or domain specific language by hand, one common method is to use a recursive descent parser. When it gets to parsing arithmetic expressions, you need to account for operator precedence (* has higher precedence than +) and associativity (assignment and exponentiation are right associative). The classical way to handle precedence and associativity is to split operators from different precedence in different rules.

Here are a fragment of the rules for the Bantam language in EBNF.

assignment = identifier "=" expression ; (right associative)
expression = term { ( "+" | "-" ) term } ;
term = exponent { ( "*" | "/" ) exponent } ;
exponent = factor [ "^" exponent ] ; (right associative)
factor = [ "-" ] primary ;
primary = identifier | "(" expression ")" ;
identifier = letter { letter } ;

This is already complex and hard to get your head around and where Vaughan Pratt got a stroke of genius. What Pratt realized is that precedence and right associativity can be used to decide when to stop and group what you have already and when to keep parsing. The pseudo code for the Pratt parser looks like:

parse_expr(min_prec):
  // Read the first token, could be a standalone token or the left part of an infix expression.
  left = parse_prefix(cur_token)
  // Keep parsing additional terms as long as the left part has a higher precedence than
  // what is on the right.
  while more(tokens) and next_token().prec > min_prec:
    op = read_next_token()
    left = parse_infix(op, left)
  return left

parse_infix(op, left):
  // We simulate right-associativity by decreasing the operator precedence of what we have already parsed.
  // The parser will keep parsing the right side even when it encounters an operator with the same precedence as the left operator.
  op_prec = op.prec
  if right_assoc(op) op_prec -= 1 
  right = parse_expr(op_prec)
  return Node(op, left, right)

If this is too much in one take, Bob has a much better explanation in his blog post.

The point is that, instead of a complicated set of EBNF rules to account for the different precedences and associativity, you can just use the parsing algorithm above and define a table of operator precedence. In our small example, that table would look like:

The advantage of the Pratt Parser compounds as the number of operator grows. It is also extremely easy to change operator precedence or associativity (compared with reworking the EBNF rules and the associated code).

I am playing with design variants to see how far I can take advantage of the Odin features in the parser design. Each experiment is captured in its own branch that you can explore in git.

The main branch reflects a refinement of the original solution (see original branch below).

Where in the original solution we automatically converted any OO inheritance solution to a tagged union with one variant per Java subclass, we revisited the solution for Prefix_Parselet and Infix_Parselet. Instead of having separate variants for each Parselet, like in Java, we stored the parser procedure directly in the Parselet structure. Odin has first class procedure so that's easy to do. Once the Parselet contains the parser procedure, we can get rid of all the Parselet variants. We can also get rid of the top-level prefix_parse() and infix_parse() since they are just dispatching to the different variants.

This branch is the original solution that I derived from Bob's Java code. The differences with the Java solutions are:

• The Lexer returns a list of all the Tokens in the source (instead of an iterator). Odin doesn't have built-in support for custom iterators but the solution is easy (returns an array of Token). Actually it avoid having to define the equivalent to the mRead field in the Parser for lookahead operations.
• The original interface/subclass solution used for Expression and Parselet is replaced by the use of a tagged union (a sum type) and a single procedure handling the variants via a type switch. In Odin, this is the idiomatic way to handle types with variable payload such as an Abstract Syntax Tree nodes.
• Odin uses manual memory management so typically you would see a lot of free() and delete(). I bypassed the problem here by assuming the Parser caller will setup a memory arena and clean all the allocation at once since they have a similar lifetime. Using an arena is an idiomatic (and simple) solution in Odin (see Mistakes and Cool Things to Do with Arena Allocators if you are interested in the topic). It also helps keep the code simple and focused on the parser problem.

You will need to install Odin if you want to run the examples. Odin has tooling for Windows, MacOS, and Linux. Odin comes with battery included if you are into game development or graphics but that's a story for another day. The language is fairly simple and you can go through the overview in a few hours. It is very readable and if you know a language like C or Pascal, you can probably understand the code without learning the language first.

You can run the tests with:

odin test .

I kept the structure flat, with all the code in a single package (barbu). All procedures and fields are public. The point is to demonstrate the parser so I have striven for less code in the hope of making the logic stand out.

• Pratt Parsing: Expression Parsing Made Easy, by Bob Nystrom
• Bob Nystorm's Bantam Repository
• Top Down Operator Precedence
• Odin Website