about something which is quite close to my heart, because I wrote some of the

early papers on it many years ago, and that's something called functional

parsing, or combinator parsing. Before we get started with actual live coding, I

want to begin with the question. And the question is: what actually is a parser?

So for me a parser is a program which takes a string of characters as its input, and

as its output produces some form of tree. And the idea is that the tree makes

explicit the structure in the input string. So that's a bit of a mouthful, so

let's have a simple example to explain what's going on with this. So what we've

got here is we've got a string of five characters -- 2 plus 3 times 4 -- and

that's our input string. But when we look at this we know that that's not just a

random sequence of five characters, it's actually got some structure to it. So in

particular, we've got three numbers here -- 2, 3 and 4 -- and we've got two

arithmetic operators -- we've got the plus and the times -- and one of the things we

learn at school is that the times happens before the plus. So you really do 3 times 4

here, and then you add the 2 on at the end. So that's our input string.

So what a parser does, is it takes a string of characters -- like that -- and it

tries to recognize the structure in the form of a tree. And the tree we would get

from a parser is something like this here. And you see we've got some leaves

in the tree -- the leaves are the numbers 2, 3 and 4 -- and the nodes in the

tree are the two arithmetic operators -- that's the plus symbol and the times

symbol -- and you can see the structure of the tree reflects the fact that we do

the multiplication. First we multiply 3 by 4, and then we do the

addition second. So that's the basic idea of what a parser is: it takes as input a

string of characters, and as output it produces a tree. So it's really a

function -- it's taking as input a string and as output as a tree. So we've seen

what a parser is. It's a function that takes a string as an input and produces

a tree as an output. So now we want to think how can we actually implement this:

how can we implement the idea of a parser? And I'm going to do this in Haskell

today, but it doesn't matter if you don't know anything about Haskell because

I'll be explaining everything as I go along. And actually, nothing I'm going

to show you today is specific to a language like Haskell.

You can do it in any general-purpose programming language. So if you do a web

search for a 'combinator parsing' or 'functional parsing', and then whichever

language you're interested in, you'll find the same kind of stuff which I'm

going to show you today. So it's not specific to the Haskell setting. So

what we're going to do then first, is we're going to define precisely, in our

programming language, what it means to be a parser. We're going to define a new

type called Parser, and it's simply going to be a function which takes a string as

an input and produces a tree as an output. So it captures the very simple

idea of what we are wanting to do -- a parser is a function that takes a string

as an input, and gives the tree as an output, and the arrow here just means

that we have a function from one thing into the other. So this captures the

basic idea of what a parser is. But unfortunately, it's not sufficient to

program with. We need to refine this a little bit to actually write programs

with this. So the first little refinement we're going to make is that a parser

might not consume all of its input. So for example, if we're trying to parse a

number, like 2, we maybe we find the 2, and then maybe we've got some more stuff

left in the input string that we need to parse. And if we want to chain parsers

together, we're going to need to have access to the remaining input string

that we didn't manage to consume. So the first little refinement that we'll make

is rather than just returning a single tree, we're actually going to return a

pair now. We're going to return two things -- we're going to return a tree as

before, and we're also going to return the unconsumed part of the input string.

So that's the first refinement we've made. The second refinement we're going

to make is that a parser may not always succeed. We may be trying to parse a

number, and we don't find the number, we find something else. So we need to have a

way of representing that a parser can fail. So the way we're going to do that, is

we're actually going to make a parser return a list of results, rather than a

single result. So lists in Haskell are denoted using square brackets. So this

simply means that rather than returning one pair of results, we could return zero,

or one, or two, or as many as we like. And the idea is going to be if our parser can't

parse, so it doesn't succeed, we'll return an empty list of results. And if it does

succeed, we'll return a list with one pair -- we'll return a tree,

that represents the structure of the input string, and we'll return the

unconsumed part of the input. But because we're working with lists here,

we could actually be more flexible. We could return two, three, or four, or five,

or as many as we like parses. And this is actually quite a good flexibility,

because for some languages the input string may be ambiguous -- maybe we're

trying to parse English, and English sentences don't always have one parse,

they can be interpreted in many ways. So this type here is giving us a

flexibility to return many results if we wanted. We're not actually going to use

that flexibility today, but it's nice to actually have it. So I haven't told you

what the tree data type is here. And that's because I'm actually going to get

rid of that now. Sometimes you may want to return a number, or a program, or some

kind of other structure. So we're going to replace that specific type of trees

by some arbitrary type 'a'. And I'll make this a parameter of my type. This is our

final type, which we're going to work with today. What we're saying is that a

parser whose results have type 'a' is simply a function which takes a string

as an input, and then it gives a list of results. And each result is a pair

comprising a single value of type 'a' -- maybe a tree, maybe a number, maybe

something else -- and then an unconsumed part of the input string. Okay, so this is

our final type. And if you look in any of the articles, or books, about these kind

of parser combinators, or functional parsers, you'll find a type very

similar to this there. It's quite a mouthful again, so let's think about how

we could understand this in a simpler way. And actually, we can write a little

rhyme to understand what's going on with this type. So let me write the rhyme out

for you as a comment. So what we can say is: a parser for things, is a function

