Very Simple F# Compiler

I have decided to try and implement a version of the Demo Compiler in Chapter 1 of Modern Compiler Design by Grune, Bal, Jacobs & Langendoen. To make it harder for myself I'd like to use as much functional code as possible and as little object oriented code. I want to try and change as little of the design as possible so I'll be taking their "narrow" compiler approach.

Let's start by defining the data structured used in the design.

The design in the book has two data structures, token and expression, which are both implemented as structs. To make the code more F#y these structures will be implemented as Discriminated Unions rather than the struct's direct equivalent the Record. This is because both of the structures had redundancy built into them as they both represent data that is could be in more than one mutually exclusive form. This is the kind of structure that Discriminated Unions are made for. This decision will also make our pattern matching code much simpler to write later on. I've also decided to add a further structure the operator which will allow me to keep character checking to a minimum outside of the lexing and parsing code.

Here are my data structures:

  1 type token =
  2     | Digit of char
  3     | Char of char
  4     | Eof
  5 
  6 type operator =
  7     | Add
  8     | Multiply
  9 
 10 type expression = 
 11     | DigitExpression of int
 12     | ParenthesizedExpression of expression * operator * expression