\section{Lexing \& parsing}\label{sec:pars}
\subsection{\Yard}
For both lexing and parsing we use a minimal parser combinator
library called \Yard. \Yard{} is inspired by the well-known \textsc{Parsec}
library. Where \Yard{} only has 7 primitive parser(s) (combinators)
\textsc{Parsec} already has 9 categories of parser combinators with numerous 
combinators in every category.

Parsers implemented in Yard parse left to right and are greedy, that is that
they always try to consume as much input as possible, starting from the left
most encountered token. \Yard's parsers also automatically apply backtracking,
when the left parser combined with \CI{<|>} fails, then any input it might have
consumed is restored and the right parser is executed. 

\begin{lstlisting}[language=Clean]
:: Error = PositionalError Int Int String | Error String
:: Parser a b = Parser ([a] -> (Either Error b, [a]))

(<?>) :: (Parser a b) Error -> Parser a b
fail :: Parser a b
top :: Parser a a
peek :: Parser a a
eof :: Parser a Void
pure :: b -> Parser a b
(>>=) :: (Parser a b) (b -> Parser a c) -> Parser a c
(<|>) :: (Parer a b) (Parser a b) -> Parser a b
--derived parser functions
satisfy :: (a -> Bool) -> Parser a a
check :: (a -> Bool) -> Parser a a
(until) infix 2 :: (Parser a b) (Parser a c) -> Parser a [b]
item :: a -> Parser a a | Eq a
list :: [a] -> Parser a [a] | Eq a
\end{lstlisting}

\subsection{Lexing \& Grammar}
The existing \SPL{} grammar was not suitable for parsing and lexing. The
grammar listed in Listing~\ref{lst:grammar} shows the current and final
grammar. The grammar for \SPLC{} has been extended to accommodate for the
syntactic sugar \SPLC{} introduces, such as string and list literals, and for
anonymous lambda functions. Moreover we have applied transformations on the
grammar including eliminating left recursion, fixing operator priority and
associativity.

To make the parsing easier we first lex the character input into tokens. In
this way the parser can be simplified a lot and some more complex constructs
can be lexed as one token such as literal characters.

As said, the lexer uses a \Yard{} parser. The parser takes a list of characters
and returns a list of \CI{Token}s. A token is a \CI{TokenValue} accompanied
with a position. An excerpt of the \emph{ADT} of tokens is shown in 
Listing~\ref{lst:lextoken}.
The used parser combinators make it very easy to account for arbitrary white 
space and in a much more elegant way manipulating the input as a list of
characters directly.
Listing~\ref{lst:lexerwhite} shows the way we handle white space and
recalculate positions. By choosing to lex with parser combinators the speed of
the phase decreases. However due to the simplicity of the lexer this is barely
measurable.

\begin{lstlisting}[
	language=Clean,
	label={lst:lexerwhite},
	caption={Lexer whitespace handling}]
lexProgram :: Int Int -> Parser Char [Token]
lexProgram line column = lexToken >>= \t->case t of
	LexEOF = pure []
	LexNL = lexProgram (line+1) 1
	(LexSpace l c) = lexProgram (line+l) (column+c)
	(LexItemError e) = fail <?>
		PositionalError line column ("LexerError: " +++ e)
	(LexToken c t) = lexProgram line (column+c)
		>>= \rest->pure [({line=line,col=column}, t):rest]
\end{lstlisting}

\begin{lstlisting}[
	language=Clean,
	label={lst:lextoken},
	caption={Lexer token ADT}]
:: Pos = {line :: Int, col :: Int}
:: Token :== (Pos, TokenValue)
:: TokenValue
	//Value tokens
	= IdentToken String
	| NumberToken Int
	| CharToken Char
	| StringToken [Char]
	//Keyword tokens
	| VarToken
	| ReturnToken
	| IfToken
	| ...
\end{lstlisting}

A lexer written with parser combinators is pretty straight forward and in
practice it is just a very long list of \texttt{alternative} monadic
combinators. However the order is very important since some tokens are so
greedy they might consume other tokens. Almost all tokens can be lexed trivially
with the \CI{list} combinator
for matching literal strings. Comments and literals are the only exception that
require a non trivial parser.

\subsection{Parsing}
The parsing phase is the second phase of the parser and is yet again a \Yard{}
parser that transforms a list of tokens to an \emph{Abstract Syntax
Tree} (\AST). The full abstract syntax tree is listed in Listing~\ref{lst:ast}
and closely resembles the grammar.

