% !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 ensure the

examples are simple. 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. See also

a question in the homework regarding this issue.

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

\code{(using is: I => Seq[_])} for the input type. This ensures the

input is a subtype of Scala sequences.\footnote{This is a new feature

  in Scala 3 and is about type-classes, meaning if you use Scala 2 you will have difficulties

  with running my code.} 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)]}}.\footnote{In the actual code on KEATS there is some

  kerfuffle about correct type-bounds and using clauses. Ignore this

  part of the implementation for the moment---it is not needed for

  understanding how the code works.}

\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 ((hd, tl) <- parse(in); 

        if tl.isEmpty) yield hd

}

\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 $s$ 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(s: String) = 

    if (s != "" && s.head == c) Set((c, s.tail)) else Set()

}

\end{lstlisting}

\end{center}

\noindent You can see \texttt{parse} tests here whether the

first character of the input string \texttt{s} is equal to

\texttt{c}. If yes, then it splits the string into the recognised part

\texttt{c} and the unprocessed part \texttt{s.tail}. In case

\texttt{s} 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)::rest => Set((s.toInt, rest)) 

    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 in our parser,

because when we encounter a number in our program, we want to do

some calculations based on integers, not strings (or tokens). 

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}. These arrows

  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\footnote{Note

  that we cannot use a \texttt{case}-class for \texttt{AltParser}s

  because of the problem with laziness and Scala quirks. Hating

  \texttt{new} like the plague, we will work around this later with

  some syntax tricks. ;o)}

\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"}. But first 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 of the form \pcode{ccde}, therefore the

empty set is returned in the last case. Observe that parser

combinators only look at the beginning of the given input: they do not

fish out something in the ``middle'' of the input.

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}. (Actually, we will be

able to write just \pcode{p"ab"} for such parsers, but it is good to

  understand first what happens behind the scenes.) Let us look again

  at some examples of how the sequence 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

\begin{center}

\pcode{p"a" || (p"a" ~ p"b")}

\end{center}

\noindent

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} or \emph{map-parser}, does not

actually combine two smaller parsers, but applies a function to the result

of a parser.  It is implemented in Scala as follows