% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
\usepackage{../grammar}
\usepackage{../graphics}

\begin{document}

\section*{Handout 6 (Parser Combinators)}

This handout explains how \emph{parser combinators} work and how they
can be implemented in Scala. Their most distinguishing feature is that
they are very easy to implement (admittedly it is only easy in a
functional programming language).  Another good point of parser
combinators is that they can deal with any kind of input as long as
this input is of ``sequence-kind'', for example a string or a list of
tokens. The only two properties of the input we need is to be able to
test when it is empty and ``sequentially'' take it apart. Strings and
lists fit this bill. However, parser combinators also have their
drawbacks. For example they require that the grammar to be parsed is
\emph{not} left-recursive and they are efficient only when the grammar
is unambiguous. It is the responsibility of the grammar designer to
ensure these two properties hold.

The general idea behind parser combinators is to transform the input
into sets of pairs, like so

\begin{center}
$\underbrace{\text{list of tokens}}_{\text{input}}$ 
$\quad\Rightarrow\quad$
$\underbrace{\text{set of (parsed part, unprocessed part)}}_{\text{output}}$
\end{center} 

\noindent
Given the extended effort we have spent implementing a lexer in order
to generate lists of tokens, it might be surprising that in what
follows we shall often use strings as input, rather than lists of
tokens. This is for making the explanation more lucid and for quick
examples. It does not make our previous work on lexers obsolete
(remember they transform a string into a list of tokens). Lexers will
still be needed for building a somewhat realistic compiler.

As mentioned above, parser combinators are relatively agnostic about what
kind of input they process. In my Scala code I use the following
polymorphic types for parser combinators:

\begin{center}
input:\;\; \texttt{I}  \qquad output:\;\; \texttt{T}
\end{center}

\noindent That is they take as input something of type \texttt{I} and
return a set of pairs of type \texttt{Set[(T, I)]}. Since the input
needs to be of ``sequence-kind'', I actually have to often write
\texttt{I <\% Seq[\_]} for the input type. This ensures the
input is a subtype of Scala sequences. The first component of the
generated pairs corresponds to what the parser combinator was able to
parse from the input and the second is the unprocessed, or
leftover, part of the input (therefore the type of this unprocessed part is
the same as the input). A parser combinator might return more than one
such pair; the idea is that there are potentially several ways of how
to parse the input.  As a concrete example, consider the string

\begin{center}
\tt\Grid{iffoo\VS testbar}
\end{center}

\noindent We might have a parser combinator which tries to
interpret this string as a keyword (\texttt{if}) or as an
identifier (\texttt{iffoo}). Then the output will be the set

\begin{center}
$\left\{ \left(\texttt{\Grid{if}}\;,\; \texttt{\Grid{foo\VS testbar}}\right), 
           \left(\texttt{\Grid{iffoo}}\;,\; \texttt{\Grid{\VS testbar}}\right) \right\}$
\end{center}

\noindent where the first pair means the parser could recognise
\texttt{if} from the input and leaves the \texttt{foo\VS testbar} as
unprocessed part; in the other case it could recognise
\texttt{iffoo} and leaves \texttt{\VS testbar} as unprocessed. If the
parser cannot recognise anything from the input at all, then parser
combinators just return the empty set $\{\}$. This will indicate
something ``went wrong''\ldots or more precisely, nothing could be
parsed.

Also important to note is that the output type \texttt{T} for the
processed part can potentially be different from the input type
\texttt{I} in the parser. In the example above is just happens to be
the same. The reason for the difference is that in general we are
interested in transforming our input into something
``different''\ldots for example into a tree; or if we implement the
grammar for arithmetic expressions, we might be interested in the
actual integer number the arithmetic expression, say \texttt{1 + 2 *
  3}, stands for. In this way we can use parser combinators to
implement relatively easily a calculator, for instance (we shall do
this later on).

The main driving force behind parser combinators is that we can easily
build parser combinators out of smaller components following very
closely the structure of a grammar. In order to implement this in a
functional/object-oriented programming language, like Scala, we need
to specify an abstract class for parser combinators. In the abstract
class we specify that \texttt{I} is the \emph{input type} of the
parser combinator and that \texttt{T} is the \emph{output type}.  This
implies that the function \texttt{parse} takes an argument of type
\texttt{I} and returns a set of type \mbox{\texttt{Set[(T, I)]}}.

\begin{center}
\begin{lstlisting}[language=Scala]
abstract class Parser[I, T] {
  def parse(in: I) : Set[(T, I)]

