Crafting Interpreters in OCaml - Starting the Parser

We’ll now be working on building our parser. Bob’s book walks through a recursive descent parser - a top-down parser than builds an abstract syntax tree from the outermost grammer rule all the way into nested subexpressions until we reach the end. We’ve already defined our expressions, and our Scanner has our token definitions so we’ll borrow that code to start the parser.

Taking a look at Bob’s parser class, we can see some stateful values. tokens - a list of tokens, and current - some integer. We can lean on our previous pattern of passing around a context object in our module to make this work. Let’s create a file called parser.ml

open Scanner

module Parser = struct

  type parser_context = {
    current: int;
    tokens: Scanner.token list
  }

end

Pretty straightforward - we simply hold all the tokens in a list, and point to the index of the one we’re currently parsing.

Looking ahead, we’re going to need to write some code for a few functions. We have equality, match, check, advance, isAtEnd, peek, previous and comparison. We want to make sure that every one of these functions in our implementation will take a context somewhere and return a context (alongside any other values in a tuple).

To flesh this out, let’s create an implementation file.

module Parser : sig
  type parser_context
  type expr
  type token_type
  type token

  val equality: expr -> parser_context -> expr * parser_context
  val match_types: token_type list -> parser_context -> bool * parser_context
  val check: token_type -> parser_context -> bool
  val advance: parser_context -> token * parser_context
  val is_at_end: parser_context -> bool
  val peek: parser_context -> token
  val previous: parser_context -> token
end

We’ll define some abstract types in the file and later import the ones we want in our actual module.