from strings, to lists of pairs, of things and strings. This is a little Dr. Seuss

rhyme to tell you what a parser is, or what a functional parser is. And that's

actually how I remember this type. So that's our basic type now. We've seen so

far, a parser is basically a function from strings to trees, but in order to

actually program with these kind of things, we need to refine the type a

little bit. And this is the type we'll be working with today. But you don't need to

worry about the details of it. Just basically think it's a function from

strings into trees, or some other kind of structure. What we're going to do now,

is we're going to load up the parsing library. So I'll start up

the compiler. This is a library, which contains a whole bunch of parsing stuff,

which allows us to program with parsers of this form. And this is a parsing library I

wrote myself. I'll see if I can get Sean to upload it as part of the video.

A parsing library comes with any programming language you can think off.

And again, if you just search for parser combinators, functional parsing,

whichever language you like, you'll find the library, which gives you all sorts of

basic ways of building parsers. And that's what I'm going to show you now.

All of these libraries work in the same way. So you have some basic primitives, or

basic building blocks, for parsers. And then you have a way of combining parsers

to build bigger parsers. So it's like a kind of Lego kit, or a construction kit.

You have some basic bricks that you can do things with. And then you can put

those bricks, or components, or primitives, together in all sorts of different ways.

So I'm going to show you a few of the primitives, and a few of the combining

forms. And then we'll do an example. The first primitive I want to show you is

very simple. It's just a way of parsing a single digit. So what the digit parser

does, is it takes a string of characters, and it tries to consume a single numeric

digit off the start of that string. And you might think, well, what does 'parse' do

here? What parse does, is it takes a parser, which in this case is just digit,

and it takes an input string to that parser, and it just applies one to the

other. So of course, this parser here is going to succeed, because we do have a

digit at the start of the input string. So we get exactly the expected result.

We get a list with one pair. And the first thing in the pair is the actual digit. We

get the character '1'. And the second thing in the pair is the unconsumed part of

the input. And that's something we could then try and parse subsequently with

another parser. We can test, does this thing fail properly? So, if I give it an

input string that doesn't have a single digit at the start, then it's going to

fail. So if I give it the input string "abc", there's no digit at the beginning, so

we're just going to get the empty list of results. So I'll show you one more

quick primitive. If I parse a single character, say an 'a', from that string, then

that will do the right thing. If I parse single character 'a', and I didn't have an

'a' at the beginning, then it will fail. So we've seen two basic parsing

primitives here -- we've seen a way of parsing a digit,

a way of parsing a specific character, and we've seen that these things can

succeed or fail. And in the library, or in any of these libraries, there'll be a

bunch of these basic building blocks, or basic bricks, or primitives, that you can

use to build up your parsers. Where things get more interesting is when you

think how do you combine these kind of things, how do you use these basic bricks

to build actually useful parsers? Let me show you an example of this. So there's a

parsing combining form called 'some'. And what it does is it takes a parser as its

input, and it tries to apply it one or more times, as many times as possible. So

if we're trying to parse 'some' digits, what we're trying to do is consume one

digit, then two, then three, and as many as we can until we don't find any more

digits. So if we apply the 'some digit' parser to the string "123" then

it will do the expected thing. It will consume all three of the digits, and then

we'll get the empty string left here. So that's 'some', it gives us a form of

repetition. And we also have a very simple way of making a choice as well.

So if I want to make a choice here, between a digit, and a letter. And let me

parse the string "abc123". So, what we've got here, is this funny symbol

here -- with the three symbols -- that's a choice operator. It says do that, or do

that. So if I try to parse a digit, or a letter, what it's going to try first is

it will take the first character in the input string, and say is it a digit? If so,

I'll parse it. And if it's not a digit, then I'll go over to the other side, and

say is it a letter? And I will try and parse that. You can see what's happening

with this particular example here -- if I look at the first character, it's not a

digit, it's a letter. So when I apply the digit parser it would fail, and then the

'or' operator, or the choice operator here, will go over to the other side and say,

well, is it a letter instead? And of course it is, so we can parse the single

'a' off the front here, and then we get everything else as unconsumed.

And of course, if we wanted to be a bit more clever we could combine some of

these things. So I could say, some digit or letter -- get my brackets right --

"abc123", and then that will parse everything. Because all I'm doing here is

I'm repeating, or iterating, the choice between either parsing a single digit, or

a single letter. And I've got a string of digits and letters here,

so I can parse the whole thing. So I've consumed them all. And then I get nothing

left at the end. So what we've seen so far, is some basic building blocks, and

we've seen a couple of combining forms -- we've seen a way of doing

repetition, which is 'some', and we've seen a way of making a choice, which is the

funny operator in the middle there. What I haven't shown you so far, is how to do

some form of sequencing. And this is the most common thing you typically want to

do with parsers. You want to say do this, and then do that, and maybe do that as

well. You want to sequence things together. So I'll actually show you a bit

of the parsing library here. So here's the parsing library. And I don't want to

go through all the details of this, but one thing I want to know, is it's quite

short. If I kind of scroll down here, I think it's about four and a half screen

fulls. And I've got quite a big font here, and this is actually already quite a

sophisticated parsing library. So it shows you the power of this method, that you