  def parse_all(in: I) : Set[T] =
    for ((head, tail) <- parse(in); if (tail.isEmpty)) 
      yield head
}
\end{lstlisting}
\end{center}

\noindent It is the obligation in each instance of this class to
supply an implementation for \texttt{parse}.  From this function we
can then ``centrally'' derive the function \texttt{parse\_all}, which
just filters out all pairs whose second component is not empty (that
is has still some unprocessed part). The reason is that at the end of
the parsing we are only interested in the results where all the input
has been consumed and no unprocessed part is left over.

One of the simplest parser combinators recognises just a
single character, say $c$, from the beginning of strings. Its
behaviour can be described as follows:

\begin{itemize}
\item If the head of the input string starts with a $c$, then return 
  the set
  \[\{(c, \textit{tail of}\; s)\}\]
  where \textit{tail of} 
  $s$ is the unprocessed part of the input string.
\item Otherwise return the empty set $\{\}$.	
\end{itemize}

\noindent
The input type of this simple parser combinator is \texttt{String} and
the output type is \texttt{Char}. This means \texttt{parse} returns
\mbox{\texttt{Set[(Char, String)]}}.  The code in Scala is as follows:

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
case class CharParser(c: Char) extends Parser[String, Char] {
  def parse(in: String) = 
    if (in.head == c) Set((c, in.tail)) else Set()
}
\end{lstlisting}
\end{center}

\noindent You can see \texttt{parse} tests whether the
first character of the input string \texttt{in} is equal to
\texttt{c}. If yes, then it splits the string into the recognised part
\texttt{c} and the unprocessed part \texttt{in.tail}. In case
\texttt{in} does not start with \texttt{c} then the parser returns the
empty set (in Scala \texttt{Set()}). Since this parser recognises
characters and just returns characters as the processed part, the
output type of the parser is \texttt{Char}.

If we want to parse a list of tokens and interested in recognising a
number token, for example, we could write something like this

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily,numbers=none]
case object NumParser extends Parser[List[Token], Int] {
  def parse(ts: List[Token]) = ts match {
    case Num_token(s)::ts => Set((s.toInt, ts)) 
    case _ => Set ()
  }
}
\end{lstlisting}
\end{center}

\noindent
In this parser the input is of type \texttt{List[Token]}. The function
parse looks at the input \texttt{ts} and checks whether the first
token is a \texttt{Num\_token} (let us assume our lexer generated
these tokens for numbers). But this parser does not just return this
token (and the rest of the list), like the \texttt{CharParser} above,
rather it extracts also the string \texttt{s} from the token and
converts it into an integer. The hope is that the lexer did its work
well and this conversion always succeeds. The consequence of this is
that the output type for this parser is \texttt{Int}, not
\texttt{Token}. Such a conversion would be needed if we want to
implement a simple calculator program, because string-numbers need to
be transformed into \texttt{Int}-numbers in order to do the
calculations.


These simple parsers that just look at the input and do a simple
transformation are often called \emph{atomic} parser combinators.
More interesting are the parser combinators that build larger parsers
out of smaller component parsers. There are three such parser
combinators that can be implemented generically. The \emph{alternative
  parser combinator} is as follows: given two parsers, say, $p$ and
$q$, we apply both parsers to the input (remember parsers are
functions) and combine the output (remember they are sets of pairs):
 
\begin{center}
$p(\text{input}) \cup q(\text{input})$
\end{center}

\noindent In Scala we can implement alternative parser
combinator as follows

\begin{center}
\begin{lstlisting}[language=Scala, numbers=none]
class AltParser[I, T]
       (p: => Parser[I, T], 
        q: => Parser[I, T]) extends Parser[I, T] {
  def parse(in: I) = p.parse(in) ++ q.parse(in)
}
\end{lstlisting}
\end{center}

\noindent The types of this parser combinator are again generic (we
have \texttt{I} for the input type, and \texttt{T} for the output
type). The alternative parser builds a new parser out of two existing
parsers \texttt{p} and \texttt{q} which are given as arguments.  Both
parsers need to be able to process input of type \texttt{I} and return
in \texttt{parse} the same output type \texttt{Set[(T,
  I)]}.\footnote{There is an interesting detail of Scala, namely the
  \texttt{=>} in front of the types of \texttt{p} and \texttt{q}. They
  will prevent the evaluation of the arguments before they are
  used. This is often called \emph{lazy evaluation} of the
  arguments. We will explain this later.}  The alternative parser runs
the input with the first parser \texttt{p} (producing a set of pairs)
and then runs the same input with \texttt{q} (producing another set of
pairs).  The result should be then just the union of both sets, which
is the operation \texttt{++} in Scala.

