chx.tex

\chapter{The CHM Language Grammar}

This is the grammar for the CHM language. The meaning of all constructs define here is defined in chapter \ref{chap:compilerCHM} (\emph{CHM Compiler}).

\section{CHM headers}

Polymorphic functions and structures are constructed using special annotations (called CHM headers) following grammar:

\begin{lstlisting}
chm_header = '<' type_decls '>'
           | '<' type_decls ':' constraints '>'
           | '<' constraints '>'

type_decls = type_decl
           | type_decls ',' IDENT

constraints = constraint
            | constraints ',' constraint
constraint = new_type
           | predicate

new_type = IDENT '~' type
predicate = CLASS '<' type '>'

type = DECLARATOR
     | DECLARATOR ':' '<' types '>'
types = DECLARATOR
      | types ',' DECLARATOR
\end{lstlisting}

This is a simplified version of a piece of the actual grammar used in the implementation.

\begin{itemize}
    \item `IDENT' is a new identifier
    \item `CLASS' is the name of a type class
    \item `DECLARATOR' is a declarator from the C language (a type)
\end{itemize}

\section{Classes and Their Instances}

The other addition CHM brings to C are classes. They are defined (simplified version) as follows:

\begin{lstlisting}
class = chm_head 'class' IDENT '{' ext_decls '}'
      | chm_head 'class' IDENT < typevar > '{' ext_decls '}'

instance = 'instance' IDENT '<' type '>'
               '{' ext_decls '}'
           chm_head 'instance' IDENT '<' type '>'
               '{' ext_decls '}'
\end{lstlisting}

\lstinline{ext_decls} are declarations and definitions which would be legal in the global scope. However, it is not allowed to put declarations in instances, and all their definitions have to be first declared in the matching classes.

\section{Polymorphic Functions and Structures}

Polymorphic Functions and Structures are defined as regular C constructs preceded by \emph{CHM headers}:

\begin{lstlisting}
CHM_function_definition  = chm_header function_definition
CHM_function_declaration = chm_header function_declaration
CHM_struct_definition    = chm_header struct_definition
\end{lstlisting}

We omit \textbf{unions} as a lot of grammars (including ours) consider them syntactically equivalent to structs.