Logic programming
on the BEAM
← All posts

Parser

design

Strategy

We parse the Karuta code using a hand-written recursive-descent parser. The implementation is based on a grammar written using the PEG formalism, but since we factor out some common structures into high-level helper functions we end up with a flavor of parser combinators. While some of those helper functions behave like PEG primitives, others are in fact syntactic sugar and should be thought of as a layer of macros on top of the base PEG semantics. As a side note, the entire parser is pedantic about proper tail-calls; we use OCaml's proper tail-calls in such a way that any parsing expression which would be in tail position in the grammar is in fact a tail-call in OCaml.

The parser is written in a monadic style: a parser is a function taking a parser state and returning either a parse result together with the next parser state, or an error. Applicative-style operators could be derived from the monadic ones, but we don't currently use this approach. 

type ('a, 'e) parser = parser_state -> ('a * parser_state, 'e) result

The full code of the parser is located in lib/Parser.ml.

Disclaimer

We recognize that our syntax errors are bad, i.e., our parser does not take into consideration the semantics of the language, which leads to frustrating error messages in most situations. For example, pretty much everything in our language is a functor (in the Prolog sense, not the ML sense), and we parse it as such. Any syntax error will therefore note take into account what you are trying to do.

We do intend to improve our error messages, but we have other priorities right now. Contributions on this front are welcome.

Types

Source Code Location

Karuta's compiler needs to keep track of source code locations for error reporting. Originally we were using the Lexing.position type from the standard library, but we recently switched to custom types instead. These are implemented in the Location module.

To begin with, the coordinate type is used to save the numerical coordinates for a source code position. 

type coordinate = {
  offset : int;
      (** Offset from the start of the file to the current position. *)
  line_offset : int;
      (** Offset from the start of the file to the start of the current line. *)
  line : int;  (** Line number. 1-based. *)
}
(** A coordinate in source code. It has no knowledge of which file it belongs
    to.

    It is possible to recover the column number by doing offset - line_offset.
*)

A coordinate can be combined with a filename to give us a point. A point allows us to identify a source position in some particular file. The parser state has one of these to keep track of where it is. 

type point = { filename : string; coordinate : coordinate }
(** This type represents a point in source code. It is isomorphic to
    Lexing.position, but with better names for the fields. *)

If we combine two coordinate~s instead of one, we get a ~region. A region has a beginning and an end, and is what we use to actually report errors. 

type region = {
  filename : string;  (** File name *)
  startl : coordinate;  (** Beginning of region *)
  endl : coordinate;  (** End of region *)
}
(** Source code location. Locations delimit a source code region. *)

We can attach a region to an arbitrary value using the with_location type constructor: 

type 'a with_location = {
  content : 'a;  (** Generic type payload *)
  loc : region;  (** Associated location, with a beginning and end. *)
}
(** Parametric type to add a location to any other type. Used to indicate the
    source code region where the payload originated. *)

Additionally, our parser uses several helper functions to manipulate the location more conveniently: 

let step n coordinate = { coordinate with offset = coordinate.offset + n }

let jump_n n coordinate =
  if n = 0 then coordinate
  else
    {
      coordinate with
      line_offset = coordinate.offset;
      line = coordinate.line + n;
    }

let plus_str str coordinate =
  coordinate
  |> step (String.length str)
  |> jump_n
       (String.fold_left (fun n -> function '\n' -> n + 1 | _ -> n) 0 str)

let delimit { filename; coordinate = startl } { coordinate = endl; _ } v =
  { content = v; loc = { filename; startl; endl } }

We elided the comments to save space; you can read them on the source code for more details.

Parsing

There are two main types used during parsing. Let's start with parser_state: 

type parser_state = { remaining : BatSubstring.t; loc : Location.point }

The type parser_state holds the bookkeeping required to parse source files. remaining is the portion of the source file that we haven't parsed yet, represented as a BatSubstring.t for constant-time slicing. loc is the the point in the file where the parser is currently sitting. 

type ('a, 'e) parser = parser_state -> ('a * parser_state, 'e) result

The type parser is a Monad. In particular, it can be seen as a composition of the state monad with the either/result monad.

We use a very straightforward recursive-descent strategy with no memoization. Most functions in the Parser module are either implementations of primitive PEG semantics, composition operators implementing our parser combinator strategy, or implementations of grammar clauses. Please refer to the grammar for the full specification of the language.

