This handout explains how \emph{parser combinators} work and how they

can be implemented in Scala. Their distinguishing feature is that they

are very easy to implement (admittedly it is only easy in a functional

programming language). However, parser combinators 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.

Another good point of parser combinators is that they can deal with any kind

of input as long as this input of ``sequence-kind'', for example a

string or a list of tokens. The general idea behind parser combinators

is to transform the input into sets of pairs, like so

\noindent As said, the input can be anything as long as it is a

``sequence''. The only property of the input we need is to be able to

test when it is empty. Obviously we can do this for strings and lists.

For more lucidity we shall below often use strings as input in order

to illustrate matters. However, this does not make our previous work

on lexers obsolete (remember they transform a string into a list of

tokens). Lexers will still be needed to build a somewhat realistic

compiler.

In my Scala code I use the following polymorphic types for parser combinators:

input:\;\; \texttt{I}  \qquad output:\;\; \texttt{T}

\noindent that is they take as input something of type \texttt{I} and

return a set of pairs of \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 in order to indicate it is a

subtype of Scala sequences. The first component of the generated pairs

corresponds to what the parser combinator was able to process from the

input and the second is the unprocessed part of the input (therefore

the type of this unprocessed part is the same as the input). As we

shall see shortly, a parser combinator might return more than one such

pair; the idea being that there are potentially several ways of how to

parse the input.  As a concrete example, consider the string

Also important to note is that the type \texttt{T} for the processed

part is different from the input type. The reason is that in general

we are interested in transform 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 relativaley easily a calculator.

The main idea of 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 an

object-oriented programming language, like Scala, we need to specify

an abstract class for parser combinators. This abstract class states

that the function \texttt{parse} takes an argument of type \texttt{I}

and returns a set of type \mbox{\texttt{Set[(T, I)]}}.

\noindent It is the obligation in each instance (parser combinator) 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.

single character, say $c$, from the beginning of strings. Its

\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 $\{\}$.	

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

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

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

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

\texttt{sb} 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, 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 extracts 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}. Such a conversion would be

needed if we want to implement a simple calculator program.

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. For example 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)

\noindent The types of this parser combinator are again generic (we

just 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}.  Both need to be able to process

input of type \texttt{I} and return 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.}  Therefore the output

type of this parser is \texttt{T}. The alternative parser should run

the input with the first parser \texttt{p} (producing a set of pairs)

and then run the same input with \texttt{q} (producing another set of

pairs).  The result should be then just the union of both sets, which

\noindent Later on we will use again Scala mechanism for introducing some

more readable shorthand notation for this, like \texttt{"a" || "b"}. Let us look in detail at what this parser combinator produces with some somple strings 

\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$ & $\{\}$

\pcode{cde} in the unprocessed part. Clearly this parser cannot

parse anything in the string \pcode{ccde}, therefore the empty

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 like

&& $(\textit{output}_2, u_2) \in q(u_1)\}$

\noindent Notice that the $p$ wil 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 left-over, parts. We want that $q$ runs on all

these unprocessed parts $u_1$. This again will produce some

processed part , $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 would 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(sb: I) = p.parse(sb) ++ q.parse(sb)

}

\end{lstlisting}

\end{center}

\noindent The types of this parser combinator are again generic (we

just 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}.  Both need to be able to process

input of type \texttt{I} and return 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.}  Therefore the output

type of this parser is \texttt{T}. The alternative parser should run

the input with the first parser \texttt{p} (producing a set of pairs)

and then run 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 already allows us to

construct a parser that parses either a character \texttt{a}

or \texttt{b}, as

\begin{center}

\begin{lstlisting}[language=Scala, numbers=none]

new AltParser(CharParser('a'), CharParser('b'))

\end{lstlisting}

\end{center}

\noindent Later on we will use again Scala mechanism for introducing some

more readable shorthand notation for this, like \texttt{"a" || "b"}. Let us look in detail at what this parser combinator produces with some somple 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 processed part, and

\pcode{cde} in the unprocessed part. Clearly this parser cannot

parse anything in the string \pcode{ccde}, therefore the empty

set.

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 like

\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$ wil first be run on the input, producing

pairs of the form $\textit{output}_1$ and unprocessed part $u_1$. 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 parts of both parsers is the unprocessed parts the second

parser $q$ produces as left-over. The processed parts of both parsers

is just the pair of the outputs

$(\textit{output}_1, \textit{output}_2)$. This behavious can be

implemented in Scala as follows:

\noindent This parser takes again as input two parsers, \texttt{p}

\noindent

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.

Notice that we have now two output types for the sequence parser

combinator, because in general \textit{p} and \textit{q} might produce

differetn things (for example first we recognise a number and then a

string corresponding to an operator).

We have not yet looked at this in detail, but Scala allows us to

provide some shorthand notation for the sequence parser combinator. We

can write for example \pcode{"a" ~ "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 three examples of

how this parser combinator processes strings:

\texttt{\Grid{abcde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{b}}), \texttt{\Grid{cde}})\right\}$\\

\texttt{\Grid{bacde}} & $\rightarrow$ & $\{\}$\\

\texttt{\Grid{cccde}} & $\rightarrow$ & $\{\}$

\noindent In the first line we have a sucessful parse, because the

string started 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 errorneously

expects.  The parser returns the ampty 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{("a" || "b") ~ "c"}.

which parses as first character either an \texttt{a} or \texttt{b}

followed by a \texttt{c}. This parser produces the following outputs.