Crafting Interpreters in OCaml - Building our Context-Free Grammar
May 28, 2019
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
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
With these few pieces in mind, we can move on to building our parser.
I work and live in Brooklyn, NY building software.