OCaml is a relatively popular functional-imperative language with a built-in object system. It has a great compiler which generates code with performance similar to the output of the best C compilers. It also boasts a rich collection of libraries and tools; among the latter one cam mention ocamllex and ocamlyacc (provided together with the compiler), assisting implementation of compilers and interpreters.

Thanks to those tools, a seemingly difficult task of development of a working interpreter of a programming language can be accomplished in just a few hours. What is more, the tools are so easy to use that even a person with no experience with them and not knowing OCaml itself can, after a short introduction, successfully get the job done.

The point of this article is to demonstrate that this is indeed possible. In its first part we will briefly present the aforementioned tools, in the second one we will make use of them to implement an interpreter of a simple programming language containing while loops, if instructions and assignments. Meanwhile we will be explaining programming constructs of OCaml and the usage of its compiler.

Figure 1. An example derivation tree in context-less grammar

Implementation of a Simple Lexer

According to what has been said in the Structure of Interpreters inset, we should begin implementing an interpreter by implementing a lexer. We can save a lot of time here by using the aforementioned ocamllex program, which generates the source code of a lexer basing on description of its token structure (programs which do this are often called lexer generators).

Listing 1. Definition of a simple lexer (an input file for ocamllex)

 
 
{
    type token_t =
          PLUS
        | MINUS
        | LPAREN
        | RPAREN
        | NUM of int
        | EOF
}
 
let digit = ['0'-'9']
 
rule tokenize = parse
  | '+'         { PLUS }
  | '-'         { MINUS }
  | '('         { LPAREN }
  | ')'         { RPAREN }
  | digit+ as num
                { NUM (int_of_string num) }
  | eof         { EOF }
  | [' ' 't'] { tokenize lexbuf }

An example input file for this tool has been provided as Listing 1. Its first part is the header, enclosed within the characters: { and }, which can be any OCaml code; it is placed in the beginning of the code of the generated lexer. The second part is a description of tokens; this is not OCaml code.

In our examples the following tokens are valid: the characters: +, -, ( and ), integer numbers and the end-of-file character (eof). This is reflected by the definition of the token_t type (placed in the header) which represents allowable values of tokens. This is a so-called algebraic type; objects of this type are created by using one of the constructors (the names of which are separated by | characters) and this is they only way of creating an object of such a type. Algebraic-type objects are immutable.