Crafting Interpreters in OCaml - Building our Context-Free Grammar

I HIGHLY recommend reading the chapter in entirety before moving into this post.

One of the advantages of using OCaml (or really, a functional language with a strong type system) is that we can dismiss a lot of the boilerplate and OO design pattern work that Bob needs to configure his Expr.java. Let’s create a file called expr.ml.

The key bit of information in Bob’s code is here:

 defineAst(outputDir, "Expr", Arrays.asList(
    "Binary   : Expr left, Token operator, Expr right",
    "Grouping : Expr expression",
    "Literal  : Object value",
    "Unary    : Token operator, Expr right"
  ));

What this does is doing is creating 4 classes, and for each class is setting properties. We can do the same with a variant type!

open Scanner

type literal =
  | LiteralInt of int
  | LiteralString of string
  | LiteralBool of bool

type expr =
  | Binary of expr * Scanner.token * expr
  | Grouping of expr
  | Literal of literal option
  | Unary of Scanner.token * expr

Our tree contains nodes of many types. A binary node has a left and right expressions, and a token value. Our grouping is just an expression that we’ll handle by adding parentheses. A literal is either a None (representing the word “nil”) or Some int or string or boolean. Our unary is a token and an integer, where the token would be either ! or -.

With these few pieces in mind, we can move on to building our parser.