The parser uses the standard \Yard{} combinators. Due to the modularity of
combinators it was and is very easy to add functionality to the parser. The
parser also handles some syntactic sugar(Section~\ref{ssec:synsugar}). For
example the parser expands the literal lists and literal strings to the
according list or string representation. Moreover the parser transforms the let
expressions to real functions representing constant values.

As an example we show the parsing of a \CI{FunDecl} in
Listing~\ref{lst:fundecl}. The \CI{FunDecl} is one of the most complex parsers
and is composed of complex subparsers. A \CI{FunDecl} parser exactly one
complete function declaration.

First we do the non consuming \CI{peekPos} to get the position of the first 
token without consuming it, after that the identifier is parsed
which is basically a parser that transforms an \CI{IdToken} into a \CI{String}.

\CI{parseBBraces} is a parser combinator built from the basic combinators that
parses a parser when the contents are surrounded by braces. This is followed by
a yet another helper function to parse comma separated items.

Since the next element of the \ADT{} is a \CI{Maybe} the next parser is
combined with the optional combinator since the type of a function is optional
and when not given will be inferred later.

A function consists of \emph{many} \CI{VarDecl}s and then \emph{many}
\CI{Stmt}s. The word \emph{many} in \Yard{} means zero or more while the word
\emph{some} means one or more. Thus we allow a function to be empty. The reason
why \CI{flatten} is mapped on to the last argument of the \CI{liftM6} is
because the \CI{parseStmt} returns possibly multiple \CI{Stmt}s. This is
because in the parsing phase we expand the \CI{print} functions into multiple
instances and thus it can be the case that from one \CI{Stmt} we actually get
multiple.

\begin{lstlisting}[
	language=Clean,
	label={lst:fundecl},
	caption={Parsing a \CI{FunDecl}}]
:: FunDecl = FunDecl Pos String [String] (Maybe Type) [VarDecl] [Stmt]

parseFunDecl :: Parser Token FunDecl
parseFunDecl = liftM6 FunDecl
	(peekPos) //position of FunDecl
	(parseIdent) //function name
	(parseBBraces $ parseSepList CommaToken parseIdent) //list of arguments
	(optional (satTok DoubleColonToken *> parseFunType)) //optional type
	(satTok CBraceOpenToken *> many parseVarDecl) //list of VarDecls
	(flatten <$> (many parseStmt <* satTok CBraceCloseToken)) //list of Stmts
\end{lstlisting}

\subsection{Sugars} \label{ssec:synsugar}
Some syntactic sugars are processed in the lexing or parsing phase. Entering
literal lists and strings is a tedious job because you can only glue them
together with cons operators. Thus we introduced a literal lists notation as
visible in the grammar. Literal strings are lexed as single tokens and expanded
during parsing in to normal lists of characters. Literal lists are processed in
the parsing phase and expanded to their similar form with the \texttt{Cons}
operator. An example of this is shown in Listing~\ref{lst:litlist}

\begin{lstlisting}[
	language=SPLCode,
	caption={Literal lists},
	label={lst:litlist}]
//Before transformation
var a = "Hello world!";
var b = [3, 1, 4, 1, 5];

//After transformation
var a = 'H':'e':'l':'l':'o':' ':'w':'o':'r':'l':'d':'!':[]
var b = 3 : 1 : 4 : 1 : 5 : [];
\end{lstlisting}

Another sugar added is variable arguments printing. To enable the user to
pretty print data the number of arguments of the \SI{print} function is not
fixed and it is expanded at time of compilation. With this sugar the programmer
can print several different types in one line. Listing~\ref{lst:varprint} shows
an example of the sugar. In the semantic analysis phase these statements are
actually refined even more to represent the specific print function per type 
during the semantical analysis phase, since \SPLC{} allows printing of 
\SI{Int}, \SI{Bool}, \SI{Char} and \SI{[Char]}
\begin{lstlisting}[
	language=SPLCode,
	caption={Variable arguments printing},
	label={lst:varprint}]
//Before transformation
print("abc", 42, 'c', "da\n");

//After transformation
print('a':'b':'c':[]);
print(42);
print('c');
print('d':'a':'\n':[]);
\end{lstlisting}

The last sugar processed in the parsing phase are the \SI{let}
constructions. These provide an easy way of defining global
constants without real constants. While we do not allow global variables one
might want to introduce global constants and with these constructs this can be
done very easily. Listing~\ref{lst:letgl} shows the expansion of \SI{let}
declarations.
\begin{lstlisting}[
	language=SPLCode,
	caption={\SI{let} expansion},
	label={lst:letgl}]
//Before transformation
let Int x = 42;

//After transformation
x() :: -> Int{
	return 42;
}
\end{lstlisting}