The alternative parser combinator allows us to construct a parser that
parses either a character \texttt{a} or \texttt{b} using the
\texttt{CharParser} shown above. For this we can write

\begin{center}
\begin{lstlisting}[language=Scala, numbers=none]
new AltParser(CharParser('a'), CharParser('b'))
\end{lstlisting}
\end{center}

\noindent Later on we will use Scala mechanism for introducing some
more readable shorthand notation for this, like \texttt{p"a" ||
  p"b"}. Let us look in detail at what this parser combinator produces
with some sample strings.

\begin{center}
\begin{tabular}{rcl}
input strings & & output\medskip\\
\texttt{\Grid{acde}} & $\rightarrow$ & $\left\{(\texttt{\Grid{a}}, \texttt{\Grid{cde}})\right\}$\\
\texttt{\Grid{bcde}} & $\rightarrow$ & $\left\{(\texttt{\Grid{b}}, \texttt{\Grid{cde}})\right\}$\\
\texttt{\Grid{ccde}} & $\rightarrow$ & $\{\}$
\end{tabular}
\end{center}

\noindent We receive in the first two cases a successful
output (that is a non-empty set). In each case, either
\pcode{a} or \pcode{b} is in the parsed part, and
\pcode{cde} in the unprocessed part. Clearly this parser cannot
parse anything with \pcode{ccde}, therefore the empty
set is returned.

A bit more interesting is the \emph{sequence parser combinator}. Given
two parsers, say again, $p$ and $q$, we want to apply first the input
to $p$ producing a set of pairs; then apply $q$ to all the unparsed  
parts in the pairs; and then combine the results. Mathematically we would
write something like this for the set of pairs:

\begin{center}
\begin{tabular}{lcl}
$\{((\textit{output}_1, \textit{output}_2), u_2)$ & $\,|\,$ & 
$(\textit{output}_1, u_1) \in p(\text{input}) 
\;\wedge\;$\\
&& $(\textit{output}_2, u_2) \in q(u_1)\}$
\end{tabular}
\end{center}

\noindent Notice that the $p$ will first be run on the input,
producing pairs of the form $(\textit{output}_1, u_1)$ where the $u_1$
stands for the unprocessed, or leftover, parts of $p$. We want that
$q$ runs on all these unprocessed parts $u_1$. Therefore these
unprocessed parts are fed into the second parser $q$. The overall
result of the sequence parser combinator is pairs of the form
$((\textit{output}_1, \textit{output}_2), u_2)$. This means the
unprocessed part of the sequence parser combinator is the unprocessed
part the second parser $q$ leaves as leftover. The parsed parts of the
component parsers are combined in a pair, namely
$(\textit{output}_1, \textit{output}_2)$. The reason is we want to
know what $p$ and $q$ were able to parse. This behaviour can be
implemented in Scala as follows:

\begin{center}
\begin{lstlisting}[language=Scala,numbers=none]
class SeqParser[I, T, S]
       (p: => Parser[I, T], 
        q: => Parser[I, S]) extends Parser[I, (T, S)] {
  def parse(in: I) = 
    for ((output1, u1) <- p.parse(in); 
         (output2, u2) <- q.parse(u1)) 
            yield ((output1, output2), u2)
}
\end{lstlisting}
\end{center}

\noindent This parser takes again as arguments two parsers, \texttt{p}
and \texttt{q}. It implements \texttt{parse} as follows: first run the
parser \texttt{p} on the input producing a set of pairs
(\texttt{output1}, \texttt{u1}). The \texttt{u1} stands for the
unprocessed parts left over by \texttt{p} (recall that there can be
several such pairs). Let then \texttt{q} run on these unprocessed
parts producing again a set of pairs. The output of the sequence
parser combinator is then a set containing pairs where the first
components are again pairs, namely what the first parser could parse
together with what the second parser could parse; the second component
is the unprocessed part left over after running the second parser
\texttt{q}. Note that the input type of the sequence parser combinator
is as usual \texttt{I}, but the output type is

\begin{center}
\texttt{(T, S)}
\end{center}

\noindent
Consequently, the function \texttt{parse} in the sequence parser
combinator returns sets of type \texttt{Set[((T, S), I)]}.  That means
we have essentially two output types for the sequence parser
combinator (packaged in a pair), because in general \textit{p} and
\textit{q} might produce different things (for example we recognise a
number with \texttt{p} and then with \texttt{q} a string corresponding
to an operator).  If any of the runs of \textit{p} and \textit{q}
fail, that is produce the empty set, then \texttt{parse} will also
produce the empty set.