The entry point of the parser is the function Parser.parse, which corresponds in the grammar to the start symbol.

Parser Errors

By far, this is the weakest part of the compiler. Right now, we only have three possible errors in Parse.parse: 

type expr_errors =
  [ `ExpectedLowercase of Location.point
  | `UnexpectedEOF
  | `WrongPrefix of Location.point * string ]

Unfortunately, these errors are not very informative to users of the compiler.

ExpectedLowercase can occur when we hit an invalid top-level clause. In the grammar, we check for directives first and then try to parse a declaration, which must start with a functor. This is probably the lowest hanging fruit for improvement.

WrongPrefix can occur whenever we expect some particular token (usually punctuation, such as a period or comma) but get something else instead.

UnexpectedEOF is supposed to occur if there's a missing close delimiter (quote, bracket, or curly brace), but with the way the grammar is currently defined this is very unlikely.

Improving the situation here is in our TODO list.

Grammar

This is the complete formal grammar for the language. In the source code, you'll find the functions implementing each grammar clause commented with the corresponding clause, but you can read it here in one place. 

start <- top_level !.
top_level <- whitespace_and_comments (clause whitespace_and_comments)*

clause <-
  holds whitespace_and_comments directive
  / !holds func whitespace_and_comments
    (&(question_mark / comma) query /
     !(question_mark / comma) declaration)
    whitespace_and_comments

query <-
  question_mark
  / !question_mark whitespace_and_comments comma
    whitespace_and_comments func whitespace_and_comments query

declaration <- (holds whitespace_and_comments declaration_body)?
  whitespace_and_comments period

declaration_body <- func whitespace_and_comments
  (comma whitespace_and_comments declaration_body / !comma)

directive <- func
 (whitespace_and_comments
  left_curly_brace top_level right_curly_brace
  whitespace_and_comments)*
 period whitespace_and_comments

expr <- whitespace_and_comments
  (integer
   / !integer (variable
               / !variable (func
                            / !func list)))

func <- func_label
 ((&left_bracket / &left_paren) (prolog_elements / karuta_elements)
  / !(&left_bracket / &left_paren))

func_label <- (atom colon)* (quoted_atom / atom)

atom <- [a-z] ([a-zA-Z0-9] / '_' / '-')*
variable <- ('_' / [A-Z]) ([a-zA-Z0-9] / '_')*
quoted_atom <- "'" (!"'" !'\n' .)* "'"

integer <- '-'? [0-9]+

list <- left_bracket whitespace_and_comments
  (right_bracket
   / !right_bracket expr whitespace_and_comments list_tail)

list_tail <-
  comma whitespace_and_comments expr whitespace_and_comments list_tail
  / !comma (pipe whitespace_and_comments expr)? whitespace_and_comments right_bracket

single_element <- whitespace_and_comments expr

karuta_elements <- left_bracket
  (whitespace_and_comments right_bracket /
   !(whitespace_and_comments right_bracket single_element) karuta_elements_loop)

karuta_elements_loop <-
  whitespace_and_comments comma expr karuta_elements_loop
  / !(whitespace_and_comments comma expr)
    whitespace_and_comments right_bracket

prolog_elements <- left_paren
  (whitespace_and_comments right_paren /
   !(whitespace_and_comments right_paren) single_element prolog_elements_loop)

prolog_elements_loop <-
  whitespace_and_comments comma expr prolog_elements_loop
  / !(whitespace_and_comments comma expr)
    whitespace_and_comments right_paren

whitespace_and_comments <- whitespace
  (percent line whitespace_and_comments
   / !percent (hash percent expr whitespace_and_comments
               / !(hash percent)))

whitespace <- horizontal_whitespace? (newline whitespace / !newline)

newline <- '\n' / '\r\n'
line <- newline / (. line / !.)

horizontal_whitespace <- (' ' / '\t')+

colon <- ':'
percent <- '%'
hash <- '#'
single_quote <- "'"
comma <- ','
period <- '.'
pipe <- '|'
question_mark <- '?'
left_paren <- '('
right_paren <- ')'
left_bracket <- '['
right_bracket <- ']'
left_curly_brace <- '{'
right_curly_brace <- '}'
holds <- ':-'