With the shorthand notation we shall introduce later for the sequence
parser combinator, we can write for example \pcode{p"a" ~ p"b"}, which
is the parser combinator that first recognises the character
\texttt{a} from a string and then \texttt{b}. Let us look again at
some examples of how this parser combinator processes some strings:

\begin{center}
\begin{tabular}{rcl}
input strings & & output\medskip\\
\texttt{\Grid{abcde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{b}}), \texttt{\Grid{cde}})\right\}$\\
\texttt{\Grid{bacde}} & $\rightarrow$ & $\{\}$\\
\texttt{\Grid{cccde}} & $\rightarrow$ & $\{\}$
\end{tabular}
\end{center}

\noindent In the first line we have a successful parse, because the
string starts with \texttt{ab}, which is the prefix we are looking
for. But since the parsing combinator is constructed as sequence of
the two simple (atomic) parsers for \texttt{a} and \texttt{b}, the
result is a nested pair of the form \texttt{((a, b), cde)}. It is
\emph{not} a simple pair \texttt{(ab, cde)} as one might erroneously
expect.  The parser returns the empty set in the other examples,
because they do not fit with what the parser is supposed to parse.


A slightly more complicated parser is \pcode{(p"a" || p"b") ~ p"c"} which
parses as first character either an \texttt{a} or \texttt{b}, followed
by a \texttt{c}. This parser produces the following outputs.

\begin{center}
\begin{tabular}{rcl}
input strings & & output\medskip\\
\texttt{\Grid{acde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{c}}), \texttt{\Grid{de}})\right\}$\\
\texttt{\Grid{bcde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{b}}, \texttt{\Grid{c}}), \texttt{\Grid{de}})\right\}$\\
\texttt{\Grid{abde}} & $\rightarrow$ & $\{\}$
\end{tabular}
\end{center}

\noindent
Now consider the parser \pcode{(p"a" ~ p"b") ~ p"c"} which parses
\texttt{a}, \texttt{b}, \texttt{c} in sequence. This parser produces
the following outputs.

\begin{center}
\begin{tabular}{rcl}
input strings & & output\medskip\\
\texttt{\Grid{abcde}} & $\rightarrow$ & $\left\{(((\texttt{\Grid{a}},\texttt{\Grid{b}}), \texttt{\Grid{c}}), \texttt{\Grid{de}})\right\}$\\
\texttt{\Grid{abde}} & $\rightarrow$ & $\{\}$\\
\texttt{\Grid{bcde}} & $\rightarrow$ & $\{\}$
\end{tabular}
\end{center}


\noindent The second and third example fail, because something is
``missing'' in the sequence we are looking for. The first succeeds but
notice how the results nest with sequences: the parsed part is a
nested pair of the form \pcode{((a, b), c)}. If we nest the sequence
parser differently, say \pcode{p"a" ~ (p"b" ~ p"c")}, then also
our output pairs nest differently

\begin{center}
\begin{tabular}{rcl}
input strings & & output\medskip\\
\texttt{\Grid{abcde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}},(\texttt{\Grid{b}}, \texttt{\Grid{c}})), \texttt{\Grid{de}})\right\}$\\
\end{tabular}
\end{center}

\noindent
Two more examples: first consider the parser
\pcode{(p"a" ~ p"a") ~ p"a"} and the input \pcode{aaaa}:

\begin{center}
\begin{tabular}{rcl}
input string & & output\medskip\\
\texttt{\Grid{aaaa}} & $\rightarrow$ & 
$\left\{(((\texttt{\Grid{a}}, \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{\Grid{a}})\right\}$\\
\end{tabular}
\end{center}

\noindent Notice again how the results nest deeper and deeper as pairs (the
last \pcode{a} is in the unprocessed part). To consume everything of
this string we can use the parser \pcode{((p"a" ~ p"a") ~ p"a") ~
  p"a"}. Then the output is as follows:

\begin{center}
\begin{tabular}{rcl}
input string & & output\medskip\\
\texttt{\Grid{aaaa}} & $\rightarrow$ & 
$\left\{((((\texttt{\Grid{a}}, \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{""})\right\}$\\
\end{tabular}
\end{center}

\noindent This is an instance where the parser consumed
completely the input, meaning the unprocessed part is just the
empty string. So if we called \pcode{parse_all}, instead of \pcode{parse},
we would get back the result

\[
\left\{(((\texttt{\Grid{a}}, \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{\Grid{a}})\right\}
\]

\noindent where the unprocessed (empty) parts have been stripped away
from the pairs; everything where the second part was not empty has
been thrown away as well, because they represent
ultimately-unsuccessful-parses. The main point is that the sequence
parser combinator returns pairs that can nest according to the
nesting of the component parsers.


Consider also carefully that constructing a parser such \pcode{p"a" ||
  (p"a" ~ p"b")} will result in a typing error. The intention with this
parser is that we want to parse either an \texttt{a}, or an \texttt{a}
followed by a \texttt{b}. However, the first parser has as output type
a single character (recall the type of \texttt{CharParser}), but the
second parser produces a pair of characters as output. The alternative
parser is required to have both component parsers to have the same
type---the reason is that we need to be able to build the union of two
sets, which requires in Scala that the sets have the same type.  Since
they are not in this case, there is a typing error.  We will see later
how we can build this parser without the typing error.

The next parser combinator, called \emph{semantic action}, does not
actually combine two smaller parsers, but applies a function to the result
of a parser.  It is implemented in Scala as follows

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
class MapParser[I, T, S]
         (p: => Parser[I, T], 
          f: T => S) extends Parser[I, S] {
  def parse(in: I) = 
    for ((head, tail) <- p.parse(in)) yield (f(head), tail)
}
\end{lstlisting}
\end{center}


\noindent This parser combinator takes a parser \texttt{p} (with input
type \texttt{I} and output type \texttt{T}) as one argument but also a
function \texttt{f} (with type \texttt{T => S}). The parser \texttt{p}
produces sets of type \texttt{Set[(T, I)]}. The semantic action
combinator then applies the function \texttt{f} to all the `processed'
parser outputs. Since this function is of type \texttt{T => S}, we
obtain a parser with output type \texttt{S}. Again Scala lets us
introduce some shorthand notation for this parser
combinator. Therefore we will write short \texttt{p.map(f)} for it.

What are semantic actions good for? Well, they allow you to transform
the parsed input into datastructures you can use for further
processing. A simple (contrived) example would be to transform parsed
characters into ASCII numbers. Suppose we define a function \texttt{f}
(from characters to \texttt{Int}s) and use a \texttt{CharParser} for parsing
the character \texttt{c}.


\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
val f = (c: Char) => c.toInt
val c = new CharParser('c')
\end{lstlisting}
\end{center}

\noindent
We then can run the following two parsers on the input \texttt{cbd}:

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
c.parse("cbd")
c.map(f).parse("cbd")
\end{lstlisting}
\end{center}

\noindent
In the first line we obtain the expected result \texttt{Set(('c',
  "bd"))}, whereas the second produces \texttt{Set((99, "bd"))}---the
character has been transformed into an ASCII number.

A slightly less contrived example is about parsing numbers (recall
\texttt{NumParser} above). However, we want to do this here for
strings, not for tokens.  For this assume we have the following
(atomic) \texttt{RegexParser}.

\begin{center}
  \begin{lstlisting}[language=Scala,xleftmargin=0mm,
    basicstyle=\small\ttfamily, numbers=none]
import scala.util.matching.Regex
    
case class RegexParser(reg: Regex) extends Parser[String, String] {
  def parse(in: String) = reg.findPrefixMatchOf(in) match {
    case None => Set()
    case Some(m) => Set((m.matched, m.after.toString))  
  }
}
\end{lstlisting}
\end{center}

\noindent
This parser takes a regex as argument and splits up a string into a
prefix and the rest according to this regex
(\texttt{reg.findPrefixMatchOf} generates a match---in the successful
case---and the corresponding strings can be extracted with
\texttt{matched} and \texttt{after}). The input and output type for
this parser is \texttt{String}. Using \texttt{RegexParser} we can
define a \texttt{NumParser} for \texttt{Strings} to \texttt{Int} as
follows:

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
val NumParser = RegexParser("[0-9]+".r)
\end{lstlisting}
\end{center}

\noindent
This parser will recognise a number at the beginning of a string. For
example

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
NumParser.parse("123abc")
\end{lstlisting}
\end{center}  

\noindent
produces \texttt{Set((123,abc))}. The problem is that \texttt{123} is
still a string (the required double-quotes are not printed by
Scala). We want to convert this string into the corresponding
\texttt{Int}. We can do this as follows using a semantic action

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
NumParser.map{s => s.toInt}.parse("123abc")
\end{lstlisting}
\end{center}  

\noindent
The function in the semantic action converts a string into an
\texttt{Int}. Now \texttt{parse} generates \texttt{Set((123,abc))},
but this time \texttt{123} is an \texttt{Int}. Let us come back to
semantic actions when we are going to implement actual context-free
grammars.

\subsubsection*{Shorthand notation for parser combinators}

Before we proceed, let us just explain the shorthand notation for
parser combinators. Like for regular expressions, the shorthand notation
will make our life much easier when writing actual parsers. We can define
some implicits which allow us to write

\begin{center}
\begin{tabular}{ll}  
  \pcode{p || q} & alternative parser\\
  \pcode{p ~ q} & sequence parser\\ 
  \pcode{p.map(f)} & semantic action parser
\end{tabular}
\end{center}

\noindent
as well as to use string interpolations for specifying simple string parsers.

The idea is that this shorthand notation allows us to easily translate
context-free grammars into code. For example recall our context-free
grammar for palindromes:

\begin{plstx}[margin=3cm]
: \meta{Pal} ::=  a\cdot \meta{Pal}\cdot a | b\cdot \meta{Pal}\cdot b | a | b | \epsilon\\
\end{plstx}

\noindent
Each alternative in this grammar translates into an alternative parser
combinator.  The $\cdot$ can be translated to a sequence parser
combinator. The parsers for $a$, $b$ and $\epsilon$ can be simply
written as \texttt{p"a"}, \texttt{p"b"} and \texttt{p""}.


\subsubsection*{How to build parsers using parser combinators?}

The beauty of parser combinators is the ease with which they can be
implemented and how easy it is to translate context-free grammars into
code (though the grammars need to be non-left-recursive). To
demonstrate this consider again the grammar for palindromes from above.
The first idea would be to translate it into the following code

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
lazy val Pal : Parser[String, String] = 
  ((p"a" ~ Pal ~ p"a") || (p"b" ~ Pal ~ p"b") || p"a" || p"b" || p"")
\end{lstlisting}
\end{center}

\noindent
Unfortunately, this does not quite work yet as it produces a typing
error. The reason is that the parsers \texttt{p"a"}, \texttt{p"b"} and
\texttt{p""} all produce strings as output type and therefore can be
put into an alternative \texttt{...|| p"a" || p"b" || p""}. But both
sequence parsers \pcode{p"a" ~ Pal ~ p"a"} and \pcode{p"b" ~ Pal ~ p"b"}
produce pairs of the form

\begin{center}
(((\texttt{a}-part, \texttt{Pal}-part), \texttt{a}-part), unprocessed part)
\end{center}

\noindent That is how the
sequence parser combinator nests results when \pcode{\~} is used
between two components. The solution is to use a semantic action that
``flattens'' these pairs and appends the corresponding strings, like

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
lazy val Pal : Parser[String, String] =  
  ((p"a" ~ Pal ~ p"a").map{ case ((x, y), z) => x + y + z } ||
   (p"b" ~ Pal ~ p"b").map{ case ((x, y), z) => x + y + z } ||
    p"a" || p"b" || p"")
\end{lstlisting}
\end{center}

\noindent
How does this work? Well, recall again what the pairs look like for
the parser \pcode{p"a" ~ Pal ~ p"a"}.  The pattern in the semantic
action matches the nested pairs (the \texttt{x} with the
\texttt{a}-part and so on).  Unfortunately when we have such nested
pairs, Scala requires us to define the function using the
\pcode{case}-syntax

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
{ case ((x, y), z) => ... }
\end{lstlisting}
\end{center}

\noindent
If we have more sequence parser combinators or have them differently nested,
then the pattern in the semantic action needs to be adjusted accordingly.
The action we implement above is to concatenate all three strings, which
means after the semantic action is applied the output type of the parser 
is \texttt{String}, which means it fits with the alternative parsers
\texttt{...|| p"a" || p"b" || p""}.

If we run the parser above with \pcode{Pal.parse_all("abaaaba")} we obtain
as result the \pcode{Set(abaaaba)}, which indicates that the string is a palindrome
(an empty set would mean something is wrong). But also notice what the
intermediate results are generated by \pcode{Pal.parse("abaaaba")}

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
Set((abaaaba,""),(aba,aaba), (a,baaaba), ("",abaaaba))
\end{lstlisting}
\end{center}

\noindent
That there are more than one output might be slightly unexpected, but
can be explained as follows: the pairs represent all possible
(partial) parses of the string \pcode{"abaaaba"}. The first pair above
corresponds to a complete parse (all output is consumed) and this is
what \pcode{Pal.parse_all} returns. The second pair is a small
``sub-palindrome'' that can also be parsed, but the parse fails with
the rest \pcode{aaba}, which is therefore left as unprocessed. The
third one is an attempt to parse the whole string with the
single-character parser \pcode{a}. That of course only partially
succeeds, by leaving \pcode{"baaaba"} as the unprocessed
part. Finally, since we allow the empty string to be a palindrome we
also obtain the last pair, where actually nothing is consumed from the
input string. While all this works as intended, we need to be careful
with this (especially with including the \pcode{""} parser in our
grammar): if during parsing the set of parsing attempts gets too big,
then the parsing process can become very slow as the potential
candidates for applying rules can snowball.


Important is also to note is that we must define the
\texttt{Pal}-parser as a \emph{lazy} value in Scala. Look again at the
code: \texttt{Pal} occurs on the right-hand side of the definition. If we had
just written

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
val Pal : Parser[String, String] =  ...rhs...
\end{lstlisting}
\end{center}

\noindent
then Scala before making this assignment to \texttt{Pal} attempts to
find out what the expression on the right-hand side evaluates to. This
is straightforward in case of simple expressions \texttt{2 + 3}, but
the expression above contains \texttt{Pal} in the right-hand
side. Without \pcode{lazy} it would try to evaluate what \texttt{Pal}
evaluates to and start a new recursion, which means it falls into an
infinite loop. The definition of \texttt{Pal} is recursive and the
\pcode{lazy} key-word prevents it from being fully evaluated. Therefore
whenever we want to define a recursive parser we have to write

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
lazy val SomeParser : Parser[...,...] =  ...rhs...
\end{lstlisting}
\end{center}

\noindent That was not necessary for our atomic parsers, like
\texttt{RegexParser} or \texttt{CharParser}, because they are not recursive.
Note that this is also the reason why we had to write

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
class AltParser[I, T]
       (p: => Parser[I, T], 
        q: => Parser[I, T]) extends Parser[I, T] {...}

class SeqParser[I, T, S]
       (p: => Parser[I, T], 
        q: => Parser[I, S]) extends Parser[I, (T, S)] {...}
\end{lstlisting}
\end{center}

\noindent where the \texttt{\textbf{\textcolor{codepurple}{=>}}} in front of
the argument types for \texttt{p} and \texttt{q} prevent Scala from
evaluating the arguments. Normally, Scala would first evaluate what
kind of parsers \texttt{p} and \texttt{q} are, and only then generate
the alternative parser combinator, respectively sequence parser
combinator. Since the arguments can be recursive parsers, such as
\texttt{Pal}, this would lead again to an infinite loop.

As a final example in this section, let us consider the grammar for
well-nested parentheses:

\begin{plstx}[margin=3cm]
: \meta{P} ::=  (\cdot \meta{P}\cdot ) \cdot \meta{P} | \epsilon\\
\end{plstx}

\noindent
Let us assume we want to not just recognise strings of
well-nested parentheses but also transform round parentheses
into curly braces. We can do this by using a semantic
action:

\begin{center}
  \begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily,
    xleftmargin=0mm, numbers=none]
lazy val P : Parser[String, String] = 
  (p"(" ~ P ~ p")" ~ P).map{ case (((_,x),_),y) => "{" + x + "}" + y } || p""
\end{lstlisting}
\end{center}

\noindent
Here we define a function where which ignores the parentheses in the
pairs, but replaces them in the right places with curly braces when
assembling the new string in the right-hand side. If we run
\pcode{P.parse_all("(((()()))())")} we obtain
\texttt{Set(\{\{\{\{\}\{\}\}\}\{\}\})} as expected.



\subsubsection*{Implementing an Interpreter}

The first step before implementing an interpreter for a full-blown
language is to implement a simple calculator for arithmetic
expressions. Suppose our arithmetic expressions are given by the
grammar:

\begin{plstx}[margin=3cm,one per line]
: \meta{E} ::= \meta{E} \cdot + \cdot \meta{E} 
   | \meta{E} \cdot - \cdot \meta{E} 
   | \meta{E} \cdot * \cdot \meta{E} 
   | ( \cdot \meta{E} \cdot )
   | Number \\
\end{plstx}

\noindent
Naturally we want to implement the grammar in such a way that we can
calculate what the result of, for example, \texttt{4*2+3} is---we are
interested in an \texttt{Int} rather than a string. This means every
component parser needs to have as output type \texttt{Int} and when we
assemble the intermediate results, strings like \texttt{"+"},
\texttt{"*"} and so on, need to be translated into the appropriate
Scala operation of adding, multiplying and so on.  Being inspired by
the parser for well-nested parentheses above and ignoring the fact
that we want $*$ to take precedence over $+$ and $-$, we might want to
write something like

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
lazy val E: Parser[String, Int] = 
  ((E ~ p"+" ~ E).map{ case ((x, y), z) => x + z} ||
   (E ~ p"-" ~ E).map{ case ((x, y), z) => x - z} ||
   (E ~ p"*" ~ E).map{ case ((x, y), z) => x * z} ||
   (p"(" ~ E ~ p")").map{ case ((x, y), z) => y} ||
   NumParserInt)
\end{lstlisting}
\end{center}

\noindent
Consider again carefully how the semantic actions pick out the correct
arguments for the calculation. In case of plus, we need \texttt{x} and
\texttt{z}, because they correspond to the results of the component
parser \texttt{E}. We can just add \texttt{x + z} in order to obtain
an \texttt{Int} because the output type of \texttt{E} is
\texttt{Int}.  Similarly with subtraction and multiplication. In
contrast in the fourth clause we need to return \texttt{y}, because it
is the result enclosed inside the parentheses. The information about
parentheses, roughly speaking, we just throw away.

So far so good. The problem arises when we try to call \pcode{parse_all} with the
expression \texttt{"1+2+3"}. Lets try it

\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
E.parse_all("1+2+3")
\end{lstlisting}
\end{center}

\noindent
\ldots and we wait and wait and \ldots still wait. What is the
problem? Actually, the parser just fell into an infinite loop! The
reason is that the above grammar is left-recursive and recall that our
parser combinators cannot deal with such left-recursive
grammars. Fortunately, every left-recursive context-free grammar can be
transformed into a non-left-recursive grammars that still recognises
the same strings. This allows us to design the following grammar

\begin{plstx}[margin=3cm]
  : \meta{E} ::=  \meta{T} \cdot + \cdot \meta{E} |  \meta{T} \cdot - \cdot \meta{E} | \meta{T}\\
: \meta{T} ::=  \meta{F} \cdot * \cdot \meta{T} | \meta{F}\\
: \meta{F} ::= ( \cdot \meta{E} \cdot ) | Number\\
\end{plstx}

\noindent
Recall what left-recursive means from Handout 5 and make sure you see
why this grammar is \emph{non} left-recursive. This version of the grammar
also deals with the fact that $*$ should have a higher precedence. This does not
affect which strings this grammar can recognise, but in which order we are going
to evaluate any arithmetic expression. We can translate this grammar into
parsing combinators as follows:


\begin{center}
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
lazy val E: Parser[String, Int] = 
  (T ~ p"+" ~ E).map{ case ((x, y), z) => x + z } ||
  (T ~ p"-" ~ E).map{ case ((x, y), z) => x - z } || T 
lazy val T: Parser[String, Int] = 
  (F ~ p"*" ~ T).map{ case ((x, y), z) => x * z } || F
lazy val F: Parser[String, Int] = 
  (p"(" ~ E ~ p")").map{ case ((x, y), z) => y } || NumParserInt
\end{lstlisting}
\end{center}

\noindent
Let us try out some examples:

\begin{center}
\begin{tabular}{rcl}
  input strings & & output of \pcode{parse_all}\medskip\\
  \texttt{\Grid{1+2+3}} & $\rightarrow$ & \texttt{Set(6)}\\
  \texttt{\Grid{4*2+3}} & $\rightarrow$ & \texttt{Set(11)}\\
  \texttt{\Grid{4*(2+3)}} & $\rightarrow$ & \texttt{Set(20)}\\
  \texttt{\Grid{(4)*((2+3))}} & $\rightarrow$ & \texttt{Set(20)}\\
  \texttt{\Grid{4/2+3}} & $\rightarrow$ & \texttt{Set()}\\
  \texttt{\Grid{1\VS +\VS 2\VS +\VS 3}} & $\rightarrow$ & \texttt{Set()}\\                      
\end{tabular}
\end{center}

\noindent
Note that we call \pcode{parse_all}, not \pcode{parse}.  The examples
should be quite self-explanatory. The last two example do not produce
any integer result because our parser does not define what to do in
case of division (could be easily added), but also has no idea what to
do with whitespaces. To deal with them is the task of the lexer! Yes,
we can deal with them inside the grammar, but that would render many
grammars becoming unintelligible, including this one.\footnote{If you
  think an easy solution is to extend the notion of what a number
  should be, then think again---you still would have to deal with
  cases like \texttt{\Grid{(\VS (\VS 2+3)\VS )}}. Just think of the mess 
  you would have in a grammar for a full-blown language where there are 
  numerous such cases.}

\end{document}

%%% Local Variables: 
%%% mode: latex  
%%% TeX-master: t
%%% End: